Wu-Manber算法的改进研究

Research on the Improvement of Wu-Manber Algorithm

Wu-Manber算法是一种经典的多模式字符串匹配算法,常用于解决网络入侵检测等问题。为了解决Wu-Manber算法在模式集规模增长时,prefix表中会出现过长的模式链表这一问题,通过改变原有prefix表中的链表结构以及存储信息的格式,提出两种改进算法,分别用于处理较小的模式集合和较大的模式集合。实验证实了改进算法可以提高字符串匹配速度,具有很高的实用价值。

Wu-Manber algorithm is a classic multi-pattern string matching algorithm, commonly used to solve the problem of network intrusion detection. The shortcoming of the Wu-Manber algorithm is that when the scale of pattern set grows, the too long pattern list appears in the prefix table. To solve this problem, two improved algorithms were proposed to deal with the smaller and the larger pattern sets by changing the linked list structure in the original prefix table and the format of the stored information. Experiments show that the improved algorithms can improve the speed of string matching and have a high practical value.