一種改進的BMH模式匹配算法

姚保峰,王 磊

(蚌埠學(xué)院計算機科學(xué)與技術(shù)系,安徽233000)

0 引 言

隨著Internet的快速發(fā)展,網(wǎng)絡(luò)的安全問題顯得日益突出.網(wǎng)絡(luò)入侵已經(jīng)對現(xiàn)有的計算機網(wǎng)絡(luò)安全構(gòu)成了巨大威脅.因此,針對網(wǎng)絡(luò)入侵行為的入侵檢測系統(tǒng)逐漸成為當(dāng)前研究的重點.目前最常見的入侵檢測系統(tǒng)是基于特征的入侵檢測系統(tǒng),這種系統(tǒng)基于模式匹配技術(shù),就是通過提取已有攻擊信息的特征編碼成模式,然后將審計信息與該模式進行匹配,從中發(fā)現(xiàn)是否存在攻擊行為.因而制約這種入侵檢測系統(tǒng)性能的主要因素之一就是模式匹配算法的效率.

首先引入模式匹配算法的概念[1].模式匹配算法是指對文本串 T的一次掃描,只能處理一個模式串P,并且在匹配過程中不允許存在誤配字符,即模式串P[1,…,m]中的所有字符必須和文本串 T的子串T[i,…,i+m-1](0≤i≤n-m+1)中的字符一一對應(yīng).本文首先對現(xiàn)有的幾種典型模式匹配算法進行分析,并針對其中最優(yōu)的BMH算法進行改進,最后進行仿真實驗和結(jié)果分析.

1 典型算法

BF算法[2]是最簡單,最直觀的模式匹配算法,具體方法是從文本串的第1個字符起與模式串的第1個字符比較,若相等,則逐個比較后續(xù)字符,否則,從文本串第2個字符起重新和模式串第1個字符比較.此算法的特點是簡單且容易理解,但是計算復(fù)雜度大,效率低.

KMP算法[3]的基本思想是若某趟匹配過程中文本串T中的字符T[i]和模式串P中的字符P[j]不匹配,而前j-1個字符已經(jīng)匹配.此時只需右移P,T不動,即指針 i不回溯,讓 P[k]與 T[i]繼續(xù)比較.移動后重新開始比較的位置k僅與P有關(guān),而與目標(biāo)串(即文本串T還未進行匹配的串)無關(guān),而k可事先確定.若令 next(j)=k,則next函數(shù)可以定義為:

KMP算法將模式串向右滑動可以提高匹配算法的效率,但相對比較復(fù)雜,且經(jīng)實驗證明,在部分情況下效率甚至比BF低.

BM算法[4]的基本思想是先將模式串P與文本串T左對齊.匹配從P的最右端字符開始,判斷P[m]與T[m]是否匹配,如果匹配成功,則繼續(xù)判斷P[m-1]與T[m-1]是否匹配,循環(huán)繼續(xù)下去,直到P中的字符全部匹配成功或者是有不匹配的字符出現(xiàn).算法采用好后綴規(guī)則和壞字符規(guī)則分別計算劃動距離并取兩者的最小值.BM算法在實際的模式匹配中,跳過了很多無用的字符,這種跳躍式的比較方式,使BM算法獲得了極高的效率,特別是在大字符集上進行字符串的模式匹配時.在實際的應(yīng)用中,BM 算法的效率比KMP算法高出3～5倍.

BMH算法[5]只采用了BM算法的壞字符移動規(guī)則,并且將失配情況與偏移量的計算獨立,不關(guān)心文本串中哪個字符造成了失配,只考慮用與模式串最右端對齊的文本字符來決定偏移量,平均情況下提高了匹配速度.

2 改進的BMH算法

改進的BMH算法采用壞字符移動規(guī)則,當(dāng)發(fā)生失配時,則用與模式串P最右端對齊的文本字符及其下一字符來共同計算偏移量,即偏移量函數(shù)是取文本串 T中的每兩個連續(xù)字符進行計算.設(shè)c1和c2是T中的兩個連續(xù)字符,m是模式串P的長度,則偏移量函數(shù)dist可以表示為:

根據(jù)上述基本思想,我們?nèi)∧Ｊ酱甈的最后一位字符對應(yīng)的文本字符T[i]及其下一字符 T[i+1]作為一個子串.當(dāng)子串在模式串P中出現(xiàn)時,則模式串P右移,使得該子串與它在模式串P中最右端的出現(xiàn)位置對齊,如圖1所示;否則,當(dāng)子串不在模式串P中出現(xiàn)時,模式串P可以右移最大值m,如圖2所示.

