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

Improved multi-pattern matching algorithm

针对WM算法在模式集规模大且最短模式长度小的情况下性能较低的问题,分析了WM算法及其改进的快速WM（QWM）算法的优缺点,在此基础上提出了模式分集思想,并优化了跳跃和确认机制,设计了子集WM（SWM）算法;然后针对该算法在域名过滤中的应用,对hash函数、匹配顺序等进行进一步优化.针对域名过滤的实验结果表明,当模式数量超过10 000条时,SWM算法匹配时间是WM算法的8.9%-11.6%,说明SWM算法在模式集规模较大时,匹配速度能显著提高.

To resolve the problem that when the number of rules is large and the length of the shortest rule is short,the performance of the WM algorithm will become less efficient,the paper analyzes the WM algorithm and an improved algorithm named the QWM algorithm,then proposes a new algorithm—the SWM algorithm.The new algorithm uses the idea of the sub pattern set and optimizes the shifting and affirming method.To use the SWM algorithm in domain name filtering,a new hash function and a new matching order are designed specially. The results in domain name filtering indicate that the SWM algorithm’s matching time is about 8.9%~1 1.6%that of the WM algorithm when the number of patterns is more than 10 000.The SWM algorithm can improve the speed of matching when the scale of the pattern is large.