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

摘要：

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

关键词：模式匹配、自动机、动态规划、Trie树

所属期刊栏目：38

分类号：TP312(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61170108,6110019;浙江省新苗人才计划基金资助项目2011R404018

在线出版日期：2012-09-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：173-176