多模式匹配快速算法的设计.pdf

《多模式匹配快速算法的设计.pdf》由会员分享，可在线阅读，更多相关《多模式匹配快速算法的设计.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、http:/ 多模式匹配快速算法的设计多模式匹配快速算法的设计 李胜才 北京航空航天大学 北京 100083 E-mail： 摘摘 要要：字符串匹配速度是关键字检测和过滤系统的核心。本文在有限状态自动机的 AC 算法的基础上，综合 BM 算法的跳跃思想和 QS 算法的优点，提出了一个快速的多模式字符串匹配算法。该算法能充分利用每次匹配过程中匹配不成功的信息和已经成功的信息，尽可能多地跳过待查文本串中的字符，从而不需要匹配目标文本串的每个字符，而在比较次数最少的情况下，能一次性无须回溯的实现对文本的快速搜索。实验证明在模式串较长和较短的情况下，算法都能有效地改善关键字检测过滤系统的匹配性能。关键

2、词：关键词：多模式串匹配；有限自动机；关键字检测过滤；匹配 中图分类号：TP301 引言 引言 在信息检索领域,串匹配问题一直都是研究的焦点之一。在拼写检查、基于字典的语言翻译、WWW 搜索引擎、计算机病毒特征码匹配、数据压缩以及 DNA 序列匹配等应用中也都需要进行串匹配。同时在基于特征匹配的入侵检测系统中，模式匹配的效率直接决定这类入侵检测系统的性能26。因此字符串匹配速度的提高有着深渊的意义。当前的多模式速度是很多系统以及软件的瓶颈35。对于单模式匹配问题,有三种经典的匹配算法:KMP 算法,它在最坏情况下也能保持线性查找过程,其时间复杂度为15，BM 算法,它采用“跳跃式”查找策略,多

