一种改进的AC多模式匹配算法

刘春晖，黄 宇，宋 琦

（合肥工业大学计算机与信息学院，合肥 230009）

一种改进的AC多模式匹配算法

刘春晖，黄 宇，宋 琦

（合肥工业大学计算机与信息学院，合肥 230009）

在分析AC算法及其相关算法的基础上，提出一种改进的多模式匹配算法AC-TE。利用该算法构建1个字符串跳跃表和2个哈希表，字符串表存储模式树中两两相邻字符组成的字符串及其位置，2个哈希表分别存储模式树末层字符串和字符。采用多层跳跃规则依次查找这3个表，在不发生漏检的情况下，使模式树的最大移动距离为最短模式串长度加3。从模式树移动次数、匹配阶段时间、各种跳跃距离的概率3个方面测试算法性能。实验结果表明，与AC算法相比，AC-TE算法具有更大的模式树移动距离，消耗的时间更少。

多模式匹配；AC算法；漏检；移动距离；模式树

DO I：10.3969/j.issn.1000-3428.2015.10.053

1 概述

随着互联网技术的发展，模式匹配技术被广泛应用于生物医学［1］、网络搜索引擎［2］、内容过滤防火墙［3］、入侵检测系统［4］等领域，成为信息领域中重要的研究方向之一。

BF算法［5］是最早的单模式匹配算法，模式串每次移动一个字符的位置，匹配效率低。文献［6］提出了带转移函数的KMP算法，实现模式串跳跃式匹配。文献［7］提出一种更高效的算法——BM算法，通过引入好后缀规则和坏字符规则，增大模式串跳跃距离。文献［8］改进了BM算法，提出BMH算法，只保留坏字符规则，降低了预处理阶段复杂度。文献［9］进一步改进了BM算法，发生失配时，只考虑紧靠当前匹配窗口的后一个字符，增加了模式串移动距离。

文献［10］提出AC多模式匹配算法，通过构建有限状态自动机，实现一次扫描文本完成多个模式匹配。文献［11］在AC算法基础上，结合BM算法思想，采用坏字符和好后缀规则，实现了模式树的跳跃式匹配，模式树最大移动距离为最短模式串长度，因而具有更高的匹配效率。文献［12］结合了AC算法和BMH算法，只保留坏字符规则，但模式树最大移动距离没有变。文献［13］采用字符块判断方法，

增大了跳跃的概率，但最大移动距离仍为最短模式串长度。文献［14］结合了AC算法和QS算法，尽可能跳过更多的字符，模式树最大移动距离为最短模式串长度加1。

本文对AC改进算法的模式树移动规则进行研究，提出一种高效的多模式匹配算法——AC-TE（Time Efficient AC）。该算法构建1个字符串跳跃表和2个哈希表，采用多层跳跃规则依次查找这3个表，在不发生漏检情况下，模式树最大跳跃距离可达到最短模式串长度加3。

2 AC及其改进算法

2.1 AC算法

2.1.1 预处理阶段

预处理阶段构建有限状态自动机并计算转移函数和输出函数。

（1）构建有限状态自动机

对于模式串集P=｛P1，P2，…，Pr｝，构建有限状态自动机过程描述如下：从状态0开始，读取第1个模式串的第1个字符，生成新状态；再从新状态开始，读取第1个模式串的第2个字符，生成新的后继状态，以此类推，直到处理完所有字符；处理完第1个模式串之后，再从0状态处理第2个，直到处理完所有模式串。例如，对于模式串集 Pset=｛go，good，get，ago｝，构成的有限状态自动机如图1所示。

图1 有限状态自动机

（2）计算转移函数

转移函数包括状态转移函数goto和失效转移函数failure。自动机中，对于状态s，若读入字符c，生成状态s’，那么goto（s，c）=s′。对于状态s，若读入字符c，没有后继状态，那么goto（s，c）=fail。如图1所示的有限状态自动机goto（1，o）=2，goto（1，e）= 5，goto（1，c）=fail。

失效函数failure用来计算某个字符失配时，应转移的状态。失效函数计算规则：若某状态的父状态为0，则该状态的失效函数为0；对于其他状态m，若其父状态为r，标注的字符为“a”，那么failure（m）=goto（failure（r），a）。如图 1所示有限状态自动机failure（7）=0，failure（8）=goto（failure（7），g）= goto（0，g）=1，failure（9）=goto（failure（8），o）= goto（1，o）=2。

