葉 煜

(成都農(nóng)業(yè)科技職業(yè)學(xué)院電子信息分院,四川成都 611130)

0 引 言

模式匹配(Pattern Matching)問題是計算機相關(guān)領(lǐng)域中的一個基本問題,也是復(fù)雜性理論中研究得最廣泛的問題之一,其在文字編輯處理、圖像處理、文獻檢索、自然語言識別、入侵檢測等領(lǐng)域有著廣泛的應(yīng)用.所謂模式匹配,是指給定一個長為n的文本串T[1,n]和長為m的模式串P[1,m],找出文本串T中與模式串P精確匹配的子串的起始位置.好的模式匹配算法能顯著地提高模式匹配的效率,因此,研究并設(shè)計快速的模式匹配算法具有重要的理論價值和實際意義.

1 算法與分析

目前,模式匹配算法在進行搜索實踐時,最有影響的算法是K MP算法[1]和BM算法[2].

1.1 K MP算法

K MP算法由Knuth等于1977年提出,其基本思想是:采用從左向右比較的方法,設(shè)計一個與模式串本身局部匹配信息構(gòu)造的模式值數(shù)組next,當(dāng)匹配過程中出現(xiàn)失配時,利用模式值,將模式串向右“滑動”盡可能遠的一段距離,使文本串的指針在匹配過程中不用回溯,保證文本串中每個字符只進行一次比較,從而提高模式匹配的效率.K MP算法的時間復(fù)雜度為O(n).

1.2 BM算法

BM算法由Boyer等于1977年提出的,其基本思想是:采用從右向左比較的方法,它包含兩個并行的規(guī)則,壞字符規(guī)則和好后綴規(guī)則,當(dāng)出現(xiàn)不匹配字符時,通過查詢預(yù)處理好的壞字符移動表與好后綴移動表,選擇移動距離較大值向后移動模式串,再進行下一輪匹配嘗試.BM算法預(yù)處理階段時間復(fù)雜度為O(m+s),s為與模式串P和文本串T相關(guān)的有限字符集長度,搜索階段的最優(yōu)時間復(fù)雜度為O(n/ m),最差時間復(fù)雜度為O(mn).

1.3 算法分析

在實際應(yīng)用中,BM算法的搜索效率遠遠優(yōu)于K MP算法,但由于BM算法的壞字符規(guī)則所需的壞字符表與所使用的字符集有關(guān).通常,英文的字符集較小,建立壞字符表所需的時間、空間都比較少,而中文字符集非常巨大,要建立壞字符表不太現(xiàn)實,因此,高效率的BM算法并不適合于中文搜索.

此外,為提高字符串模式匹配效率,研究人員在K MP與BM算法的基礎(chǔ)上提出了相應(yīng)的改進算法[3-8].各種改進算法的目的都在于盡量減少匹配過程中的比較次數(shù),且當(dāng)模式串與文本串發(fā)生失配時模式串能夠向右移動盡可能大的距離,以減少不必要的比較.但這些算法都是單向比較,缺乏優(yōu)先考慮,而且改進算法在匹配過程中還會出現(xiàn),模式串的首字符與文本串相匹配,而尾字符與文本串不匹配,或模式串的尾字符與文本串相匹配,而首字符與文本串不匹配等情況,這就導(dǎo)致了較多不必要的比較,降低了匹配的效率.同時,這些改進算法也同樣大都不適用于中文搜索.

2 雙向比較模式匹配算法

針對上述問題,本文提出一種字符串匹配算法的新思路:雙向比較模式匹配算法.在該方法中,利用模式串尾字符建立一個只與模式串自身有關(guān)的特征數(shù)組,這個數(shù)組在匹配過程中只需要記錄下模式串尾字符在模式串前半部分出現(xiàn)的位置.

2.1 雙向比較模式匹配算法的具體思路

雙向比較模式匹配算法的具體思路是:

(1)用模式串P的尾字符與文本串T進行比較,結(jié)果失配,由于漢字是寬字符,所以模式串P右移兩位在新的位置繼續(xù)比較.

(2)用模式串P的尾字符與文本串T進行比較,結(jié)果同配(暫且稱這個字符為同配字符),再把模式串前半部分與文本串比較,當(dāng)所有字符都能匹配上時,則找到字符串返回查找結(jié)果并結(jié)束;如果出現(xiàn)失配,再利用K MP算法的模式值next得到模式串右移的距離,但如果這時開始新一輪的比較,就有可能是無效的,因為已知模式串的尾字符與文本串同配,而模式串移動到這個位置卻并沒能讓文本串中的同配字符與出現(xiàn)在模式串前半部分的同配字符對齊(見圖1).此時,可再向右移動模式串,使兩者的同配字符對齊后再進行比較(見圖2).如果模式串前半部分沒有出現(xiàn)同配字符,就可以完全移過該比較窗口(見圖3).

