Wu—Manber算法的改進(jìn)研究

王佳星　陳華輝

【摘 要】Wu-Manber算法是一種經(jīng)典的多模式字符串匹配算法，常用于解決網(wǎng)絡(luò)入侵檢測(cè)等問題。為了解決Wu-Manber算法在模式集規(guī)模增長(zhǎng)時(shí)，prefix表中會(huì)出現(xiàn)過長(zhǎng)的模式鏈表這一問題，通過改變?cè)衟refix表中的鏈表結(jié)構(gòu)以及存儲(chǔ)信息的格式，提出兩種改進(jìn)算法，分別用于處理較小的模式集合和較大的模式集合。實(shí)驗(yàn)證實(shí)了改進(jìn)算法可以提高字符串匹配速度，具有很高的實(shí)用價(jià)值。

【關(guān)鍵詞】多模式匹配 Wu-Manber算法 哈希表 二叉樹

1 引言

從給定的輸入文本T={t1， …， tn}中找出模式集合P={p1， …， pr}的模式在輸入文本T中出現(xiàn)的所有位置，稱為模式匹配問題[1]。模式匹配的應(yīng)用非常廣泛，包括搜索引擎、數(shù)據(jù)壓縮、拼寫檢查、網(wǎng)絡(luò)入侵檢測(cè)等[2]。模式匹配算法可以分為單模式匹配和多模式匹配。模式匹配算法的類型包括基于字符比較的算法、基于自動(dòng)機(jī)的算法和基于位并行的算法。經(jīng)典的模式匹配算法有Boyer-Moore算法[3]、Wu-Manber算法[4]、KMP算法[5]、Aho-Corasick算法[6]、Shift-And算法[7]等。

其中Wu-Manber算法是一種基于字符比較的多模式匹配算法，它是單模式匹配算法Boyer-Moore算法在多模式匹配的擴(kuò)展。在繼承Boyer-Moore算法壞字符機(jī)制的基礎(chǔ)上，將壞字符擴(kuò)展為壞字符塊[8]，在實(shí)驗(yàn)中性能良好，常用于解決網(wǎng)絡(luò)入侵檢測(cè)等問題[9]。

在研究Wu-Manber算法的基礎(chǔ)上，本文提出兩種改進(jìn)的Wu-Manber算法：PrefixTreeWM算法和PrefixHashWM算法。改進(jìn)算法使用改進(jìn)的PrefixList表，將模式集合通過前綴哈希值和后綴哈希值進(jìn)行分類，避免冗余操作。通過對(duì)前綴哈希值進(jìn)行排序或者哈希，進(jìn)一步降低算法的時(shí)間復(fù)雜度，減少匹配需要的時(shí)間。

2 模式匹配問題的一般解決方案

模式匹配問題的一般解決方案包括預(yù)處理模式和搜索模式。

預(yù)處理模式是將模式集合P中的所有模式進(jìn)行預(yù)處理，并存儲(chǔ)到特殊的數(shù)據(jù)結(jié)構(gòu)中，方便后續(xù)的搜索。一般情況下定義最短模式長(zhǎng)度m，將模式集合P中的所有模式都截?cái)喑砷L(zhǎng)度為m的子串，構(gòu)造模式集合P'。在預(yù)處理時(shí)只處理其長(zhǎng)度為m的子串。比如長(zhǎng)度為l的模式串pi={c1， …， cl}，l>m。首先令pi'={c1， …， cm}，然后對(duì)pi'進(jìn)行預(yù)處理。

搜索模式是搜索輸入文本T中是否存在模式集合P中的任意模式pi，i=1，…，r，假如模式pi'出現(xiàn)在輸入文本T中的某一個(gè)位置j，則返回j。具體方法是維護(hù)一個(gè)窗口，窗口的大小與模式集合P中的最短模式長(zhǎng)度m相等，首先檢查當(dāng)前窗口的字符串是否可能與模式集合P'中的某個(gè)模式pi'匹配。如果有可能匹配，則將原始模式pi={c1， …， cl}與當(dāng)前窗口對(duì)應(yīng)的長(zhǎng)度為l的字符串進(jìn)行匹配。

（1）Wu-Manber算法的預(yù)處理模式過程需要構(gòu)建三張表，分別是shift表、hash表和prefix表。shift表是一張?zhí)D(zhuǎn)表，用于記錄指針向右滑動(dòng)的距離。hash和prefix表是對(duì)模式串的后綴及前綴分別做的索引。

