梁 威，葉 猛

（1.光纖通信技術(shù)和網(wǎng)絡(luò)國家重點實驗室，湖北武漢430074;2.武漢郵電科學(xué)研究院通信與信息系統(tǒng)，湖北武漢430074;3.武漢虹旭信息技術(shù)有限責(zé)任公司安全產(chǎn)品部，湖北武漢 430074）

隨著網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，網(wǎng)絡(luò)違法犯罪行為與日俱增。不法分子常常利用互聯(lián)網(wǎng)進(jìn)行一些違法犯罪活動，如傳播色情信息、暴力信息和反動信息等，這些行為會嚴(yán)重擾亂社會次序，給人們的日常生活帶來極大危害［1］。因此，如何有效剔除不相關(guān)信息和不良信息，已經(jīng)成為新的研究熱點?；ヂ?lián)網(wǎng)中數(shù)據(jù)過濾系統(tǒng)的出現(xiàn)正是為了應(yīng)對上述問題。過濾系統(tǒng)的性能低下會導(dǎo)致網(wǎng)絡(luò)違法犯罪行為不能夠被及時發(fā)現(xiàn)并制止，因此提升過濾系統(tǒng)的性能十分必要。

模式匹配算法是數(shù)據(jù)過濾系統(tǒng)的關(guān)鍵技術(shù)，因此其效率的高低間接地影響著互聯(lián)網(wǎng)的安全。然而在實際應(yīng)用的數(shù)據(jù)過濾系統(tǒng)中，所采用的模式匹配算法的效率不盡如人意，使得過濾過程耗費大量時間，互聯(lián)網(wǎng)的安全因此無法得到保障。

本文提出了一種改進(jìn)的AC-BM匹配算法，該算法能夠充分利用匹配過程中匹配失敗的信息，以達(dá)到每一次跳躍中跳躍盡量大的距離，從而使算法的執(zhí)行更加快速。將此算法應(yīng)用于數(shù)據(jù)過濾系統(tǒng)中，能夠明顯改善過濾系統(tǒng)的性能，使得過濾系統(tǒng)能夠應(yīng)對當(dāng)前海量的數(shù)據(jù)環(huán)境，廣大網(wǎng)民能夠更加安全地享受互聯(lián)網(wǎng)。

1 模式匹配算法簡介

1.1 單模式匹配算法

經(jīng)典的單模式匹配算法包括KMP算法［2］、BM算法等。下面主要簡要分析這兩種算法。

KMP算法由3個人共同提出，K，M，P分別是3人名字的首個字母。該算法是在BF算法的基礎(chǔ)上改進(jìn)而來。KMP算法創(chuàng)造性地消除了指針回溯，利用已經(jīng)匹配的字符來確定下一次搜索的開始位置，進(jìn)而將模式串移動后繼續(xù)進(jìn)行匹配。時間復(fù)雜度由BF算法中的O（mn）降低為O（m+n）。

BM算法因其由Boyer和Moore提出而得名，該算法的基本思想是從待匹配文本的右邊向左邊依次進(jìn)行比較。當(dāng)某趟比較過程中失配情況發(fā)生時，該算法會利用壞字符和好后綴信息實現(xiàn)跳躍，這種方式能夠很大程度上降低字符比較的次數(shù)，理想狀態(tài)下，算法的時間復(fù)雜度可達(dá)O（n/m）。

總的來說，BM算法相比KMP算法簡單，效率更高，實用性也更強，是目前單模式匹配算法中最優(yōu)的算法。實踐證明，BM算法執(zhí)行速度比 KMP算法速度快3～5倍，但在短模式串情況下，BM算法的優(yōu)勢就沒那么明顯了。同時，模式集規(guī)模較大時，BM算法的效率難以滿足實際要求。再者，它使用了兩個數(shù)組，預(yù)處理開銷大。

1.2 多模式匹配算法

1.2.1 AC算法

