余 飛

(安徽電子信息職業(yè)技術(shù)學(xué)院 安徽蚌埠 233030)

隨著大數(shù)據(jù)與網(wǎng)絡(luò)技術(shù)的快速發(fā)展，每天所產(chǎn)生的數(shù)據(jù)信息量呈指數(shù)級增長。如何對互聯(lián)網(wǎng)數(shù)據(jù)流量進(jìn)行高效快速的處理，已經(jīng)成為當(dāng)今信息安全研究的重要方向。大數(shù)據(jù)具有4V特性，即體量巨大(volume)、類型繁多(variety)、時效性高(velocity)以及價值高密度低(value)[1]，傳統(tǒng)的數(shù)據(jù)處理方法很難應(yīng)對，大數(shù)據(jù)檢索與快速匹配已經(jīng)成為很多系統(tǒng)應(yīng)用需要解決的問題。如防火墻數(shù)據(jù)過濾、入侵檢測系統(tǒng)、天氣股票分析與預(yù)測等應(yīng)用，都離不開模式匹配算法。

模式匹配算法是數(shù)據(jù)檢索與快速匹配技術(shù)的核心。模式匹配算法有兩種分為單模式匹配算法和多模式匹配算法。單模式匹配算法在文本串中只能尋求一個模式串的匹配結(jié)果，而多模式匹配算法是一個模式集合即多個模式串在文本串中快速匹配的方法。對單模式匹配算法的研究是多模式匹配算法的基礎(chǔ)，而在現(xiàn)實中多模式匹配算法具有更為廣泛的應(yīng)用。例如，在網(wǎng)絡(luò)海量的數(shù)據(jù)中檢測某些特征值來識別非法信息與網(wǎng)絡(luò)攻擊；應(yīng)用在生物信息DNA搜索識別中[2]，對DNA序列進(jìn)行大量精確模式搜索，改變了以前DNA序列近似搜索的狀況；網(wǎng)站數(shù)據(jù)的搜索與處理等。

1 模式匹配算法的概念

單模式匹配算法的數(shù)學(xué)模型可描述為：文本串為T[0，1，2……n-1]，長度為n；模式串P[0，1，2……m-1]，長度為m。對于給定的文本串T，判斷模式串是否在該文本串中出現(xiàn)。如果出現(xiàn)，則稱匹配成功；如果沒有出現(xiàn)，則稱匹配失敗。當(dāng)前主流的單模式匹配算法有BM、BMH等。

多模式匹配算法的數(shù)學(xué)模型可描述為，文本串為T[0，1，2……n-1]，長度為n；模式集合為P{p1，p2，p3，……，pk}，長度為k，其中最短的模式串長度為m；P和T的字符均來自字母集∑。多模式匹配算法是指對于給定的文本串T，判斷模式集合P中的每個模式串是否在該文本串中出現(xiàn)。如果出現(xiàn)，則稱匹配成功；如果沒有出現(xiàn)，則稱匹配失敗。當(dāng)前主流的多模式匹配算法可分為兩種，基于前綴匹配算法AC和基于后綴啟發(fā)式搜索算法WM。

2 模式匹配算法的的主要種類

2.1 單模式匹配算法(BMH)

BMH(boyer-moore-horspool)算法是基于壞字符后綴的單模式匹配算法，主要利用Badchar函數(shù)進(jìn)行跳轉(zhuǎn)與偏移。具體思想是：模式串P與文本串T進(jìn)行匹配，首先從右向左比較P[m-1]和T[j+m-1]，若相同則繼續(xù)比較P[m-2]和T[j+m-2]，….，一直比較直P[0]與T[j]為止。如果都相同，則匹配成功。如果中間發(fā)現(xiàn)P[i]與T[j+i]不相等[3]，則分為如下兩種情況：

(1)在P[i]與T[j+i]處失配，但T[j+i]…T[j+m-1]與P[i]…P[m-1]都是匹配的，這些相同的字符串，標(biāo)記為u。在u中，最后一個字符T[j+m-1]，標(biāo)記為d。如果在模式串P中，除P[m-1]外，還能找到P[k]處值為d。則模式串P向右滑動，讓T[j+m-1]與P[k]對齊，并從模式串末端開始，從右向左繼續(xù)比較[3]。

