KMP算法的優(yōu)化與應用

馬銳彥

關(guān)鍵詞：KMP算法；next數(shù)組；nextval數(shù)組；優(yōu)化；算法應用

中圖分類號：TP311 文獻標識碼：A

文章編號：1009-3044（2023）20-0073-03

1 研究背景

文字，一直都是文明的象征。文字讓人類可以更高效地記錄信息，將前人的生活智慧與發(fā)生的事件一代代地積累下來，形成不同的歷史文化。將文字錄入文檔進行保存，就是主要用于記載和儲存文字信息的文本。

文本，一直都是計算機領域中最基本的元素，即使是在多媒體技術(shù)絢爛奪目的信息時代，文本一直都作為奠基性質(zhì)的元老角色而存在著[1]。

在對文本的分析中，經(jīng)常會遇到模式匹配的問題。模式匹配，可以簡單地總結(jié)為查找與目標字符串相同的模式字符串的子串，即查找與指定字符串相同的字符串。例如，在一個文本文件中查找“KMP算法”這一詞語。當文本具備一定的規(guī)模后，需要在大量信息中進行多次搜索，所以，算法每次的執(zhí)行時間和算法優(yōu)化所獲得的效益因積攢往往比表面上看起來要大得多。

互聯(lián)網(wǎng)迅速發(fā)展的信息爆炸時代，全球的信息量以幾何級別增長。人們每時每刻都面對大量的文字信息，如新聞信息、娛樂信息、廣告信息、科學技術(shù)信息等，想要獲取有用信息時，令人無從下手。當信息使用不同的語言，存在大量無法直接理解的信息時，會產(chǎn)生巨大的信息壓力。當信息真假難辨時，如何從大量的信息中，準確地篩選出所需信息，一直是令人頭痛的問題。

目前，人們已經(jīng)有一種優(yōu)秀的字符串匹配算法進行模式匹配，提高了文本編輯響應性能。KMP算法，作為著名且較高效的字符串匹配算法，在文本編輯、未知語言翻譯、生物序列模式自動識別等方面都有很好的應用，且仍在不斷地發(fā)展進化，向著更高的效率進發(fā)。

本文將從KMP算法本身出發(fā)，闡述其基本原理，對KMP算法所涉及的前綴數(shù)組的計算方法進行優(yōu)化，嘗試提高算法匹配效率，并對KMP算法在翻譯文本方面的應用進行簡單介紹。

2 KMP算法

2.1 KMP算法簡介

KMP算法是一種改進的字符串匹配算法，1997年由D.E.Knuth，J.H.Morris和V.R.Pratt三人提出，實際上是三人同時發(fā)表了基本思想相同的快速串匹配算法（簡稱KMP算法），KMP就是由他們?nèi)诵帐祥_頭字母組成的。

KMP算法中前綴數(shù)組有next數(shù)組和nextval數(shù)組之分。兩者的意義和作用基本相同，通常情況下可以混用。唯一不同的是，next數(shù)組在一些情況下有些缺陷，而nextval的創(chuàng)建是為了彌補這個缺陷。

KMP算法的時間復雜度為O（m+n）。其優(yōu)點在于：每當一趟匹配過程中出現(xiàn)字符不等時，不須回溯目標串，而是由已經(jīng)得到的“部分匹配”的結(jié)果將模式串向右“滑動”盡可能遠的一段距離后，繼續(xù)進行比較[2]。若將KMP算法與BM算法相結(jié)合，分情況選取合適的部分，理論上可以產(chǎn)生一種KMP改進算法，一定程度上能提高KMP算法的匹配效率。

KMP算法在很多領域都有應用，如文獻檢索、詞頻統(tǒng)計、敏感信息屏蔽等，本文將基于KMP算法，闡述KMP 算法在文本翻譯中的應用，得到文本的最匹配翻譯。

2.2 KMP算法代碼

主要程序如下：

int KMP（char s1[]，char s2[]，int next[]）

{int i=0; int j=0;

int len1=strlen（s1）;

int len2=strlen（s2）;

while（i

{if（j==-1||s1[i]==s2[j]）

{i++;j++;

}else

j=next[j];

}if（j>=len2）

return i-len2+1;

else

return -1;

}

3 KMP前綴數(shù)組

3.1 前綴數(shù)組

在KMP算法中，前綴數(shù)組有next和nextval數(shù)組兩種。前綴數(shù)組的數(shù)值應為簡單的整數(shù)，取值范圍應為樣本長度，作為KMP算法中的關(guān)鍵，其特點是模式串每一位對應的數(shù)組值僅依賴模式串本身，而與主串無關(guān)。

