基于BM窗口競爭的高效單模式匹配算法

陳 偉，滕宏舜

（浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江 金華321004）

1 概述

字符串模式匹配，即在一個文本T＝t1t2…tn中找出某個特定模式串P＝p1p2…pn首次出現(xiàn)或所有模式串出現(xiàn)的位置，其中，T和P都是有限字符集Z上的字符序列；n和m 為正整數(shù)，且n≥m。T中當(dāng)前和模式P進行匹配的m長子串被稱為匹配窗口。

字符串模式匹配算法作為基礎(chǔ)算法之一，已被廣泛應(yīng)用于計算機和網(wǎng)絡(luò)數(shù)據(jù)搜索方面。它在文檔編輯、文獻資料檢索、海量數(shù)據(jù)挖掘、DNA序列檢測、病毒檢測、圖像處理、Web搜索、網(wǎng)絡(luò)入侵檢測、內(nèi)容安全技術(shù)及事務(wù)管理系統(tǒng)等非數(shù)值處理方面有非常廣泛的應(yīng)用。如網(wǎng)絡(luò)入侵檢測系統(tǒng)，約有30%的時間用來進行模式匹配［1］，而在加強網(wǎng)絡(luò)交互的情況下，則用于模式匹配的時間約占總量的80%［2］。

模式匹配問題可分為單模式匹配和多模式匹配2類。典型的單模式算法主要有KMP算法、SKIP算法、BM算法［3］。其中有大量基于BM的改進算法 BMH［4］，BMHS［5］，BMH2C［6］，BMG［7］更適合中文字符的 BM 改進［8］、N－BMHS［9］。文獻［10］分析雙字符串在模式串中出現(xiàn)的不同情形和模式串后繼字符的關(guān)系確定右移量。文獻［11］提出基于Sunday算法的改進算法，在匹配前先找到模式串中的特征字符（出現(xiàn)概率最小的字符），再進行特征字符與尾字符雙重匹配，增大了首次不匹配的可能性。文獻［12］提出Sunday改進算法，利用Unicode中文雙字節(jié)編碼的內(nèi)部關(guān)聯(lián)性，優(yōu)化原Sunday算法的跳轉(zhuǎn)值，補償Sunday算法因降低空間消耗而造成的時間效能損耗，提升在中文Unicode編碼環(huán)境下的匹配性能。Y＿BMHS算法［13］利用輔助的二維數(shù)組，文本串中間隔的2位字符和模式串首字符的唯一性，使得模式串以最大位移m＋3進行右移的概率提高。

本文以經(jīng)典單模式匹配算法Boyer－Moore（BM）為研究對象，充分利用BM系列改進算法之間的差異性實現(xiàn)失配窗口右移距離最大化，以窗口競爭的思想提高匹配窗口到位率，盡量減少不必要的匹配過程。

2 BM算法及其改進算法

BM系列算法的特點是從模式串P的尾部（最右端）開始掃描。它將P與目標(biāo)文本T的左端對齊后，在匹配窗口中自右向左逐個比對。

2．1 BM 算法

BM算法采用壞字符和好后綴2項規(guī)則。設(shè)Z為與P，T相關(guān)的有限一元字符集，P中的字符構(gòu)成Z的子集Zp，k為當(dāng)前模式匹配窗口尾部所在位置，即窗口的最右端。壞字符規(guī)則使用預(yù)計算的skip數(shù)組，定義為：

在該規(guī)則中，一旦某字符失配，即P［i］≠T［j］，則跳躍距離s＝skip1（x）－（m－i），如圖1所示。

圖1 壞字符規(guī)則

好后綴規(guī)則使用預(yù)計算的shift數(shù)組。在該規(guī)則中，如果P尾部的k位（記為P1子串）已經(jīng)和當(dāng)前匹配窗口中T的部分字符串（記為T1子串）匹配成功（P1＝T1），此時的下一位字符卻突然發(fā)生失配，則算法檢查P中前邊m－k位是否存在該P1子串的同版本子串P2（P2＝P1）。若P2存在，則將模式串P右移使P2與T1對齊。否則，檢查P從最左邊字符開始的m－k位中是否存在前綴P3，使之成為P1的任意后綴。如果存在，則右移模式串使其對齊。如果兩者皆不存在，此時可直接將模式串P向右移動，使P［1］對齊T1后的第一個字符。

