一種改進的Sunday模式匹配算法

李映剛

(成都理工大學(xué)管理科學(xué)學(xué)院，成都 610059)

引言

隨著網(wǎng)絡(luò)應(yīng)用范圍的不斷擴大，對實時網(wǎng)絡(luò)信息的快速搜索的要求也與日俱增。字符串匹配在網(wǎng)絡(luò)領(lǐng)域有著廣泛的應(yīng)用，比如，拼寫檢查、語言翻譯、數(shù)據(jù)壓縮、搜索引擎、網(wǎng)絡(luò)入侵檢測、DNA序列匹配等。如何用高效的字符匹配算法解決問題成為目前研究的重要領(lǐng)域之一。

字符串匹配問題的形式化定義是［1-2］:在字符集@上，給定一個長度為N的主字符串T［1…N］，以及一個長度為M的模式串P［1…M］，M＜＜N。如果對于位置S(1＜=S＜=N-M+1)，字符串T［S…S+M-1］與P［1…M］相同，則認定模式串P出現(xiàn)在主串T的S位置。字符串匹配問題就是要尋找P在T中是否出現(xiàn)以及出現(xiàn)的位置。

1 相關(guān)算法簡介

1.1 BF算法

BF(Brute Force)算法是最原始且效率最低的算法。它從主串第一個字符開始逐個與模式串的每個字符相比較是否相同，如果不匹配，然后從主串下一個字符重新與模式串作相同性比較。BF算法原理簡單、易實現(xiàn)，但效率太低。

1.2 KMP算法

KMP(Knuth-Morris-Pratt)［3-4］算法是D.E.Kunth、J.H.Morris和V.R.Pratt等人在1977年提出的。KMP算法在一次匹配失敗后可以利用部分匹配的結(jié)果直接將模式串向右移動盡量遠的距離來進行下一次匹配。KMP算法雖然對BF算法有了很大的改進，但是原理復(fù)雜，不易推廣實現(xiàn)。

1.3 BM算法

BM算法［4-5］是Boyer和Moore提出的一種算法。最主要的特點就是在匹配過程中，可以跳過很多無用的字符，這種跳躍式的匹配可以獲得很高的匹配效率。

1.4 ZZL算法

ZZL算法［6］是紀福建等人提出的一種可用作特殊用途的字符串匹配算法。ZZL算法的核心思想是:首先在主串T中查找模式串P的首字母，每找到一個則將它的位置存儲，然后依次提取這些位置，從這些位置來匹配模式串P。對于頻繁使用的主串和模式串，匹配速度會非?？欤秉c是可能會需要大量的存儲空間來存儲那些頻繁使用的模式串的首字母的位置。

1.5 Sunday算法

Sunday算法［5，7］在匹配過程中并不要求字符比較的方向，在一次匹配完后，利用主串的下一個字符逆序搜索模式串，找到這個字符第一次出現(xiàn)的位置或者不出現(xiàn)。從而達到利用一個字符的遍歷就能決定模式串的后移位置，極大的提高了移動效率。其核心思想就是用較少的字符比較來確定較長的模式串的位移。

一般情況下，BF算法效率最低，KMP算法與BM算法原理復(fù)雜不易實現(xiàn)，Sunday算法原理簡單執(zhí)行速度最快。本文就選取快速的Sunday算法進行改進。Sunday算法有兩個缺點:首先就是對前一次匹配結(jié)果沒有進行有效的利用;其次就是Sunday算法利用主串下一個字符來遍歷模式串的作法也過于簡單。當(dāng)模式串很長的時候(很多實際應(yīng)用中，模式串都比較長)，主串下一個字符在模式串中出現(xiàn)的概率會提高，這樣的出現(xiàn)會增加很多的無效匹配。針對Sunday算法的兩個缺陷，提出了將原理簡單易實現(xiàn)的前一次比較結(jié)果再利用方法與主串下一個字符搜索加強方法相結(jié)合的思想，以此來改進Sunday算法，以期得到更高的匹配效率。

