高级AC自动机的快速构建方法

摘要：

高级AC(advanced AC,AAC)是一种基于自动机的多模式串匹配算法,应用极为广泛.在大规模匹配时AAC自动机构建耗时较大,改进了经典精确单模式匹配算法——DFA算法自动机构建过程,并将其扩展到多模式匹配领域,提出Set DFA自动机,并证明Set DFA自动机和AAC自动机一致.该自动机构建方法简单清晰,无需计算失败函数,自动机内每个状态在生成后只需访问一次即可完成自动机构建.实验表明Set DFA构建时间只有AAC自动机的一半左右.

关键词：串匹配、多模式、自动机、失败函数、高级AC

所属期刊栏目：50

分类号：TP391.3(计算技术、计算机技术)

资助基金：云南省科技厅应用基础研究面上项目2012FB131

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

页数：共8页

页码：2699-2706