Wu-Manber算法在大规模模式串下的改进

Improvement of Wu-Manber Matching Algorithm in Large Scale Patterns

对笔者在另一篇文章《一种改进的Wu-Manber多关键字匹配算法》中提出的算法进行了改进,把原算法中next链表中结点的Same-Subsuffix域中分裂成两个子域,使得搜索过程中字符比较的次数进一步减少,从而提高算法的效率.特别是在大规模模式串的情况下新算法的效率比原算法有进一步的提高.实验结果表明,当模式串较少时,新算法效率与原算法相比有一定的损失.而随着模式串的增加,新算法具有更高的效率.因此,新的算法比原算法具有更大的适用范围.

This paper produces a modified Wu - Manber multiple patterns matching algorithm, based on the idea of the Wu - Manber algorithm. The algorithm replaces the Same - subsuffix link used in with two links： Left - subsuffix and Right- subsuffix. So when it comes to comparing the characters in the Same-subsuffix link,what we need to do is compare them in one of the link we used about, and then reduces the amount of characters matching. The new algorithm works particularly well when the patterns number is large.