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

Efficient Multi-pattern Matching Algorithm Based on Two Level Hash Table Storage Mode

作　　者：殷荣网[1] 邵安贤[1] 庞京玉[1] 

机构地区：[1]合肥学院基础教学与实验中心,合肥230601

出　　处：《控制工程》2016年第3期394-399,共6页Control Engineering of China

摘　　要：为了弥补多字符串模式匹配效率低下的缺陷,给出了一种基于双哈希表的多模式匹配算法。这个算法通过两个相关联的哈希表对模式串进行存储,同时采用一个转移表将发生失配时的跳跃距离存储。处于匹配阶段时:如果模式串无公共前缀,那么仅仅于第一个哈希表中进行查找;如果模式串有公共前缀,那么就在两个哈希表中顺序查找。经分析发现,此算法在最短模式串长度很长的环境中尤为适用,相对于经典算法,其时间复杂度较低,且其尝试次数也比较少。最后经实验可以证明,该算法具备较好的时空性能。To compensate the defect of inefficient matching in multi-string pattern, this paper proposes a Two-hashing Table Multi-string Matching Algorithm. The algorithm processes the storage of pattern string through two associated hash tables, and uses one transfer table to deal with the storage of the the jump distance with a time of loss occurrence. In the matching stage, if pattern string has no public string prefix, if only needs to find in the first hash table; if pattern string has common prefix, it needs to take sequential searching to find in the two hash tables. Analysis results show that this solution is more suitable for very long length of shortest pattern string environment, and this solution's time complexity is lower than classic algorithms, and its attempting time is less than traditional algorithms. At last, the experimental results prove the proposed algorithm has better time and space performance.

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

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]