Wu_Manber算法的綜合改進

黃逸之，尹香蘭

(江南計算技術研究所，江蘇 無錫，214083)

0 引言

多模式匹配問題可以描述為：P={p1，p2，...，pk}，是一個模式串的集合，其中任意一個模式串pi都是由字符表 Σ中的字符所組成。T=t1，t2，...，tn是一個大文本串，ti屬于 Σ。求所有模式P在T中的所有出現。

多模式匹配算法一般是單模式匹配算法的推廣。單模式匹配算法中經典并且效率較高的算法主要有BM（Boyer Moore）算法[1]和QS（Quick Search）算法[2]等。多模式串匹配算法中，Wu_Manber算法[3]是實際應用中平均性能最好的一個算法。QS算法是對BM算法的改進。而Wu_Manber算法是BM算法的多模式擴展?？梢哉f，這幾個算法的核心思想是一致的。

多模式匹配過程要獲得高的效率，關鍵在于三個方面：一是盡可能多、盡可能遠地進行跳躍，避免進入無效的匹配過程；二是在可能出現匹配時，盡量減少比較次數；三是綜合利用現有硬件條件，進行并行運算。

在本文中，使用p[0..m-1]表示要匹配的模式串，長度為m。使用T=t[0..n-1]表示正文文本，長度為n。字符集以 Σ表示，大小為 σ。將匹配過程中P與T中長度為m的子串之間的一次比較稱為一次嘗試，并將T中的該子串稱為當前匹配窗口，假設當前匹配窗口在T中的起始位置為k。

1 Wu_Manber算法

在多模式匹配中，隨著模式串個數的增加，字符t[k+m]出現在各模式串尾端的概率相應增加，因而能達到的平均跳躍距離隨之變小，BM或QS算法的跳躍效果在多模式串的情況下被極大地削弱。Wu_Manber 算法利用塊字符擴展了不良字符的跳躍效果，同時用散列表來篩選匹配階段應進行匹配的候選模式串，減少算法匹配時間。在每次匹配嘗試中，一次考察一“塊”，即連續B個字符。根據這B個字符所組成的塊的匹配情況來決定跳躍距離。通常模式數量少的時候取B=2，模式數量大的時候取B=3。

Wu_Manber算法同樣分為兩個處理階段。預處理階段將建立三個表格：SHIFT表、HASH表和PREFIX表。SHIFT表中存儲字符集中所有塊字符的跳躍距離。HASH表用來指出可能匹配的所有候選模式串。PREFIX 表用來過濾候選模式串。

取所有模式串長度的最小值為m，只考慮所有模式串的前m個字符。假設當前匹配窗口的最后B個字符組成不良字符塊X：

⑴X在所有模式串中不出現，則跳躍距離為m-B+1，即SHIFT[X]=m-B+1。

⑵X在部分模式串中出現，則跳躍距離為X在所有模式串中的最右出現到X的距離。

如果X是良好字符塊，則SHIFT[X]＝0，進入精確匹配過程。HASH[X]指向所有以X結尾的模式串列表，依次訪問這些可能匹配的候選模式串，如果模式串的前綴與PREFIX表不符合，則跳過；否則比較該模式串中的每個字符以決定是否出現一個完全匹配(此時的比較不再限于模式串的前m個字符，而是完整的模式串)。

以上的討論中，SHIFT[X]和HASH[X]指的是先將X散列，得到一個整數值，再用這個整數值作索引，查詢SHIFT表和HASH表。

Wu_ Manber算法的時間復雜度在最好的情況下能達到O(B×n/m)。

2 對Wu_Manber算法的改進2.1 對跳躍距離的改進一

2.1 .1 精確的不良字符塊跳躍距離

首先研究不良字符塊X在所有模式串中不出現時，其跳躍距離是否只能達到m-B+1。

