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

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

2、g-Matching is this algorithm uses the statistic characteristic of the position and frequency of the char to build a new matching list. During the process of the matching, this algorithm will try its best to use this characteristic to skip much more chars to improve the efficiency of the matching. An

3、other characteristic of this Algorithm is it can successfully finish without comparing all chars in the Text. Comparing with the Algorithm before, like BF ,KMP, BM, this Algorithms average complication of time reaches then best condition of these. Keywords: string-matching; algorithm; statistic char

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

5、應(yīng)用。通過模式匹配，我們可以得到很多我們想要知道的信息，而這些是靠人工難以完成的。尤其是在以后的段落搜索，自然語言查詢中，對(duì)模式匹配的速度、效率等要求會(huì)越來越高，而傳統(tǒng)的BF、KMP和BM等算法并不能很高效的給出結(jié)果，因此我們有必要對(duì)模式匹配的算法進(jìn)行進(jìn)一步發(fā)展。本文主要在介紹了BF算法、KMP算法的基礎(chǔ)上提出一種更好的算法基于統(tǒng)計(jì)特征的模式匹配算法。1緒論我們?cè)谌粘Ｉ钪薪?jīng)常以局部特征判定事物，而這種方式是普遍認(rèn)可的，也是最佳的。一項(xiàng)將此技術(shù)應(yīng)用于計(jì)算機(jī)科學(xué)領(lǐng)域的就是基于統(tǒng)計(jì)特征的模式匹配算法。1.1 基于統(tǒng)計(jì)特征的模式匹配算法提出原因 對(duì)于KMP、BM等算法有一個(gè)共同的特征：順序掃描或者從

6、左至右，或者從右至左。這樣的好處是匹配時(shí)有順序的規(guī)律可循，比較容易理解，操作起來比較方便， 缺點(diǎn)就是沒有最大限度利用模式自身的一些統(tǒng)計(jì)特征而只是利用了順序的特征。如何利用統(tǒng)計(jì)特征呢？舉個(gè)例子來證明。在街上我們遇到了一個(gè)似曾相識(shí)的人，我們判斷那個(gè)人是不是我們認(rèn)識(shí)的人的時(shí)候，我們是把遇到的那個(gè)人與我們記憶中的那個(gè)人的特征相比較，比如說禿頂，眼角有顆痔，身高，性別，胖瘦，臉型，膚色等等。我們比較是鮮明的特征，而不是從頭到腳的掃描比較。也就是說我們?cè)诒容^兩個(gè)事物的時(shí)候是優(yōu)先比較他們比較特殊的地方。對(duì)于模式匹配，這個(gè)優(yōu)先級(jí)似的比較方式依然成立。1.2 基本數(shù)據(jù)規(guī)定傳統(tǒng)的算法分析在有了模式匹配的需要后，出

7、現(xiàn)了很多模式匹配的算法，在這里為后續(xù)內(nèi)容分析而規(guī)定：主串S的長(zhǎng)度為n，模式串T的長(zhǎng)度為m，子串的定位操作Index(S,T,pos)，其中pos為某個(gè)字符在主串中的位置。 2傳統(tǒng)的模式匹配算法 本章介紹三種典型的傳統(tǒng)的模式匹配算法，并分別給出部分算法實(shí)現(xiàn)。 BF算法BF（Brute-Force）算法即簡(jiǎn)單模式匹配算法，也稱樸素串匹配算法算法，其算法思想：對(duì)主串S和模式串T進(jìn)行從左至右順序匹配比較，若主串S的第一個(gè)字符和模式串T的第一個(gè)字符進(jìn)行比較，若相等則同時(shí)向后移動(dòng)一位，繼續(xù)逐個(gè)比較后續(xù)字符，否則如果在完全匹配結(jié)束前發(fā)生不匹配，那么模式串T回溯到模式首字符，而主串S則回溯到起始位置的下一個(gè)字

