彭佳容

湖北省武昌實驗中學(xué) 湖北 430061

0 引言

本文對現(xiàn)今很多 KMP模式匹配改進算法進行了總結(jié)概述，并設(shè)計了一種文件內(nèi)容快速匹配算法。該算法是在傳統(tǒng)KMP模式匹配的基礎(chǔ)上進行改良，針對現(xiàn)有的多處理器進行并行匹配運算，大大提高了病毒特征值匹配速度，有助于高效的進行病毒攔截，有很好的實際應(yīng)用效果。

1 KMP算法介紹

模式匹配是指已知長度為n的文本字符T=t1t2…tn和長度為m(m＜＜n)的模式字符串P=p1p2…pn，問T是否存在長度為m 的子串，使得 ti+1ti+2…ti+m=p1p2…pm(i＜=n-m)。

KMP算法是串匹配算法中效率較高的。KMP模式算法的基本思想：當(dāng)一次匹配過程中出現(xiàn)失敗時，無需回溯主串指針，而是充分利用已經(jīng)得到“部分匹配”的結(jié)果將模式串向右滑動，其特點是：消除了簡單算法中的主串指針在相當(dāng)多個字符串比較相等后，只要有一個字符比較不相等便需要回退的缺點。該算法時間復(fù)雜度為O(m+n)。

在KMP算法中引入模式串的next[j]函數(shù)：

設(shè)主串t，模式串p，t當(dāng)前比較字符下標(biāo)為i，p當(dāng)前比較字符下標(biāo)為j。當(dāng)ti=pj是，i和j分別增1再繼續(xù)比較；否則i不變，j改變?yōu)閚ext[j]值后再繼續(xù)比較。依次類推，直到出現(xiàn)下列兩種情況之一：一是 j退回到某個 j=next[j]值時有ti=pj，則i和j分別增1后再繼續(xù)比較；二是j退回到j(luò)=0，令主串和模式串下標(biāo)各增1，隨后比較ti+1和p1。這樣一直循環(huán)到i大于等于t.length或者j大于等于p.length時為止，KMP算法相比簡單模式匹配算法的核心是next數(shù)組的構(gòu)造。

模式串 P開頭的任意個字符，把它稱為前綴子串，如p0p1p2…pm-1。在P的第i位置的左邊，取出k個字符，稱為i位置的左子串，即 pi-k+1... pi-2pi-1pi。求出最長的(最大的 k)使得前綴子串與左子串相匹配稱為在第i位的最長前綴串。第i位的最長前綴串的長度k就是模式串P在位置i上的特征數(shù)next[i]組成的向量稱為該模式串的特征向量。

可以證明對于任意的模式串 P=p0p1…pm-1，確實存在一個由模式串本身惟一確定的與目標(biāo)串無關(guān)的數(shù)組next，計算方法為：

(1) 求p0…pi-1中最大相同的前綴和后綴的長度k;

(2) next[i] = k;

作為特殊情況，當(dāng)i=0時，令next[i] = -1；顯然，對于任意 i(0≤i＜m)，有 next[i] ＜ i；特征數(shù) next[i](-1≤next[i]≤i)是遞歸定義的，定義如下：

(1) next [0] =-1，對于i ＞ 0的next [i]，假定已知前一位置的特征數(shù)next[i-1]= k；

(2) 如果pi= pk，則next[i] ＝ k＋1；

(3) 當(dāng)pi≠ pk且k≠0時，則令k = next[k -1]；讓(3)循環(huán)直到條件不滿足；

(4) 當(dāng)pi≠ pk且k = 0時，則next[i] = 0;

根據(jù)以上分析，可以得到next特征數(shù)組的計算方法，算法代碼如下：

void get_next(const char *s, int *next) { //s是模式串，next是next[j]數(shù)組

int i = 0, j;

int len = strlen(s);

j = next[0] = -1;

while (i ＜ len - 1) {

while (j ＞ -1 && *(s + j) != *(s + i)) {

j = next[j];

}

++i;

++j;

next[i] = j;

}

}

2 改進的KMP算法的研究

2.1 文獻研究

翻閱查看了不少 KMP改進算法，發(fā)現(xiàn)其改進僅限于兩種方式，一種是對 KMP本身繼續(xù)改良，使得主串可以滑動更遠進而加快匹配進度；另一種是在主串的首端和末端交替向中間進行匹配。

