單模式字符串匹配算法效率的研究.pdf

1、字符串匹配的應用范圍非常廣泛，包括文檔編輯、入侵檢測、病毒特征碼查找、防火墻技術(shù)、基因序列匹配等多個領(lǐng)域。
　　 Sunday算法是當前應用廣泛并且比較高效的單模式匹配算法。但是當模式串和文本串均存在大量的重復字符時，Sunday算法的匹配次數(shù)將隨著首字符的重復次數(shù)快速增加，在這種情況下，算法的執(zhí)行效率將大大低于KMP算法。為了擴大Sunday算法的適用范圍，提高其平均執(zhí)行效率。本文提出了一種基于Sunday算法的改進算法，在算

2、法匹配工作開始前進行預處理，將重復的首字符壓縮為一個字符，然后使用壓縮后的字符串和正文進行匹配，如果匹配成功，返回成功匹配的位置信息，然后開始進行回溯，即對成功匹配的位置信息前的字符和首字符進行循環(huán)匹配，如果匹配位數(shù)和模式串相同，則返回成功，否則返回失敗?？梢詼p少大量無意義的匹配次數(shù)，提高算法的執(zhí)行速度。最后，分析改進后算法的性能，并通過實驗進一步證明了改進算法的有效性。
　　 由于直接對字符串匹配算法構(gòu)造狀態(tài)轉(zhuǎn)化圖進行效率分析

3、時的計算過程過于復雜。本文提出了一種以窮舉算法為基準，根據(jù)算法匹配差值計算算法效率的方法，并以Sunday算法為例進行了效率分析。因為Barth對窮舉算法的估計結(jié)果偏差較大，但窮舉算法起著非常重要的基準作用。因此首先對窮舉算法進行效率分析。在對窮舉算法的匹配過程進行了詳細分析的基礎上，構(gòu)建馬爾可夫鏈的狀態(tài)轉(zhuǎn)換圖描述其匹配過程，并對狀態(tài)轉(zhuǎn)換圖進行簡化。最終的狀態(tài)圖沒有吸收態(tài)，且當n較大時每個狀態(tài)的轉(zhuǎn)換概率都會收斂為一個穩(wěn)定值。根據(jù)以上特點

4、可求得每個狀態(tài)的轉(zhuǎn)換概率，得到窮舉算法比較精確的平均效率估計公式。
　　 其次，Sunday算法是最新的對BM算法進行了大幅改進的算法，和BM算法相比效率有了較大的提高，在實踐中得到了廣泛使用，具有新穎性和代表性。因此選擇Sunday算法進行效率分析。對Sunday算法的匹配過程比較復雜、使用壞字符啟發(fā)跳轉(zhuǎn)、難以構(gòu)建馬爾可夫鏈的特點，采用間接的方法得到算法效率。即在得到窮舉算法精確的匹配效率后，對Sunday算法和窮舉算法的匹配

5、過程進行詳細的分析，得出兩者的區(qū)別。將兩種算法按照模式串尾字符所對應文本字符的下一個字符是否屬于模式串分類討論，通過概率論相關(guān)知識計算出Sunday算法和窮舉算法平均匹配次數(shù)的差值。最后將窮舉算法的匹配效率與兩種算法的差值相減，得出Sunday算法平均效率估計公式。
　　 為使實驗文本串的大小和字母表容量嚴格相同，并在最差情況下匹配成功。我們將文本串的字符隨機交換位置后形成新的文本，將新文本和模式串進行匹配。如此不斷循環(huán)，直到不