关键词: 模式匹配, 字符串匹配, WM算法, SWM算法, 域名过滤

Abstract:

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％～11.6％ that of the WM algorithm when the number of patterns is more than 10000. The SWM algorithm can improve the speed of matching when the scale of the pattern is large.

Key words: pattern matching, string matching, Wu-Manber algorithm, subest Wu-Manber algorithm, domain name filtering