分塊法的模式匹配算法的研究

巫喜紅

(嘉應(yīng)學(xué)院計(jì)算機(jī)學(xué)院，廣東梅州514015)

0 引言

隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的快速發(fā)展，帶給網(wǎng)民無限的方便，比如網(wǎng)上訂票、網(wǎng)購等，但同時(shí)也帶來了一些安全隱患，比如密碼的失竊，因此，網(wǎng)絡(luò)的安全性一直受到大家的關(guān)注。其中，提高網(wǎng)絡(luò)系統(tǒng)安全性的重要技術(shù)之一的入侵檢測系統(tǒng)也由此越來越廣泛地應(yīng)用到網(wǎng)絡(luò)系統(tǒng)中。而要提高入侵檢測系統(tǒng)的性能，其關(guān)鍵技術(shù)—模式匹配性能的提高也得到大家極大的關(guān)注。其實(shí)，模式匹配不只應(yīng)用在網(wǎng)絡(luò)安全方面，在計(jì)算機(jī)上用編輯程序作文本編輯、在DNA序列中尋找特殊的模式等，也要用到模式匹配。由于模式匹配問題的求解效率的重要性，對(duì)模式匹配算法的研究很早就受到重視，因而積累了豐富的成果，比如最早提出的典型的單模式算法有Knuth-Morris-Pratt算法［1］、Byoer-Moore 算法［2］、Sunday算法［3］，多模式算法主要有 Aho_Corasick 算法［4］、Wu_Mander算法［5］。后來，各研究者不斷地對(duì)這些典型算法進(jìn)行了改進(jìn)，以提高算法的效率，比如文獻(xiàn)［6］對(duì)KMP算法進(jìn)行改進(jìn)，文獻(xiàn)［7］對(duì)BM算法進(jìn)行改進(jìn)，文獻(xiàn)［8］對(duì)Sunday算法進(jìn)行改進(jìn)，這些改進(jìn)算法的改進(jìn)思想是當(dāng)匹配失敗時(shí)，如何使模式串右移最大距離。本文從模式串的首字符著手，借鑒分塊查找的思路，提出一種分塊模式匹配(block pattern matching，BPM)算法。

1 幾種改進(jìn)的模式匹配算法

為了便于描述算法，現(xiàn)設(shè)文本串T=T0…Tn－1，n為文本串的長度，模式串P=P0…Pm－1，m為模式串的長度(n≥m)，T和P都建立在有限字符集上，大小為σ。

對(duì)于文本串T和模式串P，如果在T中存在等于P的子串，則稱匹配成功，否則稱為匹配失敗，這個(gè)搜索過程就是模式匹配。至于如何在T中快速尋找等于P的子串，各種算法各顯神通，各有各的思路方法，在此簡要介紹兩類經(jīng)典匹配算法，分析它們其中的一種改進(jìn)算法。

1.1 BM算法及其改進(jìn)算法

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

對(duì)于BM算法的改進(jìn)有很多種，如文獻(xiàn)［7］所提到的改進(jìn)算法，在此稱改進(jìn)算法為Im-BM，其改進(jìn)思路是:當(dāng)匹配成功時(shí)，判斷當(dāng)前窗口的下一位字符是否在P中，若不在，則跳過m+1個(gè)字符;若在，則根據(jù)此字符在P中的位置來確定;當(dāng)匹配失敗時(shí)，根據(jù)當(dāng)前匹配窗口匹配失敗的字符和當(dāng)前窗口的下一個(gè)字符來進(jìn)行跳轉(zhuǎn)，跳轉(zhuǎn)的距離是兩者中較大的那個(gè)。文獻(xiàn)［7］所得出的結(jié)論是:在總的嘗次數(shù)方面，I-BM算法是BM算法的82.83%，總的字符比較次數(shù)是BM算法的80.98%。

1.2 Sunday算法及其改進(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)行或者從左至右均可。