BM算法的預(yù)處理時間復(fù)雜度為O（m＋Z），空間復(fù)雜度為O（Z），最好情況下的時間復(fù)雜度為O（n／m），最壞情況下時間復(fù)雜度為O（nm）。

2．2 BM系列改進算法

BM的內(nèi)在缺陷在于：壞字符規(guī)則可能造成右移數(shù)為負值（回頭左移）。所以，算法取2個規(guī)則函數(shù)所產(chǎn)生移動值中更大的那個數(shù)為右移距離。

另一個問題是：好后綴規(guī)則的實用性不強。好后綴規(guī)則的預(yù)處理和計算過程都較復(fù)雜。而且，研究表明，壞字符規(guī)則在匹配過程中占主導(dǎo)地位的概率為94．03%，遠遠高于好后綴。因此，文獻［4］提出的BMH算法以及后續(xù)類似改進都拋棄了好后綴，而只采用壞字符規(guī)則。

BMH解決了BM算法中模式串有可能左移的問題。在BMH中，無論失配發(fā)生在當(dāng)前窗口的什么位置，都由目標(biāo)文本T中和模式串最后一個位置pm對應(yīng)的字符tk，即當(dāng)前窗口的尾字符來決定右移距離。它比BM更緊湊，效率也更高，在最好的情況下復(fù)雜度為O（n／m）。

文獻［5］將BMH進一步改進成了BMHS，其主要思想是：利用當(dāng)前窗口的下一個字符tk＋1而不是尾字符tk來計算右移量，即將skip函數(shù)改為：

這使得最大和平均移動距離分別由m和（m＋1）／2增加為m＋1和（m＋1）／2。BMHS在最好情況下的時間復(fù)雜度為O（n／m＋1）。通常情況下，其速度大于BMH。

但是，BMHS相對于BMH有一個缺陷：當(dāng)tk＋1出現(xiàn)在模式中，而tk不出現(xiàn)時，BMHS的右移距離反而不如BMH，使其匹配窗口反而落后于BMH。

一些研究者注意到兩者間的差異性。文獻［6］提出了BMH2C算法，用當(dāng)前窗口末字符tk和下一字符tk＋1組成二元組來計算右移量。設(shè)Z2為基于字符集Z的二元字符集，Z2P為P中二元字符組集合。文獻［6］重新定義了skip函數(shù)：

上述3種算法的右移量比較如表1所示。

表1 3種算法的右移量比較

從表1可見，BMH2C克服了BMH和BMHS的缺點，達到了后兩者的最優(yōu)解。但另一方面，BMH2C只是對它們的合并和微調(diào)，其最大右移量仍然是m＋1，并未獲得突破性改進。

2．3 BMG算法

文獻［7］的研究同樣基于BMH和BMHS。當(dāng)BMHS窗口落后于BMH時，其匹配過程是多余的。希望對BMHS進行改進，使其窗口能進一步向右滑動，提出的方法是定義一個唯一性函數(shù)：

然后，據(jù)此考察tk＋1字符在模式P中出現(xiàn)的唯一性。由此，提出了BMG算法。算法過程為：（1）計算出由字符tk得到的右移位置k1＝k＋skip1（tk）（原BMH部分）和由字符tk＋1得到的右移位置k2＝k＋skip2（tk＋1）（原 BMHS部分）。（2）判斷兩者的大小。如果k1＞k2，再判斷tk＋1在模式串中出現(xiàn)的頻次。若 Q（tk＋1）＝1，則將tk＋1＋m和模式串末端對齊作為新匹配窗口（BMHS改進部分）；否則，便意味著即使經(jīng)過這樣的改進，BMHS窗口依然跟不上BMH，只能放棄該窗口，將tk1和模式串末端對齊。

可以看出，唯一性函數(shù)Q（x）對BHMS算法的落后只是部分補償，該算法有一定的改進效果，提供了一種無需進行任何字符比對便能確定當(dāng)前窗口是否失配的前景。但對BMH和BMHS的設(shè)計思想仍然是突而不破，僅考慮了k1＞k2時的情形。其最大右移距離仍是m＋1。它存在2大問題：

（1）當(dāng)落后的BMHS窗口獲得補償超越靠前的BMH窗口，使之成為新的落后窗口時，未有效利用該新落后窗口信息，只是將之簡單地拋棄。

（2）沒有利用落后BMHS窗口的尾字符信息，浪費了獲取更大跳躍距離的可能性。

