Wu—Manber算法的改进研究

王佳星　陈华辉

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

【关键词】多模式匹配 Wu-Manber算法 哈希表 二叉树

1 引言

从给定的输入文本T={t1， …， tn}中找出模式集合P={p1， …， pr}的模式在输入文本T中出现的所有位置，称为模式匹配问题[1]。模式匹配的应用非常广泛，包括搜索引擎、数据压缩、拼写检查、网络入侵检测等[2]。模式匹配算法可以分为单模式匹配和多模式匹配。模式匹配算法的类型包括基于字符比较的算法、基于自动机的算法和基于位并行的算法。经典的模式匹配算法有Boyer-Moore算法[3]、Wu-Manber算法[4]、KMP算法[5]、Aho-Corasick算法[6]、Shift-And算法[7]等。

其中Wu-Manber算法是一种基于字符比较的多模式匹配算法，它是单模式匹配算法Boyer-Moore算法在多模式匹配的扩展。在继承Boyer-Moore算法坏字符机制的基础上，将坏字符扩展为坏字符块[8]，在实验中性能良好，常用于解决网络入侵检测等问题[9]。

在研究Wu-Manber算法的基础上，本文提出两种改进的Wu-Manber算法：PrefixTreeWM算法和PrefixHashWM算法。改进算法使用改进的PrefixList表，将模式集合通过前缀哈希值和后缀哈希值进行分类，避免冗余操作。通过对前缀哈希值进行排序或者哈希，进一步降低算法的时间复杂度，减少匹配需要的时间。

2 模式匹配问题的一般解决方案

模式匹配问题的一般解决方案包括预处理模式和搜索模式。

预处理模式是将模式集合P中的所有模式进行预处理，并存储到特殊的数据结构中，方便后续的搜索。一般情况下定义最短模式长度m，将模式集合P中的所有模式都截断成长度为m的子串，构造模式集合P'。在预处理时只处理其长度为m的子串。比如长度为l的模式串pi={c1， …， cl}，l>m。首先令pi'={c1， …， cm}，然后对pi'进行预处理。

搜索模式是搜索输入文本T中是否存在模式集合P中的任意模式pi，i=1，…，r，假如模式pi'出现在输入文本T中的某一个位置j，则返回j。具体方法是维护一个窗口，窗口的大小与模式集合P中的最短模式长度m相等，首先检查当前窗口的字符串是否可能与模式集合P'中的某个模式pi'匹配。如果有可能匹配，则将原始模式pi={c1， …， cl}与当前窗口对应的长度为l的字符串进行匹配。

（1）Wu-Manber算法的预处理模式过程需要构建三张表，分别是shift表、hash表和prefix表。shift表是一张跳转表，用于记录指针向右滑动的距离。hash和prefix表是对模式串的后缀及前缀分别做的索引。

构建shift表时，处理模式集合P'中所有的模式串，统计他们长度为B的子串（B=2或者B=3），计算子串的shift值，存入shift[h]中，h是子串的哈希值。shift值的定义是字符末位到模式串pi'末位的距离，初始化的shift值大小为m-B+1。如果某一个子串出现在多个模式串的不同位置，具有不同的shift值，取最小的shift值。

比如模式集合P={p1=abcde， p2=bcbde， p3=adcabe}，最短模式长度m=5，当B的取值为2时，每一个模式的shift值如表1、表2、表3所示，合并后的shift表如表4所示。

prefix表是为所有后缀哈希值为h的模式串构建的一个链表list。它的结构是<前缀哈希值，模式索引>。hash表的索引值与shift表相同，当某一个子串的后缀哈希值为h时，hash[h]中存储的是指向链表list的指针。如图1所示，模式集合P={…，money，…，honey，…，moley，…，holey，…}。图1中显示出的四个模式串它们的共同后缀为ey，hash[ey]=5309。根据hash表的定义，将指针p存入hash[5309]，并使p指向第一个后缀哈希值为5309的模式串的索引114，计算模式串114的前缀哈希值hash[mo]=6323，存储在prefix表中，此节点的指针指向第二个后缀哈希值为5309的模式串287。

