一種改進(jìn)的BM字符串匹配算法

李韋男，虞慧群

1.華東理工大學(xué)計(jì)算機(jī)科學(xué)與工程系，上海 200237

2.計(jì)算機(jī)軟件評(píng)測(cè)重點(diǎn)實(shí)驗(yàn)室，上海 201112

一種改進(jìn)的BM字符串匹配算法

李韋男1，2，虞慧群2

1.華東理工大學(xué)計(jì)算機(jī)科學(xué)與工程系，上海 200237

2.計(jì)算機(jī)軟件評(píng)測(cè)重點(diǎn)實(shí)驗(yàn)室，上海 201112

經(jīng)典字符串匹配算法的本質(zhì)都是從左向右或者從右向左順序進(jìn)行字符匹配的，在主串中存在大量子串與模式串前綴或者后綴相同時(shí)效率較低，并且模式串最大右移長(zhǎng)度為模式串長(zhǎng)度。改進(jìn)算法采用二分匹配字符串的方法，有效地避免了由主串中大量子串與模式串前綴相同或者后綴相同引起的無(wú)意義比較次數(shù)。模式串的移動(dòng)距離根據(jù)改進(jìn)的壞字符規(guī)則進(jìn)行計(jì)算，增大了模式串的移動(dòng)距離。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的字符串匹配算法可以有效地減少字符串的匹配次數(shù)和移動(dòng)次數(shù)，達(dá)到了提高算法效率的目的。

匹配；模式串；主串；入侵

1 引言

在計(jì)算機(jī)科學(xué)領(lǐng)域，字符串匹配算法一直都是研究焦點(diǎn)之一。在拼寫(xiě)檢查、語(yǔ)言翻譯、數(shù)據(jù)壓縮、搜索引擎、網(wǎng)絡(luò)入侵檢測(cè)、計(jì)算機(jī)病毒特征碼匹配以及DNA序列匹配等應(yīng)用中，都需要進(jìn)行字符串匹配。字符串匹配是入侵檢測(cè)系統(tǒng)所使用的基于攻擊特征的網(wǎng)絡(luò)數(shù)據(jù)包檢測(cè)技術(shù)，也是入侵檢測(cè)系統(tǒng)中一個(gè)最基本、最關(guān)鍵的技術(shù)。在實(shí)際的網(wǎng)絡(luò)運(yùn)行中，字符串匹配速度的快慢直接影響到入侵檢測(cè)系統(tǒng)的效率。

字符串的匹配問(wèn)題，是指給定一個(gè)主串和一個(gè)模式串，找到模式串是否在主串中出現(xiàn)。若出現(xiàn)返回出現(xiàn)位置，反之返回未出現(xiàn)。形式化定義為：在字符集ξ上，給定一個(gè)長(zhǎng)度為N的主串T[1…N]，以及一個(gè)長(zhǎng)度為M的模式串P[1…M]。如果有1≤x≤N，存在T[x+1，…，x+M]=P[1…M]，則P在主串T的位置x處出現(xiàn)，即模式串與主串匹配。

著名的匹配算法有BF算法、KMP算法、BM算法等。近年來(lái)，很多專家學(xué)者都提出過(guò)基于BM算法的改進(jìn)算法。文獻(xiàn)[1]提出的改進(jìn)的BM算法是在應(yīng)用壞字符規(guī)則的過(guò)程中，如果主串中連續(xù)的幾個(gè)字符不在模式串中出現(xiàn)[1]，則不需要被比對(duì)，以此改變模式串的匹配順序，這樣可增大模式串匹配的滑動(dòng)距離，提高算法的匹配效率。雖然該方法可提高算法的效率，但此種情況的發(fā)生幾率非常小，因此該方法仍有待改進(jìn)。文獻(xiàn)[2]算法改進(jìn)為：引入一個(gè)新的判斷函數(shù)Q(X)指出字符X在模式串中出現(xiàn)的次數(shù)，當(dāng)出現(xiàn)次數(shù)為l時(shí)可以利用已匹配的信息加大移動(dòng)距離[2]，同時(shí)利用文本串中不匹配字符后面的一個(gè)字符進(jìn)行匹配，從而得到一個(gè)移動(dòng)距離，將不同移動(dòng)規(guī)則下獲得的移動(dòng)距離的最大值作為實(shí)際的移動(dòng)距離，依次進(jìn)行，直到匹配完成。通過(guò)實(shí)驗(yàn)證明，該算法的移動(dòng)次數(shù)和比較次數(shù)確有減少，不過(guò)增加了內(nèi)存占用，并且當(dāng)文本字符出現(xiàn)頻率相當(dāng)時(shí)，該算法效果并不理想。

