周昊 韓彥李斌 殷曉玲

摘要：對KMP算法做出了分析，針對模式串出現(xiàn)在主串較靠后位置這一特殊情況提出對KMP算法的改進算法：并行KMP算法.這一算法在此特殊情況下顯著地減小了算法的時間復雜度.

關鍵詞：模式匹配;KMP算法;并行算法

中圖分類號：TP301 ?文獻標識碼：A ?文章編號：1673-260X（2019）05-0030-03

1 引言

字符串的模式匹配是對字符串的基本操作之一，廣泛應用于生物信息學、信息檢索、拼寫檢查、語言翻譯、數(shù)據(jù)壓縮、網(wǎng)絡入侵檢測等領域，如何簡化其復雜性一直是算法研究中的經(jīng)典問題.字符串的模式匹配實質(zhì)上就是尋找模式串P是否在主串T中，且其出現(xiàn)的位置.現(xiàn)如今我們對字符串匹配的效率的要求越來越高，應不斷地改良模式匹配算法，減少其時間復雜度.

2 相關模式匹配算法分析（n為主串長，m為模式串長）

2.1 BF（Brute Force）算法

BF算法的思想是將主串T中的第一個字符與模式串P中的第一個字符比較，若相等那么繼續(xù)比較T中的第二個字符與模式串P中的第二個字符.若匹配過程中發(fā)生不匹配，那么T的第二個字符（下一個字符）與P中的第一個字符比較.重復此過程，若最終P的全部字符匹配成功那么返回本趟匹配的T中的起始位置，否則匹配失敗.算法如下：

Abstract BF：

int start=0，j=0，i;

i=start;

While（i<n && j<m）

{

If（T[i]==p[j]）

{i++;j++;}

else

{start++;i=start;j=0}

}

If（j==m）return start+1;

else No found;

此種方法也被稱為蠻力算法.例：

第一趟：T： a b a b c a b d a

P： a b c

第二趟：T： a b a b c a b d a

P： a b c

第三趟：T： a b a b c a b d a

P： a b c

在第三趟匹配成功，可以看出主串中i不斷回溯，在這過程中很多比較都是無謂的，所以這種算法效率很低，時間復雜度為O（n+m）.

2.2 KMP算法

KMP算法是由D.E.Knuth、J.H.Morris和V.R.Pratt創(chuàng)造的算法，該算法減少了BF算法中i回溯所進行的無謂操作，極大地提高了算法的效率.算法如下：

Abstract get_next：

int j=-1，i=0，next[0]=-1;

while（i<m）

{

if（j==-1 || P[i]==P[j]）

{

i++;j++;

if（P[i]==P[j]）

next[i]=next[j];

else

next[i]=j

}

else

j=next[j];

}

Abstract KMP：

int next[]，i=-1，j=-1;

get_next（P，next）;

while（i<n && j<m）

{

if（j==-1 || T[i]==P[j]）

{i++;j++;}

else

j=next[j];

if（j==m）return i-j;

}

if（j<m） No found;

例：

第一趟：T： a b c a b d b b d

P： a b d

第二趟：T： a b c a b d b b d

P： a b d

第三趟：T： a b c a b d b b d

P： a b d

可以看出，get_next算法是該匹配算法的核心，通過next數(shù)組可以讓模式串在失配時快速地向右移動，主串中i也不用回溯.遍歷模式串得到next數(shù)組，所以時間復雜度是O（m），模式串在主串中的匹配過程由于模式串每次移動的長度j-next[j]與i的移動距離大致相當，所以匹配的時間復雜度是與主串長成線性關系，為O（n）[1].綜上，該模式匹配算法的復雜度為O（m+n）.

3 并行KMP算法

假設模式串出現(xiàn)在主串的尾部，按照KMP算法需要從第一個開始一直匹配到最后一個開始，需要遍歷整個主串.現(xiàn)提出并行KMP算法同時在主串的末尾開始匹配，既然要從末尾開始匹配，那么就需要新的數(shù)組從m串的末尾開始記錄前后綴的長度，有兩種選擇：1.存儲一個新串，使新串為原模式串的逆序，再調(diào)用get_next函數(shù)得到next2數(shù)組記錄前后綴長度[2].2.定義新的get_nextrev函數(shù)，直接從模式串的尾部開始通過調(diào)用get_nextrev獲得新的nextrev數(shù)組記錄前后綴長度.這兩種方法明顯后者優(yōu)于前者，因為方法1還得額外存儲一個字符串浪費空間[3].get_next函數(shù)偽代碼如下：

Abstract get_next：

