基于AC自动机的多模式匹配算法FACA

• 作者: 贾泂 陈新驰 韩建民
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 模式匹配 自动机 动态规划 Trie树
• 年，卷（期）: 2012,（11）
• 所属期刊栏目: 人工智能及识别技术
• 页码范围: 173-176
• 分类号: TP312
• 字数: 5244字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2012.11.053

摘要

Aho-Corasick自动机算法在模式匹配失配时,需要多次回溯才转移到有效的后继状态.为此,提出一种快速多模式匹配算法.该算法为每个状态建立失配时的后继指针,在模式匹配失配时,可以通过失配后继指针快速找到有效后继状态,从而避免Aho-Corasick自动机失配时的过多回溯,提高匹配效率.算法在自动机建立时采用动态规划的方法,为每个状态建立匹配长度和匹配量等信息,在模式匹配过程中,基于这些信息统计模式串在主串中的重复次数、最早出现模式串位置等信息.实验结果表明,该算法匹配精确、效率高,且支持在线操作.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	贾泂	浙江师范大学计算机系	30	285	10.0	16.0
2	韩建民	浙江师范大学计算机系	45	480	11.0	21.0
3	陈新驰	浙江师范大学计算机系	2	9	2.0	2.0