基于上述問(wèn)題，本文首先對(duì)這幾種常見(jiàn)匹配算法進(jìn)行分析，然后在BM算法的基礎(chǔ)上提出一種改進(jìn)的字符串匹配算法，最后進(jìn)行仿真實(shí)驗(yàn)和性能分析。

2 改進(jìn)字符串匹配算法

2.1 經(jīng)典字符串匹配算法

介紹算法之前，做如下定義，主串T：T[1…N]，長(zhǎng)度為N；模式串P：P[1…M]，長(zhǎng)度為M。

BF算法：首先T[1]和P[1]比較，若相等，則再比較T[2]和P[2]，一直到P[M]為止；若T[2]和P[2]不等，則P向右移動(dòng)一個(gè)字符的位置，再依次進(jìn)行比較。如果存在k，1≤k≤N，且T[k+1…k+M]=P[1…M]，則匹配成功；否則失敗。BF算法的實(shí)現(xiàn)比較簡(jiǎn)單，但是效率低，時(shí)間復(fù)雜度高[3]。該算法最壞情況下要進(jìn)行M×(N-M+1)次比較，時(shí)間復(fù)雜度為O(M×N)。

KMP算法：在普通匹配算法中主串與模式串都需要回溯，但這些回溯不是必要的。因?yàn)楫?dāng)某一位發(fā)生失配時(shí)，可以根據(jù)已匹配的結(jié)果進(jìn)行判斷。該算法問(wèn)題可以理解為，當(dāng)模式串中的第k位與主串的第i位比較發(fā)生不匹配時(shí)[4]，需要將模式串向右滑動(dòng)到某個(gè)位置，繼續(xù)與主串的第i位進(jìn)行比較，避免了不必要的主串回溯，減少了模式串回溯的位數(shù)。時(shí)間復(fù)雜度比BF算法低。

BM算法：BM算法在移動(dòng)模式串的時(shí)候是從左到右，而進(jìn)行比較的時(shí)候是從右到左的。BM算法在進(jìn)行匹配時(shí)[5]，包含兩個(gè)并行的算法，壞字符算法和好后綴算法，這兩種算法的目的就是為了讓模式串每次向右移動(dòng)盡可能大的距離。

2.2 改進(jìn)字符串匹配算法

眾所周知，字符串匹配算法的性能取決于模式串的移動(dòng)次數(shù)和與主串字符的匹配次數(shù)[6]。所以，如何能在最少移動(dòng)次數(shù)和最少比較次數(shù)內(nèi)得到匹配結(jié)果，就是算法改進(jìn)需要研究的主要內(nèi)容。

KMP算法的比較是從左向右，BM算法的比較是從右向左。大量的單詞是后綴相同但是前綴不一樣[7]，也有很多單詞是前綴相同而后綴不一樣。所以每次都從左向右或從右向左比較會(huì)導(dǎo)致很多無(wú)意義的比較次數(shù)。基于此思想，本文提出一種“二分匹配”的方法，即首先比較首尾字符，然后比較最中間字符，進(jìn)而遞歸比較最中間字符，有效地避免了由于前綴或者后綴相同引起的無(wú)意義比較次數(shù)。

BM算法中，模式串P最大向右移動(dòng)長(zhǎng)度為M[8]，為了提出移動(dòng)更大長(zhǎng)度的辦法，本文采用如下方式移動(dòng)字符串：針對(duì)主串中參加比較子串的最末位字符和最末位字符的下一位字符，分別采用兩種不同的壞字符規(guī)則進(jìn)行預(yù)處理，當(dāng)“二分匹配”失配時(shí)，采用改進(jìn)的壞字符規(guī)則進(jìn)行移動(dòng)，最大移動(dòng)長(zhǎng)度為M+1。

壞字符規(guī)則[9]：從右向左掃描的過(guò)程中，若發(fā)現(xiàn)某個(gè)主串字符a不匹配，則按如下兩種情況討論：

（1）如果字符a在模式P中沒(méi)有出現(xiàn)，那么從字符a開(kāi)始的M個(gè)文本顯然不可能與P匹配成功，直接全部跳過(guò)該區(qū)域即可。

（2）如果a在模式P中出現(xiàn)，則以該字符進(jìn)行對(duì)齊。

