大數(shù)據(jù)下模式匹配算法研究*

余 飛

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

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

模式匹配算法是數(shù)據(jù)檢索與快速匹配技術(shù)的核心。模式匹配算法有兩種分為單模式匹配算法和多模式匹配算法。單模式匹配算法在文本串中只能尋求一個(gè)模式串的匹配結(jié)果，而多模式匹配算法是一個(gè)模式集合即多個(gè)模式串在文本串中快速匹配的方法。對(duì)單模式匹配算法的研究是多模式匹配算法的基礎(chǔ)，而在現(xiàn)實(shí)中多模式匹配算法具有更為廣泛的應(yīng)用。例如，在網(wǎng)絡(luò)海量的數(shù)據(jù)中檢測(cè)某些特征值來識(shí)別非法信息與網(wǎng)絡(luò)攻擊；應(yīng)用在生物信息DNA搜索識(shí)別中[2]，對(duì)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。對(duì)于給定的文本串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的字符均來自字母集∑。多模式匹配算法是指對(duì)于給定的文本串T，判斷模式集合P中的每個(gè)模式串是否在該文本串中出現(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中，最后一個(gè)字符T[j+m-1]，標(biāo)記為d。如果在模式串P中，除P[m-1]外，還能找到P[k]處值為d。則模式串P向右滑動(dòng)，讓T[j+m-1]與P[k]對(duì)齊，并從模式串末端開始，從右向左繼續(xù)比較[3]。

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

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

2.2 多模式匹配算法(AC)

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

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

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

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

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

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

AC算法的掃描過程為：輸入模式P，讀入文本T的每一個(gè)字符，依據(jù)狀態(tài)機(jī)進(jìn)行跳轉(zhuǎn)，當(dāng)失效時(shí)，則依照fail表進(jìn)行跳轉(zhuǎn)，按照找各種方法對(duì)字符進(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)自動(dòng)機(jī)可以從一個(gè)狀態(tài)直接跳轉(zhuǎn)到另一個(gè)狀態(tài)，實(shí)現(xiàn)跳躍式匹配。而文本串T的長度與復(fù)雜性對(duì)算法的匹配效率基本上沒有影響，算法設(shè)計(jì)完善運(yùn)行穩(wěn)定。長度為L的文本串，算法的初始化時(shí)間復(fù)雜度為O(|P|)，匹配時(shí)間復(fù)雜度為O(L)。AC算法的缺點(diǎn)是需要占用大量的存儲(chǔ)空間來構(gòu)建狀態(tài)機(jī)，若模式集合的大小為∏，自動(dòng)機(jī)所造成的空間復(fù)雜度為O(|∏||P|)，模式P越大，該算法占用的內(nèi)存空間呈指數(shù)級(jí)上升，將會(huì)形成內(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)成，這三個(gè)表是由模式集合的每一個(gè)模式截取其前m個(gè)字符串來構(gòu)造的，構(gòu)造規(guī)則(如圖3所示)如下：

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

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

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

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

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

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

3 結(jié)語

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