面向長(zhǎng)模式串的改進(jìn)型AC算法研究

◆岳小偉 詹 瞻

?

面向長(zhǎng)模式串的改進(jìn)型AC算法研究

◆岳小偉 詹 瞻

（信息工程大學(xué) 河南 450001）

在面向?qū)崟r(shí)數(shù)據(jù)流的分類研究中，基于AC算法的多模匹配已具備一定的應(yīng)用基礎(chǔ)。本文針對(duì)數(shù)據(jù)流中的長(zhǎng)模式串特征，提出了AC_TE算法的改進(jìn)算法——AC_LSE算法，適用于高速實(shí)時(shí)網(wǎng)絡(luò)數(shù)據(jù)流的識(shí)別分類。該算法利用1個(gè)Hash表存儲(chǔ)當(dāng)前匹配窗口對(duì)應(yīng)的不同前綴字符串的跳轉(zhuǎn)距離，需要進(jìn)行跳轉(zhuǎn)時(shí)，直接查找Hash表進(jìn)行跳轉(zhuǎn)，減少了字符比較和查找開銷，提高了多模匹配的效率。實(shí)驗(yàn)結(jié)果表明，該算法在多模匹配的速度和比較次數(shù)上，均優(yōu)于AC_TE算法，在長(zhǎng)模式串的匹配上性能更佳。

數(shù)據(jù)流分類；AC_LSE算法；跳轉(zhuǎn)距離；Hash表

0 引言

模式匹配時(shí)是指在目標(biāo)序列中查找模式串的過程，若找到則匹配成功，否則匹配失敗，即失配。隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)呈現(xiàn)出爆炸性增長(zhǎng)的態(tài)勢(shì)，如何有效地將這些數(shù)據(jù)進(jìn)行分類和解析，已成為當(dāng)前互聯(lián)網(wǎng)技術(shù)發(fā)展亟需解決的問題。在實(shí)時(shí)數(shù)據(jù)流分類應(yīng)用中，多模匹配已成為一種關(guān)鍵技術(shù)，特別是針對(duì)高速數(shù)據(jù)流實(shí)時(shí)處理，在已掌握大量應(yīng)用數(shù)據(jù)特征的前提下，處理效率是考察系統(tǒng)的重要指標(biāo)，直接影響分類器的性能。

在已有的研究中，文獻(xiàn)[1]中的KMP算法是由是由Knuth等人提出的一種單模匹配算法，對(duì)于任何模式和目標(biāo)序列，均在線性時(shí)間內(nèi)完成匹配查找，算法的時(shí)間復(fù)雜度為O(n + m)；文獻(xiàn)[2]中的BM算法是由Boyer和Moore提出的一種基于后綴匹配的單模匹配算法，為了使模式串高效的移動(dòng)，算法定義了兩個(gè)規(guī)則：壞字符規(guī)則和好后綴規(guī)則，根據(jù)兩者的較大值來確定跳轉(zhuǎn)距離；1975年貝爾實(shí)驗(yàn)室的Aho和Corasick提出了AC算法[3]，該算法基于不確定的有限自動(dòng)機(jī)，對(duì)于長(zhǎng)度為n的目標(biāo)序列，算法能在線性時(shí)間復(fù)雜度內(nèi)，找到文本中的所有模式，與模式集規(guī)模無關(guān)；文獻(xiàn)[4]中Coit、Staniford 和McAlerney將AC算法的自動(dòng)狀態(tài)機(jī)和BM算法的啟發(fā)式跳躍策略相結(jié)合，提出了AC_BM算法，利用兩者的優(yōu)點(diǎn)，效率同時(shí)優(yōu)于AC算法和BM算法；文獻(xiàn)[6]的AC_BHM算法和文獻(xiàn)[7]的AC_QSS算法，均在AC算法的基礎(chǔ)上進(jìn)行改進(jìn)，但模式樹的最大移動(dòng)距離仍為最短模式串長(zhǎng)度，沒有提高最大移動(dòng)距離；文獻(xiàn)[8]將AC算法和SUNDAY算法相結(jié)合提出的AC_SUNDAY算法，使模式樹的最大移動(dòng)距離達(dá)到minlen+1，最大移動(dòng)距離增加不明顯。文獻(xiàn)[5]中的AC_TE算法根據(jù)當(dāng)前匹配窗口的前3個(gè)字符，生成1個(gè)字符串跳躍表和2個(gè)哈希表來確定移動(dòng)距離，使模式樹的最大移動(dòng)距離增加為最短模式串長(zhǎng)度加3。與AC算法相比，AC_TE算法在匹配速度上有了極大的提升，但算法的預(yù)處理步驟復(fù)雜，在匹配過程中會(huì)增加不必要字符的比較和哈希查找開銷，而針對(duì)實(shí)時(shí)數(shù)據(jù)流進(jìn)行分類，需要較高的處理速度，否則極易出現(xiàn)丟包現(xiàn)象，影響分類結(jié)果的準(zhǔn)確性。本文從減少AC_TE算法字符比較和減少哈希查找開銷的角度，提出了一種用空間開銷換取處理效率的AC_LSE（LONG STRING EFFICIENT）算法。

