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

李韋男，虞慧群

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

2.計算機軟件評測重點實驗室，上海 201112

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

李韋男1，2，虞慧群2

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

2.計算機軟件評測重點實驗室，上海 201112

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

實際的移動距離則為max(skip1(x)，skip2(y)。

算法流程如圖1。

圖1 算法流程圖

2.3 算法的實現(xiàn)

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

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

3 實例及分析

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

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

圖2 BM算法第一步

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

圖3 BM算法第二步

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

圖4 BM算法第三步

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

圖5 BM算法第四步

模式串與主串比較5次，找到模式串。總計模式串移動3次，與主串字符比較14次，完成字符串匹配。

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

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

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

比較2次，模式串c與主串b失配，模式串右移4位。模式串與主串比較5次，找到模式串?？傆嬆Ｊ酱苿?次，與主串字符比較8次，完成字符串匹配。

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

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

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

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

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

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

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

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

第一段測試文本部分內(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ù)與模式串長度關(guān)系

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

第二段測試文本部分內(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.”算法運行時間比較如圖10。

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

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

4 結(jié)論

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

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

[2]姜慶民，吳寧，劉偉華.面向入侵檢測系統(tǒng)的模式匹配算法研究[J].西安交通大學(xué)學(xué)報，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é)報，2009，12（8）：48-51.

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

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

[8]楊潔，劉聰峰.模式匹配與校驗和相結(jié)合的IP協(xié)議識別方法[J].西安電子科技大學(xué)學(xué)報，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]王浩，周曉峰.基于入侵檢測系統(tǒng)Snort的BM模式匹配算法的研究和改進(jìn)[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)超，蔣建中，郭軍利.一種基于反向有限自動機的多模式匹配算法[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.

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

李韋男（1987—），男，碩士，主要研究領(lǐng)域為入侵檢測、模式匹配算法；虞慧群（1967—），男，博士，教授，博士生導(dǎo)師，主要研究領(lǐng)域為軟件工程、信息安全、形式化方法。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