字符串模式匹配算法的研究及改進(jìn)

畢智超

（陜西職業(yè)技術(shù)學(xué)院,陜西西安,710100)

0 引言

在計算機(jī)信息科學(xué)領(lǐng)域里面，模式匹配是一個重要的研究課題。在拼寫檢查、基于字典的語言翻譯、萬維網(wǎng)搜索引擎、計算機(jī)病毒特征碼匹配、數(shù)據(jù)壓縮、以及DNA序列匹配等應(yīng)用中，都需要進(jìn)行模式匹配。字符串的模式匹配問題描述如下：設(shè)T和P是兩個給定的串，在串T中找等于P的子串的過程稱為模式匹配，其中，T稱為主串，P稱為模式。如果找到，稱為匹配成功，否則稱為匹配失敗。

模式匹配問題的特點：

（1）算法的一次執(zhí)行時間不容忽視：問題規(guī)模通常很大，常常需要在大量信息中進(jìn)行匹配；

（2）算法改進(jìn)所取得的積累效益不容忽視：模式匹配操作經(jīng)常被調(diào)用，執(zhí)行頻率高。

如何改進(jìn)模式匹配算法、提高模式匹配效率, 是本文研究的一個關(guān)鍵問題。

1 樸素的模式匹配BF算法

BF算法是一種簡單直觀的模式匹配算法，其基本思想是：從主串T的第一字符開始和模式P的第一個字符進(jìn)行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；否則，從主串T的第二個字符開始和模式P的第一個字符進(jìn)行比較。重復(fù)上述過程，若P中的字符全部比較完畢，則說明匹配成功，返回主串T在本趟比較中的起始位置；否則匹配失敗，返回0。

例如 ：主串 T=t0t1t2…tm-1…tn-1，模式 P= p0p1p2…pm-1。如果t0=p0，t1=p1，t2=p2，…tm-1=pm-1，則匹配成功，返回模式串第 0個字符p0在主串中匹配的位置；如果在其中某個位置i：ti≠pi，比較不等，這時可將模式串P右移一位，用P中字符從頭開始與T中字符依次比較。如此反復(fù)執(zhí)行，直到出現(xiàn)以下兩種情況之一，就可以結(jié)束算法：一種情況是執(zhí)行到某一趟，模式串的所有字符都與目標(biāo)串對應(yīng)字符相等，則匹配成功；另一種情況是P已經(jīng)移到最后可能與T比較的位置，但不是每一個字符都能與T匹配，這是匹配失敗的情形，函數(shù)將返回0。

這個算法是一種帶回溯的算法。一旦比較不等，就將模式P右移一位，從p0開始在進(jìn)行比較。若設(shè)目標(biāo)T的長度為n，模式P的長度為m，在最壞情況下，最多比較n-m+1趟，每趟比較都在最后才出現(xiàn)不等，要做m次比較，總比較次數(shù)達(dá)到（n-m+1）*m。在多數(shù)場合下m遠(yuǎn)遠(yuǎn)小于n，因此，算法的時間復(fù)雜度為O(n*m)。

2 模式匹配的KMP算法

分析以上算法可知，BF算法是一種帶回溯的匹配算法，也正是回溯使得BF算法效率低下。事實上，這些回溯并不一定是必要的。

例如 ：主串 T=t0t1…tn-1，模式 P= p0p1…pm-1。用前面介紹的BF算法做第s趟比較時，從目標(biāo)T的第s個位置ts與模式P的第0個位置p0開始進(jìn)行比較，直到在目標(biāo)T第s+j位置ts+j“失配”。這時，應(yīng)有 tsts+1ts+2…ts+j-1= p0p1p2…pj-1(1), 按 BF 算法，下一趟應(yīng)從目標(biāo)T的第s+1個位置起用ts+1與模式P中p0對齊，重新開始匹配比較。如果在模式P中，p0p1…pj-2≠p1p2…pj-1（2），則第s+1趟不用進(jìn)行比較，就能斷定它必然“失配”。因為由（1）式和（2）式可知：p0p1…pj-2≠ts+1ts+2…ts+j-1（= p1p2…pj-1）既然如此，第s+1趟可以不做。依次類推，直到對于某一個值k，使得 ：p0p1…pk+1≠ pj-k-2pj-k-1…pj-1且 p0p1…pk= pj-k-1pj-k…pj-1才有 p0p1…pk= ts+j-k-1ts+j-k…ts+j-1(=pj-k-1pj-k…pj-1),這樣，我們可以把在第s趟比較“失配”時的模式P從當(dāng)前位置直接向右“滑動”j-k-1位。這時，因為目標(biāo)T中ts+j之前已經(jīng)與模式P中pj之前的字符匹配了，故而可以直接從T中的ts+j與模式中的pk+1開始，繼續(xù)向下進(jìn)行匹配比較。

在這個算法中，目標(biāo)T在第s趟比較失配時，掃描指針s不必回溯。算法下一趟繼續(xù)從此處開始向下進(jìn)行匹配比較；而在模式P中，掃描指針p應(yīng)退回到pk+1位置。

關(guān)于k的確定方法，可以用一個next特征函數(shù)來確定：當(dāng)模式P中第j個字符與目標(biāo)T中相應(yīng)字符失配時，模式P中應(yīng)該由哪個字符（設(shè)為第k+1個）與目標(biāo)中剛失配的字符重新繼續(xù)進(jìn)行比較。特征函數(shù)next定義如下：

