李映剛

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

引言

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

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

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

1.1 BF算法

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

1.2 KMP算法

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

1.3 BM算法

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

1.4 ZZL算法

ZZL算法［6］是紀(jì)福建等人提出的一種可用作特殊用途的字符串匹配算法。ZZL算法的核心思想是:首先在主串T中查找模式串P的首字母，每找到一個(gè)則將它的位置存儲(chǔ)，然后依次提取這些位置，從這些位置來(lái)匹配模式串P。對(duì)于頻繁使用的主串和模式串，匹配速度會(huì)非常快，缺點(diǎn)是可能會(huì)需要大量的存儲(chǔ)空間來(lái)存儲(chǔ)那些頻繁使用的模式串的首字母的位置。

1.5 Sunday算法

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

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

2 改進(jìn)Sunday算法思路

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

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

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

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

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

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

2.3 改進(jìn)算法的處理過(guò)程

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

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

例如，模式串為P=“afkdfk”。那么倒序s個(gè)字符在模式串中除自己以外的下一次出現(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個(gè)字符來(lái)遍歷模式串，思想與Sunday算法是一致的，只有在這x個(gè)字符與模式串中的某x個(gè)字符完全一致時(shí)，才能確定模式串的下一次位移數(shù)，記為D2。

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

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

3 改進(jìn)算法的性能分析

3.1 性能分析

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

3.2 實(shí)驗(yàn)與結(jié)果

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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