(2)如果在模式串P中，除P[m-1]外，沒有找到d。則模式串P直接向右滑動m位，并從模式串末端開始，從右向左開始新的一輪比較，如圖1所示。

圖1 BMH算法找壞字符的偏移情況

2.2 多模式匹配算法(AC)

2.2.1 算法原理分析 AC(aho cora sick)算法是一種基于前綴匹配的多模式匹配算法。它構(gòu)造有限狀態(tài)自動機(jī)，基于自動機(jī)掃描文本串中的每一個字符，根據(jù)自動機(jī)進(jìn)行狀態(tài)跳轉(zhuǎn)和狀態(tài)判斷，從而進(jìn)行模式匹配。AC算法需要goto表、fail表、output表來完成，3個表的功能如下：

(1)goto表中的內(nèi)容是由P中的所有模式串構(gòu)造的有窮狀態(tài)自動機(jī)。構(gòu)造AC算法中的Tree狀結(jié)構(gòu)，通過goto函數(shù)讀入P中的每一個模式串，創(chuàng)建該模式的分支，并把該分支添加進(jìn)Tree狀結(jié)構(gòu)中，如果該模式的分支在Tree狀結(jié)構(gòu)之前已有重復(fù)的部分，則利用該重復(fù)的部分進(jìn)行創(chuàng)建，在最后一個字符標(biāo)記為終止?fàn)顟B(tài)。

(2)fail表記錄當(dāng)狀態(tài)自動機(jī)處的某個狀態(tài)，即輸入模式串，讀入文本串T的字符按照狀態(tài)機(jī)進(jìn)行狀態(tài)跳轉(zhuǎn)，當(dāng)狀態(tài)失效即匹配失敗時，fail函數(shù)則根據(jù)有窮狀態(tài)自動機(jī)計算其跳轉(zhuǎn)狀態(tài)。跳轉(zhuǎn)深度最大的狀態(tài)就是fail表中對應(yīng)的那個狀態(tài)。

(3)每一個狀態(tài)都有一個output表。output表記錄的是狀態(tài)達(dá)到終止?fàn)顟B(tài)時，模式串的集合。當(dāng)構(gòu)造goto表Tree狀結(jié)構(gòu)時，每添加一個模式分支，最后一個字符狀態(tài)都會加上一個output表，在構(gòu)造fail表的過程中，所有狀態(tài)最后無論是失效、跳轉(zhuǎn)還是匹配等，其終止?fàn)顟B(tài)都會被寫入output表。

2.2.2 原理示例 以模式集合P={ma，sma，mis，maps}為例構(gòu)建有限狀態(tài)自動機(jī)，goto表構(gòu)建的Tree狀結(jié)構(gòu)如圖2所示。

圖2 有限狀態(tài)自動機(jī)示例

AC算法的掃描過程為：輸入模式P，讀入文本T的每一個字符，依據(jù)狀態(tài)機(jī)進(jìn)行跳轉(zhuǎn)，當(dāng)失效時，則依照fail表進(jìn)行跳轉(zhuǎn)，按照找各種方法對字符進(jìn)行掃描，最后根據(jù)output表將匹配的模式進(jìn)行輸出。fail表如表1所示，output表如表2所示。

表1 fail表

表2 output表

2.2.3 優(yōu)缺點(diǎn)分析 AC算法最大的優(yōu)點(diǎn)是效率高，利用有窮狀態(tài)自動機(jī)可以從一個狀態(tài)直接跳轉(zhuǎn)到另一個狀態(tài)，實現(xiàn)跳躍式匹配。而文本串T的長度與復(fù)雜性對算法的匹配效率基本上沒有影響，算法設(shè)計完善運(yùn)行穩(wěn)定。長度為L的文本串，算法的初始化時間復(fù)雜度為O(|P|)，匹配時間復(fù)雜度為O(L)。AC算法的缺點(diǎn)是需要占用大量的存儲空間來構(gòu)建狀態(tài)機(jī)，若模式集合的大小為∏，自動機(jī)所造成的空間復(fù)雜度為O(|∏||P|)，模式P越大，該算法占用的內(nèi)存空間呈指數(shù)級上升，將會形成內(nèi)存墻[4]的問題，很難適應(yīng)大規(guī)模的模式集合。當(dāng)前AC算法的改進(jìn)大多數(shù)都是在專有硬件上提出優(yōu)化[5]。

