Wu-Manber算法的改进研究  

Research on the Improvement of Wu-Manber Algorithm

作　　者：王佳星[1] 陈华辉[1] 

机构地区：[1]宁波大学信息科学与工程学院,浙江宁波315211

出　　处：《移动通信》2017年第10期63-69,共7页Mobile Communications

基　　金：国家自然科学基金(61572266)

摘　　要：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.

关 键 词：多模式匹配 WU-MANBER算法 哈希表 二叉树 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]