并行系統中KMP串匹配算法的實現

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

LI Yan-kun1，FU Wei-na2，LIU Shuai3，ZHU Ming1

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

0 引言

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

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

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

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

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

1 并行算法參數設置

1）運行時間t（n）=tr+tc，其中tr為數據經由網絡或存儲器的選路時間，tc為數據在處理器內部進行算術、邏輯運算所需的計算時間。

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

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

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）并行算法伸縮性：給定處理器數目p，若Ep（n）隨問題規模n增加而單調遞增，則稱此算法為可伸縮的。

2 KMP算法在并行系統中的實現

2.1 KMP算法簡介

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

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

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

2.2 在SM并行系統中對KMP算法的改進

設長度為n正文串以t1-tn形式存放，處理器數目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執行算法1求得next函數值。

3）并行匹配：

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

對模式串p與正文子串textj執行算法2，輸出結果，算法結束。

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

圖1 textr函數算法

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

證明：

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

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

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

證畢。

圖2 KMP算法

3 算法的計算復雜性研究

3.1 算法在SM分布式系統中的時間復雜性

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

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

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

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

3.2 算法在DM分布式系統中的時間復雜性

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

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

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

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

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

1）代價

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

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

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

2）效率與可擴放性

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

其中加速比Sp（n）=最壞情況下最優串行算法運行時間ts（n）/tp（n），ts（n）即為改進的KMP算法所需時間tKMP（n）=O（m+n），如設通信時間開銷為ε（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，兩者均達到最優。因此本算法的下一階段工作應著重在降低通信復雜度上。

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

圖3 126K正文的擬合

4 實驗與結論

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

圖4 248K正文的擬合

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

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

[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]徐甲同,李學干.并行處理技術[M].西安：西安電子科技大學出版社.1999：1-199.

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

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

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

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

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

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