在本文算法中，對(duì)于最末位字符x的移動(dòng)距離，用數(shù)學(xué)公式表示，設(shè)skip1(x)為P右移的距離，max(x)為字符x在P中最右位置。

對(duì)于最末位字符的下一位字符y的移動(dòng)距離，用數(shù)學(xué)公式表示，設(shè)skip2(y)為P右移的距離，max(y)為字符y在P中最右位置。

實(shí)際的移動(dòng)距離則為max(skip1(x)，skip2(y)。

算法流程如圖1。

圖1 算法流程圖

2.3 算法的實(shí)現(xiàn)

當(dāng)首尾字符都相等時(shí)，采取“二分匹配”算法，start 和end代表字符串的首尾位置，T代表主串中參加比較的子串，P代表模式串，遞歸比較如下：

算法流程：當(dāng)i≤n的條件滿足，令j=m。首先比較T[i]與P[0]以及T[i+j-1]與P[j-1]，如果相等，則進(jìn)一步采用“二分匹配”算法來(lái)遞歸比較字符串，如果相等則返回出現(xiàn)位置，否則采用“改進(jìn)壞字符規(guī)則”進(jìn)行模式串的移動(dòng)；如果不相等，則采用“改進(jìn)壞字符規(guī)則”進(jìn)行模式串的移動(dòng)。

3 實(shí)例及分析

假設(shè)在入侵系統(tǒng)中，網(wǎng)絡(luò)數(shù)據(jù)包中存在的主串T是''abcbctefkbbebcbc''，入侵檢測(cè)庫(kù)中特定的模式串P是''ebcbc''。需要在最快時(shí)間內(nèi)檢測(cè)出主串T中是否有攻擊串P出現(xiàn)。如果檢測(cè)出P出現(xiàn)，則入侵系統(tǒng)就會(huì)發(fā)出警報(bào)，甚至切斷網(wǎng)絡(luò)連接。

首先對(duì)BM算法匹配流程進(jìn)行說(shuō)明。模式串與主串對(duì)齊，從右向左比較。

圖2 BM算法第一步

模式串與主串比較5次。模式串e與主串a(chǎn)失配，根據(jù)規(guī)則模式串右移4位。

圖3 BM算法第二步

模式串與主串比較1次。模式串c與主串k失配，模式串右移5位。

圖4 BM算法第三步

模式串與主串比較3次。模式串c與主串e失配，模式串向右移動(dòng)2位。

圖5 BM算法第四步

模式串與主串比較5次，找到模式串?？傆?jì)模式串移動(dòng)3次，與主串字符比較14次，完成字符串匹配。

用這個(gè)例子作為對(duì)比，介紹本文提出的改進(jìn)算法匹配流程。

圖6 改進(jìn)算法第一步

比較1次，模式串e與主串a(chǎn)失配，根據(jù)規(guī)則模式串右移6位。

比較2次，模式串c與主串b失配，模式串右移4位。模式串與主串比較5次，找到模式串。總計(jì)模式串移動(dòng)2次，與主串字符比較8次，完成字符串匹配。

可見(jiàn)本文提出算法已經(jīng)提高了字符串匹配的效率。

圖7 改進(jìn)算法第二步

圖8 改進(jìn)算法第三步

3.1 改進(jìn)算法時(shí)間復(fù)雜度分析

KMP算法在搜索階段的最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度都是O(N)[10]。在預(yù)處理階段，算法需要計(jì)算模式串的每個(gè)前綴的最長(zhǎng)邊界和模式串本身的最長(zhǎng)邊界。預(yù)處理階段的時(shí)間復(fù)雜度為O(M)。BM算法是比較快的模式匹配算法，該算法在預(yù)處理階段的時(shí)間復(fù)雜度為O(m+σ)，空間復(fù)雜度為O(m+σ)，其中σ是與主串和字符串所在的有限字符集的程度。BM算法的搜索階段的最壞時(shí)間復(fù)雜度為O(MN)[11]，而其平均時(shí)間復(fù)雜度是亞線性的，其中當(dāng)匹配一個(gè)非周期化的模式時(shí)即在最壞情況下至多需要進(jìn)行3n次比較。BM的最大不便之處是要根據(jù)壞字符和好后綴規(guī)則計(jì)算移動(dòng)距離，雖然它們可以在O(M)的時(shí)間內(nèi)完成[12]，但是很復(fù)雜。

