Hits :
First Author : 段惠超
Date of Publication : 2015-01-01
Journal : 微型机与应用
Affiliation of Author(s) : 数理与信息工程学院
Document Type : 期刊
Issue : 第2期
Page Number : 14-17
ISSN : 2096-5133
Key Words : 模式匹配;AC自动机;Trie树
Abstract : AC(Aho-Corasick)自动机是经典的多模式匹配算法,但在模式串字符集较大的情况下,AC自动机的存储开销较大。为降低存储开销提出了存储优化的多模式匹配算法SMMA,该算法在Trie树建立阶段利用正向表来存储每个状态的后续状态指针以及失配指针,而无需存储字符集所有字符的后继指针,从而压缩了每个状态的储存空间。实验表明,所提出的算法与AC自动机算法在时间效率上相近,但极大地降低了存储开销。
Translation or Not : no