李艷鵾，付維娜，劉 帥，祝 明

LI Yan-kun1，F(xiàn)U Wei-na2，LIU Shuai3，ZHU Ming1

（1.長春工業(yè)大學 工商管理學院，長春 130012；2.長春工程學院 軟件學院，長春 130012；3.吉林大學 計算機科學與技術(shù)學院，長春 130021）

0 引言

字符串匹配算法作為字符串所有算法的基礎(chǔ)，其重要性毋庸置疑，KMP算法以其為n的線性函數(shù)的時間復(fù)雜性而成為字符串匹配中的常用算法[1,2]，并一直使用至今。近年來也有很多關(guān)于KMP算法的研究[5,6]，取得了很好的結(jié)果，同時也有很多KMP在模式識別、模式匹配方面的成果[8,9]。

但是，KMP算法的時間復(fù)雜性一直無法得到有效的改善。為了改善KMP算法的復(fù)雜性，本文將KMP算法推廣至并行機進行并行處理，以降低其時間復(fù)雜性。

并行處理采用多處理機對多進程進行并行處理，對很多傳統(tǒng)算法的并行化已成為一個計算機領(lǐng)域的研究方向[3]。因此，如果能將KMP算法并行化，則可以大大降低其時間復(fù)雜性。

因此，本文在文獻[4，7]的基礎(chǔ)上，將KMP算法并行化，并通過加入冗余串來解決KMP算法的丟解情況，并得出實驗數(shù)據(jù)。通過實驗可知，本算法可以在不降低代價的前提下，對KMP算法進行優(yōu)化，并且其效率和擴展性均良好。

本文的貢獻在于：1）對KMP的并行化有效的降低了匹配時間；2）并行化算法的效率和擴展性良好，已達到并行的最優(yōu)界限。

1 并行算法參數(shù)設(shè)置

1）運行時間t（n）=tr+tc，其中tr為數(shù)據(jù)經(jīng)由網(wǎng)絡(luò)或存儲器的選路時間，tc為數(shù)據(jù)在處理器內(nèi)部進行算術(shù)、邏輯運算所需的計算時間。

2）處理器數(shù)目p（n），求解問題所需的處理器數(shù)目，通常p隨問題規(guī)模n變化函數(shù)為p（n）=n1-e（0＜e＜1）。

3）并行算法代價c（n）=t（n）·p（n），若解決某一問題的并行算法的執(zhí)行代價與最壞情況下串行算法的運行時間（步數(shù)）同階，則稱其為代價最佳。

4）加速比Sp（n）=ts（n）/tp（n），其中ts（n）為求解問題最快速的串行算法最壞情況下的運行時間，tp（n）為求解同一問題的并行算法在最壞情況下的運行時間。顯然，Sp（n）越大，并行算法越好，1≤Sp（n）≤p（n）。

5）并行算法效率Ep（n）= Sp（n）/p（n），用于度量并行算法中處理器的利用效率。

6）并行算法伸縮性：給定處理器數(shù)目p，若Ep（n）隨問題規(guī)模n增加而單調(diào)遞增，則稱此算法為可伸縮的。

2 KMP算法在并行系統(tǒng)中的實現(xiàn)

2.1 KMP算法簡介

Knuth-Morris-Pratt串匹配算法主旨思想：自左向右進行字符匹配，通過構(gòu)建模式串的next函數(shù)記錄模式串自身屬性信息，從而充分利用上次匹配得到的有效信息將正文與模式在不漏解的情況下盡可能的向右滑動足夠大的距離。

設(shè)長度為n正文串以t[n]形式存放，模式串以p[m]存放，考慮構(gòu)建KMP算法中的next函數(shù)應(yīng)具有辨別匹配位置的特性，我們將next函數(shù)定義如下：

再由于KMP算法中的next函數(shù)有可能出現(xiàn)t[j]=t[k]，影響匹配效果，所以對于所有的t[j]=t[k]，我們約定j的next函數(shù)值為對k繼續(xù)取next值，直至t[j]≠t[k]或者k=0，此時能夠保證正文塊相對滑動最大距離。

2.2 在SM并行系統(tǒng)中對KMP算法的改進