（2）Wu-Manber算法的搜索模式时，窗口首先置于输入文本T的开始位置0。对当前窗口对应的m个字符，从右向左读入长度为B的字符块，计算字符块的哈希值h。当shift[h]>0时，将窗口向右移动shift[h]位；当shift[h]=0时，定位到hash[h]的指针，取出与当前窗口字符串后缀哈希相同的模式串链表list，list中包含的所有模式串称为潜在候选模式串。对list进行遍历，首先比較前缀哈希值是否与当前窗口相同，如果不同，则继续比较下一个模式串。如果相同，该模式串称为候选模式串，将它与当前窗口对应的字符串进行完全匹配。如果完全匹配，则输出一个匹配，并将当前窗口向右移动一位；否则，继续比较下一个模式。

3 Wu-Manber算法分析

Wu-Manber算法的跳跃机制使得部分字符不需要匹配，在实际应用中具有较高的效率。hash表大小与shift表大小相同。在hash表中，存有指向具有相同后缀哈希的模式串组成的prefix表的指针，prefix表中的信息不仅包含模式串的编号，也包含该模式串的前缀哈希。

问题在于当模式集合的规模较大时，具有相同后缀的模式串数量也非常大。Wu-Manber算法在搜索过程中取出所有具有相同后缀的模式串一一进行比较，虽然首先比较前缀哈希值，这在一定程度上能提高算法效率，但是仍然存在冗余的比较操作。

Wu-Manber算法搜索模式时，首先通過后缀哈希值判断当前窗口字符串是否为潜在候选模式串，然后通过前缀哈希值判断当前窗口字符串是否为候选模式串。随着模式集合规模的增大，潜在候选模式串的数量急剧增长，在搜索时产生大量的冗余操作，即需要不停地判断当前窗口字符串的前缀哈希值是否与模式串链表list当中的潜在候选模式串的前缀哈希值相同。当搜索文本大小为10 MB时，从表5可以看出，当模式集合规模增大时，潜在候选模式串的数量急剧增长。当模式集规模为50 000时，从表6可以看出，随着搜索文本的增大，潜在候选模式串的数量不断增大。

如果改变Wu-Manber算法当中的prefix表结构，在搜索时，能够快速定位到与当前窗口字符串后缀哈希值和前缀哈希值均相同的模式串链表，那么算法的效率就能够提高很多。

4 Wu-Manber算法的改进算法

针对算法中的prefix表，本文提出Wu-Manber算法的改进算法。基本思想是在搜索过程中，不需要对具有相同后缀值的所有模式串进行前缀哈希比较，而是直接取出具有相同后缀哈希值和相同前缀哈希值的所有模式串直接进行匹配操作，并且通过对前缀哈希值进行再哈希或者排序的方式进一步加快比较速度。

4.1 改进算法的存储结构

在Wu-Manber算法中，prefix表是一个链表，存储的数据结构为<前缀哈希值prefixHash，模式串索引号index>。在改进算法中，定义prefixList表存储的数据结构为<前缀哈希值prefixHash，模式串索引号链表index list>。

prefixList表将具有相同前缀哈希值的模式串集合到一起，在搜索模式时不需要比较前缀哈希值，可以直接取出指定模式串链表进行字符匹配的操作。

4.2 PrefixTreeWM算法

PrefixTreeWM算法使用改进的prefixList表，并将<前缀哈希值prefixHash，模式串索引号链表index list>中的prefixHash作为二叉树的key，通过对前缀哈希值prefixHash进行排序，能够快速定位到指定的index list。如图2所示，模式集合P={…，money，…， honey，…，moley，…，holey，…，Goley，…}。图2中显示出的五个模式串它们的共同后缀为ey，hash[ey]=5309。PrefixTreeWM算法在hash表中存入由前缀哈希值作为key构建的二叉树，二叉树节点存储的内容就是改进的prefixList表。设前缀prefixB=2，图2中的五个模式具有三个不同的前缀，分别是Go、ho、mo，对应的哈希值分别是hash[Go]=2227，hash[ho]=5683，hash[mo]=6323。

预处理模式串pi'时，首先计算pi'的后缀哈希值suffixHash和前缀哈希值prefixHash，取出hash[suffixHash]中的二叉树，判断当前二叉树是否含有key为prefixHash的节点，如果没有，则插入一个新的key为prefixHash的节点，在index list中存入模式串的索引；如果有，那么搜索到对应的节点，在它的index list中加入模式串pi'的索引。搜索模式时，窗口置于输入文本T的开始位置0。取出当前窗口对应的m个字符，计算其前缀哈希值prefixHash和后缀哈希值suffixHash，当shift[suffixHash]>0时，将窗口向右移动shift[suffixHash]位；当shift[suffixHash]=0时，读取hash[suffixHash]中存储的二叉树，搜索到key为prefixHash的节点，取出其中的index list。index list中包含的所有模式串称为潜在候选模式串。其余搜索步骤与Wu-Manber算法相同。