對(duì)于Sunday算法的改進(jìn)有很多種，如文獻(xiàn)［8］所提到的改進(jìn)算法，在此稱為Im-Sunday，其改進(jìn)思路是:預(yù)處理階段生成的函數(shù)值與Sunday算法一致，在匹配階段有所改進(jìn)。無論匹配成功與否，根據(jù)當(dāng)前窗口的下一個(gè)字符來決定跳轉(zhuǎn)距離;當(dāng)前窗口的下一位字符是否在P中，若不在，則再判斷m個(gè)字符是否在P中以決定跳過的字符，最大右移距離是2m+1;若在，則根據(jù)此字符在P中的位置來確定。文獻(xiàn)［8］所得出的結(jié)論是:在指針移動(dòng)次數(shù)方面，Im-Sunday算法是Sunday算法的63.81%，字符比較次數(shù)是Sunday算法的67.72%。

2 BPM算法描述

借鑒文獻(xiàn)［9］中提出的分塊查找思路，在模式匹配算法中進(jìn)行應(yīng)用。分塊查找的思路是:按照一個(gè)順序表內(nèi)記錄的某種屬性把表分成n(n＞1))個(gè)塊(子表)，并建立一個(gè)相應(yīng)的“索引表”，利用此“索引表”進(jìn)行塊內(nèi)的查找，原則是后面一個(gè)塊中所有記錄的關(guān)鍵字值比前一個(gè)塊中所有記錄的關(guān)鍵字值大，但同一塊、同關(guān)鍵字值的大小可以無序。在此借鑒分塊查找的思路，對(duì)模式匹配算法進(jìn)行分塊處理。BPM算法中的塊是指字符塊，也就是在文本串T中查找出這樣的塊:首字符、尾字符分別等于模式串P的首尾字符，且長度與P的長度相等，字符塊之間沒有大小要求。其思想是:①在預(yù)處理階段，掃描T串，找出符合要求的字符塊并存儲(chǔ)其首尾字符在T中的位置，其數(shù)據(jù)結(jié)構(gòu)采用單向鏈表;②匹配階段，根據(jù)預(yù)處理階段的信息，把P與其在T中出現(xiàn)的位置進(jìn)行一一對(duì)齊進(jìn)行匹配，采用雙向匹配方式。

2.1 BPM算法的預(yù)處理

在預(yù)處理階段，保存P的首、尾2個(gè)字符在T中的位置值，設(shè)計(jì)思路是:從T的首字符開始查找P的首字符，若找到首字符，則判斷后m個(gè)字符長度的字符是否等于P的尾字符，若是，則新建結(jié)點(diǎn)以保存位置，否則，繼續(xù)下一個(gè)首字符的查找，直到T的字符結(jié)束。那么，單鏈表的長度就由符合要求的信息值決定。具體步驟如下。

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

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

3)定義并初始化一些變量，定義i為循環(huán)變量，first為P的首字符，last為P的尾字符，L為頭指針，p為新建結(jié)點(diǎn)，r為臨時(shí)結(jié)點(diǎn);

4)從T的第1個(gè)字符開始，當(dāng)T串未掃描完，執(zhí)行5)，否則，執(zhí)行8);

5)若 T［i］!=first，則往后找;

6)若找到與first相等的字符，則判斷其后m長度的字符是否等于last，若是，則找到第1個(gè)字符塊，新建結(jié)點(diǎn)，保存下標(biāo)值;

7)若不符合步驟5)，6)，則直接跳過長度為m的字符塊，執(zhí)行步驟4);

8)結(jié)束掃描。

算法中使用了單鏈表的結(jié)構(gòu)，單鏈表的定義如下。

其算法流程如圖1所示。

圖1 BPM算法預(yù)處理階段流程圖Fig.1 Preprocessing phase flow chart of BPM algorithm

2.2 BPM算法的匹配過程

BPM算法的匹配思路是進(jìn)行雙向匹配，即:從單鏈表的第1個(gè)結(jié)點(diǎn)開始，取出首尾字符的位置值進(jìn)行字符塊的匹配，每一個(gè)字符塊匹配順序是:從P的第2個(gè)和倒數(shù)第2個(gè)字符開始匹配，若此次匹配失敗，則退出匹配，進(jìn)行下一個(gè)字符塊的匹配;若匹配成功，則再進(jìn)行P的第3個(gè)和倒數(shù)第3個(gè)字符的匹配……。當(dāng)匹配成功，則輸出匹配的位置，若不成功，則輸出失配的信息。直到單鏈表的最后一個(gè)結(jié)點(diǎn)為止。

具體步驟如下。