1 AC_TE算法

AC_TE算法是在AC算法的基礎(chǔ)上，根據(jù)當(dāng)前匹配窗口的前3個(gè)字符，設(shè)計(jì)出一種新的模式樹移動(dòng)規(guī)則，在預(yù)處理階段生成1個(gè)字符串跳躍表和2個(gè)哈希表，用于輔助計(jì)算模式樹的移動(dòng)距離。匹配階段則根據(jù)這3個(gè)字符在不同條件下，比較和查找對(duì)應(yīng)的哈希表，然后計(jì)算出模式樹的移動(dòng)距離。該算法的主要思想是利用當(dāng)前匹配窗口前綴的不同，在掃描過程中盡可能跳過更多字符，即增加模式樹的移動(dòng)距離，提高了匹配速度。

1.1預(yù)處理階段

（1）構(gòu)建模式樹

從模式樹的根節(jié)點(diǎn)開始，遍歷所有的模式串，將模式串的每一個(gè)字符，放到模式樹上成為一個(gè)節(jié)點(diǎn)。每個(gè)字符的前一字符所對(duì)應(yīng)的節(jié)點(diǎn)，都為該字符對(duì)應(yīng)節(jié)點(diǎn)的父節(jié)點(diǎn)。如果該字符對(duì)應(yīng)的節(jié)點(diǎn)已經(jīng)存在，則不再添加新的節(jié)點(diǎn)。記錄每個(gè)模式串的最后一個(gè)字符對(duì)應(yīng)節(jié)點(diǎn)為結(jié)束節(jié)點(diǎn)，當(dāng)匹配成功時(shí)，進(jìn)行輸出。以模式集P={hers，his，here}為例，構(gòu)建的模式樹如圖1所示。

圖1 模式樹

（2）創(chuàng)建SST表（字符串跳躍表）

SST表記錄了minlen深度內(nèi)兩兩相鄰字符組成的字符串到模式樹根節(jié)點(diǎn)的距離，記為depth(S)，其中S=Pi[m]Pi[m+1]，1≤i≤r，1≤m≤minlen-1，則depth(S)=m-1，如果S出現(xiàn)多次，則取最小值。在模式集P={hers，his，here}中，最短模式為his，長(zhǎng)度為3，則SST表包含{he，er，hi，is}，depth(he)=depth(hi)=0，depth(er)=depth(is)=1。

（3）創(chuàng)建LTST表（末層字符串哈希表）和LCT表（末層字符哈希表）

設(shè)當(dāng)前模式集中最短模式串長(zhǎng)度為minlen，LTST表中記錄了每個(gè)模式串中第minlen-1和minlen層字符組成的字符串；LCT表則記錄了第minlen層字符。在模式集P={hers，his，here}中，LTST和LCT表項(xiàng)分別為{er，is}、{r，s}。

1.2匹配過程

初始時(shí)，將模式樹中最短模式串右端與目標(biāo)序列末端字符對(duì)齊，從模式樹的根節(jié)點(diǎn)開始，按照從左向右的順序進(jìn)行匹配。利用goto函數(shù)進(jìn)行狀態(tài)轉(zhuǎn)移，當(dāng)匹配成功時(shí)則輸出匹配成功的模式串。發(fā)生失配時(shí)，計(jì)算移動(dòng)距離shift length，并將模式樹左移shift length位。重復(fù)此過程，直到模式樹與文本串的首字符對(duì)齊，匹配過程結(jié)束。計(jì)算移動(dòng)距離shift length偽代碼如下：

輸入 SST，LTST，LCT，x，y，z，minlen，其中x,y,z分別表示當(dāng)前匹配窗口的前3、前2和前1字符

輸出 模式樹移動(dòng)距離 shift length

if(z==首字符)

shift length=1；

else if(yz∈SST表)

shift length=depth(yz)+2；

else if(hash(xy)->LIST==true)

shift length=minlen+1；

else if(hash(x)->LCT==true)

shift length=minlen+2；

else

shift length=minlen+3；

返回 shift length

2 AC_LSE算法描述