（3）计算输出函数

构造有限状态自动机过程中，每当处理完一个模式串，就将该模式串加入到当前状态 s的输出函数中。计算失效函数过程中，若failure（s）=s′，则outPut（s）=outPut（s）∪outPut（s′）。如图1所示有限状态自动机，outPut（2）=go，因为failure（9）=2，所以outPut（9）=｛ago｝∪outPut（2）=｛ago，go｝。

2.1.2 匹配过程

匹配过程的步骤如下：

（1）文本串指针P指向文本串首字符，当前状态s=0。

（2）若P！=NULL，读取所指字符c；否则匹配结束。

（3）计算 s′=goto（s，c），若 s′=fail，转步骤（4）；否则当前状态 s=s′，P右移一位；如果outPut（s）==NULL，转步骤（2）；否则，有模式串得到匹配，输出匹配信息，转步骤（2）。

（4）s=failure（s），转步骤（3）。

2.2 AC改进算法

AC算法不能跳跃，不必要的字符比较次数多。针对此问题，研究人员提出了多种改进算法。

AC-BM算法是在AC的基础上，结合BM算法的启发规则，产生的一种多模式匹配算法。与 AC算法不同，AC-BM算法将模式串集构建为Trie树（模式树）。模式树移动方向从右向左，字符比较方向从左向右。此外，AC-BM算法在预处理阶段不考虑失效函数的问题。匹配阶段通过坏字符规则和好后缀规则进行跳跃。坏字符和好后缀规则描述如下：设当前匹配窗口文本串失配字符为c，对应模式树深度为dePth（1≤dePth≤minlen），已匹配部分为字符串S，最短模式串长度为minlen。坏字符规则考察c在模式树第dePth层到第minlen层中的出现情况，若未出现，则直接将模式树移过字符c，移动距离为minlen-dePth+1；若出现在第dePth0层（dePth＜dePth0≤minlen，如果出现多次，取其中深度最小的），则移动模式树使第dePth0层和字符c对齐，移动距离为dePth0-dePth。可以看出，在最好情况下，即dePth=1时，当前匹配窗口第一个字符即失配，此时最大移动距离为最短模式串长度。好后缀规则考虑已匹配部分S在模式树minlen深度内出现情况。若模式树minlen深度内有任何模式串以S为前缀，则将模式树移动minlen-dePth个字符；否则在模式树minlen深度内查找任何以字符串S长度为P的后缀子串作为前缀的模式串，若找到则将模式串移动minlen-P个字符，否则模式树只移动1个字符。可以看出，最好情况下，即dePth=1或P=1时，最大移动距离为最短模式串长度减1。

文献［12］将AC算法与BMH算法相结合，提出了AC-BHM算法，只保留AC-BM的坏字符规则，但模式树的最大移动距离没有变，仍为最短模式串长度。

文献［13］提出了一种更高效的AC改进算法算法——AC-QSS算法。该算法将当前匹配窗口文本串第一个字符以及前一个字符组成字符块str，发生失配时，若str不在模式树minlen深度内出现，则直接将模式树移动minlen个字符。连续2个字符在模式树内出现的概率要小于单个字符出现的概率，特别是在大字符集、短模式串环境下，连续2个字符未出现的概率往往能达到100%，模式树往往能达到最大移动距离。该算法提高了达到最大移动距离的概率，但没有提高最大移动距离，仍为最短模式串长度。

文献［14］将AC算法与SUNDAY算法结合，提出了AC-SUNDAY算法，在发生失配时关注的是文本串当前匹配窗口的前一个字符c。AC-SUNDAY算法基于这样的考虑，当发生失配时，模式树移动距离至少为1，那么字符c必然会参与下一次比较，如果c不在minlen深度内出现，则可以直接跳过，使得模式树最大移动距离达到minlen+1。如果c出现在minlen深度内，且深度为dePth（1≤dePth≤minlen，若c出现多次，取其中最小深度值），则移动距离为dePth。AC-SUNDAY算法模式树最大移动距离为最短模式串长度加1。

上述4种AC改进算法的模式树最大移动距离为最短模式串长度或最短模式串长度加1，但仍不够大。