2.3 經(jīng)典算法(WM)

2.3.1 算法原理分析 WM(Wu Manber)算法是一種基于后綴掃描的多模式匹配算法。該算法使用壞字符的匹配思想，以模式集合P中最短模式串的長度m做為掃描窗口的大小，進(jìn)行最大距離的跳轉(zhuǎn)。掃描窗口的數(shù)據(jù)結(jié)構(gòu)由Hash表、Shift表、Prefix表構(gòu)成，這三個表是由模式集合的每一個模式截取其前m個字符串來構(gòu)造的，構(gòu)造規(guī)則(如圖3所示)如下：

(1)Hash表。模式集合的每一個模式截取其前m個字符的最后長度為B的字符塊，計算Hash值，形成Hash表的每一項里是該Hash值的模式鏈接成的模式鏈表[6]。

(2)Shift表。主要用于計算和記錄當(dāng)字符不匹配時跳轉(zhuǎn)的距離。利用模式集合中所有模式串的前m個字符來構(gòu)建Shift表，在選取B時通常選擇2或者3。在構(gòu)建Shift表的過程中，若字符塊L在模式集合的模式串中，則選擇L在模式集合的最靠右的位置；若L沒有出現(xiàn)在模式集合中，則Shift[L]=m-B+1[7]。

(3)Prefix表。當(dāng)模式集合較大時，Hash計算容易產(chǎn)生沖突，Prefix表記錄模式前幾個字符的Hash值，能避免相同后綴Hash值的集合過大，從而提高掃描效率。

圖3 WM算法三個表的數(shù)據(jù)結(jié)構(gòu)

算法過程為：以模式集合中模式最短長度m計算和設(shè)定掃描窗口，計算后綴字符B的Hash值h，并在Hash表中查找h，若找到則查看Shift表，若沒有找到，則跳轉(zhuǎn)m-B+1個字符。如果跳轉(zhuǎn)距離為0，則計算前綴的Hash值，找到Prefix表相應(yīng)的值，再進(jìn)行掃描來判斷模式是否命中。如果跳轉(zhuǎn)距離為正數(shù)，則按照這個數(shù)值進(jìn)行跳轉(zhuǎn)。

2.3.2 優(yōu)缺點(diǎn)分析 WM算法主要是基于Hash值尋找不能匹配的壞字符塊進(jìn)行跳躍匹配，提高算法效率。匹配成功時，時間復(fù)雜度為O(m)，掃描過程的時間復(fù)雜度為O(BN/m)[7]。不同于AC算法，WM算法空間使用率較低，匹配的模式數(shù)量與存儲空間線性增長，內(nèi)存占用很小，掃描快速穩(wěn)定，非常適合大規(guī)模數(shù)據(jù)的處理。但當(dāng)有很多短模式在模式集合中時，跳轉(zhuǎn)效率將會明顯降低，因此使用該算法要注意其模式集合中較短模式的數(shù)量。

3 結(jié)語

文章探討了大數(shù)據(jù)下用于互聯(lián)網(wǎng)數(shù)據(jù)流量處理的數(shù)據(jù)檢索與快速匹配技術(shù)，研究了該技術(shù)的核心算法—模式匹配算法。該算法分為單模式匹配算法和多模式匹配算法，單模式匹配經(jīng)典算法BMH通過Badchar函數(shù)進(jìn)行跳躍式匹配；多模式匹配算法能夠?qū)σ粋€模式集合的多個模式同時進(jìn)行匹配，具有很強(qiáng)的實用價值，經(jīng)典算法有AC和WM算法。AC算法構(gòu)造的有窮狀態(tài)自動機(jī)較為消耗內(nèi)存，適合用于模式較少的情況；WM算法占用內(nèi)存較少，適合于短模式較少的大數(shù)據(jù)流量的處理。