構(gòu)建shift表時(shí)，處理模式集合P'中所有的模式串，統(tǒng)計(jì)他們長(zhǎng)度為B的子串（B=2或者B=3），計(jì)算子串的shift值，存入shift[h]中，h是子串的哈希值。shift值的定義是字符末位到模式串pi'末位的距離，初始化的shift值大小為m-B+1。如果某一個(gè)子串出現(xiàn)在多個(gè)模式串的不同位置，具有不同的shift值，取最小的shift值。

比如模式集合P={p1=abcde， p2=bcbde， p3=adcabe}，最短模式長(zhǎng)度m=5，當(dāng)B的取值為2時(shí)，每一個(gè)模式的shift值如表1、表2、表3所示，合并后的shift表如表4所示。

prefix表是為所有后綴哈希值為h的模式串構(gòu)建的一個(gè)鏈表list。它的結(jié)構(gòu)是<前綴哈希值，模式索引>。hash表的索引值與shift表相同，當(dāng)某一個(gè)子串的后綴哈希值為h時(shí)，hash[h]中存儲(chǔ)的是指向鏈表list的指針。如圖1所示，模式集合P={…，money，…，honey，…，moley，…，holey，…}。圖1中顯示出的四個(gè)模式串它們的共同后綴為ey，hash[ey]=5309。根據(jù)hash表的定義，將指針p存入hash[5309]，并使p指向第一個(gè)后綴哈希值為5309的模式串的索引114，計(jì)算模式串114的前綴哈希值hash[mo]=6323，存儲(chǔ)在prefix表中，此節(jié)點(diǎn)的指針指向第二個(gè)后綴哈希值為5309的模式串287。

（2）Wu-Manber算法的搜索模式時(shí)，窗口首先置于輸入文本T的開始位置0。對(duì)當(dāng)前窗口對(duì)應(yīng)的m個(gè)字符，從右向左讀入長(zhǎng)度為B的字符塊，計(jì)算字符塊的哈希值h。當(dāng)shift[h]>0時(shí)，將窗口向右移動(dòng)shift[h]位；當(dāng)shift[h]=0時(shí)，定位到hash[h]的指針，取出與當(dāng)前窗口字符串后綴哈希相同的模式串鏈表list，list中包含的所有模式串稱為潛在候選模式串。對(duì)list進(jìn)行遍歷，首先比較前綴哈希值是否與當(dāng)前窗口相同，如果不同，則繼續(xù)比較下一個(gè)模式串。如果相同，該模式串稱為候選模式串，將它與當(dāng)前窗口對(duì)應(yīng)的字符串進(jìn)行完全匹配。如果完全匹配，則輸出一個(gè)匹配，并將當(dāng)前窗口向右移動(dòng)一位；否則，繼續(xù)比較下一個(gè)模式。

3 Wu-Manber算法分析

Wu-Manber算法的跳躍機(jī)制使得部分字符不需要匹配，在實(shí)際應(yīng)用中具有較高的效率。hash表大小與shift表大小相同。在hash表中，存有指向具有相同后綴哈希的模式串組成的prefix表的指針，prefix表中的信息不僅包含模式串的編號(hào)，也包含該模式串的前綴哈希。

問題在于當(dāng)模式集合的規(guī)模較大時(shí)，具有相同后綴的模式串?dāng)?shù)量也非常大。Wu-Manber算法在搜索過程中取出所有具有相同后綴的模式串一一進(jìn)行比較，雖然首先比較前綴哈希值，這在一定程度上能提高算法效率，但是仍然存在冗余的比較操作。

Wu-Manber算法搜索模式時(shí)，首先通過后綴哈希值判斷當(dāng)前窗口字符串是否為潛在候選模式串，然后通過前綴哈希值判斷當(dāng)前窗口字符串是否為候選模式串。隨著模式集合規(guī)模的增大，潛在候選模式串的數(shù)量急劇增長(zhǎng)，在搜索時(shí)產(chǎn)生大量的冗余操作，即需要不停地判斷當(dāng)前窗口字符串的前綴哈希值是否與模式串鏈表list當(dāng)中的潛在候選模式串的前綴哈希值相同。當(dāng)搜索文本大小為10 MB時(shí)，從表5可以看出，當(dāng)模式集合規(guī)模增大時(shí)，潛在候選模式串的數(shù)量急劇增長(zhǎng)。當(dāng)模式集規(guī)模為50 000時(shí)，從表6可以看出，隨著搜索文本的增大，潛在候選模式串的數(shù)量不斷增大。

如果改變Wu-Manber算法當(dāng)中的prefix表結(jié)構(gòu)，在搜索時(shí)，能夠快速定位到與當(dāng)前窗口字符串后綴哈希值和前綴哈希值均相同的模式串鏈表，那么算法的效率就能夠提高很多。

