两级哈希表存储模式的高效多模式匹配算法北大核心CSCD |
| |
引用本文: | 殷荣网邵安贤庞京玉.两级哈希表存储模式的高效多模式匹配算法北大核心CSCD[J].控制工程,2016(3):394-399. |
| |
作者姓名: | 殷荣网邵安贤庞京玉 |
| |
作者单位: | 1.合肥学院基础教学与实验中心230601; |
| |
摘 要: | 为了弥补多字符串模式匹配效率低下的缺陷,给出了一种基于双哈希表的多模式匹配算法。这个算法通过两个相关联的哈希表对模式串进行存储,同时采用一个转移表将发生失配时的跳跃距离存储。处于匹配阶段时:如果模式串无公共前缀,那么仅仅于第一个哈希表中进行查找;如果模式串有公共前缀,那么就在两个哈希表中顺序查找。经分析发现,此算法在最短模式串长度很长的环境中尤为适用,相对于经典算法,其时间复杂度较低,且其尝试次数也比较少。最后经实验可以证明,该算法具备较好的时空性能。
|
关 键 词: | 哈希表 模式串 多模式匹配算法 时空性能 |
本文献已被 维普 等数据库收录! |
|