字符串匹配算法Sunday的改進*

?

字符串匹配算法Sunday的改進*

朱寧洪

(西安科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，陜西 西安 710054)

摘要：字符串的模式匹配應(yīng)用十分廣泛，在信息的搜索查詢等方面具有重要作用，研究串匹配算法的效率具有重要的理論價值和實際意義。在分析幾種經(jīng)典模式匹配算法的基礎(chǔ)上，對當前應(yīng)用最廣泛的Sunday算法提出了改進的算法Zhusunday.算法主要改進之處是：在字符串從右向左匹配過程中，當文本字符中出現(xiàn)不匹配模式字符串的字符且該文本字符不是壞字符時，算法從右向左搜索當前文本字符在模式串中出現(xiàn)的位置；找到當前字符在模式串中的位置后繼續(xù)再向左匹配模式串字符一次，如果仍不匹配時，模式窗口比Sunday算法多向右移動一個字符。改進的算法提高了模式匹配的執(zhí)行效率，通過大量對比實驗證明了該算法的有效性。最后得出結(jié)論：在實際應(yīng)用中，壞字符大量存在的情況下，改進算法的最優(yōu)時間復(fù)雜度可達O(n/m)，在同一時間復(fù)雜度下，比Sunday算法效率提高25～50%.

關(guān)鍵詞：Sunday算法；Zhusunday算法；模式匹配；壞字符

0引言

字符串匹配問題是計算機科學(xué)中的最基本的問題，如何能在最短的時間內(nèi)確定特征字符串在文本中是否出現(xiàn)過具有重要的意義。在現(xiàn)實中，串匹配的應(yīng)用十分廣泛，主要領(lǐng)域包括：文檔編輯、內(nèi)容管理、計算機病毒檢測、信息檢索、符號操作、搜索引擎、DNA序列檢測以及入侵攻擊檢測等等[1]。而且，串匹配是這些應(yīng)用中的關(guān)鍵模塊，優(yōu)良的串匹配算法能大幅地提高應(yīng)用系統(tǒng)整體的效率[2]。因此，研究字符串的模式匹配算法的效率具有重要的理論價值和實際意義[3]。

設(shè)文本串T=T0…Tn-1，n為文本串T的長度；模式串P=P0…Pm-1，m為模式串的長度(n?m)。在T中尋找等于P的子串，如果在T中存在等于P的子串，則稱匹配成功，函數(shù)值返回P第一次出現(xiàn)在文本串T中時P的首字符的在T中的下標，否則稱為匹配失敗，這個搜索過程就是模式匹配[4]。

按照匹配遍歷時被查找的模式串個數(shù)劃分，字符串匹配算法又可以分為2種：單模式匹配和多模式匹配。單模式匹配算法遍歷一次可以搜索一個字符串，多模式匹配算法能夠在遍歷一次的情況下，搜索出文本中模式串里多個模式串的所有出現(xiàn)位置。目前，國內(nèi)外對于模式匹配算法已有不少的研究成果，比如典型的單模式算法有BF算法、KMP算法、BM算法、Sunday算法，多模式算法主要有AC算法、Wu_Mander算法[5]。鑒于許多單模式搜索算法能夠擴展成多模式搜索算法，在此簡要介紹4種經(jīng)典單模式匹配算法。

1幾種經(jīng)典的模式匹配算法

BF算法是效率最低的算法，又稱蠻力匹配算法[6]。在文本串中從左到右進行匹配。首先將T[0]與P[0]進行比較，若相等，則逐個比較后續(xù)字符；否則，就將T[1]與P[0]進行比較，繼續(xù)開始下一趟的比較，重復(fù)上述過程。算法特點是簡單易理解，但時間復(fù)雜度較大，為O(m*n)[7]。

KMP算法是由BF改進后不產(chǎn)生回溯的一種算法，每當匹配過程中出現(xiàn)字符串匹配不等時，不需回溯指針，而是利用已得到的“部分匹配”結(jié)果將模式向右滑動盡可能遠的一段距離后，繼續(xù)進行比較。模式串不一定向右移動一個字符的位置，右移也不是必須從模式串起點處重新試匹配，也就是模式串可以一次向右移動多個字符的位置，右移后可以從模式串起點后的某處開始試匹配。理論上時間最優(yōu)復(fù)雜度可達到O(m+n)；空間復(fù)雜度O(n)[8]。

