一种改进的单模式匹配算法

张玉新，李成海，白瑞阳

（空军工程大学 防空反导学院，西安 710051）

一种改进的单模式匹配算法

张玉新，李成海，白瑞阳

（空军工程大学 防空反导学院，西安 710051）

0 引言

网络已成为人们生活、学习、生产等诸多领域不可缺少的一部分，但是由于诸多的因素造成了网络安全问题的频发，在网络高速化的时代，如何从大量数据中提取特定的信息，显得十分重要。模式匹配就是给定字符串T和S，其中字符串T称为正文，字符串S称为模式，要求在正文T中找到模式S是否出现。

模式匹配可以分为单模式匹配和多模式匹配，其中单模匹配有著名的BF算法、BM算法、BMH算法、KMP算法，文献[1]提出的快速单模式匹配算法(FSBM)充分利用已匹配的后缀和字符串后一位字符的信息,已达到在每一次跳跃中跳跃尽量大的距离，文献[2]利用模式字符串中存在重复字符串来获得最大的移动距离。多模匹配有AC算法，AC-BM算法，文献[3,4]也提出了相关的一些改进。其中Snort2.9中应用的就是单模匹配和多模匹配算法。本文重点以单模式匹配为研究内容，并结合传统的一些匹配算法如BM算法、BMH算法、Sunday(QS)算法，给出一种改进后的单模式匹配算法。

1 单模式匹配

单模式匹配算法是指在文本串T=t1t2t3…tn中一次只对一个模式P=p1p2p3…pn进行匹配。

1.1 BF算法

模式匹配最简单的做法是用模式串P的字符依次与文本串T作对比，这就是BF算法的思想，是最早最简单的单模匹配算法，其特点是直观简单，图1为BF算法匹配过程。

图1 BF算法匹配过程

如果p1=t1,p2=t2,p3=t3,p4=t4,…,pm=tm，则表明匹配成功，如果中间有一位匹配不成功，则右移一位从头再次开始匹配，直到匹配成或移到文本串最右端结束匹配过程。从匹配过程可以看出指向文本串的指针在一次匹配失败的情况下，执行下次匹配的时候指针需要返回再次重头开始，涉及多次回溯，最糟糕的情况下，每一次比较到最后才出现匹配成功，则一次比较需要m次，匹配完成最多需要n-m+1趟，通常n≥m，所以时间复杂度为Q(n*m)，算法效率极低。

1.2 BM及BMH算法

BM算法的基本思想是：模式串P以左对齐的方式，从右往左依次和文本串进行匹配，发生匹配失败时使用坏字符和好后缀中的最大值实现最大右移步长。坏字符原则，即一次匹配过程中出现匹配失败ti1Pj，当ti能够在模式串P中找到，将出现在P中最右端的ti右移与文本串中的ti对齐进行下一次匹配，当ti不能够在模式串P中找到，将模式串P右移的距离为已连续匹配的字符数。好后缀原则，当模式串P的后缀中有子串与文本串T已匹配，模式串P可以右移的距离为子串的长度，当模式串P的后缀中有子串与文本串T已匹配且模式串前缀中有子串与以匹配后缀子串相同，将前缀子串与后缀子串右移对齐，实现一次右移。BM算法的匹配过程如图2所示。

图2 BM算法的匹配过程

第1次匹配时p7=t7,p8=t8且模式串中p4p5=p7p8，采用后后缀原则，第2次匹配和第4次匹配均采用坏字符原则，第3次匹配p6p7p8=t11t12t13采用好后缀原则实现左移。

在模式匹配中，坏字符产生的概率占94.03%，远大于好后缀启发规则，BMH算法就是在匹配时只考虑坏字符启法规则，在大部分情况下，BMH算法的性能要优越于BM算法。BMH算法的思想是首先匹配模式串末尾所对应文本串的字符，若果匹配成功则再匹配其余的m-1位字符。只要文本串T中的任何字符造成匹配失败，都将由文本中和模式串最后一个位置对应的字符来启发模式向右的移动。BMH算法的最大右移距离为m。BMH算法匹配过程如图3所示。

图3 BMH算法匹配过程

1.3 QS算法

Sunday提出的QS算法，任然只采用了坏字符规则，与BMH不同的是QS算法在匹配过程中考虑与模式串T对齐的最后一个字符的下一个字符，最大跳跃距离为m+1。

当发生不匹配时，QS算法用下一个字符来计算右移量，即使用T[i+l]，当该字符不出现在模式串中时，可以直接跳过T[i+1]，右移距离比BMH大，但当T[i+l]在模式串中出现时，而T[i]不在模式串中出现时，这时右移距离BMH要大于QS算法，QS效率就不如BMH了。

2 改进的一种算法

2.1 算法思想

受BMH和QS的启发，结合二者的优点提出一种改进的匹配算法。该算法的基本思想是：采用模式串P与文本串T左对齐，匹配时从右向左匹配。定义i（i=1，2，…，n）为指向文本串T的指针，j（j=1，2，…，m）为指向模式串的指针。改进的算法也采用QS算法中与模式串T对齐后的下一个字符T[i+m]位，依据T[i+m]位生成坏字符表，同时利用连续的两组字符T[i+m-1]T[i+m]和T[i+m]T[i+m+1]生成右移距离表。

2.2 匹配过程

