基于統(tǒng)計特征的模式匹配算法

《基于統(tǒng)計特征的模式匹配算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、基于統(tǒng)計特征的模式匹配算法摘要針對傳統(tǒng)模式匹配算法的按模式中字符排列順序匹配的過程，該算法模擬人腦思維利用模式中字符出現(xiàn)頻率、位置等特征信息建立了一個新的匹配序列，打亂了原來的順序匹配過程，從而在匹配過程中，利用特征信息盡可能的跳過更多的字符，從而達到比較高的匹配效率。該算法的另一大特點就是不需要遍歷完所有文本中的字符就可以找出與模式匹配的字符串。與傳統(tǒng)的BF、KMP、BM等算法相比，該算法的平均時間復(fù)雜度已經(jīng)達到了他們的最好情況。關(guān)鍵詞：模式匹配；算法；統(tǒng)計特征AbstractThedifferencetot

2、hetraditionalAlgorithmofString-Matchingisthisalgorithmusesthestatisticcharacteristicofthepositionandfrequencyofthechartobuildanewmatchinglist.Duringtheprocessofthematching,thisalgorithmwilltryitsbesttousethischaracteristictoskipmuchmorecharstoimprovetheeffic

3、iencyofthematching.AnothercharacteristicofthisAlgorithmisitcansuccessfullyfinishwithoutcomparingallcharsintheText.ComparingwiththeAlgorithmbefore,likeBF,KMP,BM,thisAlgorithm’saveragecomplicationoftimereachesthenbestconditionofthese.Keywords:string-matching;a

4、lgorithm;statisticcharacteristic目錄引言11緒論21.1基于統(tǒng)計特征的模式匹配算法提出原因21.2基本數(shù)據(jù)規(guī)定22傳統(tǒng)的模式匹配算法22.1BF算法22.2KMP算法32.3BM算法53基于統(tǒng)計特征的模式匹配算法53.1算法思想53.2算法分析7結(jié)束語9參考文獻10青海師范大學2010屆本科生畢業(yè)論文引言字符串匹配是字符串的基本運算之一。串的模式匹配即子串定位，是一種重要的串運算。模式匹配就是在主串S=s1s2s3s4……中查找模式串T=t1t2t3t4……的所有出現(xiàn)，該技術(shù)在很

5、多領(lǐng)域都發(fā)揮重要的作用，比如在情報檢索、網(wǎng)絡(luò)搜索、文本檢索、拼寫檢查、語言翻譯、數(shù)據(jù)壓縮、網(wǎng)絡(luò)入侵檢測、計算機病毒特征碼匹配以及DNA序列匹配等各個方面都有著很重要的應(yīng)用。通過模式匹配，我們可以得到很多我們想要知道的信息，而這些是靠人工難以完成的。尤其是在以后的段落搜索，自然語言查詢中，對模式匹配的速度、效率等要求會越來越高，而傳統(tǒng)的BF、KMP和BM等算法并不能很高效的給出結(jié)果，因此我們有必要對模式匹配的算法進行進一步發(fā)展。本文主要在介紹了BF算法、KMP算法的基礎(chǔ)上提出一種更好的算法—基于統(tǒng)計特征的模式匹配

6、算法。1青海師范大學2010屆本科生畢業(yè)論文1緒論我們在日常生活中經(jīng)常以局部特征判定事物，而這種方式是普遍認可的，也是最佳的。一項將此技術(shù)應(yīng)用于計算機科學領(lǐng)域的就是基于統(tǒng)計特征的模式匹配算法。1.1基于統(tǒng)計特征的模式匹配算法提出原因?qū)τ贙MP、BM等算法有一個共同的特征：順序掃描—或者從左至右，或者從右至左。這樣的好處是匹配時有順序的規(guī)律可循，比較容易理解，操作起來比較方便，缺點就是沒有最大限度利用模式自身的一些統(tǒng)計特征—而只是利用了順序的特征。如何利用統(tǒng)計特征呢？舉個例子來證明。在街上我們遇到了一個似曾相識的

7、人，我們判斷那個人是不是我們認識的人的時候，我們是把遇到的那個人與我們記憶中的那個人的特征相比較，比如說禿頂，眼角有顆痔，身高，性別，胖瘦，臉型，膚色等等。我們比較是鮮明的特征，而不是從頭到腳的掃描比較。也就是說我們在比較兩個事物的時候是優(yōu)先比較他們比較特殊的地方。對于模式匹配，這個優(yōu)先級似的比較方式依然成立。1.2基本數(shù)據(jù)規(guī)定傳統(tǒng)的算法分析在有了模式匹配的需要后，出現(xiàn)了很多模式匹配的算法，在這里為后續(xù)內(nèi)容分析而規(guī)定：主串S的長度為n，模式串T的長度為m，子串的定位操作Index(S,T,pos)，其中pos為

8、某個字符在主串中的位置。2傳統(tǒng)的模式匹配算法本章介紹三種典型的傳統(tǒng)的模式匹配算法，并分別給出部分算法實現(xiàn)。2.1BF算法BF（Brute-Force）算法即簡單模式匹配算法，也稱樸素串匹配算法算法，其算法思想：對主串S和模式串T進行從左至右順序匹配比較，若主串S的第一個字符和模式串T的第一個字符進行比較，若相等則同時向后移動一位，繼續(xù)逐個比較后續(xù)字符，否則如果在完全匹配結(jié)束前發(fā)生不匹配