(1) 對于第一種改進的模式匹配算法，查看文獻[2]和文獻[3]，可以發(fā)現(xiàn)兩篇論文幾乎一模一樣，不僅如此，兩篇論文中提到的改進KMP算法存在錯誤，在文獻[2]的第三部分“對KMP算法的改進”和文獻[3]的第四部分“算法的基本思

想”中提到的算法代碼如下：

int kmpa(char s[ ],char t[ ],int next[ ]){

int i=0,j=0,k=0;

m=len(s);

n=len(t);

while(i＜m&&j＜n) {

if(j==-1||t[j]==s[i]) {

i++;

j++;

}

else {

k=next[t];

if(i+j-k＜=m&&t[j]!=s[i+j-k]) i=i+j-k;

j=next[j];

}

}

if(j＞=n) return(i-n);

else return 0;

}

其中改進的地方是比 KMP算法多了語句 if if(i+j-k＜=m&&t[j]!=s[i+j-k]) i=i+j-k；也就是在遇到不匹配情況下主串可以繼續(xù)向前滑動 j-k，而不是簡單的向前滑動一位。其中k=next[t]，而t是未曾出現(xiàn)過的字符，根據(jù)文獻中舉例可以推斷出，此處的 t應(yīng)該是 j，也就是作者的意思是k=next[j]。同時可以舉例證明該算法是錯誤的，主串T=”abaababaabc”和模式串 P=”abaabc”,鑒于文獻[2]和文獻[3]中提出的算法，在i=5和j=5的時候不匹配，此時根據(jù)此算法k=next[5]=2，i+j-k=8，比較t[5]和s[8]可知不等，此時將i滑動至8，j=next[j]=next[5]=2；繼續(xù)比較可知s[8]=t[2]，繼續(xù)向前比較s[9]和t[3]二者不等這樣一直比較下去將會返回0得不到匹配。顯然可以看出該主串是可以匹配模式串的返回值應(yīng)該是6。由此分析可知文獻[2]和文獻[3]的算法是錯誤的。反例匹配過程如下：

Step1: T = a b a a b ab a a b c

S = a b a a b c此時i=5，j=5 T(5)≠S(5)

根據(jù)算法此時k=next[5]=2, i=i+j-k=8, j=next[j]=2 Step2: T = a b a a b a b a ab c

S = a b aa b c 此時 i =8，j=2 T(8)＝S(2)

根據(jù)算法此時i=9,j=3

Step3: T = a b a a b a b a a bc

S = a b a ab c 此時 i =9，j=3 T(9)≠S(3)

根據(jù)算法此時k=next[3]=1,i=i+j-k=11,j=next[j]=1,i＞n返回0

(2) 對于第二種改進方式是將主串與模式串從前到后、從后到前交替進行字符比較。引入函數(shù)Q(r)，在模式兩端分別求Q(r)函數(shù)值，根據(jù)兩端當(dāng)前字符的Q(r)函數(shù)值，實模式交替向中間滑動盡可能遠的一段距離后，繼續(xù)匹配。根據(jù)該改進算法的思想，分析可知，當(dāng)模式串與主串匹配成功的位置靠近左端或者中間的時候，本算法匹配的次數(shù)是簡單KMP匹配算法的兩倍；當(dāng)成功匹配的位置靠近右端的時候，設(shè)本算法已經(jīng)匹配了t次，用簡單KMP匹配了要匹配n+m-t/2次(n為主串長度，m為模式串長度)，當(dāng)n＞＞m時，改進算法效率有明顯提高。綜合分析，改進的交替算法平均時間復(fù)雜度與簡單 KMP算法平均時間復(fù)雜度一樣，在病毒特征碼掃描技術(shù)中的應(yīng)用性不強。

2.2 本文算法思想

(1) next數(shù)組的改進

傳統(tǒng)的next數(shù)組計算方法仍然存在不必要的回溯問題。例如對于 T=aaabaaaab，P=aaaa的模式匹配，使用傳統(tǒng)的方法next值為-1,0,1,2。當(dāng)T3=b與P3=a比較失敗后，根據(jù)next值，T3需要與P2比較，但是可以看出P2=P3，因此這個比較是沒有必要的。因此本文提出了一個next數(shù)組算法的改進，在本文提到的next數(shù)組算法代碼中，把next[i] = j替換為以下代碼：

if (s[i] == s[j]) d[i] = d[j];

else d[i] = j;

(2) KMP算法的改進

