基于有序二叉树的快速多模式字符串匹配算法

1、计 算 机 工 程 第 36 卷 第17期V No.17 Computer Engineering ol .36 软件技 术与数据库文章编号：10003428(2010)17004203文献标识码：A2010年9月September 2010中图分类号：TP393基于有序二叉树的快速多模式字符串匹配算法周 燕1，侯整风1，何 玲2(1. 合肥工业大学计算机与信息学院，合肥 230009；2. 深圳金山信息安全技术有限公司，深圳 518057)摘 要：将有序二叉树和QS算法相结合，提出一种快速多模式字符串匹配算法，实现在多模式匹配过程中不匹配字符的连续跳跃。为提高匹配速度，利用已匹配的字符串信息

2、进行跳跃式的比较，避免文本扫描指针的回溯。实验结果表明，与SMA算法相比，该算法在预处理阶段构造速度和匹配速度更快，在模式串较长的情况下，性能更优越。 关键词：有序二叉树；多模式匹配；QS算法Fast Multi-pattern String Matching AlgorithmBased on Sequential Binary TreeZHOU Yan1, HOU Zheng-feng1, HE Ling2(1. School of Computer and Information, Hefei University of Technology, Hefei 230009; 2. Shen

3、zhen Kingsoft Information Security Technology Co., Ltd., Shenzhen 518057)【Abstract】This paper combines sequential binary tree with Quick Search(QS) algorithm to propose a fast multi-pattern string matching algorithm, which achieves better performance by shifting unmatched characters continuously in

4、the process of multi-pattern matching. It uses jump comparison with unmatched strings to enhance the speed and decrease character matching operations. Experimental results demonstrate that the algorithm constructs more quickly in preprocessing process and its search speed is higher than SMA algorith

5、m. It achieves better performance in the cases of longer string patterns.【Key words】sequential binary tree; multi-pattern matching; Quick Search(QS) algorithm1 概述模式匹配是指在文本序列Text=t0t1t2tn-1中检索子串Pattern=p0p1p2pm-1的问题。模式匹配广泛应用于入侵检测系统、内容过滤防火墙、计算机病毒特征码匹配以及DNA序列匹配等领域，研究高效的模式匹配算法具有非常重要的理论和现实意义。模式匹配可分为单模式匹配

6、和多模式匹配。单模式匹配算法一次只能对模式串进行一个模式匹配，主要有KMP(Knuth-Morris-Patt)算法1、BM (Boyer-Moore)算法2、QS(Quick Search)算法3等。多模式匹配算法一次可对模式串同时进行多个模式匹配，包括AC (Aho-Corasick)算法4、WM(Wu-Manber)算法5、AC-BM算法6等。AC算法是一种基于自动机的算法，首先根据模式集构建一棵搜索树，然后对待搜索文本从左至右进行扫描。由于搜索树的大小与字符集的大小有关，因此AC算法一般需要较大的内存资源。WM算法主要特点是采用了BM算法的不良字符转移机制，利用块字符扩展了不良字符转移

7、的效果，同时使用散列表筛选匹配阶段应进行匹配的模式串，减少了匹配计算量，因此，应用性能较好。AC-BM算法基于BM算法，将不同的规则放在一棵树上进行同时搜索匹配，能对目标串进行跳跃式搜索。文献7提出的SMA算法采用有序二叉树结构来组织有限状态自动机，解决了AC算法中有限状态自动机构造速度慢、占用内存大的问题，但是该算法在查找过程中必须检查每一个字符，降低了算法的查找效率。本文在SMA算法的基础上，吸收QS算法的思想，利用匹配过程中匹配失败的信息，达到最大跳跃距离，实现了快速的多 42模式匹配，提高了算法的性能。2 本文的快速多模式字符串匹配算法本文算法分为2个阶段：模式集的预处理阶段和文本的匹

8、配阶段。在预处理阶段，借鉴SMA算法的思想，对所有待匹配的模式进行分析和处理，构造一个关于这些模式的有序二叉树，并计算失配后文本指针的跳跃和新状态。在模式匹配阶段，利用建立好的有序二叉树对文本进行一次性的搜索，同时结合QS算法思想，以获得足够多的跳跃信息和尽量少的比较次数，从而提高匹配效率。对于待匹配模式集，预处理过程只需进行一次，就可以经过一次扫描从文本串中查找出所有与给定模式串集合中任何模式串相同的子字符串。2.1 预处理阶段预处理阶段构造一个由模式集构成的有序二叉树，并计算失配后文本指针的跳跃和新状态。该树中的每个结点表示一种状态，每种状态都代表一个模式的前缀或多个模式的共同前缀，而模式