BM算法在匹配過程中方向是由左向右，但是在比較過程中方向是由右向左[9]，也就是把P同T進行比較時從右向左。當某趟匹配失敗時，采用壞字符(在T串中存在而P串中沒有的字符稱為壞字符)規(guī)則和好后綴規(guī)則計算模式串右移的距離，并取兩者最大值來決定模式串的右移量，移動盡可能遠的距離，直到匹配成功或文本串匹配結(jié)束。匹配時從右至左進行。BM算法的最壞時間復(fù)雜度為O(m*n)，但由于實際應(yīng)用中這種情況極少出現(xiàn)，因此BM算法仍然得到廣泛應(yīng)用。特別是當發(fā)現(xiàn)不匹配的字符時可以使用好后綴和壞字符進行跳轉(zhuǎn)，降低無效的匹配次數(shù)[10]。

Sunday算法是最新的對BM算法進行了大幅改進的算法，Sunday算法采用BM算法中的壞字符啟發(fā)規(guī)則，和BM算法相比效率有了較大的提高，在實踐中得到了廣泛使用，具有新穎性和代表性。下面以在T串“abcoefcacdxdbcd”中查找模式串P“dbcd”的過程來介紹Sunday算法，算法的匹配過程如圖1所示。

T串a(chǎn)bcoefcacdxdbcd匹配次數(shù)Sunday算法模式串p位置×　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　od不匹配,o不存在,且下一字符e1=p[0],P窗口向左移5.×　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　cd不匹配,p中c與T中c對齊,右移1.×√√　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ab不匹配,將P中右側(cè)第2個d與T當前d對齊,P窗口右移3.×　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　bd不匹配,p中右側(cè)第1個b與T當前b對齊,P窗口右移2.√√√√　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　匹配成功12345(成功)

圖1Sunday算法執(zhí)行情況

Fig.1Implementation of Sunday algorithm

Sunday算法過程敘述如下：開始時模式串P的左邊與文本串T的左邊對齊；模式匹配過程中進行P與T的比較時，從右向左反向進行比較，反復(fù)比較匹配，直到找到模式串或文本串比較完。比較過程中有2種情況1)和2)

1)在發(fā)現(xiàn)與P最右側(cè)第一個字符對應(yīng)位置的T字符不匹配時，又分2種情況A和B：A.當前字符是壞字符因此發(fā)生不匹配時，如果T當前字符右面的字符依然不匹配模式串P的第一個字符p[0]，模式窗口向右移動m+1(m為P長度)，如果當前的字符匹配，模式窗口則只向右移動m(m為P模式串的長度)繼續(xù)下一輪匹配(此時情況與圖1中的Sunday算法第一次匹配的情況相同)；B.如果不是壞字符，則在P中由右向左查找T中當前字符，讓模式窗口從右向左第一次出現(xiàn)該字符的地方與T中當前字符對齊，繼續(xù)下一輪的匹配(此時情況最常見，與圖1中的Sunday算法第2次和第4次匹配的情況相同)；

2)在發(fā)現(xiàn)與P最右側(cè)第一個字符對應(yīng)位置的T字符匹配時，P向左取第二個和T再向左取的第二個字符繼續(xù)匹配，一直匹配到字符不同或匹配完p串。也有2種情況C和D：C.如果未能匹配完，則T當前的不匹配字符d與在模式串中從右側(cè)第一次出現(xiàn)d的位置對齊，繼續(xù)下一輪的匹配；(此時情況與圖1中的Sunday算法第3次匹配的情況相同)D.如果一直匹配，直到P所有字符匹配完，則返回T中與P[0]對應(yīng)的開始位置作為匹配位置，算法結(jié)束(此時情況與圖1中的Sunday算法第5次匹配的情況相同)。

Sunday算法在最壞情況下的計算復(fù)雜度為O(m*n)。但是在實際使用中文本串的壞字符出現(xiàn)概率非常高，最好情況(在找到P串以前遇到的字符都是壞字符)下的時間復(fù)雜度可達到O(n/m)，所以在實踐中應(yīng)用廣泛。Sunday算法是目前單模式匹配算法中比較成熟，且效率最高的一種。

2Sunday算法的改進

下面是用Sunday算法和改進的算法(稱之為Zhusundays算法)進行模式串匹配的一個例子，具體說明2個算法相同部分和不同

文本串T=“abcoefcacdxdbcd”，模式串P=“dbcd”.Sunday算法和Zhusunday算法在模式窗口中都由右向左匹配。Sunday算法匹配過程(如圖1所示)上面已經(jīng)敘述完畢，下面敘述Zhusuanday算法，其具體匹配過程如圖2所示。