4.3 PrefixHashWM算法

为处理大规模模式集，本文提出PrefixHashWM算法，使用哈希表，能够在O（1）时间内查找到指定的前缀哈希值。

PrefixHashWM算法就是使用二维哈希表，使用prefixHashTable代替PrefixTreeWM算法中的二叉树。哈希表的大小Tablesize由字母表的大小size和B决定。Tablesize=size^B。

虽然PrefixHashWM算法空间复杂度比较高，但是它的时间复杂度大大降低。如图3所示，模式集合P={…，money，…，honey，…，moley，…，holey，…，Goley，…}。通过后缀哈希值hash[ey]=5309映射到前缀哈希表prefixHashTable5309后，对每个模式串计算前缀哈希值，并将索引号存入对应的哈希桶中，前缀哈希表中的list存储的是具有相同前缀哈希和相同后缀哈希的模式串索引列表。

PrefixHashWM算法在预处理模式和搜索模式时都会更加高效。预处理模式时，它不需要判断当前字符串的前缀哈希值是否已经存在，也就不需要去遍历已经处理过的前缀哈希值。搜索模式时，哈希表的时间复杂度是O（1），能够迅速找到指定的list，直接进行字符串匹配操作。

5 实验分析

为评价改进算法的性能，本文对Wu-Manber算法、PrefixTreeWM算法和PrefixHashWM算法进行实验对比。实验分析三种算法匹配过程的时间消耗，实验平台为CPU 2.7 GHz Intel Core i5，内存8 GB，操作系统OS X。

（1）实验一中采用的文本数据是大小为10 MB的文档，模式串为随机生成的字符串，最短模式长度为6，设B=3，前缀prefixB=2。实验结果如图4和图5所示。图4中的模式集大小从20 000到30 000，跨度为1000。当搜索文本较小且模式集规模较小时，三种算法时间消耗情况为Wu-Manber>PrefixHashWM>PrefixTreeWM。PrefixTreeWM算法在这种情况下，性能最优。

设N为二叉树中存储的节点个数，由于PrefixTreeWM算法对模式串集合通过后缀哈希值和前缀哈希值共同进行分类，使N不会随着数据的增大而过分增大，这使得二叉树查找指定索引列表的速度由于N的限制得到保证，即使是最坏情况O（N）也可以接受。和Wu-Manber算法相比较，PrefixHashWM算法和PrefixTreeWM算法搜索模式时的时间消耗大大减少。

图5中的模式集大小从100 000到300 000，跨度为10 000。当搜索文本较小时但模式集规模较大时，三种

算法的时间消耗情况为Wu-Manber>PrefixTreeWM>

PrefixHashWM。PrefixHashWM算法在这种情况下性能最优。当模式集规模增大时，PrefixTreeWM算法中二叉树中的节点数量增多，时间复杂度变大，超过PrefixHashWM算法的复杂度。PrefixHashWM算法中的二维哈希表在任何时刻的查找时间复杂度均为O（1）。当模式集规模增大时，宜使用PrefixHashWM算法。

（2）实验二采用的文本数据是大小为50 MB的文档，模式串为随机生成的字符串，最短模式长度为6，设B=3，前缀prefixB=2。实验结果如图6和图7所示。图6中的模式集大小从20 000到30 000，跨度为1 000。图7中的模式集大小从100 000到300 000，跨度为10 000。

当搜索文本增大时，潜在候选字符串也随着增加，这使得PrefixTreeWM算法中的二叉树的查找次数不断增加，导致PrefixTreeWM算法的时间复杂度上升，所以PrefixHashWM算法中哈希表的优势得到体现。

图6和图7说明当数据量大时，PrefixHash-WM算法的性能最优。改进的两种算法的时间复杂度受哈希桶中模式串数量的影响，如果某种具有相同后缀哈希值和前缀哈希值的模式串特别多，那么改进算法的时间消耗也会变大。当模式集规模更大时，由于实验采用的是随机数据集，分配到每个哈希桶的模式串数量基本一致。图7说明随着模式集规模的增长，Wu-Manber算法时间消耗明显增长，而PrefixTreeWM算法和PrefixHashWM算法的时间消耗增长并不明显。

