李韋男，虞慧群

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

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

一種改進的BM字符串匹配算法

李韋男1，2，虞慧群2

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

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

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

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

1 引言

在計算機科學領域，字符串匹配算法一直都是研究焦點之一。在拼寫檢查、語言翻譯、數(shù)據(jù)壓縮、搜索引擎、網(wǎng)絡入侵檢測、計算機病毒特征碼匹配以及DNA序列匹配等應用中，都需要進行字符串匹配。字符串匹配是入侵檢測系統(tǒng)所使用的基于攻擊特征的網(wǎng)絡數(shù)據(jù)包檢測技術，也是入侵檢測系統(tǒng)中一個最基本、最關鍵的技術。在實際的網(wǎng)絡運行中，字符串匹配速度的快慢直接影響到入侵檢測系統(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算法等。近年來，很多專家學者都提出過基于BM算法的改進算法。文獻[1]提出的改進的BM算法是在應用壞字符規(guī)則的過程中，如果主串中連續(xù)的幾個字符不在模式串中出現(xiàn)[1]，則不需要被比對，以此改變模式串的匹配順序，這樣可增大模式串匹配的滑動距離，提高算法的匹配效率。雖然該方法可提高算法的效率，但此種情況的發(fā)生幾率非常小，因此該方法仍有待改進。文獻[2]算法改進為：引入一個新的判斷函數(shù)Q(X)指出字符X在模式串中出現(xiàn)的次數(shù)，當出現(xiàn)次數(shù)為l時可以利用已匹配的信息加大移動距離[2]，同時利用文本串中不匹配字符后面的一個字符進行匹配，從而得到一個移動距離，將不同移動規(guī)則下獲得的移動距離的最大值作為實際的移動距離，依次進行，直到匹配完成。通過實驗證明，該算法的移動次數(shù)和比較次數(shù)確有減少，不過增加了內存占用，并且當文本字符出現(xiàn)頻率相當時，該算法效果并不理想。

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

2 改進字符串匹配算法

2.1 經典字符串匹配算法

介紹算法之前，做如下定義，主串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向右移動一個字符的位置，再依次進行比較。如果存在k，1≤k≤N，且T[k+1…k+M]=P[1…M]，則匹配成功；否則失敗。BF算法的實現(xiàn)比較簡單，但是效率低，時間復雜度高[3]。該算法最壞情況下要進行M×(N-M+1)次比較，時間復雜度為O(M×N)。

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

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

2.2 改進字符串匹配算法

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

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

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

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

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

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

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

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

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

算法流程如圖1。

圖1 算法流程圖

2.3 算法的實現(xiàn)

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

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

3 實例及分析

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

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

圖2 BM算法第一步

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

圖3 BM算法第二步

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

圖4 BM算法第三步

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

圖5 BM算法第四步

模式串與主串比較5次，找到模式串?？傆嬆Ｊ酱苿?次，與主串字符比較14次，完成字符串匹配。

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

圖6 改進算法第一步

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

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

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

圖7 改進算法第二步

圖8 改進算法第三步

3.1 改進算法時間復雜度分析

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

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

3.2 改進算法性能分析

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

第一段測試文本部分內容：”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ù)進行比較如圖9。

圖9 平均字符匹配次數(shù)與模式串長度關系

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

第二段測試文本部分內容：“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，文獻[1]算法，本文算法的運行時間分別為17，15，11。模式串長度為6時，BM，文獻[1]算法，本文算法的運行時間分別為14，12，9。模式串長度為10時，BM，文獻[1]算法，本文算法的比較次數(shù)分別為10，9，7。

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

4 結論

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

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

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

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

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

[8]楊潔，劉聰峰.模式匹配與校驗和相結合的IP協(xié)議識別方法[J].西安電子科技大學學報，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].計算機安全，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]關超，蔣建中，郭軍利.一種基于反向有限自動機的多模式匹配算法[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.

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

李韋男（1987—），男，碩士，主要研究領域為入侵檢測、模式匹配算法；虞慧群（1967—），男，博士，教授，博士生導師，主要研究領域為軟件工程、信息安全、形式化方法。E-mail：liweinan54321@163.com

2012-09-07

2012-11-02

1002-8331（2014）16-0104-05

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