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

Wu-Manber算法是一种基于后缀搜索的多模式匹配算法,该算法采用查表的方法,通过跳跃不可能匹配的字符来加速匹配,W-M算法对最短模式长度敏感,最短模式长度决定了它可以跳过的字符的最大距离。针对W-M算法的不足之处,提出了一个改进方法:新增了一个模式串末字符表,取得了比原算法更少的hash计算次数和更大的字符跳跃距离,从而加快了整个匹配过程的速度。最后,进行了设定模式串的最短长度和搜索文本长度的对比实验。实验结果显示,改进后的算法搜索效率明显高于原算法,特别是在模式串长度很短的情况下,效率提高非常明显。