海量數(shù)據(jù)過濾系統(tǒng)中匹配算法的研究

梁 威，葉 猛

（1.光纖通信技術(shù)和網(wǎng)絡(luò)國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北武漢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)行一些違法犯罪活動(dòng)，如傳播色情信息、暴力信息和反動(dòng)信息等，這些行為會(huì)嚴(yán)重?cái)_亂社會(huì)次序，給人們的日常生活帶來極大危害［1］。因此，如何有效剔除不相關(guān)信息和不良信息，已經(jīng)成為新的研究熱點(diǎn)?；ヂ?lián)網(wǎng)中數(shù)據(jù)過濾系統(tǒng)的出現(xiàn)正是為了應(yīng)對(duì)上述問題。過濾系統(tǒng)的性能低下會(huì)導(dǎo)致網(wǎng)絡(luò)違法犯罪行為不能夠被及時(shí)發(fā)現(xiàn)并制止，因此提升過濾系統(tǒng)的性能十分必要。

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

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

1 模式匹配算法簡(jiǎn)介

1.1 單模式匹配算法

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

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

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

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

1.2 多模式匹配算法

1.2.1 AC算法

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

AC多模匹配算法具有如下特點(diǎn):

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

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

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

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

1.2.2 AC-BM算法

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

同AC算法一樣，AC-BM算法會(huì)在匹配之前對(duì)模式集合進(jìn)行預(yù)先處理，匹配時(shí)，采取自后向前的方法，一旦模式確定在適當(dāng)?shù)牡胤剑瑥淖蟮接遗袛嗍欠衿ヅ涑晒Α?/p>

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

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

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

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

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

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

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

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

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

2.1 預(yù)處理階段

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

2.2 匹配階段

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

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

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

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

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

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

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

3 算法性能測(cè)試

3.1 測(cè)試環(huán)境

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

3.2 測(cè)試結(jié)果

3.2.1 時(shí)間測(cè)試

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

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

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

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

圖2 匹配時(shí)間-模式長(zhǎng)度曲線

3.2.2 空間測(cè)試

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

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

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

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

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

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

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

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

內(nèi)容過濾系統(tǒng)根據(jù)功能可以劃分為3個(gè)模塊（圖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)行文本過濾。

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

5 小結(jié)

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

：

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

［2］朱嬌嬌，葉猛.多模式匹配及其改進(jìn)算法在協(xié)議識(shí)別中的應(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.