短规则有效的快速多模式匹配算法

来源：计算机工程与应用杂志2017年第7期北京时间：

作者：夏 念，嵩 天

单位：北京理工大学 计算机学院，北京 100081

摘要：随着网络技术快速发展，多模式匹配算法所处理的模式集合数目呈爆炸式增长且模式长度不统一，传统的多模式匹配算法已无法有效适应新的模式集合：不同的模式集合，同一算法呈现的性能差异明显。针对模式长度不等且分布不均匀的模式集合，提出一种改进WM的多模式匹配算法（MWM），将模式集合分为长短两个集合并构造各自的长短SHIFT表，辅助WM算法原有SHIFT表验证匹配效果，匹配过程由单一线程完成。该算法不仅减少了模式验证次数，而且提高了算法的平均跳转距离。实验结果表明，所提出的多模式匹配算法（MWM）在模式长度不等且分布不均匀的模式集合下表现出更优的性能，随着模式集合的数目增多，性能提升越明显。在模式集合数目达到100 000时，相比WM算法，该算法性能提升达到了40%。

关键词：模式匹配,字符串匹配,Wu-Manber算法