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

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