Aho—Corasick自動機算法［3］（AC算法）是多字符串匹配中經(jīng)典的算法，1975年產(chǎn)生于貝爾實驗室，可被看作是KMP算法的改進(jìn)，而它的創(chuàng)造性在于它在進(jìn)行匹配之前對模式集進(jìn)行處理，使得匹配效率不再受到模式集合規(guī)模的制約。對模式集進(jìn)行處理的預(yù)先處理實質(zhì)上就是創(chuàng)建3個表的過程，它們分別是goto表、fail表和output表。goto表可以理解為模式集的狀態(tài)轉(zhuǎn)換表，當(dāng)goto表無法查詢到時使用fail表，而output表則是用來記錄當(dāng)前位置是否成功匹配某種模式。此算法的時間復(fù)雜度可達(dá)O（n），并且時間復(fù)雜度與模式串的數(shù)目和長度無關(guān)。

AC多模匹配算法具有如下特點:

1）算法相對簡單、效率高（一次掃描可以完成所有模式的匹配）。

2）與模式串長度和待匹配文本內(nèi)容沒有關(guān)聯(lián)。

3）適用范圍廣（算法適用任意字符）。

該算法的不足之處在于它對內(nèi)存空間需求比較大。一旦匹配模式集合規(guī)模龐大，內(nèi)存空間使用量會急劇增加，甚至可能導(dǎo)致系統(tǒng)崩潰。

1.2.2 AC-BM算法

AC算法的最突出的特點就是一次掃描可以匹配所有模式，BM算法最突出的特點在于它能夠通過跳躍匹配降低比較次數(shù)。AC-BM算法的本質(zhì)就是將這兩個算法的優(yōu)點結(jié)合產(chǎn)生的一種新的算法。

同AC算法一樣，AC-BM算法會在匹配之前對模式集合進(jìn)行預(yù)先處理，匹配時，采取自后向前的方法，一旦模式確定在適當(dāng)?shù)牡胤?，從左到右判斷是否匹配成功?/p>

在此過程中，借用了BM算法的好前綴跳轉(zhuǎn)（Good Prefix Shift）和壞字符跳轉(zhuǎn)（Bad Character Shift）技術(shù)。

所謂好前綴跳轉(zhuǎn)，就是當(dāng)待匹配字符與模式樹某個模式中的字符A不匹配時，利用字符A之前已匹配的字符串S查詢模式樹，計算距該模式樹中下一個出現(xiàn)字符串S的距離L1，將模式樹向前移動L1后繼續(xù)進(jìn)行匹配。

壞字符跳轉(zhuǎn)，就是當(dāng)待匹配字符與模式樹某個模式中的字符A不匹配時，計算該模式樹中距離下一個A字符的距離L2，將模式樹向前移動L2后繼續(xù)進(jìn)行匹配。如果字符A在模式樹中不存在，那么移動距離可以達(dá)到最小字符串長度。

AC-BM算法結(jié)合多模式匹配AC和單模式匹配BM兩者的優(yōu)點，即一次掃描過程完成所有模式的匹配又可以在模式匹配的過程中跳過不必要的字符匹配過程，因此AC-BM算法具有更高的匹配效率。它的這些優(yōu)點可以有效提高數(shù)據(jù)過濾系統(tǒng)的性能。但是，AC—BM算法的效率仍然無法使當(dāng)前過濾系統(tǒng)的性能足以應(yīng)對海量的數(shù)據(jù)環(huán)境，因此需要對AC—BM算法進(jìn)行進(jìn)一步改進(jìn)和優(yōu)化，使它能夠給過濾系統(tǒng)的性能帶來提升。

2 AC-BM算法的改進(jìn)

進(jìn)一步提高模式匹配算法效率的主要途徑是利用模式串匹配失敗時可以獲取的信息以進(jìn)一步增大跳躍距離。受BMH算法思想的啟發(fā)，減少好后綴跳轉(zhuǎn)的比較步驟后，算法的實際性能并不比BM算法差，相反，在某些情況下性能比BM算法優(yōu)越［4］。因此，可以通過簡化AC-BM算法的復(fù)雜性，同時對壞字符跳轉(zhuǎn)進(jìn)行改進(jìn)，形成一種新的算法。

