一种改进的WM多模式匹配算法

作者：蒋辉，张宇弘 日期：2008-11-03/span> 浏览：3276 查看PDF文档

一种改进的WM多模式匹配算法

蒋辉，张宇弘
（浙江大学 超大规模集成电路设计研究所,浙江 杭州 310027）

摘要：WuManber算法是一种基于后缀搜索的多模式匹配算法，该算法采用查表的方法,通过跳跃不可能匹配的字符来加速匹配，WM算法对最短模式长度敏感，最短模式长度决定了它可以跳过的字符的最大距离。针对WM算法的不足之处，提出了一个改进方法：新增了一个模式串末字符表，取得了比原算法更少的hash计算次数和更大的字符跳跃距离，从而加快了整个匹配过程的速度。最后，进行了设定模式串的最短长度和搜索文本长度的对比实验。实验结果显示，改进后的算法搜索效率明显高于原算法，特别是在模式串长度很短的情况下，效率提高非常明显。
关键词：WM算法;多模式匹配;哈希函数;后缀
中图分类号：TP301文献标识码：A文章编号：1001-4551(2008)09-0025-03

An improved WM algorithm for multipattern match
JIANG Hui, ZHANG Yu-hong
（Institute of VLSI design, Zhejiang University, Hangzhou 310027, China）
Abstract: WuManber algorithm is one of the multipattern match algorithm based on the suffix searching. The algorithm speeds up matching by looking up tables to ignore certain characters that   will not be matched. WM algorithm is sensitive to minimum length of pattern which determines the maximum number of characters that can be ignored. Aimed at the shortage of WM algorithm the improvement was proposed. A new table of last character of each pattern was added, the times of hash calculation were reduced, more characters were ignored and the matching process was speeded up. In the contrast experiments that setting the minimum length of pattern and the length of text, the efficiency of improved algorithm is much better than original algorithm, especially when there are very short patterns.
Key words: WuManber(WM) algorithm;  multipattern match;  hash function;  suffix
参考文献(Reference):
［1］AHO A V, CORASICK M J. Efficient string matching: an aid to bibliographic search［J］. Communications of the ACM,1975,18(6):333-340.
［2］WU S, MANBER U. A fast algorithm for multipattern searching［R］. University of Arizona, Tucson,1994.
［3］BOYER R S, MOORE J S. A fast string searching algorithm［J］. Communications of the ACM,1977,20(10):762-772.
［4］陈瑜，陈国龙.WuManber算法性能分析及其改进［J］.计算机科学,2006，33(6):203-209.
［5］杨东红，徐恪.改进的WuManber多模式匹配算法［J］.清华大学学报:自然科学版,2006,46(4):555-558.
［6］孙晓山，王强.一种改进的WuManber多模式匹配算法以应用［J］.中文信息学报,2006,20(2)：47-52.
［7］袁世忠，曹F.基于WM算法的多模式匹配改进算法WMN［J］.计算机工程与应用,2007,43(15):128-130.
［8］马伟华，刘玉梅.一种改进的WuManber多模式串匹配算法［J］.应用科技,2007,34(10):32-34.