8、符進(jìn)行比較。依次類推，直至模式串T和主串S中的一個(gè)子串相等，此時(shí)稱為匹配成功，否則，稱為匹配失敗。圖2-1展示了pos=1時(shí)，模式串T=abcac和主串S=ababcabcacbab的匹配過程。其中i和j指示主串S和模式串T中當(dāng)前正待比較的字符位置。串的簡(jiǎn)單模式匹配算法描述如算法2-1所示。【算法描述】int Index(SString S, SString T, int pos) int i, j;i=pos; j=1;While (i<=S0&&j<=T0) if (Si= Tj) +i; +j; else i=i-j+2; j=1; if (j>=T0)

9、 return (i- T0);else return 0;算法2-1 串的簡(jiǎn)單模式匹配 i=3第1趟匹配 S a b a b c a b c a c b a b T a b c a c j=3 i=2第2趟匹配 S a b a b c a b c a c b a b T a b c a c j=1 i=7第3趟匹配 S a b a b c a b c a c b a b T a b c a c j=5 i=4第4趟匹配 S a b a b c a b c a c b a b T a b c a c j=1 i=5第5趟匹配 S a b a b c a b c a c b a b T a b

10、c a c j=1 i=11第6趟匹配 S a b a b c a b c a c b a b T a b c a c j=6圖2-1 串的簡(jiǎn)單模式匹配過程示意這種算法看起來比較簡(jiǎn)單，但是效率比較低，最好的情況下為O(m+n)，在最壞情況下，每趟比較都在最后出現(xiàn)不等，最多要比較n-m-1趟，總比較次數(shù)為O(n-m+1)m)，算法的時(shí)間復(fù)雜度為O(m*n)。 KMP算法2.2.1簡(jiǎn)述KMP（無回溯的模式匹配）算法正是由D.E.Knuth 、V.R.Pratt 和同時(shí)發(fā)現(xiàn)的，因此稱KMP算法。它是針對(duì)上述算法頻繁回溯的不足做了實(shí)質(zhì)性的改進(jìn)。其基本思想是：某趟匹配中，主串字符si和模式串tj匹配失敗

11、后，指針i不回溯，而是讓模式串T向右“滑動(dòng)”至某個(gè)位置，假設(shè)這個(gè)位置是k，使得tj對(duì)準(zhǔn)si繼續(xù)向右進(jìn)行比較。因此，KMP算法的關(guān)鍵就在于找到模式串向右“滑動(dòng)的距離”。 若用數(shù)組元素nextj來表示字符tj不匹配時(shí)的滑動(dòng)距離，則nextj的取值滿足以下next函數(shù)的定義： 0 nextj= maxk|1<k<j且t1t2tk-1=tj-k+1t j-k+2t j-1 此集合不空時(shí)，取相等串中最長(zhǎng)字串 1 其他情況 KMP算法實(shí)現(xiàn)KMP算法是在求得模式串的next函數(shù)值的基礎(chǔ)上執(zhí)行的，next函數(shù)值僅依賴于模式T本身，而和主串S無關(guān)。由中next函數(shù)的定義實(shí)現(xiàn)可得到模式串a(chǎn)bcaabb

12、abcab的next函數(shù)值，如表2-1所示。表2-1  模式串a(chǎn)bcaabbabcab的next函數(shù)值j123456789101112模式abcaabba bcabnextj011122312345KMP算法如算法2-2所示，在形式上和算法2-1極為類似。假設(shè)模式串 T1m中前 q 個(gè)字符已經(jīng)匹配了主串 Sss+q-1，那我們就可以避免一些重復(fù)匹配。找出最大的 k 使得 T1k=T(q-k+1)q，從而計(jì)算出 s使得 T1k=Sss+k-1.其中 s，+k-1=s+q-1?！舅惴枋觥縤nt Index_KMP(SString S, SString T, int pos)int i,