根據(jù)改進算法偏移量函數(shù)的定義,需要每次取兩個字符來計算文本串中子串的偏移量.因此,我們需要定義一個二維數(shù)組作為偏移量數(shù)組.在數(shù)組初始化時,首先將二維數(shù)組的值全部置為m;然后再根據(jù)壞字符移動規(guī)則計算文本串T中每個子串的偏移量.具體算法描述如下:

void get_dist(char p[],int m,int dist[][N])

{

int n,i,j=0;

for(i=0;i＜N;i++)

for(j=0;j＜N;j++)

dist[i][j]=m;

for(i=0;i＜m-1;i++)

dist[p[i]][p[i+1]]=m-i-1;

}

int search_BM(char t[],char p[],int dist[][N])

{

int n,m,k,sp=0;

n=strlen(t);

m=strlen(p);

if(m＞n)return-1;

k=m-1;

while(k＜n)

{

int j=m-1;

int i=k;

while(j＞=0&&t[i]==p[j])

{i--;j--;}

if(j==-1)

return i+1;

else

k=k+dist[t[k]][t[k+1]];

}

return-1;

}

3 算法分析

從BMH算法的匹配過程可以看出,BMH算法在比較時每次只取T中的一個字符和P中的一個字符進行比較,當(dāng)發(fā)生失配時,以P中最后一個字符P[m]對應(yīng)的文本串字符 T[i]的偏移量作為P的移動距離.這種情況下,只有當(dāng)T[i]不在P中出現(xiàn)時,模式串才能獲得最大移動距離m.從概率論的角度考慮,兩個連續(xù)字符出現(xiàn)在模式串中的概率應(yīng)遠遠低于一個字符出現(xiàn)的概率,因此,改進的BMH算法以兩個連續(xù)字符計算偏移量作為P的移動距離,模式串獲得最大移動距離m的概率也大的多,這樣顯然可以獲得更高的匹配速度.

不能夠取更多的連續(xù)字符(如三個)去計算偏移量的原因在于,兩個連續(xù)字符出現(xiàn)在模式串中的幾率已經(jīng)很低了,采用更多的字符并不能夠得到明顯的幾率變化,卻會導(dǎo)致每次取字符時間的大幅增加,因而是得不償失的.

4 算法性能測試

本實驗使用的計算機硬件平臺為AMD Athlon64×2 3600+處理器,2G內(nèi)存,軟件平臺為Window s XP操作系統(tǒng),VC++6.0集成開發(fā)環(huán)境.在此環(huán)境下分別對BMH和改進的BMH算法進行測試,測試程序與算法均使用C語言編寫,用同一主程序分別調(diào)用這兩種算法,匹配算法中使用C語言的時間函數(shù)進行高精度計時,以便顯示比較結(jié)果.

隨機抽取十份文本文件,分別用BMH算法和改進的BMH算法進行算法性能測試,結(jié)果如下表1所示.

表1 兩種匹配算法性能測試情況

從圖3和圖4可以看出,IBMH算法無論是在完成匹配時模式串的右移次數(shù)上,還是在匹配中消耗的時間上,都具有一定的優(yōu)勢.

5 結(jié)束語

改進的BMH算法取文本串中的兩個連續(xù)字符計算偏移量,使模式串以最大移動量右移的幾率得到增加.實驗結(jié)果表明,該算法能夠有效的減少字符串匹配的次數(shù),提高了模式匹配的速度.

[1]曾慧惠,袁世忠,胡 鵬.入侵檢測系統(tǒng)中高效模式匹配算法的研究[J].計算機應(yīng)用與軟件,2008,25(4):226-227.

[2]周延森,汪永好.王 磊.入侵檢測系統(tǒng)模式匹配算法研究[J].計算機工程與設(shè)計.2008,29(7):1652-1654,1683.

[3]張國平,徐汶東.字符串模式匹配算法的改進[J].計算機工程與設(shè)計,2007,(10):4881-4884.

[4]Boyer RS,Moore J S.A Fast String Searching Algorithm[J].Communications of ACM,1977,20(10):762-772.

[5]Horspool R N.Practical Fast Searching in Strings[J].Software-practics&Experience,1990(10):501-506.