2 改進Sunday算法思路

2.1 前一次比較結(jié)果簡單再利用

得益于BM算法的逆序比較思想，提出一種簡單易理解的逆序比較結(jié)果再利用的算法。

算法描述:將模式字符串P［1…M］與主字符串T［1…N］在一次匹配比較過程中，按照字符串的逆向進行比較。從模式字符串的最后一個字符與主串相應(yīng)位置開始，依次向前比較并最后確定匹配字符的數(shù)目(記為A)。根據(jù)模式串的特性，最后A個字符組成的模式串P的子串(記為SP［A］)，從模式串后面往前遍歷，可以找到的第一個再次出現(xiàn)的子串SP［A］(本身除外)的位置(記為S)，這一過程可以在匹配前作預(yù)處理，作為模式串的特征值記錄下來。如果主串與模式串從后向前最多A個字符相同，那么根據(jù)預(yù)處理的特征值的位置S，就可以不用進行字符比較，而直接決定下一次模式串的移動距離。

例如，模式串為“facdefa”，主串為“ekjacfadbcea……”，進行第一次匹配比較，倒序比較發(fā)現(xiàn)模式串的最后兩個字符“fa”和主串的相應(yīng)位置的字符相同，而“fa”在模式串中倒序再次出現(xiàn)的位置為1，那么可以直接決定模式串在主串中向后移動5步的距離，而不用多余的比較。算法優(yōu)點就是僅僅利用預(yù)處理的結(jié)果就能決定移動步數(shù)，是一種原理簡單易實現(xiàn)的前一次匹配結(jié)果再利用方法。算法缺點就是預(yù)處理數(shù)據(jù)能否有效果要看模式串的最后一個字符在主串中出現(xiàn)的概率，就平均情況而言，這與字符集@的大小有關(guān)。

2.2 增加Sunday算法中的遍歷模式串的字符數(shù)

Sunday算法的核心體現(xiàn)在P與T進行比較確定是否匹配后，用主串下一個字符來遍歷模式串進行比較就能確定模式串下一次右移的距離，僅僅通過增加遍歷模式串的字符數(shù)目，就能極大的提高移動效率。比如增加一個遍歷字符，在進行一次匹配后，用主串后兩個字符來遍歷模式串，進行比較來確定模式串下一次右移的距離。能極大提高移動步數(shù)的原因就是兩個字符的比較不僅僅包含是否相等，還包含了他們之間的位置關(guān)系，位置關(guān)系所包含的信息是不用浪費時間去比較的，但是卻能用來辨別模式串的移動距離。模式串越長Sunday算法的下一個字符在模式串中出現(xiàn)的概率就越大，無效匹配的次數(shù)就越多，由此可以預(yù)見，對于此改進方法，模式串越長，效率越高。

2.3 改進算法的處理過程

(1)模式串預(yù)處理

在進行字符匹配前，先建立一個數(shù)組fea［M-1］，M為模式串字符數(shù)，用于記錄模式串的倒序特征值。

例如，模式串為P=“afkdfk”。那么倒序s個字符在模式串中除自己以外的下一次出現(xiàn)位置就是:

那么fea［5］={3，2，0，0，0}。如果一次倒序匹配中，匹配到的最多字符數(shù)目為s，那么直接決定模式串的下一次位移數(shù)就為D1=M-s+1-fea［s］。

(2)字符倒序匹配

記錄下倒序匹配得到的最大字符數(shù)s，利用位移公式得到下一次位移數(shù)D1。

(3)增加Sunday算法的遍歷模式串字符數(shù)

利用一次字符匹配后的主串的后x個字符來遍歷模式串，思想與Sunday算法是一致的，只有在這x個字符與模式串中的某x個字符完全一致時，才能確定模式串的下一次位移數(shù)，記為D2。