（3）实验三采用的文本数据是大小为50 MB的文档，模式串为随机生成的字符串，最短模式长度为10，设B=3，前缀prefixB=2。实验结果如图8所示，图8中的模式集大小从100 000到200 000，跨度为10 000。

（4）实验四将以上三种算法应用到入侵检测系统Snort中。Snort是一套开源代码的网络入侵预防软件与网络入侵检测软件，规则库定期发布[10]。使用Snort-2.9.9.0版本，将三种算法添加入源代码，Snort.conf文件中加载的规则数为10 212。表7记录的是三种算法在不同packet数的情况下检测消耗的时间。第一行检测的数据是使用Snort数据包记录器得到的数据，记录数据的命令为snort-dev-l log/-i en0。第二行检测的数据是DARPA 1999 Inside Dataset W5D1的inside.tcpdump文件[11]。

从表7中的数据可以看到，PrefixTreeWM算法在两个不同的检测数据上速度分别比Wu-Manber算法提高了53.79%和13.32%；PrefixHashWM算法在两个不同的检测数据上速度分别比Wu-Manber算法提高36.39%和13.65%。实验结果与实验一、实验二、实验三相同，当数据量较小时，PrefixTreeWM算法匹配速度更快；当数据量较大时，PrefixHashWM算法匹配速度更快。

根据上面两种不同类型的实验结果，可以看到改进算法在实际应用中的优势。无论在随机数据实验还是在实际入侵检测系统中，PrefixTreeWM算法和PrefixHashWM算法在时间上的效率都高于Wu-Manber算法。

6 结束语

本文研究并测试Wu-Manber算法并提出两种改进算法：PrefixTreeWM算法和PrefixHashWM算法。改进算法使用改进的prefixList表，在使用后缀哈希值进行分类的基础上，使用前缀哈希值将模式串集合进行再一次分类，避免Wu-Manber算法中的冗余操作。对前缀哈希值分别采用二叉树和哈希表的方式进行排序，加快查找速度，提高算法效率。本文对三种算法使用随机数据集和网络数据检测分别进行实验。实验结果表明当数据量不大时，PrefixTreeWM算法性能更高；当数据量增大时，使用PrefixHashWM算法效率更高。PrefixHashWM算法的高效是以大量的哈希表空间消耗为代价的，下一步的工作将致力于减少算法的空间复杂度。

参考文献：

[1] 张宏莉，徐东亮，梁敏，等. 海量模式高效匹配方法研究[J]. 电子学报， 2014，42（6）： 1220-1224.

[2] 张兴彪. 海量多模式串匹配算法關键技术研究[D]. 哈尔滨： 哈尔滨工程大学， 2013.

[3] Boyer R S， Moore J S. A fast string searching algorithm [J]. Communications of the ACM， 1977，20（10）： 762-772.

[4] Wu S， Manber U. A fast algorithm for multi?pattern searching[R]. Tuscon： University of Arizona， 1994： 1-11.

[5] Knuth D E， Jr J H M， Pratt V R. Fast Pattern Matching in Strings[J]. SIAM Journal on Computing， 1977，6（2）： 323-350.

[6] Aho A V， Corasick M J. Efficient string matching： an aid to bibliographic search[J]. Communications of the ACM， 1975，18（6）： 333-340.

[7] Prasad R， Agarwal S. Multi-patterns parameterized shift and string matching algorithm with super alphabets[C]//International Conference on Advances in Computing， Communication and Control. ACM， 2009： 8-13.

[8] Raffinot， Mathieu. Flexible pattern matching in strings [M]. Cambridge University Press， 2002.

[9] 董迎亮. 基于改进WM算法的网络入侵检测系统的研究与实现[D]. 长春： 吉林大学， 2011.

[10] 熊刚，何慧敏，于静，等. HybridFA：一种基于统计的AC自动机空间优化技术[J]. 通信学报， 2015，36（7）： 31-39.

[11] MIT Lincoln Laboratory. DARPA Intrusion Detection Evaluation Data Set[EB/OL]. [2017-04-20]. http：//www.ll.mit.ed-u/ideval/data/1999data.html.