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

摘要：

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

关键词：多模式匹配、AC算法、漏检、移动距离、模式树

所属期刊栏目：41

分类号：TP301.6(计算技术、计算机技术)

资助基金：教育部广东省产学研基金资助项目2009B090200049;安徽省自然科学基金资助项目11040606M138

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

页数：共6页

页码：280-285