一种存储优化的多模式匹配算法一种存储优化的多模式匹配算法
AC（Aho-Corasick）自动机是经典的多模式匹配算法，但在模式串字符集较大的情况下，AC自动机的存储开销
较大。为降低存储开销提出了存储优化的多模式匹配算法SMMA，该算法在Trie树建立阶段利用正向表来存储每
个状态的后续状态指针以及失配指针，而无需存储字符集所有字符的后继指针，从而压缩了每个状态的储存空
间。实验表明，所提出的算法与AC自动机算法在时间效率上相近，但极大地降低了存储开销。
摘摘 要要： AC（Aho-Corasick）自动机是经典的多
关键词关键词： 模式匹配；AC自动机；Trie树
0 引言引言
模式匹配算法一直是信息领域的研究热点，广泛应用于入侵检测、生物信息学、模式识别等领域[1]。模式匹配算法可以
分为单模式匹配算法[2-3]和多模式匹配算法[4-8]。Aho-Corasick算法[4]（以下简称AC算法）是经典的多模式匹配算法，它把
所有模式串构建成Trie树，并进一步预处理得到有限状态自动机，对主串的一次扫描即可完成所有模式串的匹配。Commentz-
Walter算法（CW算法）[5]建立反向自动机，在模式匹配阶段利用坏字规则和好后缀规则，在失配时滑动最大的距离，实现了
模式串的跳跃匹配，减少了时间开销。Wu-Manber（WM）算法[6]对多模式串进行预处理，建立三张映射表进行部分匹配，
最后进行全模式匹配，提高了效率。参考文献[7]提出了改进的多模式匹配算法，在DFSA算法的基础上，结合QS算法[8]思
想，利用匹配过程中匹配失败信息，跳过尽可能多的字符。
AC算法的一个不足是需要为自动机每个状态分配空间，在模式串字符集比较大的情况下，算法空间复杂度比较大。极端
情况下，需要使用外存来保存匹配过程的中间信息，严重影响算法效率。为此，参考文献[9]提出基于异构隐式存储的多模式
匹配算法，从横向扇出压缩与纵向路径压缩入手，减少了空间开销，但算法的空间压缩率不高，且算法效率有所降低。参考文
献[10]通过选择性分群减小匹配算法的空间复杂度，有效解决导致DFA状态膨胀的问题。参考文献[11]提出了对DFA进行高效
存储的方法，从DFA状态数目和状态转移数目两方面进行压缩。在复合的FSM中，利用新的正则特征，进一步存储压缩，但
是算法实现复杂、压缩性能不稳定、时间效率不高，实际工程应用不理想。为了减少自动机各结点的存储空间，TUCK N等人
[12]在每个结点中增加一个位图数据，以记录当前结点所有的下一层结点的状态，压缩了存储空间。AC-bitmap[13]则将自动
机的所有结点按模式树结构的层数进行划分，使得两种存储方式共存，以压缩算法的存储空间。但是，基于位图压缩自动机算
法要求采用连续的地址空间存储，以加快转移时的查找速度，算法实现比较复杂，并且算法要求为每个结点存储一个位图信
息，随着字母表的不断增大，其存储空间将迅速增大。
为更好地优化多模式匹配算法的空间复杂度，本文提出了基于存储优化的多模式匹配算法（Storage-optimized Multi-
pattern Matching Algorithm，SMMA）。该算法在建立Trie树时，动态建立自动机上每个状态结点的字符集，只保留Trie树上
的有效路径信息，以保证用最小的空间代价存储模式串的所有信息，避免了无效字符路径的创建，压缩了储存空间。在模式匹
配阶段，通过在自动机上的状态转移完成匹配。在保持算法时间复杂度不变的情况下，显著降低了算法的空间开销。
1 相关概念相关概念
定义1 设p为Trie树的一个结点，则Trie树中从根结点到结点p的简单路径上所有字符组成的字符序列称为结点p的路径，记
为path（p）。构成path（p）中字符的个数称为结点p的路径长度，记为Len（p）。
定义2 设p为Trie树的一个结点，若结点p的路径path（p）是一个模式串，则称结点p为匹配点，否则称为非匹配点。
定义3 自动机M是一个五元组：M=（Q，?撞，g，q0，F）。其中：Q是有穷状态集；?撞是字母表；g是转移函数，转向
下一个状态；q0是初始状态；F是自动机M上的终止状态集。
定义4 设pa、p为自动机上的状态结点，c为字符集中的一个字符，若?埚
p，pa，c，path（p）=c+path（pa），p∈Q，pa∈Q，c∈（sigma），则称pa为p的后缀结点，记为S（p）。
定义5 设p为Trie树的一个结点，当且仅当结点p或其后缀结点为匹配点，结点p具有匹配性。
定义6 设p为自动机上的一个状态结点，则称Len（S（p））为结点p的匹配长度。
2 SMMA模式匹配算法模式匹配算法
2.1 SMMA算法的基本思想算法的基本思想
SMMA算法包括三个阶段：建立Trie树阶段、建立自动机阶段和模式匹配阶段。SMMA算法在建立Trie树时，并不像传统
的AC自动机那样为每一个结点开辟字符集大小的后继指针空间，而是根据具体的模式串信息动态地扩增Trie树结点的后继指
针空间，因此只保留Trie树上的有效路径信息，避免了无效字符路径的创建，压缩了储存空间。在实现时，SMMA用正向表来
存储Trie树。
建立自动机和模式匹配阶段都有查询当前结点cur的某个后继ch的操作goto（cur，ch）。若当前结点的后继结点不存在，
则继续查询goto（fail[cur]，ch）。为了快速求得所需的后继结点，本文用Next（cur，ch）函数获得后继结点编号，Next（）
函数的实现在2.3节介绍。
2.2 正向表正向表
正向表是一种边表，空间代价与邻接表相当，由于正向表没有使用指针而减少了一部分结构性开销，在存储树和稀疏图时
资源评论
