一種基于KMP算法思想的字符串匹配算法的研究與實現(xiàn)

◆邵 嵐 唐永群 孔令順

?

一種基于KMP算法思想的字符串匹配算法的研究與實現(xiàn)

◆邵 嵐 唐永群 孔令順

（（CLO 北京 100054）

KMP算法是一種高效的字符匹配算法，它的思想在于其在匹配失敗以后，不需要再對內(nèi)容字符序列從頭匹配，這樣就減少了匹配的次數(shù)，提高效率。本方通過舉例比較說明這個算法的優(yōu)點。

KMP；模式匹配；KMP算法

0 引言

我們身處一個信息爆炸時代，每天產(chǎn)生的信息幾乎都是海量。無論是金融、文學(xué)、生物還是計算機領(lǐng)域，文本都是必不可少的信息載體。而大到大型網(wǎng)站論壇，小到公司內(nèi)部項目都不可避免的要涉及信息的查找、過濾等相關(guān)功能，比如在一個文件中查找出所有給的字符串，然后過濾，不好的設(shè)計思想導(dǎo)致遲遲得不到結(jié)果，無法滿足實時性高的要求，這個過程中如何高效的處理就顯得尤為重要，各種字符串查找匹配算應(yīng)運而生。

基于目前公司項目開發(fā)中正好要用到字符串查找功能，借此機會對字符串匹配算法做一次分析與比較，希望能對項目的運行效率有所裨益。

本文先簡單了解BF算法，隨后介紹KMP算法及其思想、move數(shù)組的求解，最后介紹KMP算法在項目中的實現(xiàn)和簡單應(yīng)用。

1 BF算法

BF算法的基本思想比較簡單，就說從內(nèi)容串C的第一個字符開始和關(guān)鍵字串K的第一個字符開始逐個進(jìn)行比較，如果相等則進(jìn)一步比較二者的第二個字符，依次往后移動兩者的指向，如果在某個字符比較時失配了，則分別將關(guān)鍵字串K的第一個字符與內(nèi)容串的第二個字符作為最初指向再重新進(jìn)行比較，匹配時指向各自向后移動一個位置，以此類推。

下面通過一個簡單的例子，我們可以來了解一下BF算法的原理。假設(shè)有一個內(nèi)容串C和關(guān)鍵字串K，C=”xyxyy”，K=“xyy”,也就是在C中去匹配K。由于例子比較簡單，我們可以繪制出整個的匹配過程。如圖1所示。

BF算法的基本思想從圖中的七個過程就能得到完整的體現(xiàn)，簡單的描述一下上面的流程是這樣的：首先以關(guān)鍵字串K的第一個字符和內(nèi)容串C的第一個字符作為各自的起始位置進(jìn)行比較，經(jīng)過前兩次的匹配都成功后，這時的比較位置都移動到第3個字符，也就是將關(guān)鍵字串的第三個字符’y’與內(nèi)容串的第三個字符’x’比較，由于不能匹配，就要進(jìn)行下一輪的重新匹配，也就是要重新確定比較的初始位置。對于模式來說，重新定位就是第一個字符作為初始比較位置，而對于內(nèi)容串來說就是移動一個位置而不是上一次匹配成功的最后位置。BF算法的實現(xiàn)比較簡單，思維方式也很直接，但是存在不足之處：就上面的例子來說，內(nèi)容串的定位”走了回頭路”；而且比較操作也重復(fù)執(zhí)行了：第一次失配后，在接下來的第二次匹配時，我們會首先用關(guān)鍵字串的第一個字符與內(nèi)容串的第二個字符比較，但是這個過程是可以省略的，因為我們通過觀察關(guān)鍵字串可以發(fā)現(xiàn)關(guān)鍵字串的前兩個字符是不相等的，而上一輪比較過程中，關(guān)鍵字串的第二個字符與內(nèi)容串的第二個字符是想等的，因此可以判斷關(guān)鍵字串的第一個字符與內(nèi)容串的第二個字符是不相等的。如果能在比較過程中避免這些重復(fù)比較，匹配效率也將得到很大的提高，KMP算法則正好避免了上面BF算法的不足。