改進(jìn)算法利用主串中參加比較子串的最末位字符和最末位字符的下一位字符的改進(jìn)壞字符規(guī)則進(jìn)行移動(dòng)，這樣帶來(lái)更大的平均移動(dòng)距離，在O(M)時(shí)間內(nèi)完成，并且計(jì)算起來(lái)非常簡(jiǎn)單。對(duì)于搜索階段，在模式串和主串的子串有大量前綴或者后綴相同時(shí)，采用本文提出的“二分匹配”算法，其平均時(shí)間復(fù)雜度是也要優(yōu)于BM算法。綜上所述，改進(jìn)算法在時(shí)間復(fù)雜度方面有了一定改善。

3.2 改進(jìn)算法性能分析

為了評(píng)測(cè)該算法的性能，在算法的運(yùn)行過(guò)程中，對(duì)字符串的匹配次數(shù)和算法運(yùn)行時(shí)間兩個(gè)方面的性能進(jìn)行了比較[13]。實(shí)驗(yàn)環(huán)境為P8600 2.40 GHz，2 GB內(nèi)存，W indow s XP。實(shí)驗(yàn)平臺(tái)為M icrosoft Visual C++6.0。測(cè)試用例為純英文文本，隨機(jī)抽取兩段1 MB文本，3個(gè)長(zhǎng)度不同的模式串，分別為3，6，10，字符串具體內(nèi)容為too，before，experience，在同一臺(tái)計(jì)算機(jī)上分別用BM、文獻(xiàn)[1]改進(jìn)算法，以及本文改進(jìn)算法循環(huán)執(zhí)行1 000次，進(jìn)行測(cè)試，并記錄下每種算法平均字符匹配次數(shù)和運(yùn)行時(shí)間。文本內(nèi)容較多，只給出部分示例。

第一段測(cè)試文本部分內(nèi)容：”If more than one filter matches，we assign it to the class with the highest priority.If no filter matches，the packet is discarded.To track connection cutoffs，the Time Machine keeps state for all active connections in a hash table.If a newly arrived packet belongs to a connection that has exceeded the cut off limit configured for its class，it is discarded.”平均字符匹配次數(shù)進(jìn)行比較如圖9。

圖9 平均字符匹配次數(shù)與模式串長(zhǎng)度關(guān)系

模式串長(zhǎng)度為3時(shí)，BM，文獻(xiàn)[1]算法，本文算法的比較次數(shù)分別為242，223，198。模式串長(zhǎng)度為6時(shí)，BM，文獻(xiàn)[1]算法，本文算法的比較次數(shù)分別為141，130，117。模式串長(zhǎng)度為10時(shí)，BM，文獻(xiàn)[1]算法，本文算法的比較次數(shù)分別為108，103，94。

第二段測(cè)試文本部分內(nèi)容：“It does not specify an Internet standard of any kind.Distribution of this memo is unlimited.Abstract Spam，defined as the transmission of bulk unsolicited messages，has plagued Internet email. Unfortunately，spam is not limited to email.It can affect any system that enables user-to-user communications.”算法運(yùn)行時(shí)間比較如圖10。

模式串長(zhǎng)度為3時(shí)，BM，文獻(xiàn)[1]算法，本文算法的運(yùn)行時(shí)間分別為17，15，11。模式串長(zhǎng)度為6時(shí)，BM，文獻(xiàn)[1]算法，本文算法的運(yùn)行時(shí)間分別為14，12，9。模式串長(zhǎng)度為10時(shí)，BM，文獻(xiàn)[1]算法，本文算法的比較次數(shù)分別為10，9，7。

尤其是當(dāng)主串中存在大量子串與模式串前綴或者后綴相同的時(shí)候，該算法性能必會(huì)有一定改善。實(shí)驗(yàn)結(jié)果表明，本文算法的匹配次數(shù)和運(yùn)行時(shí)間較BM算法以及文獻(xiàn)[1]改進(jìn)算法都有一定改進(jìn)，達(dá)到了提高算法效率的目的。

4 結(jié)論

本文首先對(duì)BM算法進(jìn)行分析，從字符串匹配效率和移動(dòng)效率出發(fā)，提出了一種改進(jìn)算法。該算法采用“二分匹配”方法匹配字符串，當(dāng)失配時(shí)采用了最末位字符和最末位字符的下一位字符判斷右移量，不僅提高了匹配效率，還增大了移動(dòng)距離。根據(jù)實(shí)驗(yàn)測(cè)試結(jié)果，改進(jìn)算法在效率上的確優(yōu)于BM算法以及改進(jìn)的BM算法。尤其是當(dāng)主串中存在大量子串與模式串前綴或者后綴相同的時(shí)候，該算法性能必會(huì)有一定改善。字符串模式匹配在許多科學(xué)領(lǐng)域有著非常重要的應(yīng)用，如何發(fā)掘更高效的匹配算法，還有待于進(jìn)一步的探討和研究。由于時(shí)間和精力的關(guān)系，沒(méi)有對(duì)多模式匹配算法進(jìn)行更多的研究，下一步考慮把多模式匹配引入到入侵檢測(cè)系統(tǒng)中。