9、集中的每一个前缀可用唯一的状态表示。 2.1.1 有序二叉树的构造读取模式串集合(各模式一般不是按字典序排列的)中的基金项目：安徽省自然科学基金资助项目(090412051)；广东省教育部产学研结合基金资助项目(2008B090500240)作者简介：周 燕(1985)，女，硕士研究生，主研方向：模式匹配，信息安全，计算机网络；侯整风，教授；何 玲，高级工程师 收稿日期：2010-02-01 E-mail：laxey所有模式，利用SMA算法中建立有序二叉树的子算法构造一棵有序二叉树，将树的节点作为自动机的状态，树的分支作为自动机的状态转移函数，得到状态转移函数GOTO(state, chara

10、cter)。例如，若给定模式串集合adds, mini, admin, sad, hads，其对应的有序二叉树如图1所示。图1 有限自动机的有序二叉树结构2.1.2 失配情况下文本指针跳跃和新状态的计算计算失配后文本指针的跳跃和新状态，结果用一个表move保存，movesc=(skip, newstate)，表示在状态s失配且向前看的文本字符为c时，文本扫描指针向前跳跃skip个位置，并从状态newstate开始继续比较。计算失配后的文本指针跳跃和新状态算法描述见算法1，其中，skip的计算方法如下：skip=minlen-k+1 if cPatternminlenlastck+1 ifcPa

11、ttern其中，k为状态s的深度；minlen为最短模式的长度；lastc为c在pi中最末出现的位置。算法1 计算失配后文本指针跳跃和新状态 输入 根节点为root的有序二叉树输出 保存失配后文本指针的跳跃和新状态的move表 (1)minlen最短模式的长度。(2)对每个c，lastc初始化为0。 (3)建立队列queue，并置空。(4)对每个满足GOTO(root,c)fail的字符c(即位于有序二叉树的深度为1的字符)，进行以下操作：1)lastc1；2)sGOTO(root,c)； 3)s.failstateroot； 4)s进入队列queue。 (5)当队列queue不为空，进行以下

12、循环(计算每个状态的failstate和每个字符的lastc)：1)s队列queue的队头元素出队。2)对每个满足GOTO(s,c)fail的字符进行以下操作： s1GOTO(s,c)； fail_ss.failstate；若GOTO(fail_s, c)=fail，则s1.failstate=root；否则，s1.failstateGOTO(fail_s,c)；s1进入队列queue；若s1在有序二叉树中的深度小于等于minlen，则 lastcs1在有序二叉树中的深度；否则，lastc0；(6)对自动机中的每个状态s和每个c进行以下操作(计算movesc)：1)k状态s在有序二叉树中的深度

13、；2)若c，则movesc.skipminlen-lastc-k+1； 3)若movesc.skip0，则movesc.newstateroot；否则，movesc.newstates.failstate，movesc.skip0。例如，对于图1所示的例子，用算法1建立的move表如表1所示，其中，表格的第1列表示状态；第1行表示向前看的字符；二元组表示(skip, newstate)。表1 move表状态h a d,m else0 (3,0) (2,0) (1,0) (4,0) 1 (2,0) (1,0) (0,0) (3,0) 2 (1,0) (0,0) (0,0) (2,0) 3 (0,

14、0) (0,0) (0,0) (1,0) 4 (0,16) (0,16) (0,16) (0,0) 5 (0,12) (0,12) (0,12) (1,0) 6 (0,13) (0,13) (0,13) (0,0) 2.2 模式匹配阶段在匹配过程中，利用预处理阶段构造的有序二叉树和失配转移表move对文本串进行一次性的搜索，查找文本是否包含模式集中的模式。例如，根据图1的有序二叉树对文本进行搜索，从状态0开始，根据当前的状态和从文本中读入的字符决定下一个状态。若进入终止状态，表示已找到一个匹配的模式。若根据当前状态和读入的字符找不到下一个状态，表示出现失配情况。出现失配后，本算法利用已匹配的信