Zhusunday算法針對Sunday算法最常見的(1)B和(2)C情況進行了改進，其余部分和Sunday算法一樣。改進之處在于

T串a(chǎn)bcoefcacdxdbcd匹配次數(shù)zhusuanday算法模式串p位置×　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　od不匹配,o不存在,且下一字符e1=p[0],P窗口向左移5.×　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　cd不匹配,P中右側(cè)第1個c與T中c對齊,P窗口右移1;同時,P串c左側(cè)b與對應(yīng)T串c左側(cè)字符a不同,P窗口需再右移1.×　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　dx不匹配,x不在P串,T下一字符d==p[0],P窗口右移4.√√√√　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　匹配成功1234(成功)

圖2Zhusunday算法執(zhí)行情況

Fig.2Implementation of Zhusunday algorithm

1)在Sunday算法最常見的(1)B情況(也就是不匹配，且不是壞字符，向前不能完全匹配，與圖1中的Sunday算法第2次和第4次匹配的情況相同)下，只讓P中當前字符與T對應(yīng)的字符對齊，對齊是假定T當前字符左側(cè)的字符與P當前字符左側(cè)的字符相同(2個連續(xù)字符都相同一般情況下是不常見的)，已經(jīng)在P中從右向左查找到了當前字符，但是，如果假定不成立，就可以多移動一個字符的位置，算法開銷的成本就是多比較一個字符，這種情況和圖2中Zhusunday算法第2次匹配一樣。如果相同，就和原來移動步數(shù)一樣。讓我們來分析一下改動之后效率：如果比較一次，字符不匹配時將多移動模式窗口一個字符位置(這是大概率事件)，如果不比較，按照Sunday算法移動模式窗口一個字符位置，需要的執(zhí)行步數(shù)，首先要判斷對應(yīng)位置字符是否匹配(需要比較1次)，不匹配(大概率事件)，則先判斷是否屬于壞字符，需要m次比較，如果不是壞字符，再查找在模式串中的位置，查找位置平均需要m/2次，才決定移動字符數(shù)(最多m個字符，最少1個字符，平均(m+1)/2個字符，各種情況下總比較次數(shù)為1+m+m/2，除以平均次數(shù)(m+1)/2，大約為3，也就是平均移動一個字符，比較要3次)；而改進后的算法，基本上屬于移動一次，需要比較一次(大概率事件)，這樣就顯著提高了算法效率。針對圖1，Sungday算法第2次匹配和Zhusunday算法第2次匹配面臨相同的情況，兩算法卻做出了不同操作，Zhusunday算法第2次匹配多向右移動了一步，導(dǎo)致最后算法效率的不同。同樣的情況發(fā)生在(2)C情況下，這里也對Sunday算法進行了改進；這時也向左多判斷一個字符，多數(shù)情況下也會讓匹配窗口多向右移動一步。在本示例中，以上算法的改動讓Zhusunday算法匹配次數(shù)比Sunday算法少了一次。

3算法實現(xiàn)

根據(jù)上面的算法分析，采用C語言實現(xiàn)了Zhusunday算法，該算法整體采用循環(huán)結(jié)構(gòu)，首先是雙分支，分出前面敘述的(1)和(2)2種情況

1)又分成A和B 2種情況，在B情況下，再向前判斷，又分2種情況：①不匹配，模式窗口前進多增加1字符；②匹配，模式窗口按照原來Sunday算法計算的步長移動；

2)又分成C和D 2種情況，和上面的敘述一致，下面是C語言的實現(xiàn)該算法的源程序，相關(guān)注釋進行了說明。

int zhusunday(char *T，char *p，int pos)//pos是T中下標開始位置，主體算法

