分块法的模式匹配算法的研究

巫喜红

(嘉应学院计算机学院，广东梅州514015)

0 引言

随着计算机网络技术的快速发展，带给网民无限的方便，比如网上订票、网购等，但同时也带来了一些安全隐患，比如密码的失窃，因此，网络的安全性一直受到大家的关注。其中，提高网络系统安全性的重要技术之一的入侵检测系统也由此越来越广泛地应用到网络系统中。而要提高入侵检测系统的性能，其关键技术—模式匹配性能的提高也得到大家极大的关注。其实，模式匹配不只应用在网络安全方面，在计算机上用编辑程序作文本编辑、在DNA序列中寻找特殊的模式等，也要用到模式匹配。由于模式匹配问题的求解效率的重要性，对模式匹配算法的研究很早就受到重视，因而积累了丰富的成果，比如最早提出的典型的单模式算法有Knuth-Morris-Pratt算法［1］、Byoer-Moore 算法［2］、Sunday算法［3］，多模式算法主要有 Aho_Corasick 算法［4］、Wu_Mander算法［5］。后来，各研究者不断地对这些典型算法进行了改进，以提高算法的效率，比如文献［6］对KMP算法进行改进，文献［7］对BM算法进行改进，文献［8］对Sunday算法进行改进，这些改进算法的改进思想是当匹配失败时，如何使模式串右移最大距离。本文从模式串的首字符着手，借鉴分块查找的思路，提出一种分块模式匹配(block pattern matching，BPM)算法。

1 几种改进的模式匹配算法

为了便于描述算法，现设文本串T=T0…Tn－1，n为文本串的长度，模式串P=P0…Pm－1，m为模式串的长度(n≥m)，T和P都建立在有限字符集上，大小为σ。

对于文本串T和模式串P，如果在T中存在等于P的子串，则称匹配成功，否则称为匹配失败，这个搜索过程就是模式匹配。至于如何在T中快速寻找等于P的子串，各种算法各显神通，各有各的思路方法，在此简要介绍两类经典匹配算法，分析它们其中的一种改进算法。

1.1 BM算法及其改进算法

BM算法是把P同文本串进行比较时从右向左，当某趟匹配失败时，采用坏字符启发规则和好后缀启发规则计算模式串右移的距离，并取两者最大值来决定模式串的右移量，移动尽可能远的距离，直到匹配成功或文本串匹配结束，其匹配时从右至左进行。

对于BM算法的改进有很多种，如文献［7］所提到的改进算法，在此称改进算法为Im-BM，其改进思路是:当匹配成功时，判断当前窗口的下一位字符是否在P中，若不在，则跳过m+1个字符;若在，则根据此字符在P中的位置来确定;当匹配失败时，根据当前匹配窗口匹配失败的字符和当前窗口的下一个字符来进行跳转，跳转的距离是两者中较大的那个。文献［7］所得出的结论是:在总的尝次数方面，I-BM算法是BM算法的82.83%，总的字符比较次数是BM算法的80.98%。

1.2 Sunday算法及其改进算法

Sunday算法采用BM算法中的坏字符启发规则，开始时，P的最左边与T的最左边对齐，模式匹配过程中进行P与T的比较时，可以从左向右或从右向左进行比较，在发现不匹配时，选取当前匹配窗口的下一个字符来判断右移量以跳过尽可能多的字符，从而提高了匹配效率。其匹配时从右至左进行或者从左至右均可。

对于Sunday算法的改进有很多种，如文献［8］所提到的改进算法，在此称为Im-Sunday，其改进思路是:预处理阶段生成的函数值与Sunday算法一致，在匹配阶段有所改进。无论匹配成功与否，根据当前窗口的下一个字符来决定跳转距离;当前窗口的下一位字符是否在P中，若不在，则再判断m个字符是否在P中以决定跳过的字符，最大右移距离是2m+1;若在，则根据此字符在P中的位置来确定。文献［8］所得出的结论是:在指针移动次数方面，Im-Sunday算法是Sunday算法的63.81%，字符比较次数是Sunday算法的67.72%。

2 BPM算法描述

