THT-MSMA:基于双哈希表的高效多模式匹配算法  

THT-MSMA: efficient multi-string matching algorithm based on double hashing table

作　　者：魏利峰[1,2] 纪建伟[1] 王颖[1] 王晓斌[2] 

机构地区：[1]沈阳农业大学信息与电气工程学院,沈阳110866 [2]沈阳航空航天大学经济与管理学院,沈阳110136

出　　处：《计算机应用研究》2016年第2期431-434,共4页Application Research of Computers

基　　金：国家自然科学基金青年项目(71301108);辽宁省教学科学"十二五"规划课题(JG13DB093)

摘　　要：针对已有模式匹配技术的不足进行研究,提出了THT-MSMA多模式匹配算法,该算法采用双哈希表来减少尝试比较的次数。当模式串没有公共前缀,则只需在第一个哈希表中查找;若模式串有公共前缀,则需要在两个哈希表中依次进行查找。分析表明,该算法适合于最短模式串长度很长的环境,时间复杂度要低于经典的算法,尝试比较次数少于传统的多模式匹配算法。实验结果表明,THT-MSMA算法具有良好的时空性能。Research was conducted on shortcoming of existing pattern matching techniques, this paper presented a new solu- tion called THT-MSMA by using two-hashing tables to minimize attempting times. The matching method hashed one time or twice in the first hashing table if there was no pattern overlapping or twice in＇ both hashing tables if there was only one or more pattern overlapping. Analysis shows that this solution is suitable for very long length of shortest pattern string. Its time com- plexity is more efficient than classic algorithms and its attempting times are less than traditional algorithms. At last, the experi- mental results prove that THT-MSMA has good time and space performance.

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

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