(4)選取D1與D2中較大的一個作為模式串的后移步數(shù)D。

(5)進行下一次字符倒序匹配，重復(fù)(2)。

3 改進算法的性能分析

3.1 性能分析

不考慮對模式串的預(yù)處理過程，統(tǒng)計算法運行過程中總的字符比較次數(shù)，并作為算法的性能指標(biāo)。倒序比較結(jié)果再利用算法的效率與模式串的最后一個字符在主串中出現(xiàn)的概率有關(guān)，出現(xiàn)概率越大，效率越高;通過將遍歷模式串的字符數(shù)增加到x個，那么在模式串中出現(xiàn)這x個字符并且順序一致的情況將大為減少，能提高匹配效率。同時，當(dāng)模式串越長時，兩種思想發(fā)生效果時后移的步數(shù)就越大，效果越好。

3.2 實驗與結(jié)果

為了測試改進算法的性能，先用簡單的數(shù)據(jù)來分析驗證改進算法的效率。假如得到模式串為P={a，k，f，a};主串為T={a，j，f，l，d，s，j，f，s，f，a，d，a，k，f，a…..}。那么當(dāng)模式串在與主串第7個子串進行匹配后，可以直接得到下一次模式串位移數(shù)D1=3;當(dāng)模式串與主串第9個子串進行匹配后，可以直接得到下一次模式串位移數(shù)D1=3。模式串與主串第4個子串匹配后，若采用常規(guī)的Sunday算法，可以得到的下一次模式串位移數(shù)D2=2，但是若采用遍歷字符數(shù)x=2的改進算法，可以得到的下一次模式串位移數(shù)D2=5。可見改進算法效率是有提高的。

現(xiàn)在用電腦隨機生成長度為N的主串，以及長度為M的模式串，匹配到模式串的數(shù)目記為S，遍歷模式串的字符數(shù)x=3。運行并統(tǒng)計相關(guān)算法的總的字符匹配數(shù)目。結(jié)果統(tǒng)計見表1。

表1 五種算法的匹配測試結(jié)果

對表1中的數(shù)據(jù)分析，說明兩種改進思路得到的算法在模式串較短的時候與Sunday算法性能持平，而隨著模式串的增長，效率顯著提升?；谶@兩種思路的改進算法，在模式串長度較大時，效率明顯優(yōu)于Sunday算法。

4 結(jié)束語

改進的Sunday算法在原Sunday算法的基礎(chǔ)上增加了一個模式串的倒序特征值，利用這個預(yù)先得到的特征值可以直接決定下一次的移動步數(shù);同時也增加了主串的遍歷模式串時的字符個數(shù)，減少了很多無效匹配。實驗結(jié)果表明，改進的Sunday算法提高了字符匹配的效率。

[1]曾慧惠，袁世忠，胡 鵬.入侵檢測系統(tǒng)中高效模式匹配算法的研究[J].計算機應(yīng)用于軟件，2008，25(4)：226-227.

[2]徐 珊，袁小坊，王 東，等.Sunday字符串匹配算法的效率改進[J].計算機工程與應(yīng)用，2011，47(29)：96-98，160.

[3]周延森，汪永好.網(wǎng)絡(luò)入侵檢測系統(tǒng)模式匹配算法研究[J].計算機工程與設(shè)計，2008，29(7)：1652-1654，1683.

[4]萬曉榆，楊 波，樊自甫.改進的Sunday模式匹配算法[J].計算機工程，2009，35(7)：125-126，129.

[5]王 成，劉金剛.一種改進的字符串匹配算法[J].計算機工程，2006，32(2)：62-64.

[6]趙俊杰.一種用于關(guān)鍵詞檢索的快速字符串精確匹配算法[J].計算機系統(tǒng)應(yīng)用，2010，19(2)：189-191.

[7]潘冠樺，張興忠.Sunday算法效率分析[J].計算機應(yīng)用，2012，32(11)：3082-3084，3088.