畢智超

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

0 引言

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

模式匹配問題的特點(diǎn)：

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

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

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

1 樸素的模式匹配BF算法

BF算法是一種簡單直觀的模式匹配算法，其基本思想是：從主串T的第一字符開始和模式P的第一個(gè)字符進(jìn)行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；否則，從主串T的第二個(gè)字符開始和模式P的第一個(gè)字符進(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個(gè)字符p0在主串中匹配的位置；如果在其中某個(gè)位置i：ti≠pi，比較不等，這時(shí)可將模式串P右移一位，用P中字符從頭開始與T中字符依次比較。如此反復(fù)執(zhí)行，直到出現(xiàn)以下兩種情況之一，就可以結(jié)束算法：一種情況是執(zhí)行到某一趟，模式串的所有字符都與目標(biāo)串對(duì)應(yīng)字符相等，則匹配成功；另一種情況是P已經(jīng)移到最后可能與T比較的位置，但不是每一個(gè)字符都能與T匹配，這是匹配失敗的情形，函數(shù)將返回0。

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

2 模式匹配的KMP算法

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

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

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

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

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

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

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

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

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

下面通過一個(gè)實(shí)例來說明滑動(dòng)距離的求解。

例 ：T=“thefollowsamaselomesample”,P=“sample”。第 一趟比較：i=0，j=0，0≤k≤6，S(x=t0=t)=1(因?yàn)閜0≠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的第二種情況）。模式移動(dòng)位移為2。

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

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

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

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

匹配過程如下圖所示

圖1 模式匹配過程

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

4 結(jié)束語

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

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

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

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