借鉴文献［9］中提出的分块查找思路，在模式匹配算法中进行应用。分块查找的思路是:按照一个顺序表内记录的某种属性把表分成n(n＞1))个块(子表)，并建立一个相应的“索引表”，利用此“索引表”进行块内的查找，原则是后面一个块中所有记录的关键字值比前一个块中所有记录的关键字值大，但同一块、同关键字值的大小可以无序。在此借鉴分块查找的思路，对模式匹配算法进行分块处理。BPM算法中的块是指字符块，也就是在文本串T中查找出这样的块:首字符、尾字符分别等于模式串P的首尾字符，且长度与P的长度相等，字符块之间没有大小要求。其思想是:①在预处理阶段，扫描T串，找出符合要求的字符块并存储其首尾字符在T中的位置，其数据结构采用单向链表;②匹配阶段，根据预处理阶段的信息，把P与其在T中出现的位置进行一一对齐进行匹配，采用双向匹配方式。

2.1 BPM算法的预处理

在预处理阶段，保存P的首、尾2个字符在T中的位置值，设计思路是:从T的首字符开始查找P的首字符，若找到首字符，则判断后m个字符长度的字符是否等于P的尾字符，若是，则新建结点以保存位置，否则，继续下一个首字符的查找，直到T的字符结束。那么，单链表的长度就由符合要求的信息值决定。具体步骤如下。

1)输入T串，计算其长度n=strlen(T);

2)输入P串，计算其长度m=strlen(P);

3)定义并初始化一些变量，定义i为循环变量，first为P的首字符，last为P的尾字符，L为头指针，p为新建结点，r为临时结点;

4)从T的第1个字符开始，当T串未扫描完，执行5)，否则，执行8);

5)若 T［i］!=first，则往后找;

6)若找到与first相等的字符，则判断其后m长度的字符是否等于last，若是，则找到第1个字符块，新建结点，保存下标值;

7)若不符合步骤5)，6)，则直接跳过长度为m的字符块，执行步骤4);

8)结束扫描。

算法中使用了单链表的结构，单链表的定义如下。

其算法流程如图1所示。

图1 BPM算法预处理阶段流程图Fig.1 Preprocessing phase flow chart of BPM algorithm

2.2 BPM算法的匹配过程

BPM算法的匹配思路是进行双向匹配，即:从单链表的第1个结点开始，取出首尾字符的位置值进行字符块的匹配，每一个字符块匹配顺序是:从P的第2个和倒数第2个字符开始匹配，若此次匹配失败，则退出匹配，进行下一个字符块的匹配;若匹配成功，则再进行P的第3个和倒数第3个字符的匹配……。当匹配成功，则输出匹配的位置，若不成功，则输出失配的信息。直到单链表的最后一个结点为止。

具体步骤如下。

1)定义临时指针变量q为指向每一个结点;临时变量k为模式串P的下标值;临时变量i，j分别存储首尾字符在T中的位置;临时变量flag为匹配标识。

2)当结点不空时，分别取出firstpos，lastpos的值。

3)当k小于m/2时，从P的第2个和倒数第2个字符开始匹配，若匹配成功，则执行4);否则执行5)。

4)变量i++，j－－，k++，flag=1。

5)q指向一个结点，执行2)。

6)结束匹配。

其算法流程如图2所示。

图2 BPM算法匹配阶段流程图Fig.2 Matching phase flow chart of BPM algorithm

3 BPM与其他改进算法的实例对比及性能分析

3.1 实例对比

对于BPM算法，在此通过简单实例进行匹配演示，并将其与改进的Im-BM算法、Im-Sunday算法进行实例的对比。

例如:设 T=“strkdesignsdeawisestetementstep”，P=“step”，现通过 Im-BM 算法、Im-Sunday算法、BPM算法分别演示P在T中的实现，以显示BPM算法的优越性。

1)Im-BM算法的匹配演示。

首先生成字符集 C{a，d，e，g，i，k，m，n，p，r，s，t，w}，Im-BM_Bc 函数值对应为 {4，4，1，4，4，4，4，4，4，4，3，2，4}，根据 Im-BM 算法的匹配思路，其匹配过程如表1所示。本例结果:匹配次数是8，匹配的字符个数是12。

表1 Im-BM算法匹配过程Tab.1 Matching procedure of the Im-BM algorithm

2)Im-Sunday算法的匹配演示。