1)定義臨時(shí)指針變量q為指向每一個(gè)結(jié)點(diǎn);臨時(shí)變量k為模式串P的下標(biāo)值;臨時(shí)變量i，j分別存儲(chǔ)首尾字符在T中的位置;臨時(shí)變量flag為匹配標(biāo)識(shí)。

2)當(dāng)結(jié)點(diǎn)不空時(shí)，分別取出firstpos，lastpos的值。

3)當(dāng)k小于m/2時(shí)，從P的第2個(gè)和倒數(shù)第2個(gè)字符開始匹配，若匹配成功，則執(zhí)行4);否則執(zhí)行5)。

4)變量i++，j－－，k++，flag=1。

5)q指向一個(gè)結(jié)點(diǎn)，執(zhí)行2)。

6)結(jié)束匹配。

其算法流程如圖2所示。

圖2 BPM算法匹配階段流程圖Fig.2 Matching phase flow chart of BPM algorithm

3 BPM與其他改進(jìn)算法的實(shí)例對(duì)比及性能分析

3.1 實(shí)例對(duì)比

對(duì)于BPM算法，在此通過簡單實(shí)例進(jìn)行匹配演示，并將其與改進(jìn)的Im-BM算法、Im-Sunday算法進(jìn)行實(shí)例的對(duì)比。

例如:設(shè) T=“strkdesignsdeawisestetementstep”，P=“step”，現(xiàn)通過 Im-BM 算法、Im-Sunday算法、BPM算法分別演示P在T中的實(shí)現(xiàn)，以顯示BPM算法的優(yōu)越性。

1)Im-BM算法的匹配演示。

首先生成字符集 C{a，d，e，g，i，k，m，n，p，r，s，t，w}，Im-BM_Bc 函數(shù)值對(duì)應(yīng)為 {4，4，1，4，4，4，4，4，4，4，3，2，4}，根據(jù) Im-BM 算法的匹配思路，其匹配過程如表1所示。本例結(jié)果:匹配次數(shù)是8，匹配的字符個(gè)數(shù)是12。

表1 Im-BM算法匹配過程Tab.1 Matching procedure of the Im-BM algorithm

2)Im-Sunday算法的匹配演示。

首先生成字符集 C{a，d，e，g，i，k，m，n，p，r，s，t，w}，Im-Sunday_Bc 函數(shù)值對(duì)應(yīng)為 {5，5，2，5，5，5，5，5，1，5，4，3，5}，根據(jù) Im-Sunday 算法的匹配思路，其匹配過程如表2所示。本例結(jié)果:匹配次數(shù)是8，匹配的字符個(gè)數(shù)是13。

表2 Im-Sunday算法匹配過程Tab.2 Matching procedure of the Im-Sunday algorithm

3)BPM算法的匹配演示。

BPM算法在預(yù)處理階段首先查找P的首字符's'，再把首字符位置加3(P的長度減1)，判斷此位置的字符是否等于P的尾字符'p'，最終保存在單鏈表中。單鏈表的示意圖如圖3所示，其中“^”表示“空”。

圖3 BPM算法鏈表圖Fig.3 Llist of BPM algorithm

根據(jù)單鏈表的信息，從第1個(gè)結(jié)點(diǎn)開始，從P的第2個(gè)字符和倒數(shù)第2個(gè)字符進(jìn)行匹配，其匹配過程如表3所示。本例結(jié)果:匹配次數(shù)是2，匹配的字符個(gè)數(shù)是4。

表3 BPM算法匹配過程Tab.3 Matching procedure of the BPM algorithm

從表1—表3的結(jié)果可看出，BPM算法在匹配次數(shù)和匹配的字符個(gè)數(shù)方面比Im-BM算法、Im-Sunday算法有很明顯的改進(jìn)，比典型的BM算法、Sunday算法有更大的改進(jìn)。

3.2 性能分析

為了說明BPM算法的高效性，在此進(jìn)行預(yù)處理階段和匹配階段的算法性能分析。