圖1 匹配過程

2 KMP模式匹配算法

2.1 算法前瞻

KMP算法之所以高效，在于其在匹配失敗以后，不需要再對目標(biāo)字符序列從頭匹配，這樣就減少了匹配的次數(shù)，提高效率。算法實現(xiàn)的核心就是基于一個move數(shù)組，move數(shù)組存儲了關(guān)鍵字串的特征信息。

下面圖2我們舉一個例子，從中體會一下KMP算法的思想并且與BF算法做一下比較，就能找出KMP算法的高效所在，假設(shè)有一個內(nèi)容串C和關(guān)鍵字串K ，C=” ababcabcacb”，K =”abcac”，當(dāng)比較到到第二個字符時出現(xiàn)失配，即C[2]！=K[2]。

圖2 例子

這時如果按照傳統(tǒng)的BF算法，則第二輪的比較應(yīng)該從內(nèi)容串的第一個字符與關(guān)鍵字串的第零個字符開始，這種思想前面我們已經(jīng)知悉。KMP算法則會首先發(fā)現(xiàn)K串本身的一些特性，即最開始的兩個字符是不相等，同時根據(jù)第一輪的比較發(fā)現(xiàn)：C[0] = K[0]，C[1] = K[1]。因此可以立即得出結(jié)論C[1] != K[0]，所以可以省略它們的比較，直接從C第二個字符與K第零個字符進(jìn)行比較開始，如圖3：

圖3 第二輪比較

從圖中可以看到，當(dāng)比較到C[6]和K[4]時，再次出現(xiàn)失配情況。根據(jù)KMP思想只要從C[6]和K[1]開始進(jìn)行比較即可。如圖4：

圖4 從C[6]和K[1]開始進(jìn)行比較

可以看到整個過程中只發(fā)生了3次重新匹配，就得到了匹配成功的結(jié)論，加快了匹配的執(zhí)行速度。上面的例子只是大概描述了方法的思路，但是這種方法的本質(zhì)到底是什么，又如何才能精確的描述，最后到代碼的實現(xiàn)，我們下面就來解決這些問題。

2.2 KMP模式匹配算法思想

通過上面的例子分析，我們可以看到整個匹配過程中，失敗時只對關(guān)鍵字串K的初始比較位置回溯，而內(nèi)容串的比較位置一直是向后，沒有重復(fù)。

我們得到的結(jié)論是：KMP算法思想關(guān)鍵在于匹配失敗時，我們能夠知道從關(guān)鍵字串的哪一個位置與內(nèi)容串在失配時的位置重新開始比較，定位關(guān)鍵字串的重新比較位置就是整個算法思想的關(guān)鍵，而這些都與內(nèi)容串沒有干系。

KMP算法的關(guān)鍵是它的move數(shù)組，利用move數(shù)組能夠高效地確定在當(dāng)前失配的情況下，應(yīng)當(dāng)將關(guān)鍵字串移動多少位才能夠避免不必要的匹配。KMP如何借助move數(shù)組移位，道理其實很簡單，如果內(nèi)容串和關(guān)鍵字串的字符匹配，那么就同時移動兩者的下標(biāo)；如果不能匹配，關(guān)鍵字串就使用move數(shù)組來獲得移動的數(shù)目。

2.3 求解move數(shù)組

move數(shù)組的含義：如果關(guān)鍵字串K與內(nèi)容串C匹配到了n個字符，這n個字符也就是關(guān)鍵字串K的前n個字符，我們對這個子串記為tmp做如下分析：

這個串tmp的前后是否有重復(fù)的內(nèi)容，哪怕是重復(fù)一個字符，當(dāng)然越多越好，我們也只記錄最多的重復(fù)情況，這個最多的長度就是下次重新匹配時不需要再次匹配測試的長度，同時也要記錄這兩個重復(fù)的部分之間的間隔距離，這個距離就是失配時關(guān)鍵字串K的回溯長度。為提高效率，匹配長度n就是move數(shù)組的下標(biāo)。我舉一個例子同時附一個表格來體會一下思想：

