基于字符頻率的字符串模式匹配算法的研究

巫喜紅，凌 捷

WU Xi-hong1，LING Jie2

(1. 嘉應(yīng)學(xué)院 計(jì)算機(jī)學(xué)院，梅州 514015；2. 廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510090)

0 引言

網(wǎng)絡(luò)帶給人們方便的同時(shí)也存在安全隱患，而入侵檢測系統(tǒng)(IDS)也越來越廣泛地應(yīng)用到網(wǎng)絡(luò)系統(tǒng)中，因?yàn)樗翘岣呔W(wǎng)絡(luò)系統(tǒng)安全性的重要技術(shù)之一。目前，許多IDS都是依靠模式匹配技術(shù)來進(jìn)行入侵檢測的，但是，在進(jìn)行入侵檢測時(shí)，花費(fèi)在模式匹配上的時(shí)間占到整個(gè)IDS總處理時(shí)間的30%，對(duì)于密集型的流量，這一消耗達(dá)到80%[1]。因此，模式匹配性能的提高成為解決IDS的關(guān)鍵技術(shù)。目前，國內(nèi)外對(duì)于模式匹配算法已有不少的研究成果，比如典型的單模式算法有Brute Force算法[2]、Knuth-Morris-Pratt(KMP)算法[3]、Byoer-Moore(BM)算法[4]、Sunday算法[5]，多模式算法主要有Aho_Corasick(AC)算法[6]、Wu_Mander算法[7]。這些算法在實(shí)際應(yīng)用中忽略了字符串的特征，沒有實(shí)際考慮到字符的頻率情況，為此，本文提出了利用字符統(tǒng)計(jì)特征的算法，在掃描過程中利用某個(gè)頻率字符去進(jìn)行匹配，跳過了一系列無用的字符，從而提高匹配速度。

1 幾種經(jīng)典的模式匹配算法

設(shè)文本串T=T0……Tn-1，n為文本串的長度；模式串P=P0……Pm-1，m為模式串的長度，(n＞＞m)；T和P都建立在有限字符集上，大小為σ。

對(duì)于文本串T和模式串P，在T中尋找等于P的子串，如果在T中存在等于P的子串，則稱匹配成功，函數(shù)值返回為P中第一個(gè)字符相等的字符在主串T中的序號(hào)，否則稱為匹配失敗，這個(gè)搜索過程就是模式匹配。至于如何在T中尋找等于P的子串，各種算法各顯神通，各有各的尋找方法，在此簡要介紹4種經(jīng)典匹配算法。

BF算法[2]是效率最低的算法，從左到右進(jìn)行匹配。首先將T[1]與P[1]進(jìn)行比較，若不同，就將T[2]與P[1]進(jìn)行比較，……，否則從T[2]開始與P[1]進(jìn)行比較，繼續(xù)開始下一趟的比較，重復(fù)上述過程。

KMP算法是由BF改進(jìn)后不產(chǎn)生回溯的一種算法，每當(dāng)匹配過程中出現(xiàn)字符串比較不等時(shí)，不需回溯i指針，而是利用已經(jīng)得到的“部分匹配”結(jié)果將模式向右滑動(dòng)盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。

BM算法是把P同文本串進(jìn)行比較時(shí)從右向左，當(dāng)某趟匹配失敗時(shí)，采用壞字符啟發(fā)規(guī)則和好后綴啟發(fā)規(guī)則計(jì)算模式串右移的距離，并取兩者最大值來決定模式串的右移量，移動(dòng)盡可能遠(yuǎn)的距離，直到匹配成功或文本串匹配結(jié)束，其匹配時(shí)從右至左進(jìn)行。

Sunday算法采用BM算法中的壞字符啟發(fā)規(guī)則，開始時(shí)P的最左邊與T的最左邊對(duì)齊，模式匹配過程中進(jìn)行P與T的比較時(shí)，可以從左向右或從右向左進(jìn)行比較，在發(fā)現(xiàn)不匹配時(shí)，選取當(dāng)前匹配窗口的下一個(gè)字符來判斷右移量以跳過盡可能多的字符，從而提高了匹配效率。其匹配時(shí)從右至左進(jìn)行或者從左至右均可。

2 字符頻率描述及其已有的應(yīng)用

在網(wǎng)絡(luò)的流量中，絕大部分的報(bào)文屬于正常報(bào)文，鑒于此特征，考慮各字符在報(bào)文中出現(xiàn)的頻率來實(shí)現(xiàn)算法。文獻(xiàn)[8]給出了ASCII字符（頻率分布程序）的頻率分布表，如表1所示。