3 窗口競爭技術(shù)

3．1 窗口滑動過程

從第2節(jié)可以看出，對BMH，BMHS的改進成為模式匹配算法進化的主要途徑之一。一種最簡單的改進方式為：對于skip（tk）＝m，通過連續(xù)測試找到滿足skip（tk＋lm）≠m（l∈N＋）的最小l值，以此定位窗口位置。對于skip（tk＋1）＝m，亦可作類似處理。

從表1可以看出，BMH，BMHS和BMH2C3種算法的右移步伐是不一樣的。設(shè)它們自同一匹配窗口起步后，右移距離從小到大依次排列為a，b，c，即有a≥b≥c，如圖2所示。此時，若有a＝b＝c，說明3種算法達成一致，可以開始在窗口字符與模式串之間進行比對，判斷是否能找到一個匹配。否則，必有至少一個窗口的右移距離最大，處于最右的位置，被稱為前端窗口，而其余窗口則落在后面，被稱為落后窗口。可以認為落后窗口無需比對即告失配。此時，如何處理它們成為關(guān)鍵問題。

圖2 3種算法的不同步右移

如同BMG和其他類似改進所期望的那樣，每個落后窗口的使命都是盡快超越當(dāng)前的前端窗口，使之與自己地位對換。如此反復(fù)，便可以在不進行任何字符比對嘗試的情況下，僅通過計算skip函數(shù)就使窗口不斷向前滑動，從而大大減小比對次數(shù)。

為達上述目的，落后窗口應(yīng)盡量使用右移距離最大的BMH2C實現(xiàn)超越（即測試tktk＋1的skip3函數(shù)），并且需要維護一張按位置前后排序的窗口狀態(tài)表。

3．2 BMHS2C

結(jié)合BMHS和BMH2C算法，利用模式串對應(yīng)文本串末尾后面2個字符串tk＋1tk＋2來計算右移量，使得文本串的右移量最大提升到m＋2。skip函數(shù)如下：

3．3 Q（x）函數(shù)

為使每個落后窗口都能產(chǎn)生盡可能大的右移量，引入文獻［7］中定義的唯一性函數(shù)Q（x），并將其擴展到二元字符組上，定義類似函數(shù)如下：

因此，每次落后窗口右移時，如果skip1（tk）＜m 但Q（tk）＝1，則視同skip1（tk）＝m。類似的，如果skip2（tk＋1）＜m＋1 但 Q（tk＋1）＝1，則 視 同skip2（tk＋1）＝m＋1。如果skip3（tktk＋1）＜m＋1但Q2（tktk＋1）＝1，則視同skip3（tktk＋1）＝m＋1。

顯然，當(dāng)落后窗口雖努力右移仍無法超越當(dāng)前的前端窗口時，則消亡。一旦落后窗口消化殆盡，一個新的匹配窗口便自然產(chǎn)生，此時便可以開始字符逐個比對的匹配過程。當(dāng)匹配窗口發(fā)生失配時，則需要使用3種算法進行窗口衍生。

4 算法使用數(shù)據(jù)及處理過程

本文充分利用BM改進算法之間的差異性達到右移距離最大化，考慮特征字符tk＋1在模式串P中出現(xiàn)的次數(shù)，以及窗口競爭思想，使匹配窗口到位率大大提高，盡量減少不必要的匹配過程。

4．1 數(shù)據(jù)項

根據(jù)上節(jié)描述，算法需要使用如下數(shù)據(jù)：

（1）長為m的模式P的匹配序數(shù)組；

（2）長為3的窗口狀態(tài)數(shù)組State，其值為：2＝當(dāng)前窗口，1＝落后窗口，0＝作廢窗口；

（3）長為3的窗口尾部位置數(shù)組k，分別代表BMH，BMHS和BMH2C算法計算得到的窗口位置；

（4）標(biāo)識當(dāng)前窗口屬于哪個算法的變量up；

4．2 預(yù)處理

預(yù)處理步驟如下：

（1）初始化各個數(shù)組；

（2）掃描模式串，按式（1）～式（3）分別建立skip函數(shù)數(shù)據(jù)項，按式（4）、式（5）分別建立Q 和Q2數(shù)據(jù)項。

上述預(yù)處理步驟的復(fù)雜度為O（Z＋Z2），稍高于BM的預(yù)處理復(fù)雜度O（Z＋m）。

4．3 算法流程