設(shè)長度為n正文串以t1-tn形式存放，處理器數(shù)目p（n）=k，則改進的算法如下所示：

1）初始化正文串分解：

將正文等分為k段，則每段長度s=n/k，在每段后面加上長度為m-1的擴展串，將此長度為s+m-1的k段正文按處理器序號依次放入處理器中，處理器i分配的正文子串為texti=t（i-1）·s+1～ti·s+m-1，這里默認正文與匹配串編號均從1開始。

2）對模式串p執(zhí)行算法1求得next函數(shù)值。

3）并行匹配：

For all Pj where 0＜j≤k do in parallel

對模式串p與正文子串textj執(zhí)行算法2，輸出結(jié)果，算法結(jié)束。

其中算法1與算法2如圖1，2所示，算法1為next函數(shù)匹配過程，算法2為每個處理器的基本KMP算法。考慮到對子串進行分割可能造成的丟解情況，因此在本算法中對邊界做出擴展，即需要在匹配串后端加入長度為m-1的擴展串，相當于在任意兩段子串texti與texti+1之間有m-1個冗余字符。此時在各子串中以KMP方法進行匹配時能保證其不丟解，現(xiàn)證明如命題1所示。

圖1 textr函數(shù)算法

命題1.改進的KMP并行算法不丟解。

證明：

i＞顯然原始的KMP算法不丟解。

ii＞假設(shè)改進的KMP并行算法存在丟解情況，因為匹配串長度為m，故不妨設(shè)從tq開始至tq+m-1結(jié)束的字符串為遺漏解，則按照構(gòu)造子串的方法，令r=q/s+1，則該串頭tq應(yīng)在textr中出現(xiàn)，且q＜r ·s，則q+m-1＜ i ·s+m-1,而textr的結(jié)束字符序號為i ·s+m-1，因此該串應(yīng)全部在textr中出現(xiàn)，即該串必能被在textr中找到，與假設(shè)矛盾。

iii＞因此，假設(shè)不成立，即該算法為完備算法，不丟解。

證畢。

圖2 KMP算法

3 算法的計算復(fù)雜性研究

3.1 算法在SM分布式系統(tǒng)中的時間復(fù)雜性

算法的時間復(fù)雜性tp（n）主要包括：分配文本的時間tt（n）與改進的KMP算法的時間tk（n）。

1）分配文本的時間tt（n）：如果將字符串復(fù)制作為基本操作的話，則顯然tt（n）=n/k+m-1=s+m-1，其時間復(fù)雜性為O（s+m）。

2）改進的KMP算法的時間tk（n）：其中計算模式串的next函數(shù)需要時間O（m），由于各分段的長度均為s+m-1，故計算各分段的KMP算法時間實際是tk（n）=O（m）+O（s+m-1）=O（s+2m）。

因此算法在SM分布式系統(tǒng)中的時間復(fù)雜性為tp（n）= tt（n）+tk（n）=O（s+2m）。

3.2 算法在DM分布式系統(tǒng)中的時間復(fù)雜性

算法的時間復(fù)雜性tp（n）同樣由分配文本的時間tt（n）與改進的KMP算法的時間tk（n）構(gòu)成。

1）分配文本的時間tt（n）：與算法在SM系統(tǒng)中不同，此時的文本分配時間應(yīng)在SM的基礎(chǔ)上加入初始分配的時間，顯然此時間為O（log2k）故tt（n）=O（s+m+log2k）。

2）改進的KMP算法的時間tk（n）：與算法在SM系統(tǒng)中相同，為O（s+2m）。

因此算法在DM分布式系統(tǒng)中的時間復(fù)雜性為tp（n）= tt（n）+tk（n）=O（s+2m）+O（s+m+log2k）。故log2k≤m，即k≤2m時復(fù)雜性 為O（s+2m），當k＞2m時復(fù)雜性為O（s+m+log2k）。因為k為系統(tǒng)中處理機數(shù)目，m為模式串長度，故在常規(guī)情況下可認為k≤2m。此時時間復(fù)雜性為tp（n）為O（s+3m）。

3.3 算法代價、效率與可擴放性

1）代價