next數(shù)組求解過程為：依據(jù)其定義可知，第一位和第二位分別為0 和1。當判斷所求位置的next 值時，需要將前一個位置的字母X和其next值相等的字母Y進行比較。若X與Y相同，則將X的next值加一即為所求。若X與Y不同，則依次向前比較，直到相同為止。其中，若一直到首位都沒有相等的內(nèi)容，則將所求位上的next值置為1。

nextval數(shù)組的求解是基于next數(shù)組。第一位為0。其余位置求解時需要將本位字符與next數(shù)組所對應的字符相比較。如果相等則為nextval數(shù)組所對應的next的值，如果不相等則為next數(shù)組所對應的值。

3.2 next 和nextval對比

在給定模式串無太多重復字符時，二者無太大差別。當給出的模式串有大部分重復時，next數(shù)組會重復多次無實際效果的代碼，使用nextval數(shù)組可一定程度上減少冗余的步驟。

為體現(xiàn)nextval的優(yōu)勢，可選取較為特殊的字符串進行舉例。例如模式串T=‘a(chǎn) a a a d與主串S=‘a(chǎn) a ab a c a a a a d e在匹配時，當i=4，j=4時，S[4]≠T[4]，由next[4]=3可知下一步需進行i=4，j=3的比較，又由于S[4]≠T[3]，需要依次向前比較，直到j=1。進行了多次數(shù)據(jù)與步驟完全相同的比較，過程拖沓冗長。而且實際上，很容易看出模式串的前四個字符完全相等，因此主串中的第4個字符無須再和模式串中的前三個字符進行比較，可以將模式串一次性向后滑動4個字符的位置，直接進行i=5，j=1時的字符比較[3]，即直接從字符不同的地方開始，減少冗余的步驟。

4 KMP改進算法

4.1 BM算法

BM（Boyer-Moore） 算法，由Boyer和 Moore在1977 年提出的經(jīng)典算法，是一種局部立體匹配算法，它采用壞字符和好后綴兩項規(guī)則。

BM算法在進行匹配時，采用從右向左比較的方法，同時，引入兩種啟發(fā)式跳轉(zhuǎn)規(guī)則，即壞字符算法和好后綴算法，來決定模板向右移動的步長。

壞字符跳轉(zhuǎn)規(guī)則定義如下圖1所示，針對的是文本串，其中ch為文本T與模式P比較時出現(xiàn)的不匹配文本字符：

當模式串中沒有對應的壞字符，則直接后移到壞字符后面。若模式串中包含壞字符，則移到最后一個壞字符處。

好后綴跳躍規(guī)則與其類似但針對的是模式串，當匹配失敗時，后移到好后綴位置，向前比較。

在匹配的時候要同時根據(jù)壞字符跳躍表和好后綴跳躍表，模式串的右移量為兩者的最大值[4]。

4.2 KMP改進算法

KMP改進算法的優(yōu)化思路可簡單理解為：在匹配階段出現(xiàn)不匹配的字符時，結(jié)合BM算法和KMP算法的優(yōu)點，利用已知部分，令模式串最大程度地后移。

匹配階段在遇到T、P不匹配時進行兩個部分操作。第一部分是計算模式串移動nextval[j]后末字符在文本中的位置；第二部分是比較目標串和模式串在該位置的字符是否匹配，如果兩字符不匹配，則文本該位置的字符應進行壞字符跳轉(zhuǎn)，否則按KMP的匹配過程繼續(xù)比較[5]。

KMP改進算法的流程如下圖3所示：

4.3 程序代碼

匹配階段的核心代碼如下：

while（i

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

{if（j==m-1）

{i++；j=0；//找到一個匹配

}else{i++；j++；}

}else{

//計算模式串移動 nextval[j]后末字符在文本中的位置

tLast=T[i+pLen－nextval[j]－1]；

//判斷該位置的文本字符與末字符是否匹配

if（tLast！=pLast）

{j=0；//進行壞字符跳轉(zhuǎn)

i=i+bmBc[tLast]－nextval[j]；

}else

j=nextval[j]；

}}

改進后的KMP算法在理論上可以彌補KMP算法從左開始對比的局限性，當左邊的判斷移動效率不高時，改為從右開始對比的BM算法壞字符跳轉(zhuǎn)，結(jié)合兩者的優(yōu)點，減少比較次數(shù)。

5 KMP 算法在翻譯文本的應用

5.1 翻譯基礎

1） 分詞

在進行翻譯之前需要先討論“分詞”的概念。詞是語言表達的最小單位，相比于有明確分界符的西方拼音語言，一些亞洲語言的詞之間沒有明確的分界符，所以做進一步自然語言處理的基礎是對句子進行分詞。