13、 j;i=pos; j=1;while (i<=S0&&j<=T0)if (j=0|Si= Tj) +i; +j; else j = nextj;if j>T0) return(i- T0);else return 0;算法2-2 KMP模式匹配KMP算法最大限度的利用先前已經(jīng)匹配成功的部分模式串，減少比較的次數(shù)，過濾掉那些多余的比較，進(jìn)行最大限度的向前跳躍，再繼續(xù)進(jìn)行比較，從而提高模式匹配的效率。當(dāng)模式中很少自我匹配的子串時(shí)，運(yùn)行速度比較快，是O(m+n)。其在最壞情況下的運(yùn)行時(shí)間仍然是(n-m+1)m)。 BM算法 BM(Boyer Moore)算法可比K

14、MP算法快上3至5倍。其與樸素匹配算法及KMP算法的不同點(diǎn)是在作Sk+1.k+m與T1.m的匹配測(cè)試時(shí)是從后面往前面掃描，而不是從左到右。與KMP算法的相同點(diǎn)是在得到部分匹配時(shí)充分地利用部分匹配所隱含的、可幫助跳過不必要的測(cè)試、提高算法效率的信息。采用“壞字符”和“好尾綴”的啟發(fā)式技術(shù)來修改s的值。 壞字符思想：當(dāng)匹配發(fā)生在tj!=si時(shí)，且如果si不出現(xiàn)在模式串T中，則將模式串右移至ti右端再開始重新匹配。 如果ti在模式串T中有若干出現(xiàn)， 則將模式中的tj右移至模式串T中最后出現(xiàn)的位置。 具體的算法2-3如下：【算法描述】Bad_string(SString T, int m, int o

15、cc) ()      char a;int j;for (a=0; a<=m; a+)  occa=-1;for (j=0; j<=m; j+)       a= Tj;occa=j;算法2-3 壞字符匹配好尾綴思想：當(dāng)模式串T的后面k位和主串S中一致的部分有部分在T中其他部分出現(xiàn)，則可以將T向右移動(dòng)直至這一部分與要求一致的部分盡可能長(zhǎng)。其基本算法和KMP中的 next比較相似，不作說明。 BM算法在最好的情況下時(shí)間復(fù)雜度可以達(dá)到O(n/m)

16、。3基于統(tǒng)計(jì)特征的模式匹配算法3.1算法思想在每個(gè)模式串中，各個(gè)字符出現(xiàn)的頻率是不一樣的，同一個(gè)字符出現(xiàn)的位置也是無法預(yù)測(cè)的。我們可以很好的利用這些無法預(yù)測(cè)性，因?yàn)樵绞翘厥?，那就越不容易被匹配成功，這樣，我們?cè)谀Ｊ狡ヅ溥^程中就可以盡早的發(fā)現(xiàn)錯(cuò)誤，盡早的調(diào)整匹配方案，從而達(dá)到最優(yōu)的匹配結(jié)果。 整個(gè)算法的思想是：利用對(duì)模式的統(tǒng)計(jì)分析，將各個(gè)字符按照出現(xiàn)的頻率、位置排序，出現(xiàn)次數(shù)最少的優(yōu)先級(jí)越高，如果有頻率相同的字符，則按照第一次出現(xiàn)的位置由大向小排。這樣，就建立了一個(gè)新的序列，我們給它起個(gè)名字叫匹配序列。 3.1.1模式中相同字符的處理 針對(duì)模式中的相同字符，需要記錄下同一字符出現(xiàn)位置之間的距離序

17、列。只有當(dāng)某個(gè)字符的所有出現(xiàn)都匹配成功才轉(zhuǎn)向下一個(gè)字符。當(dāng)匹配不成功時(shí)，如果是第一個(gè)就不成功，將文本向后移一位重新匹配；如果是某個(gè)字符的第k次出現(xiàn)匹配不成功，則可以通過類似于KMP中的next方法來獲取該跳過的位置，只是這個(gè)時(shí)候傳給next方法的是某字符的距離序列。也就是說用匹配序列代替模式原來的匹配順序與文本的進(jìn)行匹配。下面以一個(gè)例子來具體的說明。假使在一隨機(jī)模式串為dfdacaijaitopaqay則建立的匹配序列為yqpotjcfiiddaaaaaa如果在主串中，y匹配成功，如下表3-1。表3-1主串a(chǎn)gcfqytmapck模式y(tǒng)原模式中q的位置應(yīng)該在y的前面第二位，而文本中對(duì)應(yīng)的是f,