15、息，通过向右看文本的一个字符实现跳跃式比较的方法，避免了文本扫描指针的回溯，减少了比较的次数。失配后，有序二叉树至少要向前移动一个位置，若要匹配成功，前方的字符必须在成功匹配的模式中出现，因此，以最短模式为标准向右看文本的一个字符，并计算该字符在所有模式中最后出现的位置，然后把整个有序二叉树移动若干位，使该字符与其在模式中最后出现的位置对齐，从而跳过一些不必要的比较。算法2 模式匹配算法输入 文本串T1:n，根为root的有序二叉树，move表 输出 匹配成功的模式串在文本中出现的位置(1)minlen最短模式的长度，初始化文本扫描指针i1，初始化当前状态s0。(2)当in，进行以下循环： 1

16、)cTi。2)若GOTO(s,c)fail，则： sGOTO(s,c)；若s.output为true，则输出i； ii+1。3)若GOTO(s,c)=fail(即出现失配情况)，则：计算向前看的字符的位置kminlen-s所处的层次+1； 向前看的字符为chTi+k；43若ch，则文本指针跳跃到新位置ii+ movesch.skip，新状态为smovesch.newstate；否则，文本指针跳跃到新位置ii+minlen-s所处的层次+1，新状态为sroot。2.3 示例选取含有5个模式串的模式串集合P=adds, mini, admin, sad, hads，若文本串为T=addsxyzxm

17、ini，用算法2在文本串T中查找模式串P中的任一模式串。模式串集合转换成的有序二叉树如图1所示，最短模式长度minlen=3，匹配过程如图2所示。字符比较 状态s(skip,state)输出 addsxyzxmini addsxyzxmini addsxyzxmini addsxyzxmini addsxyzxmini addsxyzxmini addsxyzxmini addsxyzxmini addsxyzxmini addsxyzxmini 图2 模式串匹配过程3 算法分析设模式串集合的模式个数为k，长度分别为l1,l2,lk，所有模式串的长度之和为kli=1i，其中，模式串的最短长度为

18、minlen；字符集的大小为；待搜索文本串的长度为n。算法分析分预处理和匹配2个阶段进行。在预处理阶段，构造有序二叉树的时间复杂度为O(k)，算法1中，计算failstate的时间复杂度主要由内层循环决定，为O(kli)，计算move表的时间复杂度为O(kli=1i=1i)，因此，算法1的时间复杂度为O(klki=1i+li=1i)。综上所述，预处理阶段的时间复杂度为 O(k+klki+li=1i=1i)。在匹配阶段，算法2中文本扫描指针i是无回溯且进行跳跃式比较的，最坏情况下的比较次数不超过2n次，设每次比较后指针的平均跳跃距离为len，则匹配过程的时间复杂度为O(n/len)，最好情况下l

19、en可以达到minlen+1，因此，匹配阶段最好时间复杂度可达到O(n/(minlen+1)，最坏情况下为O(n)。SMA算法必须检查文本中每个字符，而且文本扫描指针不能跳跃，其匹配阶段时间复杂度为O(nh/2)7。4 实验结果及分析为测试本文算法的性能，并与SMA算法做比较，实验中待匹配文本为从互联网上下载的17 Mb英语新闻，模式串44 集合由英文新闻常用人名、地址名以及一些计算机常用术语组成。实验在Pentium4 2.4 GHz、1 GB内存、Windows XP下进行，测试在不同模式集和模式长度下算法的性能。实验结果如表2、表3所示。从表2可看出，本文算法与SMA算法预处理的时间都随

20、着模式串数目的增加而增加，本文算法预处理时间略多。由表3可看出，本文算法的匹配时间明显低于SMA算法，因为本文算法在匹配时采用了加速处理，当文本中模式串出现的频率较小时，模式比较之前跳过的字符较多，最大可以达到minlen+1。特别是在最小模式串较长、模式串数目较多时，本文算法的优势更加突出。表2 预处理时间比较 ms模式数目SMA本文算法100 0 0 200 16 31 400 110 125 600 312 344表3 不同minlen下匹配时间比较 ms模式minlen3 minlen6 minlen9 数目SMA本文算法SMA本文算法SMA本文算法100 531 422 578 28

21、1 766 329 200 750 =516 =813 312 =1 078765 400 984 625 1 047 391 1 109813 6001 1887501 1724071 2488655 结束语模式串匹配是计算机研究领域的一个热点问题。本文结合QS算法思想，提出一种基于有序二叉树的快速多模式字符串匹配算法，利用已匹配信息，尽可能多地跳过待查文本串字符，因此，在模式串较长和模式串数目较多时，本文算法相比其他算法具有更好的性能。参考文献1 Knuth D E, Morris J H, Pratt V R. Fast Pattern Matching inStringsJ. SIAM Journal on Computing, 1977, 6(2): 323-350. 2 Boyer R S, M