如圖1所示，假設“ABCDE”為模式串集中長度最小的模式，此時匹配窗口的塊字符為“XAB”，雖然“XAB”是個不良字符塊，但是它的后綴“AB”是模式“ABCDE”的前綴，此時如果將匹配窗口移動m=5，那么就會漏掉一次正確的匹配。長度為B的不良字符塊，至多它的長度為B-1的后綴可能在模式串中出現。因此安全的跳躍距離為m-(B-1)=m-B+1=3。但是這種情況的出現次數相對于匹配中遇到的大多數不良字符塊轉移來說所占比例非常少，它減少了大多數情況下的跳躍距離，因此可以引入精確的不良字符跳躍表Shift[ ]，其最大跳躍距離可以達到m。

圖1 匹配窗口圖

精確的Shift[ ]計算過程：

2.1 .2 弱化的良好字符塊跳躍距離

Wu_Manber算法中沒有使用BM算法中使用的良好字符跳躍方法，因此無論當前良好字符塊的匹配結果如何，跳躍距離都固定為1。為此引入一種弱化了的良好字符塊跳躍表GBSShift[ ]來改進這一問題。該表記錄了每一個模式串的長度為B的后綴(最后一個塊字符)在所有模式串中的所有非后綴出現位置與后綴的距離的最小值。這樣，在匹配失敗后，其跳躍距離很可能大于1。

實際試驗證明了在附加微小的預處理時間(約為原預處理時間的10%)后，以上兩種改進能夠有效地降低比較次數，從而減少了對整個文本數據的掃描時間(約為原算法掃描時間的85%～92%) 。

2.2 對跳躍距離的改進二

結合Q S算法的思想，忽略當前匹配窗口的信息，不管匹配是否成功，直接使用字符塊t[m-B+1..m]來確定跳躍距離。跳躍距離至少為1，最大為m-B+2。但這樣做的話，跳躍表就無法用來判斷當前窗口是否存在可能匹配了(原算法跳躍距離為0表明存在可能匹配，應該進入精確匹配過程)。根據QS算法的特點，其匹配順序沒有要求，因此可以查看各模式串的前B個字符(前綴)與當前窗口的前綴是否匹配。為此需要增加一個表Head [ ]，記錄各模式串前綴的信息。Shift表記錄的是若當前文本與所有模式的前綴不同時， 數據指針向后跳躍距離。

Shift [ ]表計算方法為：

實驗結果顯示， 在最小模式長度較小時，當m<9時，改進后的算法比原算法性能顯著提高，用于英文文本時平均提高 8%～20%，用于中文文本時平均提高約15%～30%；當最小模式長度較大時， 改進后的算法性能與原算法基本相同。

2.3 對跳躍距離的綜合改進

以2.2節為基礎，結合2.1節的思想，計算其不良字符塊的精確跳躍距離，將使得最大跳躍距離能夠達到m+1。另外，同樣引入2.1節所使用的弱化的良好字符塊跳躍表。這樣，改進后的算法思想為：在當前匹配窗口中，如果根據Head[ ]表發現不可能出現匹配，則使用精確的不良字符塊跳躍表直接向右移動窗口，其最大距離可達m+1，否則，進入精確匹配過程，比較順序為從右向左。如果找到匹配則輸出，再次采用精確的不良字符塊跳躍表直接向右移動窗口，否則比較不良字符塊跳躍表和弱化的良好字符塊跳躍表，選取較大值作為窗口的跳躍距離。

2.4 匹配過程改進一

進入精確匹配過程后，Wu_Manber 算法對HASH[X]指向的候選模式串列表進行逐個比較。如果模式串pj和pk都匹配成功，則pj是pk的后綴或者反之。稱存在一個模式是其他模式的后綴的一組模式為后綴模式。例如模式this、his、is，如果沒有后綴模式，就不可能有兩個模式串同時匹配成功，所以一旦某個模式串匹配成功，就可以提前結束循環，根據跳躍表移動匹配窗口到下一個位置。