表1 英文字母頻率表

根據(jù)表1中字母出現(xiàn)的頻率值，從小到大排序后獲得的字母順序?yàn)椋簔qxjkvbpygfwmucldrhsnioate。

字符頻率在模式匹配中的應(yīng)用也有一些研究，如文獻(xiàn)[1]是預(yù)處理T中所有出現(xiàn)字符的頻率，并記錄其在T中出現(xiàn)的位置，之后根據(jù)這些信息查找P在T中的位置，若找到，先匹配頻率最低的，再匹配次低的，直到最后成功或遇到不匹配的字符。文獻(xiàn)[9]盡可能選擇失配率高度的字符進(jìn)行比較，利用切分字符（T中不在模式字符串里出現(xiàn)而且在T中相對(duì)居中的字符）把T及T的子串不斷地一分為二，直到找到P或沒有長度大于或等于P的T的子串為止。文獻(xiàn)[10]是把字符頻率應(yīng)用到Sunday算法的改進(jìn)中，它在預(yù)處理階段先確定P中最小頻率值的某個(gè)字符及其在P中的位置，在匹配過程中只是第一次根據(jù)預(yù)處理階段的信息進(jìn)行匹配，第二次的右移距離還是采用Sunday算法的右移量進(jìn)行跳轉(zhuǎn)。文獻(xiàn)[11]是在模式串中找出使用頻率最低的和次低的兩個(gè)漢字(或字符)，將它們提取作為模式串的特征子串，其他漢字(或字符)做模糊處理。

以上各文獻(xiàn)對(duì)字符頻率在模式匹配算法中的應(yīng)用各有千秋，在此提出另一種基于字符頻率的模式匹配算法Characters-Frequency-Pattern-Matching算法，簡稱為CFPM，其思想是：1)在預(yù)處理階段有兩個(gè)任務(wù)，一是確定P中頻率值最小的那個(gè)字符稱為關(guān)鍵字符及其在P中的位置值，二是掃描T串，確定關(guān)鍵字符在T中的位置；2)匹配階段，根據(jù)預(yù)處理階段的信息，把關(guān)鍵字符與其在T中出現(xiàn)的位置進(jìn)行一一對(duì)齊，并進(jìn)行雙向匹配。

3 CFPM算法

3.1 CFPM算法的預(yù)處理

在預(yù)處理階段有兩個(gè)任務(wù)，首先確定關(guān)鍵字符及其在P中的位置值，設(shè)計(jì)思路是：

1)輸入P串，計(jì)算其長度m=strlen(P)；

2)定義char *CF_value=″zqxjkvbpygfwmucldr hsnioate″，就是按照字母出現(xiàn)的頻率值從小到大的排序；

3)從CF_value[0]開始尋找P中的每個(gè)字符，若沒找到，則從CF_value[1]開始，直到找到為止，此時(shí)記錄找到的字符即關(guān)鍵字符key_ch，并記錄其在P中的位置。

其具體算法如下：

輸入：P模式串；

定義：字符串的頻率字符串CF_value，關(guān)鍵字符key_ch，key_ch在P中的位置pos，其它循環(huán)變量；

賦值：P的長度m；

功能：確定關(guān)鍵字符key_ch及其位置pos的值。

其次確定關(guān)鍵字符及其在P中的位置值，設(shè)計(jì)思路是：

1)輸入T串，計(jì)算其長度n=strlen(T)；

2)從T的第1個(gè)字符開始查找，若等于key_ch，則記錄其位置在數(shù)字?jǐn)?shù)組index[]當(dāng)中。

其具體算法如下：

輸入：T文本串

定義：數(shù)組index[]，其下標(biāo)值為num，num的初值為0；

功能：記錄關(guān)鍵字符key_ch在T中的位置

3.2 CFPM算法的匹配過程

CFPM算法的匹配思路是進(jìn)行雙向匹配，即：以關(guān)鍵字符為始點(diǎn)，先進(jìn)行向左匹配，再進(jìn)行了向右匹配，當(dāng)發(fā)現(xiàn)左部分失配時(shí)，直接進(jìn)行下一輪的匹配，而不用進(jìn)行右部分的匹配。當(dāng)兩部分均匹配成功，則輸出匹配的位置，若不在成功，則輸出失配的信息。具體算法描述如下：

1)i=0；

2)以T[index[i]]為起始點(diǎn)，進(jìn)行T[index[i]-1]的字符與P[pos-j](j的初值是1)進(jìn)行比較，若匹配，j加1不斷地進(jìn)行匹配，直到匹配至P[0]；若出現(xiàn)第一個(gè)不匹配的字符，則結(jié)束左部分的匹配，執(zhí)行4)；否則執(zhí)行3)；(說明：此步驟是向左匹配)

