KMP模式匹配算法探討論文

時間:2022-10-11 10:32:00

導(dǎo)語:KMP模式匹配算法探討論文一文來源于網(wǎng)友上傳,不代表本站觀點,若需要原創(chuàng)文章可咨詢客服老師,歡迎參考。

KMP模式匹配算法探討論文

摘要介紹了kmp算法并與樸素查找算法進行了比較,提出了前綴函數(shù)的概念,并利用改進的前綴函數(shù)改進KMP算法,最后結(jié)合KMP的改進算法給出了多次匹配的算法。

關(guān)鍵詞串匹配,前綴函數(shù),KMP算法

在計算機科學(xué)領(lǐng)域,串的模式匹配(以下簡稱為串匹配)算法一直都是研究焦點之一。在拼寫檢查、語言翻譯、數(shù)據(jù)壓縮、搜索引擎、網(wǎng)絡(luò)入侵檢測、計算機病毒特征碼匹配以及DNA序列匹配等應(yīng)用中,都需要進行串匹配。串匹配就是在主串中查找模式串的一個或所有出現(xiàn)。在本文中主串表示為S=s1s2s3…sn,模式串表示為T=t1t2…tm。串匹配從方式上可分為精確匹配、模糊匹配、并行匹配等,著名的匹配算法有BF算法、KMP算法、BM算法及一些改進算法。本文主要在精確匹配方面對KMP算法進行了討論并對它做一些改進以及利用改進的KMP來實現(xiàn)多次模式匹配。

1KMP算法

最簡單的樸素串匹配算法(BF算法)是從主串的第一個字符和模式串的第一個字符進行比較,若相等則繼續(xù)逐個比較后續(xù)字符,否則從主串的第二個字符起再重新和模式串的第一個字符進行比較。依次類推,直至模式串和主串中的一個子串相等,此時稱為匹配成功,否則稱為匹配失敗。樸素模式匹配算法匹配失敗重新比較時只能向前移一個字符,若主串中存在和模式串只有部分匹配的多個子串,匹配指針將多次回溯,而回溯次數(shù)越多算法的效率越低,它的時間復(fù)雜度一般情況下為O((n-m+1)m)(注:n和m分別為主串和模式串的長度),最壞的情況下為O(m*n),最好的情況下為O(m+n)。KMP模式匹配算法正是針對上述算法的不足做了實質(zhì)性的改進。其基本思想是:當(dāng)一趟匹配過程中出現(xiàn)失配時,不需回溯主串,而是充分利用已經(jīng)得到的部分匹配所隱含的若干個字符,過濾掉那些多余的比較,將模式串向右“滑動”盡可能遠的一段距離后,繼續(xù)進行比較,從而提高模式匹配的效率,該算法的時間復(fù)雜度為O(m+n)。

那么如何確定哪些是多余的比較?在KMP算法中通過引入前綴函數(shù)f(x)來確定每次匹配不需要比較的字符,保證了匹配始終向前進行,無須回溯。假設(shè)主串為s1s2,sn.,模式串為t1t2,tm.,其中m≦n,從si+1開始的子串遇到一個不完全的匹配,使得:

(1.1)

如果我們能確定一個最小的整數(shù),使得:

(1.2)

其中,所以確定i''''等價于確定k,這里的k值就是我們要求的前綴函數(shù)f(x)。由式1.1和1.2中K值與主串s無關(guān),只與給定的模式串t中與主串匹配的q有關(guān),即k=f(q),

f(q)=max{i|0iq且t[1..i]是t[1..q]的后綴}(1.3)

確定KMP前綴函數(shù)的算法如下:

#defineMAXSIZE100

Typedefunsignedcharstring[MAXSIZE+1];//0號單元用來存放串的長度

voidf(sstringt,int*array)

{

m=t[0];//m為當(dāng)前模式串的長度

array=(int*)malloc((m+1)*sizeof(int));//0號元不用

array[1]=0;k=0;

for(q=2;q<=m;q++)

{while(k>0&&t[k+1]!=t[q])k=array[k];

if(t[k+1]==t[q])k=k+1;

array[q]=k;

}

}

關(guān)于KMP算法的前綴函數(shù)f(x)的示例見表1。

當(dāng)模式串中有i個字符串匹配成功,第i+1個字符不匹配時,則從i-f(i)個字符重新開始比較,這樣不僅無須回溯,而且一次可以向前滑動i-f(i)個字符,大大提高了模式匹配的效率。下面給出樸素匹配算法和KMP匹配算法的比較,見表2。

表2樸素匹配算法和KMP匹配算法比較表

樸素算法KMP算法

時間復(fù)雜度O((n-m+1)m)O(m+n)

向前移動字符個數(shù)1q-f(q)

回溯次數(shù)q-1無

其中:n為主串長度,m為模式串長度,q為匹配成功的字符個數(shù)

2KMP算法的改進

在KMP算法的實際應(yīng)用中,發(fā)現(xiàn)該算法也存在著不足,結(jié)合下面的表一來論述KMP模式匹配算法的改進。假設(shè)模式串前4個字符與主串的第i+1..i+4匹配成功,第5個字符匹配失敗,此時前綴函數(shù)f(4)=1,下一次匹配將從第i+4開始,并直接將模式串中的第2個字符與主串中的第i+5個字符進行比較,從表1中可知,匹配必將失敗,此次比較是多余的。這說明此時的前綴函數(shù)f(x)并不是最優(yōu),需要對前綴函數(shù)進行改進。實質(zhì)上,所謂對KMP算法的改進就是對其前綴函數(shù)的改進。

4結(jié)語

本文給出的算法較樸素匹配算法在效率上有了較大的提高,尤其是對重復(fù)字符出現(xiàn)較少的數(shù)據(jù)段進行模式匹配可取得較高的查找效率。應(yīng)用于大型數(shù)據(jù)庫的數(shù)據(jù)查詢,會更加有效地縮短查找時間。

參考文獻

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

[2]傅清祥,王曉東.算法與數(shù)據(jù)結(jié)構(gòu)[M].電子工業(yè)出版社,1998

[3]D.Wood,DataStructures,AlgorithmsAndPerfomance,Reading,MA:AddisonWesley,1993

[4]onnetGH.HandbookofAlgorithmsAndDataStructure[M].Addison-WesleyPublishingCompany,1999