在最少詞數(shù)分詞原理的基礎上，可以運用統(tǒng)計語言模型得到最佳分詞效果。即應確保分完詞后這個句子出現(xiàn)的概率是最大的。

關(guān)于分詞的討論與分析，參照已有知識，需要說明三點。首先，每種方法都有其局限性，雖然利用統(tǒng)計語言模型的數(shù)據(jù)可以得到最佳效果，但也不是完全準確。尤其在特定情況下，無法消除文本原有的二義性。第二，分詞問題屬于已解決問題，只要采用基本的統(tǒng)計語言模型，再加上一些已有技巧就能得到很好的分詞效果，不值得再花很大精力去研究。第三，分詞技術(shù)不只針對于亞洲語言，在識別西方拼音語言的手寫體時，原本的分界符不夠明顯，因此原本用來對中文進行分詞的技術(shù)，也在英語手寫體識別中派上了用場。

2） 翻譯與KMP算法

當面臨不同語言的文本，尤其是未知語言的文本時，在每段文本中重復出現(xiàn)的序列片段通常情況下具備某種固定的含義，可以將其作為分析的依據(jù)。找出文本中在誤差允許范圍內(nèi)相同的字母序列片段，為該語言的翻譯研究提供重要的理論依據(jù)。

當分詞結(jié)束后，收集分詞結(jié)果形成詞匯庫，依據(jù)詞匯庫運用KMP相似字符串搜索匹配算法進行對比分析?？梢赃M行高頻詞的統(tǒng)計，常用短語、詞組等語言分析。

5.2 KMP 算法翻譯文本的思路

在進行文本翻譯，尤其是未知語言文本的翻譯時，需要先對機器進行訓練得到雙語語料庫。對于高頻詞或最佳翻譯的分析，可以運用KMP算法。

首先，運用已知的分詞技巧得到語料庫；其次，運用KMP算法統(tǒng)計文本中出現(xiàn)字符串的次數(shù)，并將次數(shù)較多的設為高頻詞；第三，依據(jù)出現(xiàn)次數(shù)，進行分析，得到該語言初步的常用詞或短語；第四，根據(jù)語法語義等進行逐詞翻譯，并通過語言統(tǒng)計模型進行統(tǒng)計，得到最可能的翻譯。

5.3 缺點分析

1） 工作量較大，需要大量的文本作為分詞基礎，當文本不充足時，若直接采用分詞會導致分詞不準確。需要加入人工進行校對，需要很大的工作量才能得到有效的分詞。雖然通過數(shù)據(jù)驅(qū)動的機器學習進行語料庫的創(chuàng)建，可減少人工的投入，但一旦涉及遠距離調(diào)序，譯文的生成難度就非常大，往往效果不夠好。整個譯文感覺往往語句不通順，同時還會引入漏譯問題。

2） KMP算法匹配時有限制，當采用KMP算法對生成的文本數(shù)據(jù)進行匹配，發(fā)現(xiàn)符合條件的字母序列數(shù)量非常少時，可以對KMP算法進行改進。例如添加容錯范圍參數(shù)，即找出與隨機字符串相似的字符串，進行統(tǒng)計，可有效地提高效率。

在KMP算法的基礎上加入變異的概念，以KMP為基礎的相似字符串搜索匹配模型，以提高匹配的準確度。當匹配失敗但在設定容錯范圍內(nèi)時，忽略錯誤，繼續(xù)進行比較。這樣，算法的準確度會大大提高[6]。

6 結(jié)束語

在當今的信息社會中，每天都有大量的信息產(chǎn)生，如何高效地得到有用信息是亟待解決的問題。利用字符串匹配算法可以有效地得到所需信息，利用算法對不同語言的文本信息進行分析，有助于對該語言的理解與翻譯。本文通過對著名的字符串匹配算法——KMP算法的分析，挖掘KMP算法本身的優(yōu)化方式，并簡單闡述算法在翻譯文本時的應用思路。

KMP算法的前綴數(shù)組有兩種選擇，在有較多重復字符時選取nextval數(shù)組的方式，可以有效地提高算法效率。將KMP算法的前綴數(shù)組回溯方式與BM算法的壞字符跳轉(zhuǎn)方式相結(jié)合，雖然在時間復雜度上與KMP 算法相同，但是在字符集較大的情況下，KMP改進算法的比較次數(shù)和運行時間均低于KMP算法和BM算法。當遇到未知文本時，運用KMP算法的匹配，在語料庫的基礎上，可以有效地進行分詞，并得到高頻詞和常用語，有利于文本翻譯并了解一門新的語言。