18、所以此時(shí)匹配不成功，因此文本應(yīng)該向左移動(dòng)后重新開始比較，因?yàn)樽址鹹在模式中僅僅出現(xiàn)一次，而且位置在第17位，所以移動(dòng)后必須要保證文本對(duì)應(yīng)著模式中字符y的位置的前面17個(gè)字符都沒有y，也就是說，可以將文本直接向左移動(dòng)17位。下面考慮更加一般的情況： 原模式中出現(xiàn)字符a的次數(shù)為6，出現(xiàn)的位置依次為：4，6，9，14，16，18 。可以得出字符a的距離序列為：2，3，5，2，2，利用前面KMP算法中的next方法，把字符a的距離序列當(dāng)成是模式，可以算出：next0=0，next1=0，next2=0，next3=1，next4=1；這里的next數(shù)組值的意義和KMP中是next數(shù)組值的意義相同。如果

19、就單單從這個(gè)序列來看，當(dāng)?shù)谌齻€(gè)a不匹配時(shí)，我們就可以簡(jiǎn)單的將文本向左移動(dòng)兩位然后重新進(jìn)行匹配；當(dāng)?shù)诹鶄€(gè)a不匹配時(shí)，將文本向左移動(dòng)10位然后重新進(jìn)行匹配。如果所有a都匹配時(shí)，如果另一個(gè)不同的字符(例如d)不匹配時(shí)，那么至少可以象右移動(dòng)第一個(gè)a和第五個(gè)a之間的距離12。但是，這些僅僅是從字符的序列上來看，還要考慮一個(gè)比較重要的因素：第一個(gè)a在模式中的位置。以上例為主：當(dāng)?shù)谌齻€(gè)a不匹配時(shí)，原本按照next的含義，可以移動(dòng)第一個(gè)a到第二個(gè)a的位置。如下表3-2：模式1為原先模式的位置，模式2，模式3為移動(dòng)后模式的位置。表3-2主串a(chǎn)at模式1dfdacaijaitopaqa模式2dfdacaijait

20、opa模式3dfdacaijai在這里可以發(fā)現(xiàn)，如果這樣移動(dòng)，那么文本中與模式2的第一個(gè)a前面第二位對(duì)應(yīng)的是a，這是不合理的，文本中與模式第一個(gè)a匹配的位置的前三個(gè)字符應(yīng)該都不是a才對(duì)。所以，可以跳過更多的字符，事實(shí)上，模式可以向右移動(dòng)6個(gè)字符(如模式3所示)。也就是說，當(dāng)按照求得的next值去移動(dòng)的同時(shí)，用考慮所移動(dòng)到的位置與前一個(gè)相同字符之間的距離是否大于等于第一個(gè)字符的位置k。那么有必要對(duì)next進(jìn)行修正，即在求nextk時(shí)，要加上一個(gè)條件:第nextk位距離前面一個(gè)相同字符的距離要大于等于k。具體的算法如算法3-1。 【算法描述】Void Next(SString T, int m,

21、int k, int next)int t=0;m=strlen(T);next1=0;for (int q=2; q<=m; q+)while (t!=0)while (t>0&&Tt+1!=Tq)t=nextt;if (Tt+1=Tq&&pt>k)t=t+1;break;else t=nextt;nextq=t;return (next);算法3-1 基于統(tǒng)計(jì)特征的模式匹配同理，對(duì)每個(gè)出現(xiàn)的字符都做一次這樣的運(yùn)算?？梢缘贸霎?dāng)字符的某次出現(xiàn)沒有匹配時(shí)，應(yīng)該移動(dòng)的最大數(shù)。 3.1.2模式中不同的字符的處理 對(duì)于模式中不同的字符，此時(shí)應(yīng)該注意一點(diǎn)