[1]劉沛騫，馮晶晶.一種改進(jìn)的BM模式匹配算法[J].計(jì)算機(jī)工程，2011，37（17）：248-251.

[2]姜慶民，吳寧，劉偉華.面向入侵檢測(cè)系統(tǒng)的模式匹配算法研究[J].西安交通大學(xué)學(xué)報(bào)，2009，43（2）：58-62.

[3]Boyer R S，Moore J S.A fast searching algorithm[J].Communications of the ACM，1977.

[4]Hernandez M.A taxonom y of some right-to-left stringmatching algorithms[J].Computer Science，2010，58：79-95.

[5]黃文奇，熊正大.基于BM方法的字符串匹配復(fù)化算法[J].華東科技大學(xué)學(xué)報(bào)，2009，12（8）：48-51.

[6]王天聰，侯整風(fēng)，何玲.基于BM的模式匹配改進(jìn)算法[J].合肥工業(yè)大學(xué)學(xué)報(bào)，2011（34）：38-40.

[7]王浩，張霖，張慶.基于雙字符序檢測(cè)的BM模式匹配改進(jìn)算法[J].計(jì)算機(jī)工程與科學(xué)，2012（3）：20-24.

[8]楊潔，劉聰峰.模式匹配與校驗(yàn)和相結(jié)合的IP協(xié)議識(shí)別方法[J].西安電子科技大學(xué)學(xué)報(bào)，2012（3）：47-51.

[9]Sundey D M.A very fast substring search algorithm[J]. Communications of the ACM，1990，33（8）：132-142.

[10]王浩，周曉峰.基于入侵檢測(cè)系統(tǒng)Snort的BM模式匹配算法的研究和改進(jìn)[J].計(jì)算機(jī)安全，2009（2）：38-40.

[11]Horspoon N.Practical fast searching in strings[J].Software-Practice and Experience，1980，10：501-506.

[12]Salmela L，Tarhio J，Kalsi P.Approximate Boyer-Moore string matching for small alphabets[J].A lgorithm ica，2010，58（3）：591-198.

[13]關(guān)超，蔣建中，郭軍利.一種基于反向有限自動(dòng)機(jī)的多模式匹配算法[J].計(jì)算機(jī)工程，2010，36（1）：208-210.

LI Weinan1，2,YU Huiqun2

1.Department of Computer Science and Engineering,East China University of Science and Technology,Shanghai 200237,China
2.Shanghai Key Laboratory of Computer Softw are Evaluating and Testing,Shanghai 201112,China

The essence of classical string matching algorithms is sequential character matching which is always from left to right or from right to left.In the main string,if there are many substrings which have the same prefix or suffix with the pattern string,the algorithms are in the low efficiency.The maximum length for the shift is the length of the pattern string. The improved algorithm uses the two-string-separate-comparison method,effectively avoiding meaningless comparison times due to the same prefix or suffix of substrings and the pattern string.Since the algorithm calculates moving distance of the pattern string according to the improved bad character rule,it increases moving distance of the pattern string.The experimental results show that the improved string matching algorithm can effectively reduce the string matching times and moving times to im prove the algorithm efficiency.

matching;pattern string;main string;intrusion

A

TP313

10.3778/j.issn.1002-8331.1208-0524

LI Weinan,YU Huiqun.Improved string matching algorithm based on BM.Computer Engineering and Applications,2014,50（16）：104-108.

國(guó)家自然科學(xué)基金（No.61173048，No.60773094）；上海市曙光計(jì)劃（No.07SG32）資助。

李韋男（1987—），男，碩士，主要研究領(lǐng)域?yàn)槿肭謾z測(cè)、模式匹配算法；虞慧群（1967—），男，博士，教授，博士生導(dǎo)師，主要研究領(lǐng)域?yàn)檐浖こ?、信息安全、形式化方法。E-mail：liweinan54321@163.com

2012-09-07

2012-11-02

1002-8331（2014）16-0104-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2012-11-28,http://www.cnki.net/kcm s/detail/11.2127.TP.20121128.1453.001.htm l