首先生成字符集 C{a，d，e，g，i，k，m，n，p，r，s，t，w}，Im-Sunday_Bc 函数值对应为 {5，5，2，5，5，5，5，5，1，5，4，3，5}，根据 Im-Sunday 算法的匹配思路，其匹配过程如表2所示。本例结果:匹配次数是8，匹配的字符个数是13。

表2 Im-Sunday算法匹配过程Tab.2 Matching procedure of the Im-Sunday algorithm

3)BPM算法的匹配演示。

BPM算法在预处理阶段首先查找P的首字符's'，再把首字符位置加3(P的长度减1)，判断此位置的字符是否等于P的尾字符'p'，最终保存在单链表中。单链表的示意图如图3所示，其中“^”表示“空”。

图3 BPM算法链表图Fig.3 Llist of BPM algorithm

根据单链表的信息，从第1个结点开始，从P的第2个字符和倒数第2个字符进行匹配，其匹配过程如表3所示。本例结果:匹配次数是2，匹配的字符个数是4。

表3 BPM算法匹配过程Tab.3 Matching procedure of the BPM algorithm

从表1—表3的结果可看出，BPM算法在匹配次数和匹配的字符个数方面比Im-BM算法、Im-Sunday算法有很明显的改进，比典型的BM算法、Sunday算法有更大的改进。

3.2 性能分析

为了说明BPM算法的高效性，在此进行预处理阶段和匹配阶段的算法性能分析。

1)在预处理阶段，根据文献［7］描述，Im-BM算法在此阶段的时间复杂度为O(σ+n)，空间复杂度为O(σ+n)。根据文献［8］描述，Im-Sunday算法在此阶段的时间复杂度为O(σ)，空间复杂度为O(σ+n)。BPM算法在预处理阶段扫描T串以寻找P的首字符，所以这一过程仅循环一次T的长度n，故时间复杂度是T(n)=O(n);在此阶段，需要存储长度等于P的长度的字符块的相关信息，故存储空间由P的首尾字符在T中出现的机率有关，由于采用动态存储即单链表方式，故存储空间很小，最好情况是0，即没有找到符合要求的字符块，最坏情况是n/m，即T串都是由P串组成的，故其空间复杂度S(n)=O(n/m)。

2)在匹配阶段，根据文献［7］描述，Im-BM算法在此阶段的最好时间复杂度为O(n)，最坏为O(n·m)。根据文献［8］描述，Im-Sunday算法在此阶段的最坏时间复杂度为O(n·m)。BPM算法在匹配阶段是根据单链表的存储空间来决定循环次数，由前面分析可知，最坏情况下S(n)=O(n/m)，也就是T(n)=O(n/m)，而匹配每个字符块时是从P的第2个字符开始，采用双向匹配，所以最坏情况是匹配m/2次，故在匹配阶段的时间复杂度是T(n)=(n/m)·(m/2)=n/2=O(n)。最好情况是0，即无需匹配。也就是说，BPM算法在最坏情况下的时间复杂度为O(n)，最好情况是0。

综上分析，在预处理阶段，虽然BPM算法要扫描一次T串，需要花费时间，但是其在匹配阶段所花时间只是由单链表的存储空间来决定循环次数，而单链表的长度远远小于n，因此，从BPM算法、Im-BM算法和Im-Sunday算法2个阶段的时间复杂度可看出，BPM算法的时间开销是最少的。

4 BPM算法性能测试

为了更好地体现BPM算法性能的高效性，现将BPM算法的性能进行检测。现从两方面进行实验，测试的平台相同，即:操作系统用Windows 7，编译器是 Visual C++6.0。

实验1 从匹配次数和匹配字符个数方面去测试。方法是:随机抽取一段文本和一个模式串，在相同环境下实现Im-BM算法、Im-Sunday算法和BPM算法。测试文本如下。

The year that many computers may develop problems because of lack of foresight on the part of programmers.In the 1980s and before，most computer programs were designed to store only the last two digits of the years on all dates .When the Year 2000 comes，these programs will show dates of 00，which maybe interpreted the same as 1900.This discrepancy may cause widespread problems，especially in the large computer systems used in government and big industries.

模式串为'computer'。分别测试3种算法的匹配次数和匹配字符个数，结果如表4所示。

表4 实验一结果对比表Tab.4 Results of the first experimentation

