一种改进的W-M多模式匹配算法  

An improved W-M algorithm for multi-pattern match

作　　者：蒋辉[1] 张宇弘[1] 

机构地区：[1]浙江大学超大规模集成电路设计研究所,浙江杭州310027

出　　处：《机电工程》2008年第9期25-27,共3页Journal of Mechanical & Electrical Engineering

摘　　要：Wu-Manber算法是一种基于后缀搜索的多模式匹配算法,该算法采用查表的方法,通过跳跃不可能匹配的字符来加速匹配,W-M算法对最短模式长度敏感,最短模式长度决定了它可以跳过的字符的最大距离。针对W-M算法的不足之处,提出了一个改进方法:新增了一个模式串末字符表,取得了比原算法更少的hash计算次数和更大的字符跳跃距离,从而加快了整个匹配过程的速度。最后,进行了设定模式串的最短长度和搜索文本长度的对比实验。实验结果显示,改进后的算法搜索效率明显高于原算法,特别是在模式串长度很短的情况下,效率提高非常明显。Wu-Manber algorithm is one of the muhi-pattern 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. W-M algorithm is sensitive to minimum length of pattern which determines the maximum number of eharacters that ean be ignored. Aimed at the shortage of W-M algorithm the improvement was proposed. A new table of last eharaeter of each pattern was added, the times of hash calculation were reduced, more eharaeters 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 mueh better than original algorithm, especially when there are very short patterns.

关 键 词：W—M算法 多模式匹配 哈希函数 后缀 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]