3、数情况下无须对文本进行一次完整的扫描,在模式中字符在文本中出现很少时时间复杂度能到最好的,平均情况下其时间复杂度为(O mn+)(/)O n m(O mn+4568。QS 算法，在那些待匹配模式集中未使用的字符在文本 T 中大量出现时,可以利用它们的信息加快匹配速度。在最优情况下(模式串较短、模式串中出现的字母数较少)比 BM 算法更快,其时间复杂度为，最坏情况时为5。目前的多模式匹配中没有一个很好的算法能结合以上各个单模式的优点，本文在充分分析各个单模式匹配算法的基础上提出了一个新的多模式匹配的算法。该算法结合了 Boyer_Moore(BM)算法从右向左跳跃的思想8，以及能实现最大跳跃和尽

4、可能少的比较次数的 Quick Search(QS)算法的优点，能充分利用每次匹配过程中匹配不成功的信息和已经成功的信息，尽可能多地跳过待查文本串中的字符，从而不需要匹配目标文本串的每个字符，而在比较次数最少的情况下，就能一次性无须回溯的实现对文本的快速搜索。(/)O n m(O nm)n 1.1.新算法设计 新算法设计 设待查找文本为,其定义在一个有限的字母表(本文处理背景选择处理ANSI字 符 集 0256)上。多 模 式 匹 配 则 是 从 文 本 T 中 一 次 查 找 多 个 模 式 串（这里patten_num代表模式串的数目）,最短模式串的长度用表示。算法设计的主要思想在于匹配不

5、成功后充分挖掘已经成功匹配的信息结合当前匹配失1,2,T?123_,pattennumP P PP?minlen-1-败信息得到向后跳跃的距离t_shift。整个算法可以分为预处理和搜索两个部分。1.1 预处理阶段 预处理阶段 1.1.11.1.1 构建模式匹配自动机，即构建状态转移函数state_shift,输出函数output记录该状态下匹配成功的模式串下标，matchedstate记录当前状态state时已经匹配的字符串。构建多模式匹配自动机，也就是构建多模式下的搜索树。首先用待搜索的模式集构建一棵搜索树，然后将树的节点作为自动机的状态，树的分支作为自动机的状态转换函数。当字符在整个搜索

6、树内进行匹配时，由于搜索树是预先知道的，故可用 AC 算法预先构造一个包含所有模式信息的反向树型有限自动机。然后再利用 BM 算法，在文本中用搜索树对文本进行跳跃式的搜索。在构建搜索树时，将模式串的右边对齐，从右向左进行构建，树上相同的分支节点进行合并。这样匹配窗内文本最右面的字符就不需要和搜索树中的每一个字符进行匹配，而是直接将这个字符输入到匹配自动机，得到搜索树的匹配输出。在反向有限自动机的构造中，每个模式串的字符是从后向前输入到反向树型有限自动机的；匹配过程中，目标串的输入也是从后向前进行逆向扫描的。为方便描述本文的有限自动机是通过二维矩阵 state_shiftMAXSTATEM1来表

7、示的，其中 MAXSTATE 事先定义，代表最大可能状态数，M1 代表模式匹配的文本集合总数（本文限制在 0256 之间）。以添加 li，sheng，cai 为例，介绍反向树的构造过程（如图 1）012il-i Step1 添加 li Step2 添加 sheng 图 1:Step3 添加 cai 图中灰色状态表示该状态成功匹配模式串。1.1.21.1.2 计算在扫描阶段可能出现的任何字符可以跳跃的最大距离:要获得更快的匹配算法，关键是在模式串匹配失败时获得最大的跳跃距离从而得到最少的比较次数。构造完反向树型有限自动机后先利用BM算法从右向左逆向匹配的思想，从自动机的0状态出发,从后向前逆向扫

8、描目标串。若匹配失败，则根据坏字符移动规则(Badcharacter_shift)和好后缀移动(Goodsuffix_shift)规则，选取二者中的最大值作为模式集向右移动的距离。其中好后缀规则移动函数Goodsuffix_shift的计算利用了已成功匹配的信息，以及最后一次失败的信息，使得目标串中的一个字符串在和模式集中的某个模式串中部分匹配时，模式集将获得比较大的右移距离。特别是当模式集中最短模式串的长度也比较大时，-2-http:/ 好后缀规则移动函数Goodsuffix_shift的值有可能会变得比较大从而获得最少的比较次数。Goodsuffix_shift的计算方法46（式（2）：当

9、已匹配的字符串在某个模式串中的除本身外的最右重现时，好后缀规则移动函数Goodsuffix_shift的值是匹配成功的字符串到除本身外的最右重现之间的距离；当已匹配的字符串的后缀又是某个模式串的前缀时，好后缀规则移动函数Goodsuffix_shift的值是字符串后缀到对应前缀之间的距离。根据待匹配模式串集合中出现的字符分布，通常情况下，模式串集合不是很大，模式串集合中的字符在文本串中出现的概率较小，而且模式串在文本串中也比较稀疏，这时模式集向右移动的距离将主要决定于坏字符规则移动函数Badcharacter_shift。实际应用中只要状态不是在零状态的跳跃都是利用的Goodsuffix_sh

10、ift计算的距离。在我们前面的算法的基础上，再利用QS算法中利用坏字符规则移动函数Badcharacter_shift获得的跳跃值要比BM算法中根据坏字符移动获得的跳跃值大的优点。实现QS算法中坏字符规则移动Badcharacter_shiftchar的方法7(式(1)，其值等于字符char在任一模式串中的最右位置到该模式串尾的距离加1。加1的原因是在计算坏字符规则移动时，考虑了目标串中对齐模式串右边界的右边一个字符，即计算了Badcharacter_shift(stringi+1),i 是 模 式 串 右 边 界 所 在 位 置。应 用 于 多 模 式 匹 配 中，还 必 须 要 限 制Ba

11、dcharacter_shiftchar的值不能超过，否则，一次匹配失败后，右移距离超过，则有可能漏过最短模式串。minlenminlen以上各个函数计算及实现：Badcharacter_shift 的实现步骤为:Step 1：对每个字母表中的字符 char,令 Badcharacter_shiftchar=minlen.Step 2：对模式串 Pk中的字符 Pkj(1jmk),令 Badcharacter_shiftPkj =minlenk-j,Badcharacter_shiftPkj Badcharacter_shift 的计算公式：Badcharacter_shift(char)min

12、|&=minmin,1_kkkkklencharPlenj P jcharlenlenjlenkpattennum=(1)Goodsuffix_shift 的实现步骤为:Step 1：对每个字母表中的字符 char 和状态 state,令 Goodsuffix_shift(state,char)=minlen.Step 2：当文本串中本次匹配不成功的字符 char 加上已匹配成功的串 Ptj+1:mt所组成的子串在模式串集合中是除本身外的最右重现时,计算 Goodsuffix_shift(state,char)=mind(1dminlen)且(Pkj-d)=char)且(Pki-d=Pti),

13、for jilent),1kq.Step 3：当 Ptj+1:mt的后缀是某个模式串 Pk 的前缀时,计算 Goodsuffix_shift(state,char)=mind(1dminlen)且(Pki-d=Pti),for d 0d_shiftstatechar=goodsuffix_shift(state,char)char+开始d_shiftstatechar=badcharacter_shift(char)char 256state max_state结束state+state=0YYYNNN 图 2:计算流程图 d_shift搜索阶段 利用有限自动机对字符文本进行扫描，首先读入指定

14、字符判断有限自动机接收到该字符后系统状态，如果有输出则做相应匹配操作，否则判断状态是否为零，如果状态为零则利用d_shift 计算向后跳跃的距离（此距离是最大的可移动距离），继续进行，如果非零则说明当前匹配成功，需要先后回朔查找（回朔的字符之前比没有读取过，所以实际上并没有重复的读取、比较）。-4-http:/ Char=getchar()开始结束Char!=EOFState=0State=state_shiftstatecharState!=0匹配成功，向前退一查找YNNYYDforward=d_shift statecharOutputstate匹配成功相应操作NY 图 3:查找匹配阶段流

