一种改进的AC多模式匹配算法

• 作者: 刘春晖 宋琦 黄宇
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 多模式匹配 AC算法 漏检 移动距离 模式树
• 年，卷（期）: 2015,（10）
• 所属期刊栏目: 开发研究与工程应用
• 页码范围: 280-285
• 页数: 6页
• 分类号: TP301.6
• 字数: 5129字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2015.10.053

摘要

在分析AC算法及其相关算法的基础上,提出一种改进的多模式匹配算法AC _TE.利用该算法构建1个字符串跳跃表和2个哈希表,字符串表存储模式树中两两相邻字符组成的字符串及其位置,2个哈希表分别存储模式树末层字符串和字符.采用多层跳跃规则依次查找这3个表,在不发生漏检的情况下,使模式树的最大移动距离为最短模式串长度加3.从模式树移动次数、匹配阶段时间、各种跳跃距离的概率3个方面测试算法性能.实验结果表明,与AC算法相比,AC_TE算法具有更大的模式树移动距离,消耗的时间更少.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄宇	合肥工业大学计算机与信息学院	5	15	2.0	3.0
2	宋琦	合肥工业大学计算机与信息学院	3	11	1.0	3.0
3	刘春晖	合肥工业大学计算机与信息学院	3	10	1.0	3.0