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

摘　要 多字符串模式匹配是在给定的文本中并行查找多个模式串的一种方法。本文中提出THT-MSMA多模式匹配算法，该算法采用双哈希表来减少尝试比较的次数。分析表明，该算法适合于最短模式串长度很长的环境，时间复杂度要低于经典的算法，尝试比较次数少于传统的多模式匹配算法。最后，实验结果表明，THT-MSMA算法具有良好的时空性能。

THT-MSMA : EFFICIENT MULTI- PATTERN MATCHING ALGORITHM BASED ON DOUBLE HASHING TABLE

Abstract Multi-string pattern matching is one of many approaches to simultaneously search occurrences of a large number of patterns in a given text. Research is conducted on shortcoming of existing pattern matching techniques, and a new solution called THT-MSMA is presented by using two-hashing tables to minimize attempting times. The matching method hashes one time or twice in the first hashing table if there is no pattern overlapping or twice in both hashing tables if there is only one or more pattern overlapping. Analysis shows that this solution is suitable for very long length of shortest pattern string. Its time complexity is more efficient than classic algorithms and its attempting times are less than traditional algorithms. At last, the experimental results prove that THT-MSMA has good time and space performance.