1)在預(yù)處理階段，根據(jù)文獻(xiàn)［7］描述，Im-BM算法在此階段的時(shí)間復(fù)雜度為O(σ+n)，空間復(fù)雜度為O(σ+n)。根據(jù)文獻(xiàn)［8］描述，Im-Sunday算法在此階段的時(shí)間復(fù)雜度為O(σ)，空間復(fù)雜度為O(σ+n)。BPM算法在預(yù)處理階段掃描T串以尋找P的首字符，所以這一過程僅循環(huán)一次T的長度n，故時(shí)間復(fù)雜度是T(n)=O(n);在此階段，需要存儲(chǔ)長度等于P的長度的字符塊的相關(guān)信息，故存儲(chǔ)空間由P的首尾字符在T中出現(xiàn)的機(jī)率有關(guān)，由于采用動(dòng)態(tài)存儲(chǔ)即單鏈表方式，故存儲(chǔ)空間很小，最好情況是0，即沒有找到符合要求的字符塊，最壞情況是n/m，即T串都是由P串組成的，故其空間復(fù)雜度S(n)=O(n/m)。

2)在匹配階段，根據(jù)文獻(xiàn)［7］描述，Im-BM算法在此階段的最好時(shí)間復(fù)雜度為O(n)，最壞為O(n·m)。根據(jù)文獻(xiàn)［8］描述，Im-Sunday算法在此階段的最壞時(shí)間復(fù)雜度為O(n·m)。BPM算法在匹配階段是根據(jù)單鏈表的存儲(chǔ)空間來決定循環(huán)次數(shù)，由前面分析可知，最壞情況下S(n)=O(n/m)，也就是T(n)=O(n/m)，而匹配每個(gè)字符塊時(shí)是從P的第2個(gè)字符開始，采用雙向匹配，所以最壞情況是匹配m/2次，故在匹配階段的時(shí)間復(fù)雜度是T(n)=(n/m)·(m/2)=n/2=O(n)。最好情況是0，即無需匹配。也就是說，BPM算法在最壞情況下的時(shí)間復(fù)雜度為O(n)，最好情況是0。

綜上分析，在預(yù)處理階段，雖然BPM算法要掃描一次T串，需要花費(fèi)時(shí)間，但是其在匹配階段所花時(shí)間只是由單鏈表的存儲(chǔ)空間來決定循環(huán)次數(shù)，而單鏈表的長度遠(yuǎn)遠(yuǎn)小于n，因此，從BPM算法、Im-BM算法和Im-Sunday算法2個(gè)階段的時(shí)間復(fù)雜度可看出，BPM算法的時(shí)間開銷是最少的。

4 BPM算法性能測試

為了更好地體現(xiàn)BPM算法性能的高效性，現(xiàn)將BPM算法的性能進(jìn)行檢測?，F(xiàn)從兩方面進(jìn)行實(shí)驗(yàn)，測試的平臺(tái)相同，即:操作系統(tǒng)用Windows 7，編譯器是 Visual C++6.0。

實(shí)驗(yàn)1 從匹配次數(shù)和匹配字符個(gè)數(shù)方面去測試。方法是:隨機(jī)抽取一段文本和一個(gè)模式串，在相同環(huán)境下實(shí)現(xiàn)Im-BM算法、Im-Sunday算法和BPM算法。測試文本如下。

The year that many computers may develop problems because of lack of foresight on the part of programmers.In the 1980s and before，most computer programs were designed to store only the last two digits of the years on all dates .When the Year 2000 comes，these programs will show dates of 00，which maybe interpreted the same as 1900.This discrepancy may cause widespread problems，especially in the large computer systems used in government and big industries.

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

表4 實(shí)驗(yàn)一結(jié)果對(duì)比表Tab.4 Results of the first experimentation

實(shí)驗(yàn)2 從算法的執(zhí)行時(shí)間方面去測試。方法是:隨機(jī)選用純英文文檔作為文本串，共有1 334個(gè)字符，隨機(jī)選取模式串長度分別為8，20，35的模式串(包括匹配不成功和匹配成功的模式串)，運(yùn)行程序100萬次，取它們運(yùn)行時(shí)間的平均值，獲得的結(jié)果如表5所示。

表5 實(shí)驗(yàn)二結(jié)果對(duì)比表Tab.5 Results of the second experimentation

從表4可以看出:BPM算法無論是在匹配次數(shù)還是匹配的字符個(gè)數(shù)方面，均比Im-BM算法、Im-Sunday算法有很明顯的優(yōu)勢;從表5可以看出，當(dāng)模式串較短時(shí)，時(shí)間方面比Im-BM算法、Im-Sunday算法稍長，但隨著模式串長度的增加，所花費(fèi)時(shí)間越來越少，在實(shí)驗(yàn)測試過程中，特別是匹配失敗情況下，BPM算法運(yùn)行時(shí)間非常小，幾乎為零。

