高级AC自动机的快速构建方法
Release time:2019-03-10
Hits:
Indexed by:
期刊论文
First Author:
范洪博
Correspondence Author:
Fan, H.(270677673@qq.com)
Co-author:
姚念民
Date of Publication:
2013-12-15
Journal:
计算机研究与发展
Included Journals:
EI、PKU、ISTIC、CSCD、Scopus
Document Type:
J
Volume:
50
Issue:
12
Page Number:
2699-2706
ISSN No.:
1000-1239
Key Words:
串匹配;多模式;自动机;失败函数;高级AC
Abstract:
高级AC(advanced AC,AAC)是一种基于自动机的多模式串匹配算法,应用极为广泛.在大规模匹配时AAC自动机构建耗时较大,改进了经典精确单模式匹配算法——DFA算法自动机构建过程,并将其扩展到多模式匹配领域,提出Set DFA自动机,并证明Set DFA自动机和AAC自动机一致.该自动机构建方法简单清晰,无需计算失败函数,自动机内每个状态在生成后只需访问一次即可完成自动机构建.实验表明Set DFA构建时间只有AAC自动机的一半左右.
Translation or Not:
no