設(shè)模式串長為m，則求next的算法時間復(fù)雜度是O(m)。若主串長為n，KMP算法的時間復(fù)雜度是O(n)；如果包括求next(j)的時間，KMP算法的時間復(fù)雜度是O(n+m)。

3 改進(jìn)的模式匹配算法

串模式匹配算法待解決關(guān)鍵問題是：模式串在主串某個位置比較失敗時，如何使模式串向右移動最佳距離，盡量多的跳過不必要比較的字符，減少匹配的次數(shù)。通過上述匹配算法的分析研究，可以看出KMP算法避免了BF算法頻繁回溯，提高了模式匹配的工作效率，但是我們對于模式匹配算法還可以進(jìn)一步改進(jìn)，最大限度的減少匹配的次數(shù)。改進(jìn)后的算法簡單實用，便于理解。

改進(jìn)算法的精髓是對模式串移動距離的確定。同理設(shè)主串T=t0t1…tn-1，模式 P= p0p1…pm-1。我們做匹配比較時，設(shè)目標(biāo) T 的第i個位置ti與模式P的第0個位置p0開始進(jìn)行比較。在比較過程中失配于 pj處，即 titi+1ti+2…ti+j-1= p0p1p2…pj-1，且 ti+-j≠pj。首先定義一個特征函數(shù)S來確定主串中出現(xiàn)的字符x（x的值為當(dāng)前字符）在模式P中的位置。此算法還要在模式P中補(bǔ)充一個字符pm，該字符的位置緊隨pm-1，取值可任意，其目的一是方便對特征函數(shù)S（x）的定義；二是x能取到ti+m的值。這樣模式P= p0p1…pm-1pm。

特征函數(shù)S（x）定義如下：

其中，x在目標(biāo)T中取值，取失配位置j和其后的字符即x=ti+k，j≤k≤m，且x取值位置的變化可產(chǎn)生前面模式串的子串p0p1…pk-1長度的變化。特征函數(shù)S（x）的作用是求失配時模式串P向右滑動的合理距離，這樣就可以減少匹配次數(shù)。

此算法如果模式P字符數(shù)m較大，此時在逐一的計算求滑動距離，那么算法收益明顯降低。其實可采用目標(biāo)T中的三個位置的字符來計算，分別為ti+j、ti+j+1和ti+m。之所以讓ti+j+1和ti+m參與進(jìn)來決定模式P的滑動距離其目的有二：一是減少函數(shù)S的運(yùn)算次數(shù)；二是如果前面發(fā)生失配，那么模式勢必需要向右滑動。假如S（ti+j+1）和S（ti+m）的取值有一方屬于函數(shù)S的第二種情況，最終移動距離的確定屬于該方，這時ti+j+1和ti+m對于移動距離屬于該方的必然會有模式移動的距離與模式中和它相同的字符對齊。假如這兩位置上的字符有一方不屬于模式串時，最終移動距離的確定屬于該方，這時能夠獲得最大的滑動距離。所以我們之需要考慮它們參與所產(chǎn)生的移動距離即可。此算法最終移動距離的確定是通過計算 S（ti+j）、S（ti+j+1）和 S（ti+m）并取其最大值。

下面通過一個實例來說明滑動距離的求解。

例 ：T=“thefollowsamaselomesample”,P=“sample”。第 一趟比較：i=0，j=0，0≤k≤6，S(x=t0=t)=1(因為p0≠ti，取函數(shù)S的第三種情況)；S(x=t1=h)=2（k=1，h? {p0}，取函數(shù)S的第一種情況）；但 S(x=t6=l)=2（k=6，l∈ {p0p1p2p3p4p5}且q=4，取函數(shù)S的第二種情況）。模式移動位移為2。

第二趟比較：i=2，j=0，0≤ k≤ 6，S(x=t2=e)=1；S(x=t3=f)=2；S(x=t8=w)=7。模式移動位移為7。

第三趟比較：i=9，j=3，3≤ k≤ 6，S(x=t12=a)=2；S(x=t13=s)=4；S(x=t15=l)=2。模式移動位移為4。

第四趟比較：i=13，j=1，1≤ k≤ 6，S(x=t14=e)=2；S(x=t15=l)=3；S(x=t19=s)=6。模式移動位移為6。

第五趟比較：i=19，匹配成功。

匹配過程如下圖所示

圖1 模式匹配過程

筆者通過實驗論證，對于上述實例用改進(jìn)后的算法需要進(jìn)行5趟共12次字符比較；而KMP算法需要18趟共27次字符比較。如果問題規(guī)模很大時，此算法更能體現(xiàn)出它的高效求解。

4 結(jié)束語

字符串模式匹配技術(shù)在當(dāng)今已經(jīng)成為解決計算機(jī)科學(xué)中的關(guān)鍵技術(shù)之一。本文改進(jìn)后的算法能夠很大程度上提高匹配檢測的效率。如何能更好的應(yīng)用此算法，是我們今后研究的工作重點。

[1]李洋,王康,謝萍.模式匹配改進(jìn)算法[J].計算機(jī)應(yīng)用研究,2004,21(4):58-59.

[2]程偉,劉玉軍,盧澤新.最佳比較序字符串匹配算法研究和應(yīng)用[J].計算機(jī)工程與設(shè)計2004,25(9):1430-1432.

[3]殷人昆.數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC++語言描述)[M].北京:清華大學(xué)出版社,2007.