{

int j=-1，i=0，next[0]=-1;

while（i<m）

{

if（j==-1 || P[i]==P[j]）

{

i++;j++;

if（P[i]==P[j]）

next[i]=next[j];

else

next[i]=j

}

else

j=next[j];

}

get_nextrev函數(shù)偽代碼如下：

Abstract get_nextrev：

{int k，i=0，j=-1;

k=m-1;

while（k+i>0）

{

if（j==-1 || P[k+i]==P[k-j]）

{

i--;

j++;

if（P[k+i]==P[k-j]）

nextrev[-i]=nextrev[j];

else

nextrev[-i]=j;

}

else

j=nextrev[j];

}

}

}

并行KMP算法偽代碼如下：

{

int sstart1，sstart2，wstart1，wstart2，k，pos1，pos2;

get_next（P，next1）;

get_nextrev（P，next2）;

sstart1=-1;

sstart2=n;

wstart1=-1;

wstart2=m;

if（m==1）

{

for（k=0;k<n;k++）

{

if（w==s[k]）

return k+1;

else：

return -1;

}

}

while（sstart1 < n && wstart1< m && sstart2>=0 && wstart2>=0）

{

if（wstart1==-1 || s[sstart1]==w[wstart1]）

{

wstart1+=1;

sstart1+=1;

}

else

wstart1=next1[wstart1];

if（wstart1==m）

return sstart1-m;

if（wstart2==m || s[sstart2]==w[wstart2]）

{

wstart2-=1

sstart2-=1

}

else

wstart2=m-1-next2[m-1-wstart2];

if（wstart2==-1）

return sstart2+2;

if（sstart1+1==sstart2）

{

pos1=sstart2;

pos2=sstart1;

}

if（sstart2<=pos2）

if（pos2-sstart2<m-1）

if（wstart2>=m-1-（pos2-1）-1）

return -1;

if（pos2-sstart2>=m-1）

return -1;

if（sstart1>=pos1）

if（sstart1-pos1<m-1）

if（wstart1<=sstart1-pos1）

return -1;

if（sstart1-pos1>=m-1）

return -1;

}

}

例：

T： a b a b b a d c c a b a c b c a

P： a b a ? ? ? ? ? ? ? ? ? a b a

首尾同時匹配，最終成功的位置在第1個字符，共比較5次，近似等于KMP需要比較的3次.

T： a b a b b a d c c a b a c b c a

P： d c c ? ? ? ? ? ? ? ? ?d c c

首尾同時匹配，最終成功的位置在第8個字符，共比較18次，大于KMP所需比較的9次

T： a b a b b a d c c a b a c b c a

P： b c a ? ? ? ? ? ? ? ? ?b c a

首尾同時匹配，最終成功的位置在第14個字符，共比較8次;遠小于KMP需要比較的20次.

可以看出匹配成功的位置pos=n-km+1，隨著k的增大，并行KMP算法的時間復雜度在增加，KMP算法的時間復雜度在減小.

若K>n/2m+1/m時：

主串中副串前部分的字符出現(xiàn)的概率越小，并行KMP算法的時間復雜度就越接近KMP算法的時間復雜度.

若K>n/2m+1/m時：

主串中副串后部分的字符出現(xiàn)的概率越小，并行KMP算法相對于KMP算法對時間復雜度的優(yōu)化效果越明顯[4].

由于在最壞情況下依然要遍歷整個主字符串，所以并行KMP的時間復雜度是O（n+2m）.但是當模式串出現(xiàn)在主字符串越靠后的位置時（遠大于m/2），提前匹配成功的可能性越大，字符串匹配效率大大提高[5].

4 結(jié)束語

隨著計算機科學的發(fā)展，對模式串匹配效率的要求不斷提高，我們應不斷研究如何提高模式串匹配效率這一問題.本文介紹的改進算法是針對模式串所在主串位置較靠后這一特殊情況，該算法從串頭和串尾同時開始匹配，相當于是并行運行，在大量處理字符串匹配時優(yōu)化效果明顯.

參考文獻：

〔1〕嚴蔚敏，吳偉民.（C語言版）數(shù)據(jù)結(jié)構(gòu)[M].清華大學出版社，1996.

〔2〕周雅翠，孫磊.基于KMP算法的next函數(shù)理解與分析[J].吉林建筑大學學報，2012，29（1）：79-82.

〔3〕楊俊麗，呂曉燕，滿晰.基于改進的KMP算法的詞頻統(tǒng)計[J].微計算機信息，2010，26（27）：161-162.

〔4〕孟曉笑.KMP算法的并行研究[J].湖北第二師范學院學報，2011，28（2）：20-21.

〔5〕李艷鵾，付維娜，劉帥，等.并行系統(tǒng)中KMP串匹配算法的實現(xiàn)[J].制造業(yè)自動化，2011，33（2）：189-191.