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

Abstract: With the rapid development of network technology, the number of pattern, used in multi-pattern matching algorithms, have experienced explosive growth in recent years, and the length of pattern is not uniform. Traditional multi-pattern matching algorithm cannot meet the newest pattern sets: the characteristic of pattern set plays largely influences on the performance of algorithms. A novel algorithm enhanced from the Wu-Manber（WM） algorithm, namely the Modified Wu-Manber（MWM） algorithm, is responsible for pattern set which has variant length of pattern and uneven distribution. The new algorithm partitions the pattern set into long and short subset and constructs respective SHIFT table in order to help the original SHIFT built in WM to verify whether exists pattern matching more deeply under a single thread program. In fact, the new algorithm not only reduces the verification frequency but also increases the average shift distance. Experiments show that the improved multi-pattern algorithm has better performance to deal with the non-uniform distribution and variant length of pattern set, in addition, the larger the pattern set, the better improved performance with new algorithm. Especially, when the number of pattern is 100 000, it improves performance by more than 40 percent.

Key words: pattern matching, string matching, Wu-Manber algorithm