15、程简图 2.进一步改进进一步改进 鉴于在海量数据中搜索数量相对较少的模式串时，模式集字符出现在目标文本中的概率符合泊松分布(Poisson)，即模式串的中字符出现在目标文本中的概率会很小。所以有限状态自动机的状态通常是在零状态的，零状态下考察 Ti这个字符时,该字符一般不会出现在模式集中，于是搜索树向右移动。由于在多模式字符串匹配算法中,整个匹配过程所花费的时间大多是在状态转换上。所以要想提高匹配速度，就必须尽可能的减少字符比较次数。而要减少字符比较次数,就需要在每次匹配失败后尽可能多的跳过更多字符.此时在进行状态转换前,先考察 Ti+minlen这个字符，依此类推，只有当考察的字符出现在搜索

16、树中时才进行比较。通过设置一个布尔型的考察函数 analysis()进一步减少搜索树的比较次数，算法的执行效率将更高。特别是在模式集合越大，效率提高越明显。minlend_shift0cminanalysis(c)=othersFALSElenTRUE=这样每次在状态转换到零状态时读入字符后先判断改字符是不是需要分析，若不需要则继续向后跳过，从而进一步减少了与模式树的比较。minlen 3.结论：结论：本算法是在采用 AC 算法构建反向树型自动机的基础上,吸收了 BM 算法从右向左跳跃的思想，同时结合了能实现最大跳跃和尽可能少的比较次数的改进的 QS 算法的优点,来实现搜索树和文本的快速匹配，

17、从而避免了对文本内每一个字符的匹配。新算法的这些特性使得关键字检测过滤速度大大提高，关键词容量大大增加。算法的查找时间对模式串数目的增加不敏感,敏感的只是模式串的最短长度，而且算法可以通过改善使得只需通过增加有限的空间开销,就可获得明显的速度提高。在模式串较长和较短的条件下,算法都有相当好的性能，-5-http:/ 匹配效果理想。使用本算法，能提高内容过滤检测系统的性能。适用于高性能网络信息过滤，入侵检测，信息监控，病毒检测等领域。参考文献 References 1 王瀛,王冬.基于KMP算法的确定型有穷自动机的设计J.河南大学学报,2002.第32卷第3期:90-92 WangYing,Wa

18、ng Dong.Design for DFA Based on KMP AlgorithmJ.Journal of Henan University,2002.Vol.32 No.3:90-92 2 伊静,刘培玉.入侵检测中模式匹配算法的研究J.计算机应用与软件,2005,第22卷第1期,112-114 Yi Jing,Liu Peiyu.The Survey of the Pattern Matching Algorithm in Intrusion Detection System.Computer Applications and Software,2005.Vol.22 No.1 11

19、2-114 3 李树文.入侵检测系统中模式匹配算法的研究J.科技情报开发与经济 2006.第16卷第5期252-253 Li Shuwen.Analysis on the Pattern Matching Algorithm in the Intrusion Detection SystemJ.2006 SCI-TECH INFORMATION DEVELOPMENT&ECONOMY.Vol.16:252-253 4 金人超,宋恩民.一种改进Boyer-Moore.算法效率的预处理算法J.华中科技大学学报.2005.第33 卷增刊:265-267 Jin Renchao,Song Enmin.

20、A pre-processing algorithm for improving efficiency of the Boye-Moore algorithm J.J.HuazhongUniv.of Sci.&Tech.2005.Vol.33:265-267 5 程圣宇,白英杰模式匹配算法性能测试J.计算机应用2003第23 卷:358-360 Chengshengyu,Baiyingjie.Patten Matching Algorithm Testting J.Computer Applications.2003.Vol.23:358-360 6 庞善臣,王淑栋.串匹配的一个改进算法J.计

21、算机应用.2004.第24卷第12期:11-13 Pang Shanchen,Wang Shudong.Improved BM algorithm for pattern matching in string J.Computer Applications.2004Vol.24 No.12:11-13 7 许一震,王永成,沈洲.一种快速的多模式字符串匹配算法J.上海交通大学学报.2002第36卷第4期:516-520 Xu Yihen,Wang Yongcheng,Shen Zhou.A Fast Algorithm for Matching Multiple Patterns.JOURNAL

22、 OF SHANGHAI JIAO TONG UNIVERSITY.2002.Vo l.36No.4:516-520 8 Boyer RS,Moore J S.A fast string searching algorithm J.Communications of ACM,1977,20(10):762772 The Design of a New Fast Multi-pattern Matching Algorithm Li Shengcai School of Science,BeiHang University,Beijing,PRC,(100083)Abstract The str

23、ing matching speed is one of central issues of keywords detection and filtering system.Based on the AC algorithm for finite states automation,a fast algorithm to perform multi-pattern matching in a string is proposed which combines idea of Boyer-Moore(BM)algorithm and the advantages of an improved Q

24、uick Search(QS)algorithm.The algorithm makes full use of the successful results and failure ones in each matching and skips as more characters as possible.Hence,it can perform fast searching under least comparison times and without retrospect to each character in the target text.Experimental results show that the algorithm improves the matching ability of the keywords detection and filtering system for both cases of very long and very short patterns.Key words:Multi-pattern matching;finite state automaton;keywords detection and filtering;matching.-6-http:/