該算法的核心思想是:匹配的過程中模式串從左向右依次進(jìn)行比較，當(dāng)匹配過程中遇到失配字符時，繼續(xù)判斷文本后一字符是否存在于模式樹中，如果當(dāng)前字符和后一字符不存在于模式樹當(dāng)中，就可以直接跳過模式樹最小字符串長度加1再進(jìn)行比較。相比AC-BM算法，突破了無法跳躍大于最大字符串長度的限制，從而減少了比較的次數(shù)。如果在模式串中，則跳轉(zhuǎn)到下一個同時出現(xiàn)當(dāng)前字符和下一字符的位置。

與AC-BM的壞字節(jié)相比，在失配的情況下，采用兩個字節(jié)來查找下一個匹配的位置，無疑加大了失配時的跳躍距離。此外，省去了好前綴跳轉(zhuǎn)步驟，簡化了算法，提升了效率。

算法的整個過程可以按時間先后分為模式集的預(yù)先處理階段和字符的匹配階段。下面將對這兩個階段的處理過程進(jìn)行介紹。

2.1 預(yù)處理階段

假設(shè)待匹配的文本字符串為Text，長度為N，模式字符串為P，模式個數(shù)為k，字符集合為Σ，模式集合中最短模式的長度為Lmin。模式集合的預(yù)處理階段首先將模式集合P中所有模式按照AC算法的預(yù)處理方式構(gòu)成模式樹，之后再構(gòu)造一個跳躍數(shù)組skip［x1］［x2］（x1和x2為字符集Σ上的字符）。

2.2 匹配階段

從樹的根字符開始逐個與文本字符串Text進(jìn)行比較，如果出現(xiàn)了不匹配字符，讀取文本字符串Text字符T（i）的下一字符T（i+1），在skip表中查找下一個出現(xiàn)T［i］T［i+1］的位置。若找不到，則移動模式樹，將模式樹向右移動Lmin+1，若找到，則移動模式樹相應(yīng)距離，與第一次出現(xiàn)T［i］T［i+1］字符的位置對齊。當(dāng)整個文本字符搜索完成或者匹配成功時返回匹配結(jié)果。

改進(jìn)的AC-BM算法對應(yīng)的偽代碼將展示該算法的具體實現(xiàn)過程，如下:

算法的改進(jìn)主要體現(xiàn)在:

1）利用兩個元素來定位跳轉(zhuǎn)位置，能夠加大失配時的移動距離，從而減少比較次數(shù)。

2）修改了壞字符跳轉(zhuǎn)距離的計算方法，使其只與當(dāng)前匹配字符有關(guān)，而與當(dāng)前節(jié)點無關(guān)。

對偶句在我國古代文學(xué)作品中是極得作家青睞的，它句式整齊，讀起來朗朗上口。據(jù)筆者統(tǒng)計，《卜算子》中不僅對偶句數(shù)眾多，且對偶形式豐富多樣。

3）取消了好前綴跳轉(zhuǎn)的計算，計算得到了簡化，效率相應(yīng)得到提升。

3 算法性能測試

3.1 測試環(huán)境

測試中硬件環(huán)境是采用:CPU Intel Pentium 4，主頻1.70 GHz，內(nèi)存2 Gbyte，redhat 9.0平臺上進(jìn)行測試。算法用C語言實現(xiàn)，編譯器采用gcc version 4.1.2，優(yōu)化開關(guān)全部打開。

3.2 測試結(jié)果

3.2.1 時間測試

時間測試主要的目的是為了比較各個算法在外部環(huán)境相同的情況下處理不同模式集合所需的時間。

首先測試模式數(shù)量和匹配時間之間的關(guān)系。測試過程中選擇的模式長度為20 byte，記錄4種算法完成匹配過程所耗時間數(shù)據(jù)，根據(jù)測試數(shù)據(jù)繪制匹配時間-模式數(shù)量圖。圖1中顯示，改進(jìn)算法相比其他3種算法在模式數(shù)量較小和模式數(shù)量較大的情況下性能都得到了較大改善，與預(yù)期結(jié)果一致。

