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

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

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

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

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

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