{int Tindex=pos+lengthP-1；

int pindex=lengthP-1；

//Tindex是在T中搜索的當前位置，采用從右向左探索

int pipeipos；

while(Tindex≤lengthT-1)//遍歷源串T

{

pipeicishu++；//2種情況1和2.

if(T[Tindex]!=p[pindex])//不匹配模式串p最后一個字符，有2種情況，分別是1和2.

{if(dist[T[Tindex]]==lengthP)//1A：目標字符不在模式串中，是壞字符；dist是模式串預(yù)處理數(shù)組，對0～127的ASCII字符能使模式窗口向右移動距離進行了預(yù)先統(tǒng)計。

if(T[1+Tindex]!=p[0])//多驗證壞字符左側(cè)的一個字符。

Tindex+=lengthP+1；//跳躍模式串長度個字符探索，驗證成功比壞字符多跳一個。

else //驗證不成功，跳躍模式串長度個字符。

Tindex+=lengthP；

else//1B：改進處：目標字符在模式串中，但不是模式串最后一個字符；

{intx=lengthP-2-dist[T[Tindex]]；//x是由右向左第一次不匹配時字符的下標，因為沒有全匹配，其值不能小于0.

if(p[x]!=T[Tindex-1]&&x>=0)

Tindex+=dist[T[Tindex]]+1；

else //這種情況多數(shù)不成立(而Sunday算法假定這里始終成立)。

Tindex+=dist[T[Tindex]]；

}

}

else//2：匹配模式串的最后一個字符，回溯追查，對應(yīng)2種情況，分別是C和D.

{pipeipos=quanpipei(T，p，Tindex，lengthP-1)；//從最后一個字符向前進行匹配

if(pipeipos!=0)//C：由后向前部分字符匹配，沒有全匹配。這里也對Sunday進行了改進。

{intx=lengthP-2-dist[T[Tindex]]；

//x是由右向左最后一次匹配的字符左側(cè)的字符的下標，因為沒有全匹配，其值不能小于0.

if(p[x]!=T[Tindex-1]&&x>=0)

Tindex+=dist[T[Tindex]]+1；//多移動

else

Tindex+=dist[T[Tindex]]；

}

else//D：所有字符全匹配。

return Tindex-lengthP+1；//返回匹配的起始下標。

}

}

if(Tindex>=lengthT)//匹配結(jié)束，依然沒有返回，表示未匹配成功。

return-1；

}

4實驗結(jié)果評測

為了評測該算法的性能，對算法運行的匹配次數(shù)和語句執(zhí)行次數(shù)進行了比較。針對圖1和圖2列舉的情況，兩算法運行結(jié)果顯示如圖3，程序?qū)η懊娴膶嵗M行了驗證，得出了Sunday算法匹配5次和Zhusunday匹配4次的結(jié)果；同時，在兩算法的執(zhí)行語句的位置旁都添加了全局變量count的自增語句作為計數(shù)器，來統(tǒng)計兩者時間復(fù)雜度的依據(jù)，運行結(jié)果顯示，優(yōu)化后的Zhusunday執(zhí)行了17步，Sunday算法執(zhí)行了25步，是原算法執(zhí)行步數(shù)的68%，同時針對不同數(shù)據(jù)進行了多次驗證，結(jié)果都顯示Zhusunday優(yōu)于Sunday算法，特別是針對模式串P后綴在文本串T重復(fù)率高的情況，優(yōu)化比率更明顯。由于該實例T中大量包含模式串P中的字符，Zhusunday的執(zhí)行次數(shù)在1.1n左右，達到17次；Sunday執(zhí)行次數(shù)為1.7n左右，達到25次。在實際中經(jīng)過大量測試，在壞字符大量存在的情況下，二者的時間復(fù)雜度逐漸接近O(n/m)，基本一致，但Zhusunday算法的執(zhí)行次數(shù)始終優(yōu)于Sunday算法，Zhusunday算法的執(zhí)行次數(shù)約為Sunday算法執(zhí)行次數(shù)的65%～80%之間，效率提高25%～50%.限于篇幅，更多的比較結(jié)果這里不再一一列舉顯示結(jié)果。

圖3　2種算法比較程序運行結(jié)果Fig.3　Comparison of two algorithm program results

5結(jié)論

文中針對當前研究的熱點字符串匹配算法(Sunday算法)，提出了改進的算法Zhusunday，并對兩者算法進行了分析和實現(xiàn)，并通過實驗驗證了Zhusunday優(yōu)于Sunday算法。經(jīng)過大量實際測試，在壞字符大量存在的情況下，Zhusuanday算法能達到O(n/m)的時間復(fù)雜度，且Zhusunday算法的效率比Sunday算法提高25%～50%.

參考文獻References

[1]潘冠樺.單模式字符串匹配算法效率的研究[D].太原：太原理工大學(xué)，2013.

PAN Guan-hua.Research on the efficiency of single mode string matching algorithm[D].Taiyuan:Taiyuan University of Technology, 2013.

[2]孫藝珍，季小迪，張京濤.基于.Net的全文搜索引擎設(shè)計與實現(xiàn)[J].西安科技大學(xué)學(xué)報,2014，34(6)：701.

SUN Yi-zhen,JI Xiao-di,ZHANG Jing-tao.Design and implementation of full text search engine based on .Net[J].Journal of Xi’ an University of Science and Technology，2014，34(6)：701.