算法流程及匹配過程如圖3～圖7所示。在以上實例中，對I＿BMH2C和Skii－BM算法的匹配過程進行了對比。利用BMH和BMHS2C進行窗口競爭，在第2輪中BMH的窗口超過了BMHS2C，則跳過字符匹配，BMHS2C直接進行下一輪右移。

圖3 Skii－BM算法總體流程

圖4 BMH和BMHS窗口滑動流程

圖5 BMH2C窗口滑動流程

圖6 I＿BMH2C算法匹配過程

圖7 Skii－BM算法匹配過程

5 實驗結(jié)果與分析

在Windows XP操作平臺，CPU酷睿雙核T6600，主頻2．2GHz，內(nèi)存2GB，主頻1 067MHz的環(huán)境下，選擇200KB大小的英文語料重復(fù)500次對BMH，BMHS，BMH2C和Skii－BM 4種算法進行測試。為增強準(zhǔn)確性，選取了模式長度分別為10以下和10以上的2組模式進行比較。窗口競爭對比實驗數(shù)據(jù)如表2和表3所示。

表2 模式長度小于10時的窗口競爭實驗數(shù)據(jù)

表3 模式長度大于10時的窗口競爭實驗數(shù)據(jù)

由上述實驗可以看出，Skii－BM算法在比對字符數(shù)和窗口滑動數(shù)較BMH，BMHS，BMH2C算法減少明顯，匹配效率大幅提高。其中，當(dāng)模式串長度小于10時，由于tk，tk＋1所組成的雙字符組出現(xiàn)在模式串P中的概率較小，則BMH2C的右移量為m＋1的概率較大。窗口競爭的思維也主要以BMHS2C的右移量為主。在字符比對數(shù)和窗口滑動數(shù)方面優(yōu)勢明顯，由于處理階段的額外開銷高于BMH2C，因此利用Q函數(shù)和窗口競爭的Skii－BM算法速度有所下降。但在處理長模式時，其優(yōu)勢更明顯。

6 結(jié)束語

目前對于BM算法的改進算法有很多，在對不同文本模式進行匹配時也有各自的優(yōu)勢。本文在對已有的BM算法研究基礎(chǔ)上提出改進算法，即Skii－BM算法。實驗數(shù)據(jù)證明，與以往改進算法相比，該算法的速度和效率都有較大改善，在模式匹配算法的應(yīng)用領(lǐng)域中具有更好的性能。

［1］Fisk M，Varghese G．An Analysis of Fast String Matching Applied to Content－based Forwarding and Intrusion Detection，CS2001－0670［R］．San Diego，USA：University of California，2002．

［2］Antonatos S，Anagnostakis K G，Markatos E P．Generating Realistic Workloads for Network Intrusion Detection Systems［C］／／Proceedings of ACM Workshop on Software and Performance．New York，USA：ACM Press，2004：207－215．

［3］Boyer R S，Moore J S．A Fast String Searching Algorithm［J］．Communications of the ACM，1977，20（10）：762－772．

［4］Horspool N．Practical Fast Searching in Strings［J］．Software Practice and Experience，1980，20（10）：501－506．

［5］Sunday D M．A Very Fast Substring Search Algorithm［J］．Communications of the ACM，1990，33（3）：132－142．

［6］錢 屹，侯義斌．一種快速的字符串匹配算法［J］．小型微型計算機系統(tǒng)，2004，25（3）：400－413．

［7］張 娜，侯整風(fēng)．一種快速的BM 模式匹配改進算法［J］．合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2006，29（7）：834－838．

［8］劉沛騫，馮晶晶．一種改進的BM模式匹配算法［J］．計算機工程，2011，37（17）：248－250．

［9］單懿慧，蔣玉明，田詩源．面向入侵檢測的改進BMHS模式匹配算法［J］．計算機工程，2009，35（24）：170－173．

［10］王艷霞，江艷霞．BMH2C單模匹配算法的研究與改進［J］．計算機工程，2014，40（3）：299－301．

［11］萬曉榆．改進的Sunday模式匹配算法［J］，計算機工程，2009，35（7）：125－129．

［12］朱永強．基于Sunday算法的改良單模式匹配算法［J］．計算機應(yīng)用，2014，34（1）：208－214．

［13］楊子江．一種快速的單模式匹配算法［J］．華南師范大學(xué)學(xué)報：自然科學(xué)版，2013，45（5）：32－35．