两级哈希表存储模式的高效多模式匹配算法

来源期刊：控制工程2016年第3期

论文作者：殷荣网 邵安贤 庞京玉

文章页码：394 - 399

关键词：哈希表;模式串;多模式匹配算法;时空性能;

摘    要：为了弥补多字符串模式匹配效率低下的缺陷,给出了一种基于双哈希表的多模式匹配算法。这个算法通过两个相关联的哈希表对模式串进行存储,同时采用一个转移表将发生失配时的跳跃距离存储。处于匹配阶段时:如果模式串无公共前缀,那么仅仅于第一个哈希表中进行查找;如果模式串有公共前缀,那么就在两个哈希表中顺序查找。经分析发现,此算法在最短模式串长度很长的环境中尤为适用,相对于经典算法,其时间复杂度较低,且其尝试次数也比较少。最后经实验可以证明,该算法具备较好的时空性能。