[3]馬莉，李樹剛，肖鵬，等.云計算環(huán)境下煤礦應(yīng)急管理海量數(shù)據(jù)存儲技術(shù)[J].西安科技大學(xué)學(xué)報,2014，34(5)：596.

MA Li,LI Shu-gang,XIAO Peng,et al. Mass data storage technology of coal mine emergency management in cloud computing environment[J].Journal of Xi’ an University of Science and Technology，2014，34(5)：596.

[4]李軍民，李立博.人工魚群和蒙特卡羅混合算法的應(yīng)用[J].西安科技大學(xué)學(xué)報，2014，34(2)：224.

LI Jun-min,LI Li-bo.Application of artificial fish swarm and Monte Carlo hybrid algorithm[J].Journal of Xi’ an University of Science and Technology，2014，34(2)：224.

[5]巫喜紅，凌捷.基于字符頻率的字符串模式匹配算法的研究[J].制造業(yè)自動化，2013，35(9)：11-14.

WU Xi-hong,LING Jie.Research on string pattern matching algorithm based on character frequency[J].Manufacturing Automation,2013,35(9):11-14.

[6]許元飛 基于紋理的圖像檢索算法研究[J].西安科技大學(xué)學(xué)報,2013，33(4)：470.

XU Yuan-fei.Research on texture based image retrieval algorithm[J].Journal of Xi’ an University of Science and Technology，2013，33(4)：470.

[7]徐珊，袁小坊.Sunday字符串匹配算法的效率改進[J]．計算機工程與應(yīng)用，2011，47(29)：96-98.

XU Shan,YUAN xiao-fang. Efficiency improvement of Sunday string matching algorithm[J].Computer engineering and Application,2011，47(29)：96-98.

[8]潘冠樺，張興忠.Sunday算法效率分析[J].計算機應(yīng)用，2012，32(11)：3 082-3 084.

PAN Guan-hua,ZHANG Xing-zhong.Efficiency analysis of Sunday algorithm[J].Computer Applications,2012，32(11):3 082-3 084.

[9]馮川放.規(guī)則引擎技術(shù)的可配置EOS平臺的設(shè)計與實現(xiàn)[J].西安科技大學(xué)學(xué)報，2013，33(3)：353.

FENG Chuan-fang. Design and implementation of configurable EOS platform for rule engine technology[J].Journal of Xi’ an University of Science and Technology，2013，33(3)：353.

[10]李明月，張善卿，陸劍鋒，等.一種改進的Sunday匹配算法[J].杭州電子科技大學(xué)學(xué)報，2015，35(1)：93-97.

LI Ming-yue,ZHANG Shan-qing，LU Jian-feng,et al.An improved Sunday matching algorithm[J].Journal of Hangzhou Electronic and Science University,2015，35(1)：93-97.

Improvement of Sunday pattern matching algorithm

ZHU Ning-hong

(CollegeofComputerScienceandEngineering,Xi’anUniversityofScienceandTechnology,Xi’an710054,China)

Abstract:String pattern matching is widely used in information search and query，and it is important to study the efficiency of the string matching algorithm with theoretical value and practical significance.On the basis of the analysis of several classical pattern matching algorithms，the paper puts forward a Zhusunday algorithm which is improved from the most widely used Sunday algorithm.The improved position of the algorithm is：in the matching process from the right of the text string to the left，when the character of the text does not match the character of the pattern string，it is not a bad character，the algorithm searches the position of the current text character from the right to the left in the pattern string.After finding the position，the improved algorithm continues to match the two characters in the left for another time.If there is no match，the pattern window will move to right one step more than the movement of Sunday algorithm.The improved algorithm improves the efficiency of the pattern matching，and the effectiveness of the proposed algorithm is proved by a lot of experiments.Finally the paper draws a conclusion：in practical application there are a large number of the bad characters，the optimal time complexity of the improved algorithm isO(n/m)，and at the same time complexity，the improved algorithm is more efficient than the Sunday algorithm by 25～50%.

Key words：Sunday algorithm；Zhusunday algorithm；pattern matching；bad character

中圖分類號：TP 391

文獻標志碼：A

作者簡介：朱寧洪(1969-)，男，山東兗州人，講師，E-mail:zhuninghong@sohu.com

基金項目：國家自然基金(煤炭聯(lián)合基金)(U1261114)

收稿日期：*2015-07-29責(zé)任編輯：高佳

文章編號：1672-9315(2016)01-0111-05

DOI：10.13800/j.cnki.xakjdxxb.2016.0119