解析一下：

比如對于匹配到了2個字符，也就是K與C的前兩個字符都是ab，也即是K[0]=C[0], K[1]=C[1],但是K[2]!=C[2]失配，繼續(xù)比較時，將K的指針回溯到K的頭部再偏移move[2]=0個長度，這也應(yīng)該是K的最前部，而C不用回溯。

假設(shè)關(guān)鍵字串K = “abxabyz”,計算結(jié)果如表1：

表1 計算結(jié)果

比如對于匹配到了5個字符，也就是K與C的前兩個字符都是abxab，也即是K[0]=C[0], K[1]=C[1]…K[4]=C[4]但是K[5]!=C[5]失配，繼續(xù)比較時，將K的指針回溯到K的頭部再偏移move[5]=2個長度，而C不用回溯，也就是用K中的K[2]=’x’字符與C[5]比較而不是K[0]與C[1]做比較。

2.4 求解move數(shù)組的算法實現(xiàn)

代碼其實并不復(fù)雜，整體思路是對于每一個關(guān)鍵字串與內(nèi)容串匹配到的長度j，得到匹配的內(nèi)容tmp，然后將 tmp分拆為前后兩個部分，稱為前綴和后綴，在前綴長度不大于后綴長度下，判斷前綴是否在后綴中重復(fù)出現(xiàn)。匹配長度作為move數(shù)組的下標(biāo)，前綴在后綴中能夠找到重復(fù)時的最大長度值存放在move[j]中。move數(shù)組的初始值都是0，意思是關(guān)鍵字串默認(rèn)都回到頭部并且沒有偏移。

圖5 求解move數(shù)組的算法實現(xiàn)

3 算法在項目中的實現(xiàn)與應(yīng)用

3.1 KMP模式匹配算法實現(xiàn)

函數(shù)的功能是基于KMP思想，在內(nèi)容串中找出所有的關(guān)鍵字串的位置。簡單的解釋一下：matchlen是匹配長度的計數(shù)器，每次字符比較成功就+1（37行），當(dāng)完全匹配時（38行），matchlen置0（43行），重新開始計數(shù)。當(dāng)出現(xiàn)失配情況時（50行），如果已經(jīng)匹配的長度是0，也就是第一個字符就不匹配，就要后移內(nèi)容串指針（52行）。move[matchlen] （53行）中的matchlen表示已經(jīng)成功匹配了多少個字符，move[matchlen]則表示在成功匹配了matchlen個字符的情況下，前綴中有多少個字符在后綴中重復(fù)出現(xiàn)，所以下一次重新比較時，關(guān)鍵字串要定位到頭部再偏移move[matchlen]個長度（54行）。跳過的長度move[matchlen]雖然是不用重復(fù)比較的長度，但是還是要算匹配長度的，所以有53行的賦值。

圖6 KMP模式匹配算法實現(xiàn)

3.2 KMP算法應(yīng)用

代碼很簡單（圖7），看一下執(zhí)行結(jié)果（圖8）：

圖7 代碼

圖8 執(zhí)行結(jié)果

4 結(jié)束語

本文從BF算法講起，隨后闡述KMP的算法思想以及優(yōu)勢、move 數(shù)組的簡單求解以及KMP算法在項目中的實現(xiàn)。通過分析BF算法和KMP算法并通過實驗證明在字符集較大的情況下，KMP算法在運行比較次數(shù)和運行時間上都優(yōu)于BF算法。綜上所述，KMP算法提高了匹配效率，具有廣闊的應(yīng)用前景。

通過上述對算法的分析，以及對不同算法的實現(xiàn)的運行效率比較，為我們更清楚的分析算法的優(yōu)劣，去選擇對自己更實用的算法，提供了可遵循的方式方法，并廣泛應(yīng)用到自己的學(xué)習(xí)工作中。

[1] KMP算法詳細(xì)講解: https://blog.csdn.net/suguoliang/article/details/77460455

[2] KMP算法Move數(shù)組計算: https://blog.csdn.net/xiao xian8023/ article/details/8134292