1 BM演算法研究
1977年Boyer和Moore提出了一種全新的演算法,即BM演算法。它的特點在於匹配過程中,模式從左向右移動,但字元比較卻從右向左進行。其基本演算法思想是:(1)匹配從右至左進行。(2)若匹配失敗發生在Pi≠Ti且Ti不出現在模式P中,則將模式右移直到Pi位於匹配失敗位置T的右邊第一位(即Ti 1位),若Ti在P中有若干地方出現,則選擇j=max{k|Pk=Ti}即通過Skip函式計算文字字元Ti失配時模式向右移動的距離,也稱壞字元啟發。(3)若模式後面k位與文字T中一致的部分有一部分在P中其他地方出現,則可以將P向右移動,直接使這部分對齊,且要求這一部分儘可能大,Shift函式通過對已經匹配部分的考查決定模式向右移動的距離,也稱好字尾啟發。
例項分析:
第1次匹配:
Example
here is a simple example
第2次匹配(壞字元啟發):
Example
here is a simple example
第3次匹配(壞字元啟發):
Example
here is a simple example
第4次匹配(好字尾啟發):
Example
here is a simple example
第5次匹配(壞字元啟發):
Example
here is a simple example
BM演算法預處理時間複雜度為O(m s),空間複雜度為O(s),s是與P, T相關的有限字符集長度,搜尋階段時間複雜度為O(mn)。最壞情況下要進行3n次比較,最好情況下的時間複雜度為O(n/m)。
2 改進BM匹配演算法研究
2.1 改進的意義
綜合分析會發現雖然BM演算法考慮較全面,但它使用了兩個陣列,預處理時間開銷較大,於是在BM演算法基礎上我們對其進行了簡化,使得演算法更簡單、高效,提出了一種改進的BM演算法。通過實驗表明改進的模式匹配演算法能減少比較次數,有效地提高了匹配效率。
2.2 改進的原理
在BM演算法匹配過程中,常出現模式的一部分字尾與文字匹配,而模式的字首卻不匹配,在這種情況下,就進行了一些不必要的比較。因此在BMGJ演算法中,我們在對模式串與文字字串進行匹配時採用從模式兩端向中間位置交替的匹配順序,模式匹配先從模式最右端Pm開始進行。若Pm匹配不成功,則通過Skip函式計算出模式向右移動的距離,這與BM演算法中壞字元啟發思想相同;若Pm匹配成功,則比較模式P1與文字中相應的字元。若P1匹配不成功,則考查文字中與模式中Pm下一個字元對齊的字元,若該字元不出現在模式中,則模式可以向右移動m 1個位置,若該字元出現在模式中,則計算其Skip函式,然後將模式向右移動相應的長度;若P1匹配成功,則按上述方法依次對Pm-1,P2,Pm-2,P3,…進行匹配,依此類推,直到匹配過程完成。例項分析:
第1次匹配:
Example
here is a simple example
第2次匹配:
Example
here is a simple example
第3次匹配(傳統BM演算法匹配中,此遍比較需要從右端比較5次才可以找到一個壞字元,但對於改進後的演算法,只比較兩次就可以找到一個壞字元):
Example
here is a simple example
第4次匹配:
Example
here is a simple example
第5次匹配:
Example
here is a simple example
在上例中,我們可以看出用傳統的BM演算法匹配共進行了4次移動15次比較,用改進的BM演算法匹配共進行了4次移動12次比較,匹配次數減少。
改進後的BM演算法的預處理時間複雜度為O(m s),空間複雜度為O(s),搜尋階段時間複雜度為O(mn)。該演算法在比較右端字元失配時採用BM壞字元啟發的思想,在比較了左端字元失配時採用對文字中與模式最右端對齊的下一個字元進行考查的方法,使得大多數情況下具有比BM演算法更大的右移長度,從而有更好的平均效能。
2.3 改進的實驗分析
我們所做的實驗軟體環境主要是:採用的作業系統是MicroSoft Windows XP Professional(Service Pack2),使用JBuilder2006編譯工具,所用JDK為jdk1.6。
為了對各演算法的效能進行比較次數和比較用時的測試,我們隨機地選取了一段純英文自然語T文字和模式串P,在同一臺計算機上用不同演算法進行3萬、5萬、10萬次迴圈匹配,分別統計各演算法迴圈匹配所進行的.字元比較次數和總消耗的時間。
文字串:T=One day one pig went to a bar and the bar tender asked what can I get for you today and the pig said five beers. He drank up all the beer and then he asked were the bathroom was the bar tender said straight down the hall to the left. Then three more pigs came in and the bar tender asked what can I get you today.
模式串:P= I get you today.
測試結果下表1所示:
經過多次匹配實驗,結果顯示改進後的BM演算法進行模式匹配時字元比較次數、匹配時間均少於原BM演算法,匹配效率有所提高。
3 結語
隨著網路規模的不斷擴大和入侵手段的不斷更新,對入侵檢測也提出了更高的要求。目前,BM演算法還是入侵檢測系統中主要使用的模式匹配方法,而它本身存在的一些問題使其還是有改進的餘地,本文對其進行了改進,並且通過實驗結果分析得出改進以後在匹配效率的提高。以後我們還可以在檢測引擎中結合其他智慧化的檢測方法,如協議分析、神經網路、遺傳演算法等,這將是我們下一步研究的重點。
參考文獻
[1]?谷曉鋼,江榮安,趙銘偉t的高效規則匹配演算法[J].計算機工程,2006,(18).
[2]?唐正軍.入侵檢測技術導論(第一版)[M].北京:機械工業出版社,2004.
[3]?邊肇祺,閻平凡,楊存榮.模式識別(第一版)[M].北京:清華大學出版社,1988.
[4]?郭軍,笹尾勤.入侵檢測中模式匹配演算法的FPGA實現[J].科技創新導報,2007,(14).