Wu_Manber算法的綜合改進(jìn)

黃逸之，尹香蘭

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

0 引言

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

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

多模式匹配過程要獲得高的效率，關(guān)鍵在于三個(gè)方面：一是盡可能多、盡可能遠(yuǎn)地進(jìn)行跳躍，避免進(jìn)入無效的匹配過程；二是在可能出現(xiàn)匹配時(shí)，盡量減少比較次數(shù)；三是綜合利用現(xiàn)有硬件條件，進(jìn)行并行運(yùn)算。

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

1 Wu_Manber算法

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

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

取所有模式串長(zhǎng)度的最小值為m，只考慮所有模式串的前m個(gè)字符。假設(shè)當(dāng)前匹配窗口的最后B個(gè)字符組成不良字符塊X：

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

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

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

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

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

2 對(duì)Wu_Manber算法的改進(jìn)2.1 對(duì)跳躍距離的改進(jìn)一

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

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

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

圖1 匹配窗口圖

精確的Shift[ ]計(jì)算過程：

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

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

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

2.2 對(duì)跳躍距離的改進(jìn)二

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

Shift [ ]表計(jì)算方法為：

實(shí)驗(yàn)結(jié)果顯示， 在最小模式長(zhǎng)度較小時(shí)，當(dāng)m<9時(shí)，改進(jìn)后的算法比原算法性能顯著提高，用于英文文本時(shí)平均提高 8%～20%，用于中文文本時(shí)平均提高約15%～30%；當(dāng)最小模式長(zhǎng)度較大時(shí)， 改進(jìn)后的算法性能與原算法基本相同。

2.3 對(duì)跳躍距離的綜合改進(jìn)

以2.2節(jié)為基礎(chǔ)，結(jié)合2.1節(jié)的思想，計(jì)算其不良字符塊的精確跳躍距離，將使得最大跳躍距離能夠達(dá)到m+1。另外，同樣引入2.1節(jié)所使用的弱化的良好字符塊跳躍表。這樣，改進(jìn)后的算法思想為：在當(dāng)前匹配窗口中，如果根據(jù)Head[ ]表發(fā)現(xiàn)不可能出現(xiàn)匹配，則使用精確的不良字符塊跳躍表直接向右移動(dòng)窗口，其最大距離可達(dá)m+1，否則，進(jìn)入精確匹配過程，比較順序?yàn)閺挠蚁蜃?。如果找到匹配則輸出，再次采用精確的不良字符塊跳躍表直接向右移動(dòng)窗口，否則比較不良字符塊跳躍表和弱化的良好字符塊跳躍表，選取較大值作為窗口的跳躍距離。

2.4 匹配過程改進(jìn)一

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

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

改進(jìn)后算法效率在模式的各個(gè)規(guī)模上都有明顯的提高，提高幅度達(dá)到8%～15%，說明后綴模式處理能夠比較穩(wěn)定、有效地提高算法的運(yùn)行效率。

2.5 匹配過程改進(jìn)二

由于 CPU進(jìn)行一次8位的字符比較與進(jìn)行一次機(jī)器字長(zhǎng)的整數(shù)比較所花費(fèi)的時(shí)間完全相同，因此完全可以一次比較4個(gè)字符（32位CPU），以此提高效率。

2.6 其他改進(jìn)

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

圖2 HASH結(jié)構(gòu)圖

實(shí)驗(yàn)得出的數(shù)據(jù)為：當(dāng)m=1時(shí)，算法所用時(shí)間是其他情況下的7～10倍；m=2時(shí)，算法所用時(shí)間是其他情況下的4～9倍。針對(duì)這個(gè)問題，可以將模式串集一分為二，長(zhǎng)度小于等于2的為一組，其他的為另一組。將算法在這兩個(gè)模式串子集上分別運(yùn)行，最后得到總結(jié)果。

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

2.7 并行處理

現(xiàn)在隨著CPU內(nèi)核數(shù)的增多，在算法實(shí)現(xiàn)時(shí)應(yīng)充分利用其并行處理能力。

2.5節(jié)提出的問題和解決方法完全可以用兩個(gè)線程或進(jìn)程同時(shí)并行處理。不僅如此，應(yīng)將模式串集合合理分組，用多個(gè)線程或進(jìn)程并行處理，每個(gè)線程或進(jìn)程負(fù)責(zé)處理一個(gè)模式串子集，降低模式串集合過度增加后算法效率的下降。

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

3 結(jié)束語

多模式匹配算法是一個(gè)基礎(chǔ)算法，有許多重要應(yīng)用場(chǎng)合，對(duì)其進(jìn)行深入研究和試驗(yàn)具有重要意義。通過對(duì)Wu_Manber算法的仔細(xì)研究，在算法實(shí)現(xiàn)過程中對(duì)算法作出了多方面的改進(jìn)，在實(shí)際應(yīng)用中，取得了良好的效果。

[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] 楊東紅，徐恪，崔勇.改進(jìn)的Wu-Manber 多模式串匹配算法[J]. 清華大學(xué)學(xué)報(bào) (自然科學(xué)版)，2006，46(14)：109-112.

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

[6] 張?chǎng)危T建龍，程學(xué)旗.一種改進(jìn)的Wu_Manber 多關(guān)鍵詞匹配算法[J]. 計(jì)算機(jī)應(yīng)用，2003，23(7)：544-549.

[7] 孫曉山，王強(qiáng)，關(guān)毅，等.一種改進(jìn)的 Wu_Manber 多模式匹配算法及應(yīng)用[J]. 中文信息學(xué)報(bào)，2006,20(2)：47-53.

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