4 Wu-Manber算法的改進(jìn)算法

針對(duì)算法中的prefix表，本文提出Wu-Manber算法的改進(jìn)算法?；舅枷胧窃谒阉鬟^程中，不需要對(duì)具有相同后綴值的所有模式串進(jìn)行前綴哈希比較，而是直接取出具有相同后綴哈希值和相同前綴哈希值的所有模式串直接進(jìn)行匹配操作，并且通過對(duì)前綴哈希值進(jìn)行再哈?；蛘吲判虻姆绞竭M(jìn)一步加快比較速度。

4.1 改進(jìn)算法的存儲(chǔ)結(jié)構(gòu)

在Wu-Manber算法中，prefix表是一個(gè)鏈表，存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)為<前綴哈希值prefixHash，模式串索引號(hào)index>。在改進(jìn)算法中，定義prefixList表存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)為<前綴哈希值prefixHash，模式串索引號(hào)鏈表index list>。

prefixList表將具有相同前綴哈希值的模式串集合到一起，在搜索模式時(shí)不需要比較前綴哈希值，可以直接取出指定模式串鏈表進(jìn)行字符匹配的操作。

4.2 PrefixTreeWM算法

PrefixTreeWM算法使用改進(jìn)的prefixList表，并將<前綴哈希值prefixHash，模式串索引號(hào)鏈表index list>中的prefixHash作為二叉樹的key，通過對(duì)前綴哈希值prefixHash進(jìn)行排序，能夠快速定位到指定的index list。如圖2所示，模式集合P={…，money，…， honey，…，moley，…，holey，…，Goley，…}。圖2中顯示出的五個(gè)模式串它們的共同后綴為ey，hash[ey]=5309。PrefixTreeWM算法在hash表中存入由前綴哈希值作為key構(gòu)建的二叉樹，二叉樹節(jié)點(diǎn)存儲(chǔ)的內(nèi)容就是改進(jìn)的prefixList表。設(shè)前綴prefixB=2，圖2中的五個(gè)模式具有三個(gè)不同的前綴，分別是Go、ho、mo，對(duì)應(yīng)的哈希值分別是hash[Go]=2227，hash[ho]=5683，hash[mo]=6323。

預(yù)處理模式串pi'時(shí)，首先計(jì)算pi'的后綴哈希值suffixHash和前綴哈希值prefixHash，取出hash[suffixHash]中的二叉樹，判斷當(dāng)前二叉樹是否含有key為prefixHash的節(jié)點(diǎn)，如果沒有，則插入一個(gè)新的key為prefixHash的節(jié)點(diǎn)，在index list中存入模式串的索引；如果有，那么搜索到對(duì)應(yīng)的節(jié)點(diǎn)，在它的index list中加入模式串pi'的索引。搜索模式時(shí)，窗口置于輸入文本T的開始位置0。取出當(dāng)前窗口對(duì)應(yīng)的m個(gè)字符，計(jì)算其前綴哈希值prefixHash和后綴哈希值suffixHash，當(dāng)shift[suffixHash]>0時(shí)，將窗口向右移動(dòng)shift[suffixHash]位；當(dāng)shift[suffixHash]=0時(shí)，讀取hash[suffixHash]中存儲(chǔ)的二叉樹，搜索到key為prefixHash的節(jié)點(diǎn)，取出其中的index list。index list中包含的所有模式串稱為潛在候選模式串。其余搜索步驟與Wu-Manber算法相同。

4.3 PrefixHashWM算法

為處理大規(guī)模模式集，本文提出PrefixHashWM算法，使用哈希表，能夠在O（1）時(shí)間內(nèi)查找到指定的前綴哈希值。

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

雖然PrefixHashWM算法空間復(fù)雜度比較高，但是它的時(shí)間復(fù)雜度大大降低。如圖3所示，模式集合P={…，money，…，honey，…，moley，…，holey，…，Goley，…}。通過后綴哈希值hash[ey]=5309映射到前綴哈希表prefixHashTable5309后，對(duì)每個(gè)模式串計(jì)算前綴哈希值，并將索引號(hào)存入對(duì)應(yīng)的哈希桶中，前綴哈希表中的list存儲(chǔ)的是具有相同前綴哈希和相同后綴哈希的模式串索引列表。