实验2 从算法的执行时间方面去测试。方法是:随机选用纯英文文档作为文本串，共有1 334个字符，随机选取模式串长度分别为8，20，35的模式串(包括匹配不成功和匹配成功的模式串)，运行程序100万次，取它们运行时间的平均值，获得的结果如表5所示。

表5 实验二结果对比表Tab.5 Results of the second experimentation

从表4可以看出:BPM算法无论是在匹配次数还是匹配的字符个数方面，均比Im-BM算法、Im-Sunday算法有很明显的优势;从表5可以看出，当模式串较短时，时间方面比Im-BM算法、Im-Sunday算法稍长，但随着模式串长度的增加，所花费时间越来越少，在实验测试过程中，特别是匹配失败情况下，BPM算法运行时间非常小，几乎为零。

从以上实验可证明，BPM算法是一个性能很好的改进算法，这是因为BPM算法在匹配时只匹配首尾字符均等于模式串的首尾字符的字符块，而这样的字符块在文本中出现的概率是很低的，也就意味着跳跃距离较大且比较次数是较少的。

5 结束语

由于BPM算法只匹配首尾字符均等于模式串的首尾字符的字符块，并且字符长度等于模式串长度，实验证明本文采用的分块法改进的模式匹配算法能够有效地提高模式匹配的速度。基于模式匹配的Snort入侵检测系统有4大模块，通过设定不同的规则选项，在处理时就会调用不同的插件，其中，改进后的BPM算法用于sp_pattern_match插件中，它使用的数据结构PatternMatchData用于模式匹配。因此，对将改进后的算法植入到Snort系统中进行应用的研究具有重要的意义，今后的研究方向是把改进的多模式匹配算法应用到Snort系统当中。

［1］曾诚，李兵，何克清.KMP算法在Web服务语义标注中的应用［J］.微电子学与计算机，2010，27(8):1-3.ZENG Cheng，LI Bing，HE Keqing.Application of KMP Algorithm in Web Service Annotation［J］.Micro Electronics ＆ Computer，2010，27(8):1-3.

［2］LI Yankun，FU Weina.Realization of String-Matching in SIMD-MC2Grid［C］//IEEE.2010 3rd International Conference on Computational Intelligence and Industrial Application(PACIIA).Hubei:IEEE Press，2010:311-314.

［3］潘冠桦，张兴忠.Sunday算法效率分析［J］.计算机应用，2012，32(11):3082-3084，3088.PAN Guanhua，ZHANG Xingzhong.Study on Efficiency of Sunday Algorithm ［J］.Journal of Computer Applications.2012，32(11):3082-3084，3088.

［4］巫喜红，曾锋.AC多模式匹配算法研究［J］.计算机工程，2012，38(6):279-281.WU Xihong，ZENG Feng.Research on AC Multiple Pattern Matching Algorithm［J］.Computer Engineering，2012，38(6):279-281.

［5］巫喜红.入侵检测系统中Wu_Manber多模式匹配算法的研究［J］.计算机应用与软件，2008，25(8):114-125.WU Xihong.On Wu_Manber Multiple Pattern Matching Algorithm in Intrusion Detection System［J］.Computer Applications and Software，2008，25(8):114-125.

［6］杨战海.KMP模式匹配算法的研究分析［J］.计算机与数字工程，2010，38(5):39-40.YANG Zhanhai.Research and Analysis of KMP Pattern Matching Algorithm［J］.Computer＆ Digital Engineering，2010，38(5):39-40.

［7］薛传庆，韩明畅，金伟信.入侵检测系统中BM算法的改进［J］.计算机技术与发展，2011，21(6):136-139.XUE Chuanqing，HAN Mingchang，JIN Weixin.Improvement of BM Algorithm in Intrusion Detection System［J］.Computer Technology and Development，2011，21(6):136-139.

［8］武旭东.Snort入侵检测系统研究与应用［D］.吉林:吉林大学，2011.WU Xudong.The Research and Application of Intrusion Detection System Based on Snort［D］.Jilin:Jilin University，2011.

［9］王裕明.数据结构与程序设计［M］.北京:清华大学出版社，2010:10-210.WANG Yuming.Data Structures and Programming［M］.Beijing:Tsinghua University Publishing House，2010，10-210.