從以上實(shí)驗(yàn)可證明，BPM算法是一個(gè)性能很好的改進(jìn)算法，這是因?yàn)锽PM算法在匹配時(shí)只匹配首尾字符均等于模式串的首尾字符的字符塊，而這樣的字符塊在文本中出現(xiàn)的概率是很低的，也就意味著跳躍距離較大且比較次數(shù)是較少的。

5 結(jié)束語

由于BPM算法只匹配首尾字符均等于模式串的首尾字符的字符塊，并且字符長度等于模式串長度，實(shí)驗(yàn)證明本文采用的分塊法改進(jìn)的模式匹配算法能夠有效地提高模式匹配的速度?；谀Ｊ狡ヅ涞腟nort入侵檢測系統(tǒng)有4大模塊，通過設(shè)定不同的規(guī)則選項(xiàng)，在處理時(shí)就會(huì)調(diào)用不同的插件，其中，改進(jìn)后的BPM算法用于sp_pattern_match插件中，它使用的數(shù)據(jù)結(jié)構(gòu)PatternMatchData用于模式匹配。因此，對(duì)將改進(jìn)后的算法植入到Snort系統(tǒng)中進(jìn)行應(yīng)用的研究具有重要的意義，今后的研究方向是把改進(jìn)的多模式匹配算法應(yīng)用到Snort系統(tǒng)當(dāng)中。

［1］曾誠，李兵，何克清.KMP算法在Web服務(wù)語義標(biāo)注中的應(yīng)用［J］.微電子學(xué)與計(jì)算機(jī)，2010，27(8):1-3.ZENG Cheng，LI Bing，HE Keqing.Application of KMP Algorithm in Web Service Annotation［J］.Micro Electronics ＆ Computer，2010，27(8):1-3.

［2］LI Yankun，F(xiàn)U Weina.Realization of String-Matching in SIMD-MC2Grid［C］//IEEE.2010 3rd International Conference on Computational Intelligence and Industrial Application(PACIIA).Hubei:IEEE Press，2010:311-314.

［3］潘冠樺，張興忠.Sunday算法效率分析［J］.計(jì)算機(jī)應(yīng)用，2012，32(11):3082-3084，3088.PAN Guanhua，ZHANG Xingzhong.Study on Efficiency of Sunday Algorithm ［J］.Journal of Computer Applications.2012，32(11):3082-3084，3088.

［4］巫喜紅，曾鋒.AC多模式匹配算法研究［J］.計(jì)算機(jī)工程，2012，38(6):279-281.WU Xihong，ZENG Feng.Research on AC Multiple Pattern Matching Algorithm［J］.Computer Engineering，2012，38(6):279-281.

［5］巫喜紅.入侵檢測系統(tǒng)中Wu_Manber多模式匹配算法的研究［J］.計(jì)算機(jī)應(yīng)用與軟件，2008，25(8):114-125.WU Xihong.On Wu_Manber Multiple Pattern Matching Algorithm in Intrusion Detection System［J］.Computer Applications and Software，2008，25(8):114-125.

［6］楊戰(zhàn)海.KMP模式匹配算法的研究分析［J］.計(jì)算機(jī)與數(shù)字工程，2010，38(5):39-40.YANG Zhanhai.Research and Analysis of KMP Pattern Matching Algorithm［J］.Computer＆ Digital Engineering，2010，38(5):39-40.

［7］薛傳慶，韓明暢，金偉信.入侵檢測系統(tǒng)中BM算法的改進(jìn)［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2011，21(6):136-139.XUE Chuanqing，HAN Mingchang，JIN Weixin.Improvement of BM Algorithm in Intrusion Detection System［J］.Computer Technology and Development，2011，21(6):136-139.

［8］武旭東.Snort入侵檢測系統(tǒng)研究與應(yīng)用［D］.吉林:吉林大學(xué)，2011.WU Xudong.The Research and Application of Intrusion Detection System Based on Snort［D］.Jilin:Jilin University，2011.

［9］王裕明.數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)［M］.北京:清華大學(xué)出版社，2010:10-210.WANG Yuming.Data Structures and Programming［M］.Beijing:Tsinghua University Publishing House，2010，10-210.