隨著高性能計(jì)算機(jī)的廣泛運(yùn)用，廉價(jià)的硬件資源可以用于換取處理效率， AC_TE算法中運(yùn)用多張表來計(jì)算模式樹移動(dòng)距離，實(shí)現(xiàn)了模式樹的最大移動(dòng)由最短模式串長(zhǎng)度增加到最短模式串長(zhǎng)度加3，但算法的預(yù)處理步驟復(fù)雜，在匹配過中會(huì)增加不必要字符的比較和哈希查找開銷。在此基礎(chǔ)上，本文針對(duì)AC_TE算法進(jìn)行改進(jìn)，在不影響算法時(shí)間復(fù)雜度和不產(chǎn)生漏檢的前提下，設(shè)計(jì)出更高效的AC_LSE算法，以內(nèi)存開銷換取匹配速度，減少不必要字符的比較和查找開銷，以適應(yīng)實(shí)時(shí)數(shù)據(jù)流分類的需要。改進(jìn)思想如下：

設(shè)當(dāng)前匹配窗口的前3個(gè)字符分別為x，y，z，模式集中最短模式串長(zhǎng)度為minlen，生成的哈希表空間大小為256*256*256*2字節(jié)（有實(shí)驗(yàn)數(shù)據(jù)表明，當(dāng)哈希表負(fù)載不超過50%時(shí)，性能較高），AC_LSE算法生成哈希跳轉(zhuǎn)表規(guī)則如下：

（1） 初始化設(shè)置所有的Hash表空間的值為最短模式串長(zhǎng)度加3，即hash[*,*,*] = minlen+3，其中*表示任意ASCII表字符；

（2） 對(duì)于任一模式串，如果x與模式串第minlen層字符相同，則移動(dòng)距離為minlen+2，即hash[x,*,*] = minlen+2；

（3） 如果xy組成的字符串與任一模式串第minlen-1和第minlen層字符組成的字符串相同，則移動(dòng)距離為minlen+1，即hash[x,y,*] = minlen+1；

（4） 如果yz組成的字符串在模式樹minlen深度內(nèi)出現(xiàn)，則選取到模式樹首層字符距離最短的出現(xiàn)位置，記為depth(yz)，則移動(dòng)距離為depth(yz)+2，即hash[*,y,z]=depth(yz)+2；

（5） 如果z為模式樹首層字符，則移動(dòng)距離為1，即hash[*,*,z]=1。

生成Hash跳轉(zhuǎn)表的偽代碼如下，

輸入 P={P1, P2,…，Pr},最短模式串長(zhǎng)度minlen，depth(Pi[m]Pi[m+1])，其中1≤i≤r，1≤m≤minlen-1

輸出 Hash跳轉(zhuǎn)表

//算法步驟1

初始化置hash[*,*,*]= minlen+3;

for(i = 1;i <= r;i++) //處理模式集中的每一個(gè)模式串

{ //算法步驟2

for(j = 0;j < 256;j++) {

for(k = 0;k < 256;k++) {

hash[Pi[minlen],ch(j),ch(k)]=minlen+2;

hash[ch[j],ch[k],Pi[0]] = 1;

} }

//算法步驟3

for(k = 1;k < 256;k++) {

hash[Pi[minlen-1],Pi[minlen],ch(k)]=minlen+1;

}

//算法步驟4

for(k = 1;k < 256;k++) {

for(m=1;m <= minlen-1;m++) {

hash[ch(k),Pi[m],Pi[m+1]]=depth(Pi[m]Pi[m+1])+2;

} }

//算法步驟5

for(j = 0;j < 256;j++) {

for(k = 0;k < 256;k++) {

hash[ch[j],ch[k],Pi[0]] = 1;

} } }

返回Hash跳轉(zhuǎn)表

以模式集P={abc，aef，aaaef}為例，最小的模式串長(zhǎng)度為3，SST表項(xiàng)為{ab，bc，ae，ef，aa}，其中SST(ab)=SST(ae)=SST(aa)=0，SST(bc)=SST(ef)=1。設(shè)當(dāng)前目標(biāo)序列T=abcgaaefjkp，則匹配過程如圖2所示，初始時(shí)將最短模式串最右字符與T的末端字符對(duì)齊，發(fā)生失配。此時(shí)xyz=aef，根據(jù)規(guī)則4，ef串a(chǎn)ef和aaaef的子串，hash[*,y,z]=ef最小深度+2=1+2=3，模式樹左移3位，第一次移動(dòng)后匹配出aef。移動(dòng)后xyz=cga，z=a為模式串首字符，此時(shí)根據(jù)規(guī)則5，模式樹左移1位。比較過程中發(fā)生失配，此時(shí)xyz=bcg，根據(jù)規(guī)則3，hash[b,c,*]=minlen+1=3+1=4，第三次移動(dòng)后匹配出abc。

圖2 AC_LSE算法匹配過程

