病毒特征值掃描中模式匹配算法的研究.

彭佳容

湖北省武昌實驗中學 湖北 430061

0 引言

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

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模式算法的基本思想：當一次匹配過程中出現失敗時，無需回溯主串指針，而是充分利用已經得到“部分匹配”的結果將模式串向右滑動，其特點是：消除了簡單算法中的主串指針在相當多個字符串比較相等后，只要有一個字符比較不相等便需要回退的缺點。該算法時間復雜度為O(m+n)。

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

設主串t，模式串p，t當前比較字符下標為i，p當前比較字符下標為j。當ti=pj是，i和j分別增1再繼續比較；否則i不變，j改變為next[j]值后再繼續比較。依次類推，直到出現下列兩種情況之一：一是 j退回到某個 j=next[j]值時有ti=pj，則i和j分別增1后再繼續比較；二是j退回到j=0，令主串和模式串下標各增1，隨后比較ti+1和p1。這樣一直循環到i大于等于t.length或者j大于等于p.length時為止，KMP算法相比簡單模式匹配算法的核心是next數組的構造。

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

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

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

(2) next[i] = k;

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

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

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

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

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

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

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

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改進算法，發現其改進僅限于兩種方式，一種是對 KMP本身繼續改良，使得主串可以滑動更遠進而加快匹配進度；另一種是在主串的首端和末端交替向中間進行匹配。

(1) 對于第一種改進的模式匹配算法，查看文獻[2]和文獻[3]，可以發現兩篇論文幾乎一模一樣，不僅如此，兩篇論文中提到的改進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；也就是在遇到不匹配情況下主串可以繼續向前滑動 j-k，而不是簡單的向前滑動一位。其中k=next[t]，而t是未曾出現過的字符，根據文獻中舉例可以推斷出，此處的 t應該是 j，也就是作者的意思是k=next[j]。同時可以舉例證明該算法是錯誤的，主串T=”abaababaabc”和模式串 P=”abaabc”,鑒于文獻[2]和文獻[3]中提出的算法，在i=5和j=5的時候不匹配，此時根據此算法k=next[5]=2，i+j-k=8，比較t[5]和s[8]可知不等，此時將i滑動至8，j=next[j]=next[5]=2；繼續比較可知s[8]=t[2]，繼續向前比較s[9]和t[3]二者不等這樣一直比較下去將會返回0得不到匹配。顯然可以看出該主串是可以匹配模式串的返回值應該是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)

根據算法此時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)

根據算法此時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)

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

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

2.2 本文算法思想

(1) next數組的改進

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

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

else d[i] = j;

(2) KMP算法的改進

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

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

3 算法性能測試

評價一個模式匹配算法優劣程度的一個重要指標是字符的匹配次數。本文對傳統的KMP算法和本文提出的KMP改進算法的匹配次數進行了實驗比較。

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

表1 一般文本串匹配次數比較

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

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

表2 病毒特征值檢測匹配次數比較

4 總結

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

[1]嚴蔚敏,吳偉民.數據結構[M].北京:清華大學出版社.2003.

[2]蔣文沛.對字符串模式匹配KMP算法的探討[J].南寧師范高等專科學校學報.2001.

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

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

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

[6]魯宏偉,魏凱,孔華鋒.一種改進的 KMP高效模式匹配算法[J].華中科技大學學報(自然科學版).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]秦曉明,牛全營,吳淼.入侵檢測系統中模式匹配算法的優化研究[J].計算機與現代化.2009.

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

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

[12]劉云峰.模式匹配及其改進算法在入侵檢測系統中的應用[J].電腦開發與應用.2011.

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

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