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

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

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

2、orithmofString-Matchingisthisalgorithmusesthestatisticcharacteristicofthepositionandfrequencyofthechartobuildanewmatchinglist.Duringtheprocessofthematching,thisalgorithmwilltryitsbesttousethischaracteristictoskipmuchmorecharstoimprovetheefficiencyofthematching.Anothercharac

3、teristicofthisAlgorithmisitcansuccessfullyfinishwithoutcomparingallcharsintheText.ComparingwiththeAlgorithmbefore,likeBF,KMP,BM,thisAlgorithm’saveragecomplicationoftimereachesthenbestconditionofthese.Keywords:string-matching;algorithm;statisticcharacteristic目錄引言11緒論21.1基于統(tǒng)計(jì)

4、特征的模式匹配算法提出原因21.2基本數(shù)據(jù)規(guī)定22傳統(tǒng)的模式匹配算法22.1BF算法22.2KMP算法32.3BM算法53基于統(tǒng)計(jì)特征的模式匹配算法53.1算法思想53.2算法分析7結(jié)束語9參考文獻(xiàn)10青海師范大學(xué)2010屆本科生畢業(yè)論文引言字符串匹配是字符串的基本運(yùn)算之一。串的模式匹配即子串定位，是一種重要的串運(yùn)算。模式匹配就是在主串S=s1s2s3s4……中查找模式串T=t1t2t3t4……的所有出現(xiàn)，該技術(shù)在很多領(lǐng)域都發(fā)揮重要的作用，比如在情報(bào)檢索、網(wǎng)絡(luò)搜索、文本檢索、拼寫檢查、語言翻譯、數(shù)據(jù)壓縮、網(wǎng)絡(luò)入侵檢測、計(jì)算機(jī)病毒特征碼匹配以及

5、DNA序列匹配等各個(gè)方面都有著很重要的應(yīng)用。通過模式匹配，我們可以得到很多我們想要知道的信息，而這些是靠人工難以完成的。尤其是在以后的段落搜索，自然語言查詢中，對模式匹配的速度、效率等要求會(huì)越來越高，而傳統(tǒng)的BF、KMP和BM等算法并不能很高效的給出結(jié)果，因此我們有必要對模式匹配的算法進(jìn)行進(jìn)一步發(fā)展。本文主要在介紹了BF算法、KMP算法的基礎(chǔ)上提出一種更好的算法—基于統(tǒng)計(jì)特征的模式匹配算法。1青海師范大學(xué)2010屆本科生畢業(yè)論文1緒論我們在日常生活中經(jīng)常以局部特征判定事物，而這種方式是普遍認(rèn)可的，也是最佳的。一項(xiàng)將此技術(shù)應(yīng)用于計(jì)算機(jī)科學(xué)領(lǐng)域的

6、就是基于統(tǒng)計(jì)特征的模式匹配算法。1.1基于統(tǒng)計(jì)特征的模式匹配算法提出原因?qū)τ贙MP、BM等算法有一個(gè)共同的特征：順序掃描—或者從左至右，或者從右至左。這樣的好處是匹配時(shí)有順序的規(guī)律可循，比較容易理解，操作起來比較方便，缺點(diǎn)就是沒有最大限度利用模式自身的一些統(tǒng)計(jì)特征—而只是利用了順序的特征。如何利用統(tǒng)計(jì)特征呢？舉個(gè)例子來證明。在街上我們遇到了一個(gè)似曾相識(shí)的人，我們判斷那個(gè)人是不是我們認(rèn)識(shí)的人的時(shí)候，我們是把遇到的那個(gè)人與我們記憶中的那個(gè)人的特征相比較，比如說禿頂，眼角有顆痔，身高，性別，胖瘦，臉型，膚色等等。我們比較是鮮明的特征，而不是從頭到腳

7、的掃描比較。也就是說我們在比較兩個(gè)事物的時(shí)候是優(yōu)先比較他們比較特殊的地方。對于模式匹配，這個(gè)優(yōu)先級似的比較方式依然成立。1.2基本數(shù)據(jù)規(guī)定傳統(tǒng)的算法分析在有了模式匹配的需要后，出現(xiàn)了很多模式匹配的算法，在這里為后續(xù)內(nèi)容分析而規(guī)定：主串S的長度為n，模式串T的長度為m，子串的定位操作Index(S,T,pos)，其中pos為某個(gè)字符在主串中的位置。2傳統(tǒng)的模式匹配算法本章介紹三種典型的傳統(tǒng)的模式匹配算法，并分別給出部分算法實(shí)現(xiàn)。2.1BF算法BF（Brute-Force）算法即簡單模式匹配算法，也稱樸素串匹配算法算法，其算法思想：對主串S和模式

8、串T進(jìn)行從左至右順序匹配比較，若主串S的第一個(gè)字符和模式串T的第一個(gè)字符進(jìn)行比較，若相等則同時(shí)向后移動(dòng)一位，繼續(xù)逐個(gè)比較后續(xù)字符，否則如果在完全匹配結(jié)束前發(fā)生不匹配