3)進(jìn)行T[index[i]+k](k的初值是1)的字符與P[pos+k]進(jìn)行比較，若匹配，k加1不斷地進(jìn)行匹配，直到匹配至P[m-1]；若出現(xiàn)第一個(gè)不匹配的字符，則結(jié)束右部分的匹配，執(zhí)行4)；否則執(zhí)行5)；

4)之后i加1，若i小于num，執(zhí)行2)，否則執(zhí)行6)；

5)若雙向匹配成功，則輸出匹配的位置；

6)結(jié)束匹配

其具體算法如下：

定義：定義向左、向右匹配的變量j，k，初值均為1；定義成功匹配的標(biāo)志 flag，初值為0；

功能：確定P在T中的位置。

3.3 CFPM與典型算法的實(shí)例對(duì)比

對(duì)于CFPM算法，在此通過簡單實(shí)例進(jìn)行匹配演示，并將之與效率較高的BM算法、Sunday算法進(jìn)行對(duì)比。

例如：T=”theykasenjoyformingworks”，P=”works”，現(xiàn)通過BM算法、Sunday算法、CFPM算法分別演示P在T中的實(shí)現(xiàn)，以對(duì)比CFPM算法的優(yōu)越性。

1）BM算法的匹配演示

首先生成字符集C {k,o,r,s,w},BM_Bc函數(shù)值對(duì)應(yīng)為{1,3,2,5,4}，其余字符值均為5，其匹配過程如表2所示(表中的?表示不需要匹配的字符，粗體的字符表示匹配過的字符)。

表2 BM算法匹配過程

本例結(jié)果：匹配次數(shù)是7，匹配的字符個(gè)數(shù)是11。

表3 Sunday算法匹配過程

本例結(jié)果：匹配次數(shù)是5，匹配的字符個(gè)數(shù)是9。

表4 CFPM算法匹配過程

本例結(jié)果：匹配次數(shù)是2，匹配的字符個(gè)數(shù)是5，因?yàn)殛P(guān)鍵字符不需要再進(jìn)行匹配。

2）Sunday算法的匹配演示

首先生成字符集C {k,o,r,s,w},Sunday_Bc函數(shù)值對(duì)應(yīng)為{2,4,3,1,5}，其余字符值均為6，其匹配過程如表3所示(表中的?表示不需要匹配的字符，粗體的字符表示匹配過的字符)。

3）CFPM算法的匹配演示

根據(jù)char *CF_value=″zqxjkvbpygfwmucldrhs nioate″，得P ="works"的關(guān)鍵字符key_ch= 'k'，其在P中的位置pos=3。在T中查找key_ch的位置分別是index[0]=4，index[1]=22。之后根據(jù)這些信息進(jìn)行左右匹配，其匹配過程如表4所示(表中的?表示不需要匹配的字符，包括key_ch，即字符 'k'，只要把'k'與T[index[0]]對(duì)齊；粗體的字符表示匹配過的字符)。

從表2、表3和表4的結(jié)果可看出，CFPM算法在匹配次數(shù)和匹配的字符個(gè)數(shù)方面比BM算法、Sunday算法有明顯的改進(jìn)。

3.4 CFPM算法性能分析

CFPM算法在預(yù)處理階段要進(jìn)行兩個(gè)任務(wù)，其一是確定key_ch在P中的位置，根據(jù)文獻(xiàn)[8]，在所有的ASCII碼當(dāng)中，26個(gè)小寫字母出現(xiàn)的概率較高，所以在這一過程的時(shí)間復(fù)雜度是O(m)；其二是在掃描T的過程中記錄key_ch在T中的所有位置，這一過程定義了index[]數(shù)組，由于key_ch是P中概率最小的，所以index[]數(shù)組的長度遠(yuǎn)遠(yuǎn)小于n，這一過程的時(shí)間復(fù)雜度是O(n)。綜合這兩點(diǎn)，CFPM算法在預(yù)處理階段的時(shí)間復(fù)雜度是O(m+n)。

CFPM算法在匹配階段的跳躍次數(shù)完全取決于key_ch在T中出現(xiàn)的次數(shù)也就是index[]數(shù)組的大小，而算法在匹配最多次數(shù)是m-1(key_ch不需要進(jìn)行匹配)，假設(shè)key_ch的概率為p，則此階段的時(shí)間的時(shí)間復(fù)雜度是p*O(m)。當(dāng)字符集較大、關(guān)鍵字符出現(xiàn)概率越小時(shí)，復(fù)雜度越小，效率越高。