本文提出了從主串T兩頭同時匹配的思想。使用并行計算或者多線程處理，可以使得匹配從主串兩頭同時進行。這里使用多線程實現(xiàn)作為例子，其中一個線程匹配成功后立即返回，另一個線程同時終止計算，也就是說模式串位于主串的任何位置，總是能夠通過最少的匹配次數(shù)完成匹配。如果模式串位于主串的前半段，那么從首部開始匹配的線程很可能首先匹配成功然后終止匹配；如果模式串位于主串后半部分，那么從尾部開始匹配的線程很可能首先匹配成功，這樣就解決了文獻[4]中模式串位于主串前半部分帶來的匹配次數(shù)增加的問題。

當(dāng)然并不是說模式串位于主串的前(后)半段，那么從首(尾)部開始匹配的線程就一定首先匹配成功，但是不論如何總是用較少匹配次數(shù)就匹配成功的線程首先返回，也就是說使用本文提出的思想，匹配次數(shù)總是最少。

3 算法性能測試

評價一個模式匹配算法優(yōu)劣程度的一個重要指標(biāo)是字符的匹配次數(shù)。本文對傳統(tǒng)的KMP算法和本文提出的KMP改進算法的匹配次數(shù)進行了實驗比較。

首先使用一般文本串和模式串進行實驗，結(jié)果如表1所示。

表1 一般文本串匹配次數(shù)比較

當(dāng)模式串位于主串的前半部分，那么匹配次數(shù)小于等于傳統(tǒng) KMP算法，而當(dāng)模式串中有大量重復(fù)子串時匹配次數(shù)小于傳統(tǒng) KMP算法；當(dāng)模式串位于主串的后半部分，改進算法的匹配次數(shù)顯然是小于傳統(tǒng) KMP算法的。也就是說，改進算法的平均匹配次數(shù)是小于傳統(tǒng)的 KMP算法的，當(dāng)主串很長時這種優(yōu)勢尤其明顯。下面就來看看改進算法用在病毒特征值檢測時的表現(xiàn)。

測試采用不同的病毒文件和不同的模式串對兩種串匹配算法進行測試比較，測試程序有C++實現(xiàn)，具體結(jié)果如表2所示。

表2 病毒特征值檢測匹配次數(shù)比較

4 總結(jié)

本文在傳統(tǒng) KMP模式匹配算法和一系列改進的模式匹配算法進行分析比對，結(jié)合現(xiàn)有改進算法，對 KMP進一步改進，通過對算法的分析及實驗證實，改進后的算法具有更高的匹配效率。因此將本文算法應(yīng)用到病毒特征碼掃描檢測系統(tǒng)中，可以極大提高系統(tǒng)檢測效率。

[1]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社.2003.

[2]蔣文沛.對字符串模式匹配KMP算法的探討[J].南寧師范高等?？茖W(xué)校學(xué)報.2001.

[3]楊戰(zhàn)海.KMP 模式匹配算法的研究分析[J].計算機與數(shù)字工程.2010.

[4]俞松,鄭俊,胡文心.一種改進的 KMP算法[J].華東師范大學(xué)學(xué)報.2009.

[5]田宏,李君秋.一種改進的模式匹配算法[J].大連交通大學(xué)學(xué)報.2010.

[6]魯宏偉,魏凱,孔華鋒.一種改進的 KMP高效模式匹配算法[J].華中科技大學(xué)學(xué)報(自然科學(xué)版).2006.

[7]D E Knuth,J H Morris.V R Pratt. Fast Pattern Matching in Strings[J].SIAM Journals on Computing.1977.

[8]王成,劉金剛.一種改進的字符串匹配算法[J].計算機工程.2006.

[9]秦曉明,牛全營,吳淼.入侵檢測系統(tǒng)中模式匹配算法的優(yōu)化研究[J].計算機與現(xiàn)代化.2009.

[10]G. Navarro, K. Fredriksson. Average complexity of exact and approximate multiple string matching[J]. Theoretical Computer Science.2004.

[11]湯亞玲.KMP算法中next數(shù)組的計算方法研究[J].計算機技術(shù)與發(fā)展.2009.

[12]劉云峰.模式匹配及其改進算法在入侵檢測系統(tǒng)中的應(yīng)用[J].電腦開發(fā)與應(yīng)用.2011.

[13]M. Crochemore,A. Czumaj,L.Gasieniec,et al.Speeding Up Two String-Matching Algorithms[J]. Algorithmica.1994.

[14]王戰(zhàn)紅,張珂,姚瑤.一種KMP算法中求nextval數(shù)組的改進算法[J].信陽師范學(xué)院學(xué)報(自然科學(xué)版).2008.