3 AC-TE算法

针对AC-BM等算法模式树移动距离不足的问题，本文考虑当前匹配窗口前3个字符，设计新的模式树移动规则，在不发生漏检情况下，模式树最大移动距离可达最短模式串长度加3。在此基础上，设计一种更高效的多模式匹配算法——AC-TE算法。

3.1 算法设计思想

AC-TE算法用1个字符串跳跃表和2个哈希表来确定发生失配时的移动距离。设模式串集Pset=｛abc，aef，aaaef｝，当前匹配窗口前3个字符分别为χ，y，z，如图2所示。AC-TE算法模式树移动规则描述如下：

（1）若z=模式树首层字符，移动距离为1。

（2）若yz在模式树minlen深度内出现，移动使之对齐（查找字符串跳跃表）。

（3）若 χy=任一模式串第 minlen-1和第minlen层字符组成的字符串，移动距离为minlen+1（查找哈希表1）。

（4）若χ=任一模式串第minlen层字符，移动距离为minlen+2（查找哈希表2）。

（5）若以上均不满足，移动距离为minlen+3。

图2 匹配窗口

3.2 算法步骤

AC-TE算法分为2个阶段：预处理阶段和匹配阶段。

（1）预处理阶段

1）构建模式树。

2）创建字符串跳跃表（String Shift Table，SST），记作SST。

将模式树minlen深度内两两相邻字符组成字符串。字符串表用来记录这些字符串在模式树中的位置，通过到模式树首层字符的距离来表示，记为dis（S）。对任一字符串S=Pi［k］Pi［k+1］（1≤i≤r，1≤k≤minlen-1），dis（S）=Pi［k］到模式树首字符距离等于k-1。若某个字符串多次出现，取其中的最小值。SST表创建算法伪代码具体如下：

算法1创建字符串跳跃表SST

例如，对于模式集Pset=｛abc，aef，aaaef｝，P1= abc，P2=aef，P3=aaaef，minlen=3。minlen深度内

所有两两相邻字符构成的字符串集合为 S=｛ab，bc，ae，ef，aa｝。以字符串aa为例，在minlen深度内出现了2次，均在 P3中。选深度较小的位置计算，由于a=P3［1］，k=1，因此dis（aa）=0。由Pset创建的SST表如表1所示。

表1 SST表

3）创建末层字符串哈希表（Last Two String hashing Table），记作LTST。LTST表存储每个模式串第minlen-1个字符及第minlen个字符组成的字符串。LTST表创建算法伪代码如下：

算法2创建LTST

例如，模式集 Pset=｛abc，aef，aaaef｝对应的LTST表如表2所示。

表2 LTST表

4）创建末层字符哈希表（Last Character hash Table），记作LCT。LCT表存储每个模式串第minlen层的字符。LCT表创建算法伪代码如下：

算法3创建LCT表

例如，模式集Pset=｛abc，aef，aaaef｝对应LCT表如表3所示。

表3 LCT表

（2）匹配阶段

1）初始状态。模式树的首层节点对齐文本串的倒数第minlen个字符，第minlen层节点对齐文本串的末字符。模式树移动方向从右向左，字符比较方向从左向右。

2）字符比较。在当前匹配窗口内，从左向右逐个读入文本串字符，利用goto函数进行状态转移，当outPut函数不为空时，输出匹配成功的字符串；当发生失配时，计算移动距离shift length，并将模式树左移shift length位。移动距离计算算法伪代码如下：

算法4计算移动距离

3）重复步骤2），直到模式树和文本串的首字符对齐，匹配过程结束。

3.3 AC-TE算法分析

3.3.1 模式树最大移动距离的增大

已有的改进AC多模式算法模式树最大移动距离为最短模式串长度加 1。AC-BM 算法和AC-BMH算法的坏字符在匹配窗口内，最多能跳过当前匹配窗口，距离为最短模式串长度。AC-QSS算法最大安全移动距离也为最短模式串长度，任何大于最短模式串长度的移动都有可能造成漏检。AC-SUNDAY算法的坏字符是当前匹配窗口外前一个字符，跳过这个坏字符能达到最短模式串长度加1的移动距离。之所以没有出现移动距离超过最短模式串长度加1的算法，是因为按照传统的移动规则，会导致不能达到1位或2位的移动距离，从而导致漏检。以AC-SUNDAY算法跳跃思想为例，若要使