圖1 匹配時間-模式數(shù)量曲線

接著測試模式長度和匹配時間之間的關(guān)系。模式數(shù)量固定在1 000個的情況下，記錄4種算法完成匹配過程所耗時間數(shù)據(jù)，根據(jù)測試數(shù)據(jù)繪制匹配時間-模式長度關(guān)系圖。圖2中顯示，改進(jìn)算法相比其他3種算法在長模式和短模式的情況下性能都得到了較大改善，與預(yù)期結(jié)果一致。

圖2 匹配時間-模式長度曲線

3.2.2 空間測試

圖3 不同算法的內(nèi)存消耗

通過對各個算法進(jìn)行時間和空間的測試可以得出如下結(jié)論:

1）改進(jìn)的匹配效率不受模式個數(shù)的限制。

2）改進(jìn)的匹配算法在模式長度較小和較大時匹配效率都較高，能夠很好地抵抗短模式長度帶來的性能低下。

3）改進(jìn)的算法對消耗內(nèi)存資源的消耗并沒有很大的增長。

圖4 內(nèi)容過濾系統(tǒng)的一般模型

4 改進(jìn)算法在內(nèi)容過濾系統(tǒng)中的應(yīng)用

數(shù)據(jù)過濾系統(tǒng)是保護(hù)網(wǎng)絡(luò)安全的一道重要防線，它通過對網(wǎng)絡(luò)數(shù)據(jù)內(nèi)容進(jìn)行匹配，能夠有效發(fā)現(xiàn)不良信息及違法信息，即時阻止其在網(wǎng)絡(luò)中的傳播和蔓延，從而保證網(wǎng)絡(luò)的安全。內(nèi)容過濾系統(tǒng)處理的對象主要是文本數(shù)據(jù)，在互聯(lián)網(wǎng)中，需要處理的文本數(shù)據(jù)量非常的龐大，因此對內(nèi)容過濾系統(tǒng)的性能要求很高。

內(nèi)容過濾系統(tǒng)根據(jù)功能可以劃分為3個模塊（圖4），分別為數(shù)據(jù)采集模塊、數(shù)據(jù)還原模塊和過濾模塊。采集模塊負(fù)責(zé)將網(wǎng)絡(luò)中傳輸?shù)腗AC幀進(jìn)行處理，還原出TCP和UDP流。TCP和UDP流經(jīng)過還原模塊后得到大量的文本數(shù)據(jù)，之后發(fā)送給過濾模塊進(jìn)行文本過濾。

過濾模塊的工作過程分為兩個階段，首先匹配算法的預(yù)處理階段，會將用戶的需求以規(guī)則串的形式構(gòu)建狀態(tài)機和規(guī)則相應(yīng)的失配跳躍表skip，在信息匹配階段，系統(tǒng)會對待過濾的文本數(shù)據(jù)進(jìn)行預(yù)先處理，之后對文本信息進(jìn)行匹配，實時將匹配結(jié)果發(fā)送給用戶。

5 小結(jié)

本文通過對各種匹配算法進(jìn)行分析，進(jìn)而提出了一種改進(jìn)的算法。改進(jìn)的算法在進(jìn)行模式匹配時執(zhí)行速度得到了明顯提升。盡管空間上比AC-BM算法增加了一些額外開銷，但它使得數(shù)據(jù)過濾系統(tǒng)的性能得到較大提升，綜合考慮，這種空間換時間的方法是值得的。

：

［1］耿金秀.淺談計算機網(wǎng)絡(luò)安全防范措施［J］.中國科技信息，2011（8）:110-111.

［2］朱嬌嬌，葉猛.多模式匹配及其改進(jìn)算法在協(xié)議識別中的應(yīng)用［J］.電視技術(shù)，2012，36（7）:60-63.

［3］KUNTH D E，MORRIS J H，PRATT V R.Fast pattern matching in strings［J］.SIAM Journal on Computing，1977，6（2）:323-350.

［4］NIGEL HR.Practical fast searching in strings［J］.Software Practice and Experience，1980，10（6）:501-506.