改進后的HASH數據結構增加了 same_suffix域，如圖2。后綴處理算法把后綴模式的模式使用same_suffix域鏈接起來，這樣在HASH表的next鏈表中的模式就不存在后綴模式。圖2中，Pi為is，Pi1為his，Pi2為this，Pi、Pi1、Pi2構成一個后綴模式，其中Pi是其他模式公共后綴；通過Pi的 same_suffix鏈表鏈接Pi1、Pi2。

改進后算法效率在模式的各個規模上都有明顯的提高，提高幅度達到8%～15%，說明后綴模式處理能夠比較穩定、有效地提高算法的運行效率。

2.5 匹配過程改進二

由于 CPU進行一次8位的字符比較與進行一次機器字長的整數比較所花費的時間完全相同，因此完全可以一次比較4個字符（32位CPU），以此提高效率。

2.6 其他改進

算法在匹配過程中的最大“跳躍” 距離是由所有模式串中最短的模式串長度m決定的。所以如果最小模式串的長度為1或2，則最大跳躍距離將非常有限，會大大降低算法的性能。

圖2 HASH結構圖

實驗得出的數據為：當m=1時，算法所用時間是其他情況下的7～10倍；m=2時，算法所用時間是其他情況下的4～9倍。針對這個問題，可以將模式串集一分為二，長度小于等于2的為一組，其他的為另一組。將算法在這兩個模式串子集上分別運行，最后得到總結果。

改進后的Wu_Manber算法性能有明顯提高。特別是對于英文匹配，在單字節模式串出現個數較少時，匹配速度較原來提高了 5～8倍?？紤]到現實中，單字節(單漢字)模式串出現個數較少，所以這種改進還是具有一定的實用價值。

2.7 并行處理

現在隨著CPU內核數的增多，在算法實現時應充分利用其并行處理能力。

2.5節提出的問題和解決方法完全可以用兩個線程或進程同時并行處理。不僅如此，應將模式串集合合理分組，用多個線程或進程并行處理，每個線程或進程負責處理一個模式串子集，降低模式串集合過度增加后算法效率的下降。

大文本則切成數段，每段之間有一定的重合，保證不遺漏可能匹配，采用多個線程或進程同時處理，每個線程或進程負責處理一段文本，這樣在線程數不超過CPU核心數的前提下，超大文本串的掃描速度將以近似線性增加。

3 結束語

多模式匹配算法是一個基礎算法，有許多重要應用場合，對其進行深入研究和試驗具有重要意義。通過對Wu_Manber算法的仔細研究，在算法實現過程中對算法作出了多方面的改進，在實際應用中，取得了良好的效果。

[1] BOYER R S，MOORE J S. A fast string searching algorithm[J]. Communications of the ACM，1977(20)：762-772.

[2] SUNDAY D M. A very fast substring search algorithm[J].Communications of the ACM，1990, 33(8)：132-142.

[3] Sun Wu，MANBER U. A fast algorithm for multi pattern searching [R]. Technical Report TR94217，University of Arizona at Tuscon， 1994.

[4] 楊東紅，徐恪，崔勇.改進的Wu-Manber 多模式串匹配算法[J]. 清華大學學報 (自然科學版)，2006，46(14)：109-112.

[5] 李雪梅，代六玲，童新海，等.對 QS串匹配算法的一種改進[J]. 計算機應用與軟件，2006，23(3)：55-57.

[6] 張鑫，譚建龍，程學旗.一種改進的Wu_Manber 多關鍵詞匹配算法[J]. 計算機應用，2003，23(7)：544-549.

[7] 孫曉山，王強，關毅，等.一種改進的 Wu_Manber 多模式匹配算法及應用[J]. 中文信息學報，2006,20(2)：47-53.

[8] 陳瑜、陳國龍. Wu_Manber算法性能分析及其改進[J]. 計算機科學，2006，33(16)：207-029.