首次匹配时由T[i+m]位生成坏字符表，如果T[i+m]不在模式串P中按照QS算法思想模式串将会右移m+1位；若T[i+m]在模式串P中能够找到，计算连续的T[i+m-1]T[i+m]和T[i+m]T[i+m+1]两个字符是否在模式串中有连续出现的，两组连续的子串只要有一个出现就将模式串P中最右端中出现的子串右移与其中跳跃距离最大的对齐，即跳跃距离=max{( T[i+m-1]T[i+m]),( T[i+m]T[i+m+1])}，如果T[i+m-1]T[i+m]和T[i+m]T[i+m+1]直接跳过T[i+m-1]T[i+m]和T[i+m]T[i+m+1]，此时跳跃距离可达m+2。图4是改进算法的匹配过程。

图4 改进算法的匹配过程

在第一次匹配中可以看出T[9]=P[3]，且T[8]T[9]=P[2]P[3]，T[9]T[10]=T[3]T[4]，二者右移距离都为2，将模式串P右移2位；第二次匹配T[15]=P[8]，且T[14]T[15]=P[1]P[2]，T[15]T[16]在模式串P中没有找到对应的子串，模式串P右移7位；依次在第4次完成整个匹配。

从上图4可以看出，整个匹配过程主需要循环4次就可以完成，该算法同时获得了较大的移动距离，提高了匹配效率，从图2、图3的对比中可以发现该算法在某些情况下比BM算法、BHM算法匹配速度更快。

3 实验结果及结论

本实验在windows XP，Pentium Dual-Core E5800，2GB RAM环境下对BM算法，BMH算法、QS算法和改进的算法分别编程测试，在一篇纯英文文章153KB，149829个字符的情况下，以4、6、8、12长度的模式串进行测试得到如图5匹配比较次数和图6匹配经历时间所示的结果。从图中比较次数和运行时间可以看出改进后的算法具有一定的优越性。

图5 匹配比较次数

图6 匹配经历时间

4 结束语

改进后的匹配算法通过实验证实提高了匹配效率，在网络数据高速增长的时代，只有高效的算法才能胜任实时入侵检测的需求，本文提出的改进算法为下一步在入侵检测中的应用奠定了基础。

[1]王天聪,侯整风,何玲.基于BM的模式匹配改进算法[J].合肥工业大学学报,2011,34(3):363-366.

[2]丁国强,赵国增,李传锋.改进BM算法策略的网络入侵检测系统设计[J].计算机测量与控制,2011,11(19):2661-2664.

[3]汪永进,顾乃杰,任开新.一种按字长匹配的Wu－Manber多模式匹配算法[J].小型微型计算机系统,2013,34(7):1650-1653.

[4]王培凤,李莉.基于Aho-Corasick算法的多模式匹配算法研究[J].计算机应用研究,2011,28(4):1251-1253,1259.

[5]张宇,刘萍,刘燕兵,谭建龙,郭莉.对模式串匹配算法WuManber的复杂度攻击[J].计算机研究与发展,2011,48(8):1381-1389.

[6]嵩天,李冬妮,汪东升,薛一波. 存储有效的多模式匹配算法和体系结构[J]. 软件学报,2013,24(7):1650-1665.

[7]王英,左祥麟,左万利,王鑫. 基于本体的Deep Web查询接口集成[J]. 计算机研究与发展,2012,49(11):2383-2394.

[8]梁栋,朱明,唐俊,范益政,颜普. 基于局部相对形状上下文与Q-谱的点模式匹配算法[J].电子学报,2012,40(4):636-641.

[9]朱映映,吴锦锋,明仲. 基于网络事件和深度协议分析的入侵检测研究[J].通信学报,2011,32(8):171-178.

[10]Tan GM, Liu P, Bu DB et al. Revisiting multiple pattern matching algorithms for multi-core architecture[J].Journal of computer science and technology,2011,26(5):866-874.

[11]Dong Liang,PuYan,MingZhu, Yizheng Fan, Kui Wang.Spectral matching algorithm based on nonsubsampled contourlet transform and scale-invariant feature transform[J]. Journal of Systems Engineering and Electronics,2012,23(3):453-459.

[12]李艳鵾,付维娜,刘帅,祝明. 并行系统中KMP串匹配算法的实现[J].制造业自动化,2011,33(1):189-191.

[13]梁威,叶猛. 海量数据过滤系统中匹配算法的研究[J].电视技术,2013,37(1):87-90.

[14]侯宝剑,谢飞,胡学钢,刘应玲,王海平. 基于后缀树的带有通配符的模式匹配研究[J].计算机科学,2012,39(12):177-180,194.

[15]朱西讲.一种改进的BM算法在网络安全控制中应用[J].科技通报,2012,28(6):49-51.

Improved single pattern matching algorithm

ZHANG Yu-xin, LI Cheng-hai, BAI Rui-yang

模式匹配算法在病毒特征码检测、入侵检测、生物信息等诸多领域有着广泛的应用，如何提高匹配的效率是制约模式匹配算法的决定因素，本文通过分析传统的模式匹配算法提出一种改进的单模式匹配算法，通过对比分析和验证，该算法提高了匹配效率。

模式匹配；BM算法；BMH算法

张玉新（1990 -），男，甘肃民乐人，硕士研究生，研究方向为网络信息安全。

TP393.08

A

1009-0134(2014)06(上)-0015-03

10.3969/j.issn.1009-0134.2014.06(上).04

2014-03-08

国家自然科学（61272486）