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

• 作者: 姚念民 范洪博
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 串匹配 多模式 自动机 失败函数 高级AC
• 年，卷（期）: 2013,（12）
• 所属期刊栏目: 计算机科学理论
• 页码范围: 2699-2706
• 页数: 8页
• 分类号: TP391.3
• 字数: 7002字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	姚念民	大连理工大学计算机科学与技术学院	10	31	4.0	5.0
2	范洪博	昆明理工大学信息工程与自动化学院	27	75	5.0	6.0