Hits:

Indexed by:期刊论文

Date of Publication:2013-12-15

Journal:计算机研究与发展

Included Journals:EI、PKU、ISTIC、CSCD、Scopus

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自动机的一半左右.