22、，如果該字符不是優(yōu)先級(jí)最高的字符，那么移動(dòng)的位置還應(yīng)該考慮到優(yōu)先級(jí)比它高的字符最多能移動(dòng)的距離，然后取最大值。以上例為主，假使字符y, q的匹配成功，p匹配不成功，對(duì)于q說，至少向右移動(dòng)15位，而對(duì)于y來說至少向右移動(dòng)17位，那么最終移動(dòng)的位置要取最大值17位。 通過上面的例子會(huì)發(fā)現(xiàn)兩個(gè)現(xiàn)象： (1)y匹配成功后，只要模式?jīng)]有完全匹配成功，模式至少可以向右移17位，這種效率在其他算法中是沒有的。 (2)在y右移的17位中，有一些的字符根本就沒有被比較過，也就是說，這個(gè)算法不一定要遍歷所有主串S的字符。 這并不是一個(gè)特例，在實(shí)際運(yùn)用上面，尤其是在模式比較長(zhǎng)的時(shí)候，這種優(yōu)勢(shì)特別明顯。 3.2算法分

23、析 3.2.1算法應(yīng)用舉例在分析算法之前，先看一個(gè)簡(jiǎn)單的例子：串a(chǎn)abaaacaaddacac，在KMP中，每次不匹配可以右移的距離如下：表3-3 表示在某一位字符上不匹配所對(duì)應(yīng)的移動(dòng)的位置aabaaacaaddacac11133347771011111313在本文介紹的算法中，由于是按照新的排序模式進(jìn)行匹配，所以，匹配順序與KMP中的順序不同，每次不匹配時(shí)可以右移的距離如下： 表3-3 表示在某一位字符上不匹配所對(duì)應(yīng)的移動(dòng)的位置bddcccaaaaaaaaa1311111113151515151515151515相比之下可見，按照新的排序模式進(jìn)行匹配的效率極高。此例并非特例，是各種算法的復(fù)雜

24、度進(jìn)行比較所得。算法比較下面就KMP、BM兩種算法和此算法做個(gè)簡(jiǎn)單的比較。（1）KMP算法分析：KMP算法效率最高的時(shí)候應(yīng)該對(duì)于模式串t1t2tm中的任意t1t2tk，都不存在一個(gè)j（1<j<=k），使得t1t2tj=tk-j+1tk；此時(shí)如果在第k位匹配不成功時(shí)，相當(dāng)于可以跳過k-1位，也就是說，每比較一位就可以向后移一位，比較次數(shù)最多為m。 （2）BM算法分析：BM算法如果在最后一位字符就匹配不成功，并且主串S中的那個(gè)字符不在模式中出現(xiàn)，那么也可以向后移n位，但是此時(shí)仍然用主串S中的那個(gè)字符與模式串T比較了n次，因此BM算法的最好情況也是比較m次。 （3）基于統(tǒng)計(jì)特征的模式匹配算法分析：對(duì)于匹配序列中的第一個(gè)字符（即優(yōu)先級(jí)最高的字符），在模式中出現(xiàn)的位置是隨機(jī)的，假使在每個(gè)位置上出現(xiàn)的概率都是相同的。對(duì)于長(zhǎng)度為n的模式，匹配序列中第一個(gè)字符出現(xiàn)在第i位的概率為1/n，所以該字符出現(xiàn)位置的平均值為：pos=（1+2+3+n）/n=(n+1)/2。所以當(dāng)匹配序列中任一字符匹配不成功時(shí)跳過的位置d應(yīng)該是：d>=(n+1)/2；在模式匹配過程中，假設(shè)在任一位匹配不成功的概率相等，則在第i位匹配不成功的概率為p=1/n，移動(dòng)的位數(shù)為d>=(n+1)/2。所以每比較一位移動(dòng)的位數(shù)為pos=