PrefixHashWM算法在預(yù)處理模式和搜索模式時(shí)都會(huì)更加高效。預(yù)處理模式時(shí)，它不需要判斷當(dāng)前字符串的前綴哈希值是否已經(jīng)存在，也就不需要去遍歷已經(jīng)處理過的前綴哈希值。搜索模式時(shí)，哈希表的時(shí)間復(fù)雜度是O（1），能夠迅速找到指定的list，直接進(jìn)行字符串匹配操作。

5 實(shí)驗(yàn)分析

為評(píng)價(jià)改進(jìn)算法的性能，本文對(duì)Wu-Manber算法、PrefixTreeWM算法和PrefixHashWM算法進(jìn)行實(shí)驗(yàn)對(duì)比。實(shí)驗(yàn)分析三種算法匹配過程的時(shí)間消耗，實(shí)驗(yàn)平臺(tái)為CPU 2.7 GHz Intel Core i5，內(nèi)存8 GB，操作系統(tǒng)OS X。

（1）實(shí)驗(yàn)一中采用的文本數(shù)據(jù)是大小為10 MB的文檔，模式串為隨機(jī)生成的字符串，最短模式長(zhǎng)度為6，設(shè)B=3，前綴prefixB=2。實(shí)驗(yàn)結(jié)果如圖4和圖5所示。圖4中的模式集大小從20 000到30 000，跨度為1000。當(dāng)搜索文本較小且模式集規(guī)模較小時(shí)，三種算法時(shí)間消耗情況為Wu-Manber>PrefixHashWM>PrefixTreeWM。PrefixTreeWM算法在這種情況下，性能最優(yōu)。

設(shè)N為二叉樹中存儲(chǔ)的節(jié)點(diǎn)個(gè)數(shù)，由于PrefixTreeWM算法對(duì)模式串集合通過后綴哈希值和前綴哈希值共同進(jìn)行分類，使N不會(huì)隨著數(shù)據(jù)的增大而過分增大，這使得二叉樹查找指定索引列表的速度由于N的限制得到保證，即使是最壞情況O（N）也可以接受。和Wu-Manber算法相比較，PrefixHashWM算法和PrefixTreeWM算法搜索模式時(shí)的時(shí)間消耗大大減少。

圖5中的模式集大小從100 000到300 000，跨度為10 000。當(dāng)搜索文本較小時(shí)但模式集規(guī)模較大時(shí)，三種

算法的時(shí)間消耗情況為Wu-Manber>PrefixTreeWM>

PrefixHashWM。PrefixHashWM算法在這種情況下性能最優(yōu)。當(dāng)模式集規(guī)模增大時(shí)，PrefixTreeWM算法中二叉樹中的節(jié)點(diǎn)數(shù)量增多，時(shí)間復(fù)雜度變大，超過PrefixHashWM算法的復(fù)雜度。PrefixHashWM算法中的二維哈希表在任何時(shí)刻的查找時(shí)間復(fù)雜度均為O（1）。當(dāng)模式集規(guī)模增大時(shí)，宜使用PrefixHashWM算法。

（2）實(shí)驗(yàn)二采用的文本數(shù)據(jù)是大小為50 MB的文檔，模式串為隨機(jī)生成的字符串，最短模式長(zhǎng)度為6，設(shè)B=3，前綴prefixB=2。實(shí)驗(yàn)結(jié)果如圖6和圖7所示。圖6中的模式集大小從20 000到30 000，跨度為1 000。圖7中的模式集大小從100 000到300 000，跨度為10 000。

當(dāng)搜索文本增大時(shí)，潛在候選字符串也隨著增加，這使得PrefixTreeWM算法中的二叉樹的查找次數(shù)不斷增加，導(dǎo)致PrefixTreeWM算法的時(shí)間復(fù)雜度上升，所以PrefixHashWM算法中哈希表的優(yōu)勢(shì)得到體現(xiàn)。

圖6和圖7說明當(dāng)數(shù)據(jù)量大時(shí)，PrefixHash-WM算法的性能最優(yōu)。改進(jìn)的兩種算法的時(shí)間復(fù)雜度受哈希桶中模式串?dāng)?shù)量的影響，如果某種具有相同后綴哈希值和前綴哈希值的模式串特別多，那么改進(jìn)算法的時(shí)間消耗也會(huì)變大。當(dāng)模式集規(guī)模更大時(shí)，由于實(shí)驗(yàn)采用的是隨機(jī)數(shù)據(jù)集，分配到每個(gè)哈希桶的模式串?dāng)?shù)量基本一致。圖7說明隨著模式集規(guī)模的增長(zhǎng)，Wu-Manber算法時(shí)間消耗明顯增長(zhǎng)，而PrefixTreeWM算法和PrefixHashWM算法的時(shí)間消耗增長(zhǎng)并不明顯。