最大移动距离为最短模式串长度加3，则可以考虑匹配窗口前第 3个字符。若该字符不存在于模式树minlen深度内，直接将其跳过，移动距离为minlen+ 3。但是，此时最小跳跃距离为3，遗漏了距离为1和2的移动情况。AC-TE算法移动距离计算算法考虑到较小的跳跃距离，能够跳跃1～minlen+3的任一距离，所以不会发生漏检。AC-TE算法最好情况下能跳过当前匹配窗口前3个字符，使得模式树最大跳跃距离为最短模式串长度加3。最大移动距离的增大使得平均移动距离得到增加，减少了字符比较次数，提高了匹配速度。

3.3.2 预处理阶段时空复杂度

算法1的外层循环次数等于模式串的数量r，内层循环次数为 minlen-1，时间复杂度为 r×（minlen-1）。算法1字符串表存储的是所有模式串minlen深度内长度为2的字符串及对应dis值，空间复杂度为r×（minlen-1）。算法2只有一层循环，时间复杂度是 r。算法 2存储所有模式串第minlen-1个字符及第minlen个字符组成的字符串，所以空间复杂度也为r。和算法2类似，算法3时间空间复杂度均为r。

因此，预处理阶段总的时间复杂度为 O（r×（minlen-1）+r+r），即O（r×（minlen+1））。预处理时间空间复杂度也为O（r×（minlen+1））。

3.3.3 匹配阶段时间复杂度

AC-TE算法匹配阶段时间复杂度分3种情况讨论。在最坏情况下，模式树每次都移动一个字符位置，且最长模式串比较到最后一个字符，时间复杂度为O（n×maχlen），n为文本串长度，maχlen为最长模式串长度。最好情况下，匹配窗口每次均移动minlen+3个字符，此时时间复杂度为O（n/（minlen+ 3））。平均情况下，时间复杂度为O（n）。

最坏情况下，AC-BM，AC-BMH，AC-QSS和ACSUNDAY算法时间复杂度均为O（n×maχlen）。平均情况下，上述算法时间复杂度也为O（n）。但是，在最好情况下，上述算法时间复杂度分别为O（n/minlen），O（n/minlen），O（n/minlen）和O（n/（minlen+1））。

考虑到AC-TE算法最大移动距离大，且采用字符块判断规则，达到超过minlen移动距离的概率也大，故匹配阶段时间效率优于上述算法。

4 实验与结果分析

实验环境：Window s 8.1系统，因特尔Core Dual-Core 1.5 GHz，3 GB内存。

实验数据：待匹配文本串为路透社Reuters-21578新闻数据集，约为28 MB。然后，从纽约时报、中国日报、华盛顿邮报的500个新闻网页上随机截取长度分别为4 Byte，8 Byte，16 Byte，24 Byte，32 Byte的模式串各400个。

（1）模式树移动次数

固定模式串长度为8 Byte，改变模式串数量。实验结果如图3所示，最好情况下，AC-TC算法模式树移动次数只有AC-BMH算法的71.0%，ACQSS算法的82.8%，AC-SUNDAY算法的88.9%。模式树移动次数越少，平均移动距离越大，时间效率越高。

图3 固定模式串长度时的模式树移动次数

固定模式串数量为400，取不同模式串长度进行实验。实验结果如图4所示，AC-TE算法的模式树移动次数始终最少，效率最高。

图4 固定模式串数量时的模式树移动次数

（2）匹配阶段时间

固定模式串长度为8 Byte，数量分别为10，20，50，100和400，结果如图5所示，可以看出AC-TE算法的时间性能最优。

图5 改变模式串数量所用时间

固定模式串数量为400，分别取不同模式串长度进行实验，结果如图6所示，可以看出AC-TE算法消耗时间始终最少。

图6 改变模式串长度所用时间

（3）各种跳跃距离的概率

AC-TE模式树移动距离有 5种情况，即 1，dis（yz）+2，minlen+1，minlen+2，minlen+3。根据表4实验结果，5种情况出现的平均概率分别为3.0%，17.6%，9.6%，7.0%和62.9%，达到minlen以上跳跃距离的平均概率可达79.5%，时间效率高。