(3)特征數(shù)組的建立需要在預(yù)處理階段完成,該數(shù)組只與模式串自身有關(guān),記錄的是模式串尾字符在模式串前半部分出現(xiàn)的位置.設(shè)模式串尾字符為b,其計算公式如下:

建立數(shù)組specialArray的算法描述如下:

2.2 雙向比較模式匹配算法

雙向比較匹配算法分為尾字符匹配和前半部分匹配兩部分.假設(shè)在index位置對模式串P尾字符進行匹配,如果失配,將模式串右移兩位在下一個位置進行比較;如果同配,則匹配模式串前半部分,前半部分也同配,字符串找到.當(dāng)前半部分在j位置失配,結(jié)合模式值與特征數(shù)組以獲得最大距離來移動模式串,減少匹配次數(shù).雙向比較模式匹配算法的核心代碼如下:

2.3 雙向比較模式匹配算法時間復(fù)雜度分析

根據(jù)雙向比較模式匹配算法的匹配過程分析可知:在最優(yōu)的情況下,模式串尾字符總是與文本串字符同配,而首字符與文本串失配且尾字符未在模式串前半部分出現(xiàn),使模式串在每次匹配時只比較了兩個字符且失配后右移距離為m個字符,即時間復(fù)雜度為O(2n/m);在最差的情況下,無論模式串哪個字符與文本串字符失配,由于文本串指針不回溯,保證文本串中的每個字符都只會進行一次比較,故最差時間復(fù)雜度為O(n).

3 實 驗

在雙向比較模式匹配算法的匹配實驗中,我們選擇一部1 249 020字的小說,其文本大小是2.4 MB.在該文本中隨機選擇幾個長度依次是63、41、36、27、7、3字的字符序列P1、P2、P3、P4、P5、P6為模式串進行實驗,分別測試了K MP、雙向比較模式匹配算法在查詢命中目標(biāo)過程中的匹配次數(shù)及CPU運行時間.測試環(huán)境為Windows XP,系統(tǒng)配置為AMD CPU 1.9 GHz,內(nèi)存1 G B.實驗結(jié)果如表1所示.

表1 算法實驗結(jié)果

從表1可以看出,在同一個模式串P的查詢過程中,雙向比較模式匹配算法比較次數(shù)和CPU運行時間都遠遠少于K MP.由于雙向比較模式匹配算法所采用的模式值及特征數(shù)組都只與模式串自身有關(guān),所需的輔助空間等于模式串長度,因此,雙向比較模式匹配算法無論時間復(fù)雜度還是空間復(fù)雜度都是較理想的.

4 結(jié) 語

本文提出的雙向比較模式匹配算法,通過建立模式串尾字符的特征數(shù)組,以及尾字符與文本串比較進所獲得的信息,使模式串取得更大的右移距離,大大減少了模式匹配中不必要的比較,提高了匹配的效率.實驗結(jié)果表明,雙向比較模式匹配算法的匹配效率是較理想的.

[1]Knuth D E,Morris JR J H,Pratt V R.Fast Pattern Matching In Strings[J].SIAMJ on Comput,1977,6(2):323-350.

[2]Boyer R S,Moore J S.A Fast String Searching Algorithm[J]. Communications of the ACM,1977,20(10):762-772.

[3]李雪梅,代六玲,童新海,等.一種串匹配的快速Boyer-Moore算法[J].計算機應(yīng)用研究,2005,22(9):49-51.

[4]渠瑜,王亞弟,韓亞紅,等.對BM模式匹配算法的一個改進[J].計算機工程,2006,32(23):78-81.

[5]單懿慧,蔣玉明,田詩源.面向入侵檢測的改進BMHS模式匹配算法[J].計算機工程,2009,35(24):170-173.

[6]俞松,鄭駿,胡文心.一種改進的 K MP算法[J].華東師范大學(xué)學(xué)報(自然科學(xué)版),2009,55(4):92-97.

[7]蔡曉妍,戴冠中,楊黎斌.一種快速的單模式匹配算法[J].計算機應(yīng)用研究,2008,25(1):45-47.

[8]賀龍濤,方濱興,余翔湛.一種時間復(fù)雜度最優(yōu)的精確串匹配算法[J].軟件學(xué)報,2005,16(5):676-683.