因為算法在SM與DM系統(tǒng)下的計算時間僅有m的差異，故可統(tǒng)一計算代價，代價c（n）=tp（n）·p（n）≈k ·O（s+c·m）=O（n+ckm），（其中c=2，3），所以在ck≤n/m時算法代價為O（n）達到最佳，最佳情況需滿足ckm≤n，即正文串足夠長時達到最優(yōu)，顯然此為本算法適用范圍。

觀察最壞情況下串行KMP算法復(fù)雜度可知其復(fù)雜度為O（m+n），因此當正文串n＞＞模式串m時其復(fù)雜度可看作O（n），此時本算法的執(zhí)行代價與最壞情況下的串行算法所需時間已經(jīng)同階，因此本文中提出的并行算法在滿足ckm≤n時為代價最佳的并行算法。

顯然可知，通常情況下能夠滿足此條件。

2）效率與可擴放性

效率主要由算法的加速比和效率得出。

其中加速比Sp（n）=最壞情況下最優(yōu)串行算法運行時間ts（n）/tp（n），ts（n）即為改進的KMP算法所需時間tKMP（n）=O（m+n），如設(shè)通信時間開銷為ε（n）忽略不計，則加速比Sp（n）= ts（n）/tp（n）≈O（m+n）/O（n+ckm）。

而效率Ep（n）= Sp（n）/p（n）。當ckm≤n時Ep（n）≈1/k，兩者均達到最優(yōu)。因此本算法的下一階段工作應(yīng)著重在降低通信復(fù)雜度上。

由算法效率可知，只要滿足ckm≤n，則本算法最優(yōu)，則由可擴放性的概念顯然可知，本算法的可擴放性為線性的。

圖3 126K正文的擬合

4 實驗與結(jié)論

下面由圖3、4給出擬合的實驗結(jié)果，圖3正文長度為126K，圖4為284K，模式串長度分別為256B，512B，1K，2K與4K。處理機數(shù)目分別為1，2，4。

圖4 248K正文的擬合

由圖3、4可以看出，隨著處理機數(shù)目的增加，本算法在處理時的各項并行指標相對于1處理機而言均接近于最優(yōu)，且隨模式串長度的改變不明顯。當處理機增加一倍時，處理時間接近原來的一半，若同時將正文串增加一倍時，則處理時間近似不變。且在實驗過程中沒有丟解現(xiàn)象發(fā)生，由此可以驗證上文結(jié)論。

本文提出的并行KMP算法是并行字符串運算的基礎(chǔ)，也是并行模式識別的基礎(chǔ)，在文中提出的并行算法是最優(yōu)代價算法。在模式匹配領(lǐng)域中一個待解的問題就是無法有效地降低匹配的時間開銷，而文中算法在有效降低處理機的排列與通信時間復(fù)雜度的前提下可以最大化的降低模式匹配時間開銷。

[1]Boyer R S,Moore J S.A fast string searching algorithm [J].Commun ACM,1977,20（10）：762-772.

[2]Knuth D.E,Morris J.H,Pratt V.R.Fast Pattern Matching in Strings,SIAM J.Computing,1977,6：323-350.

[3]徐甲同,李學干.并行處理技術(shù)[M].西安：西安電子科技大學出版社.1999：1-199.

[4]蘇德富,鐘誠.計算機算法設(shè)計與分析[M].北京：電子工業(yè)出版社.2005.7：92-102.

[5]蔡曉妍,戴冠中,楊黎斌.一種快速的單模式匹配算法[J].計算機應(yīng)用研究.2008,25（1）：45-46,81.

[6]張國平,徐汶東.字符串模式匹配算法的改進[J].計算機工程與設(shè)計.2007,28（20）：4881-4884.

[7]陳國良,林潔,顧乃杰.分布式存儲的并行串匹配算法的設(shè)計與分析[J].軟件學報.2000,11（6）：771-778.

[8]郭薇,耿伯英,陳文靜.改進的KMP算法在艦船圖像匹配中的應(yīng)用[J].艦船電子工程.2008,28（6）：113-116.

[9]戈曉斐,黃競偉,胡磊.改進的KMP算法在生物序列模式自動識別中的應(yīng)用[J].計算機工程.2004,30（10）：140-142.