（3）實(shí)驗(yàn)三采用的文本數(shù)據(jù)是大小為50 MB的文檔，模式串為隨機(jī)生成的字符串，最短模式長(zhǎng)度為10，設(shè)B=3，前綴prefixB=2。實(shí)驗(yàn)結(jié)果如圖8所示，圖8中的模式集大小從100 000到200 000，跨度為10 000。

（4）實(shí)驗(yàn)四將以上三種算法應(yīng)用到入侵檢測(cè)系統(tǒng)Snort中。Snort是一套開源代碼的網(wǎng)絡(luò)入侵預(yù)防軟件與網(wǎng)絡(luò)入侵檢測(cè)軟件，規(guī)則庫(kù)定期發(fā)布[10]。使用Snort-2.9.9.0版本，將三種算法添加入源代碼，Snort.conf文件中加載的規(guī)則數(shù)為10 212。表7記錄的是三種算法在不同packet數(shù)的情況下檢測(cè)消耗的時(shí)間。第一行檢測(cè)的數(shù)據(jù)是使用Snort數(shù)據(jù)包記錄器得到的數(shù)據(jù)，記錄數(shù)據(jù)的命令為snort-dev-l log/-i en0。第二行檢測(cè)的數(shù)據(jù)是DARPA 1999 Inside Dataset W5D1的inside.tcpdump文件[11]。

從表7中的數(shù)據(jù)可以看到，PrefixTreeWM算法在兩個(gè)不同的檢測(cè)數(shù)據(jù)上速度分別比Wu-Manber算法提高了53.79%和13.32%；PrefixHashWM算法在兩個(gè)不同的檢測(cè)數(shù)據(jù)上速度分別比Wu-Manber算法提高36.39%和13.65%。實(shí)驗(yàn)結(jié)果與實(shí)驗(yàn)一、實(shí)驗(yàn)二、實(shí)驗(yàn)三相同，當(dāng)數(shù)據(jù)量較小時(shí)，PrefixTreeWM算法匹配速度更快；當(dāng)數(shù)據(jù)量較大時(shí)，PrefixHashWM算法匹配速度更快。

根據(jù)上面兩種不同類型的實(shí)驗(yàn)結(jié)果，可以看到改進(jìn)算法在實(shí)際應(yīng)用中的優(yōu)勢(shì)。無論在隨機(jī)數(shù)據(jù)實(shí)驗(yàn)還是在實(shí)際入侵檢測(cè)系統(tǒng)中，PrefixTreeWM算法和PrefixHashWM算法在時(shí)間上的效率都高于Wu-Manber算法。

6 結(jié)束語

本文研究并測(cè)試Wu-Manber算法并提出兩種改進(jìn)算法：PrefixTreeWM算法和PrefixHashWM算法。改進(jìn)算法使用改進(jìn)的prefixList表，在使用后綴哈希值進(jìn)行分類的基礎(chǔ)上，使用前綴哈希值將模式串集合進(jìn)行再一次分類，避免Wu-Manber算法中的冗余操作。對(duì)前綴哈希值分別采用二叉樹和哈希表的方式進(jìn)行排序，加快查找速度，提高算法效率。本文對(duì)三種算法使用隨機(jī)數(shù)據(jù)集和網(wǎng)絡(luò)數(shù)據(jù)檢測(cè)分別進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明當(dāng)數(shù)據(jù)量不大時(shí)，PrefixTreeWM算法性能更高；當(dāng)數(shù)據(jù)量增大時(shí)，使用PrefixHashWM算法效率更高。PrefixHashWM算法的高效是以大量的哈希表空間消耗為代價(jià)的，下一步的工作將致力于減少算法的空間復(fù)雜度。

參考文獻(xiàn)：

[1] 張宏莉，徐東亮，梁敏，等. 海量模式高效匹配方法研究[J]. 電子學(xué)報(bào)， 2014，42（6）： 1220-1224.

[2] 張興彪. 海量多模式串匹配算法關(guān)鍵技術(shù)研究[D]. 哈爾濱： 哈爾濱工程大學(xué)， 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] 董迎亮. 基于改進(jìn)WM算法的網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的研究與實(shí)現(xiàn)[D]. 長(zhǎng)春： 吉林大學(xué)， 2011.

[10] 熊剛，何慧敏，于靜，等. HybridFA：一種基于統(tǒng)計(jì)的AC自動(dòng)機(jī)空間優(yōu)化技術(shù)[J]. 通信學(xué)報(bào)， 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.