4 CFPM算法性能測試

為了檢測CFPM算法的性能，隨機(jī)抽取一段文本和一個(gè)模式串，在同一臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)BM算法、Sunday算法和CFPM算法。測試的操作系統(tǒng)用Windows XP，實(shí)現(xiàn)算法的軟件是Visual C++6.0。測試文本如下：

Many networks are managed by a computer called a file server. A file server has a large－capacity hard disk and special software that manages access to flies on the network. It controls how data and database are shared among users on the network and how users access master copies of data and application software on the centralized hard disk. It is the file server's job to make sure that users don't accidentally try to update a file at the same time and scramble the data. The file server may also manage the access to an expensive piece of hardware such as a laser printer.

模式串為hardware。分別測試三種算法的匹配次數(shù)和匹配字符個(gè)數(shù)，結(jié)果如表5所示。

表5 BM算法、Sunday算法和CFPM算法的實(shí)驗(yàn)結(jié)果對(duì)比表

從表5可以看出：CFPM算法無論是在匹配次數(shù)還是匹配的字符個(gè)數(shù)方面，均比BM算法、Sunday算法有明顯的優(yōu)勢(shì)，這是因?yàn)槠ヅ鋾r(shí)只選取P中字符頻率最小的字符進(jìn)行匹配，那么該字符在T中出現(xiàn)的次數(shù)也就最小，所需要右移的次數(shù)當(dāng)然是最少的。另外，匹配時(shí)采用左右兩部分比較方式，在一定程度上能夠快速地判斷是否匹配。因此，CFPM算法效率更高。

5 結(jié)束語

模式匹配算法效率高低由相關(guān)算法的移動(dòng)距離決定，對(duì)于移動(dòng)距離和匹配字符的順序，各算法也大相徑庭。BM算法由當(dāng)前匹配窗口的末字符在P中的位置來決定下一輪的移動(dòng)距離，匹配方向是從右向左，Sunday算法下一輪的移動(dòng)距離則由當(dāng)前匹配窗口的下一位字符在P中的位置來決定，本文提出的CFPM算法是與這兩種算法不同，其移動(dòng)距離是根據(jù)P中字符頻率最低的字符在T中的位置來移動(dòng)，匹配時(shí)是先匹配左邊的，再匹配右邊的。由于CFPM算法能夠很大幅度地跳過壞字符，大大減少了移動(dòng)的次數(shù)和比較的字符個(gè)數(shù)，減少了匹配時(shí)間，而且CFPM算法在編程方面容易實(shí)現(xiàn)，再加上入侵檢測系統(tǒng)中模式匹配的成功率很低，所以更能提高匹配失敗的概率。從總體上看，CFPM算法更符合入侵檢測系統(tǒng)的需求，在入侵檢測系統(tǒng)中更實(shí)用、更有效。

[1] 陳論,魏海平,王福威.一種面向入侵檢測的模式匹配算法[J]. 遼寧石油化工大學(xué)學(xué)報(bào).2009,29(1):69-72.

[2] 王成,劉金剛.一種改進(jìn)的字符串匹配算法.計(jì)算機(jī)工程.2006,32(2):62-64.

[3] Knuth D E,Morris J H,Pratt V R. Fast pattern in strings.SIJM Journal on computing:1977,6(2):323-350.

[4] Boyer RS.Moore JS.A Fast String Searching Algorithm.Communications of the ACM,1977 20(10):762-772.

[5] SUNDAY D M.A very fast substring search algorithm.Communications of the ACM,1990,33(3):132-142.

[6] Aho A V,Corasick M J. Ef ficient String Matching: An Aid to Bibliographic Search[J].Communications of the ACM,1975,18(6):333-340.

[7] S. Wu. U.Manber. A Fast Algorithm For Multi-Pattern Searching.Technical Report TR-94-17.University of Arizona.,1994,1-11.

[8] http://zh.wikipedia.org/wiki/%E8%8B%B1%E6%96%87%E5%AD%97%E6%AF%8D.

[9] 鄧一貴.基于字符頻率及分治法的字符串模式匹配算法[J]. 計(jì)算機(jī)科學(xué).2008,35(6):168-170.

[10] 萬曉榆,楊波,樊自甫.改進(jìn)的Sunday模式匹配算法[J].計(jì)算機(jī)工程.2009,35(7):125-126.

[11] 洪濤,侯整風(fēng).基于字頻的模式匹配算法[J].微計(jì)算機(jī)信息.2010,26(11-3):188-189.