表4 各种跳跃距离下的概率

5 结束语

本文提出一种高效的多模式匹配算法——ACTE。该算法基于有限状态自动机，采用多层判断规则查找3个预处理表，实现了模式树的跳跃式匹配。理论分析和实验表明，AC-TE算法的时间性能优于已有AC改进算法。下一步将对AC-TE算法如何高效地应用于内容过滤防火墙进行研究。

［1］ Bergeron B.Bioinformatic Computing［M］.Indianapolis，USA：Prentice Hall，2002.

［2］ 王继成，萧 嵘，孙正兴，等.Web信息检索研究进展［J］.计算机研究与发展，2001，38（2）：187-193.

［3］ 宋 华，戴一奇.一种用于内容过滤和检测的快速多关键词识别算法［J］.计算机研究与发展，2004，41（6）：940-945.

［4］ 蒋建春，卿斯汉.网络安全入侵检测：研究综述［J］.软件学报，2000，11（11）：1460-1467.

［5］ 卢开澄.计算机算法导引-设计与分析［M］.北京：清华大学出版社，1996.

［6］ Knuth D E，Morris JH，Pratt V R.Fast Pattern Matching in Strings［J］.SIAM Journal on Computing，1977，6（2）：323-350.

［7］ Boyer R S，Moore J S.A Fast String Searching Algorithm［J］.Communications of the ACM，1977，20（10）：762-772.

［8］ Horspool R N.Practical Fast Searching in Strings［J］. Software-Practice&Experience，1980，10（6）：501-506.

［9］ Sunday D M.A Very Fast Substring Searching Algorithm［J］.Communications of the ACM，1990，33（8）：132-142.

［10］ Aho A V，Corasick M J.Efficient String Matching：An Aid to Bibliographic Search［J］.Communications of the ACM，1975，18（6）：333-340.

［11］ Commerntz W R.A String Matching Algorithm Fast on the Average［C］//Proceedings of the 6th Colloquium on Automata，Languages and Programming.Berlin，Germ any：Springer-Verlag，1979.

［12］ 陆琳琳，田 野.基于确定有限状态自动机的改进多模式匹配算法研究［J］.计算机应用与软件，2013，30（7）：322-326.

［13］ 舒银东.基于有限状态自动机的多模式匹配算法研究［D］.合肥：合肥工业大学，2011.

［14］ 董世博，李训根.一种改进的字符串多模式匹配算法［J］.计算机工程与应用，2013，49（8）：133-137.

编辑顾逸斐

An Improved AC Multiple Pattern Matching Algorithm

LIU Chunhui，HUANG Yu，SONG Qi
（School of Computer&Information，Hefei University of Technology，Hefei 230009，China）

A time efficient AC algorithm AC-TE is suggested for multiple pattern string matching based on the analysis of AC and related algorithms.The AC-TE algorithm constructs a string shift table and two hash tables.The string shift table stores every adjacent two characters of pattern tree and their positions，while the two hash tables store last two strings and last character of pattern tree respectively.AC-TE uses multiple level skipping rules to check these three constructed tables.As a result，pattern tree’s shift distance can be shortest pattern length pluses 3 without missing matched position. To analyze the performance of the AC-TE algorithm，some experiments are done from three aspects which are pattern tree shift times，matched time and probability of different shift distance.Experimental results show that compared with AC algorithm，AC-TE has longer pattern tree shift distance and better time performance.

multiple pattern matching；AC algorithm；omission；shift distance；pattern tree

刘春晖，黄 宇，宋 琦.一种改进的AC多模式匹配算法［J］.计算机工程，2015，41（10）：280-285.

英文引用格式：Liu Chunhui，Huang Yu，Song Qi.An Improved AC Multiple Pattern Matching Algorithm［J］.Computer Engineering，2015，41（10）：280-285.

1000-3428（2015）10-0280-06

A

TP301.6

教育部广东省产学研基金资助项目（2009B090200049）；安徽省自然科学基金资助项目（11040606M 138）。

刘春晖（1989-），男，硕士研究生，主研方向：网络与信息安全，防火墙技术；黄 宇、宋 琦，硕士研究生。

2014-10-15

2014-11-11E-mail：742233361@qq.com