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

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

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

0 引言

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

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

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

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

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

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

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

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

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

4）加速比Sp（n）=ts（n）/tp（n），其中ts（n）為求解問題最快速的串行算法最壞情況下的運(yùn)行時(shí)間，tp（n）為求解同一問題的并行算法在最壞情況下的運(yùn)行時(shí)間。顯然，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)中的實(shí)現(xiàn)

2.1 KMP算法簡介

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

設(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，此時(shí)能夠保證正文塊相對滑動(dòng)最大距離。

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

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

1）初始化正文串分解：

將正文等分為k段，則每段長度s=n/k，在每段后面加上長度為m-1的擴(kuò)展串，將此長度為s+m-1的k段正文按處理器序號(hào)依次放入處理器中，處理器i分配的正文子串為texti=t（i-1）·s+1～ti·s+m-1，這里默認(rèn)正文與匹配串編號(hào)均從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為每個(gè)處理器的基本KMP算法?？紤]到對子串進(jìn)行分割可能造成的丟解情況，因此在本算法中對邊界做出擴(kuò)展，即需要在匹配串后端加入長度為m-1的擴(kuò)展串，相當(dāng)于在任意兩段子串texti與texti+1之間有m-1個(gè)冗余字符。此時(shí)在各子串中以KMP方法進(jìn)行匹配時(shí)能保證其不丟解，現(xiàn)證明如命題1所示。

圖1 textr函數(shù)算法

命題1.改進(jìn)的KMP并行算法不丟解。

證明：

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

ii＞假設(shè)改進(jìn)的KMP并行算法存在丟解情況，因?yàn)槠ヅ浯L度為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é)束字符序號(hào)為i ·s+m-1，因此該串應(yīng)全部在textr中出現(xiàn)，即該串必能被在textr中找到，與假設(shè)矛盾。

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

證畢。

圖2 KMP算法

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

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

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

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

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

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

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

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

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

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

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

3.3 算法代價(jià)、效率與可擴(kuò)放性

1）代價(jià)

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

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

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

2）效率與可擴(kuò)放性

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

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

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

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

圖3 126K正文的擬合

4 實(shí)驗(yàn)與結(jié)論

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

圖4 248K正文的擬合

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

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

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

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

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

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

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

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

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