由此可以看出在每一次跳轉(zhuǎn)時(shí)，只需根據(jù)當(dāng)前匹配窗口的前3位字符組成的字符串，結(jié)合預(yù)處理時(shí)生成的哈希表進(jìn)行跳轉(zhuǎn)，而AC_TE算法的匹配過程則需要根據(jù)不同的xyz值進(jìn)行查找比較后再計(jì)算出跳轉(zhuǎn)距離，增加了字符比較和Hash查找開銷。AC_LSE算法通過統(tǒng)一的Hash映射，實(shí)現(xiàn)了跳轉(zhuǎn)長(zhǎng)度的快速查詢，減少了不必要字符的比較，提高了匹配效率。

3 實(shí)驗(yàn)結(jié)果

測(cè)試環(huán)境為Intel(R) Xeon(R) CPU E7-4820 v2 @ 2.00GHz，8核，內(nèi)存256G的Linux X64服務(wù)器。測(cè)試數(shù)據(jù)為從kdd.ics.uci.edu選取英文新聞文本作為匹配輸入，大小為37M，并從文本的隨機(jī)位置生成了長(zhǎng)度為4字節(jié)、8字節(jié)、16字節(jié)、32字節(jié)的模式串各500個(gè)，從算法的執(zhí)行時(shí)間和比較次數(shù)上與AC_TE算法進(jìn)行對(duì)比，測(cè)試結(jié)果如圖3、圖4所示。

圖3 不同長(zhǎng)度模式串匹配耗時(shí)對(duì)比圖

圖4 不同長(zhǎng)度模式串比較次數(shù)對(duì)比圖

圖3和圖4的橫坐標(biāo)表示模式串長(zhǎng)度，縱坐標(biāo)分表表示算法執(zhí)行時(shí)間和比較次數(shù)，執(zhí)行時(shí)間單位為秒（s），每種長(zhǎng)度的模式串個(gè)數(shù)均為500個(gè)。由圖3可知，改進(jìn)后的算法的時(shí)間開銷優(yōu)于AC_TE算法，且隨著模式串長(zhǎng)度越長(zhǎng)，匹配耗時(shí)越短。這是因?yàn)殡S著模式串長(zhǎng)度的增加，失配的概率也隨之增大，從而間接增加了模式樹以最大距離移動(dòng)的概率。圖4則表明改進(jìn)后算法在比較次數(shù)上明顯減少。同時(shí)，將2000個(gè)不同長(zhǎng)度的模式串進(jìn)行匹配驗(yàn)證，AC_TE算法耗時(shí)3.44秒，AC_LSE算法耗時(shí)2.90秒。由實(shí)驗(yàn)結(jié)果不難得出，AC_LSE算法在匹配速度和比較次數(shù)上，均優(yōu)于AC_TE算法。

4 結(jié)語

本文針對(duì)AC_TE算法進(jìn)行優(yōu)化，以空間開銷換取匹配速度的方式，將AC_TE算法的多張規(guī)則表統(tǒng)一映射到一個(gè)統(tǒng)一的Hash空間，減少了比較和查找開銷。通過實(shí)驗(yàn)驗(yàn)證了改進(jìn)算法的效率。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的AC_LSE算法在執(zhí)行時(shí)間和比較次數(shù)上均優(yōu)于AC_TE算法。在數(shù)據(jù)流分類應(yīng)用中，不同應(yīng)用對(duì)應(yīng)數(shù)據(jù)包特征長(zhǎng)度都會(huì)偏長(zhǎng)，這與AC_LSE算法相一致，該算法在數(shù)據(jù)流分類中的應(yīng)用將是本文的后續(xù)課題。

[1]Knuth DE,Morris JH,Pratt VR. Fast pattern matching in strings[J]. SIAM J Comput，1977.

[2]Boyer RS,Moore JS. A fast string searching algorithm[J]. Communications of the ACM，1977.

[3]Aho A V,Corasick M J. Efficient string matching: an aid to bibliographic search[J]. Communications of ACM，1975.

[4]Coit C J,Staniford S. Toward Faster String Matching for Intrusion Detection or Exceeding the Speed of Snort[C]. Proc. of the DISCEX，2001.

[5]劉春暉，黃宇，宋琦.一種改進(jìn)的ＡＣ多模式匹配算法[J].計(jì)算機(jī)工程，2015.

[6]劉升，陳志剛，鄺祝芳.認(rèn)知無線電中結(jié)合差異性的免疫克隆優(yōu)化頻譜分配算法[J].計(jì)算機(jī)工程與科學(xué)，2014.

[7]El-Nainay,Mustafa Y.Island Genetic Algorithm-based Congnitive Networks[D]. Blacksburg,USA: Virginia Polytechnic Institute and State University,2009.

[8]趙知?jiǎng)?基于量子遺傳算法的認(rèn)知無線電頻譜分配[J].物理學(xué)報(bào), 2009.