適合中文的雙向比較模式匹配算法

葉 煜

(成都農業科技職業學院電子信息分院,四川成都 611130)

0 引 言

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

1 算法與分析

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

1.1 K MP算法

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

1.2 BM算法

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

1.3 算法分析

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

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

2 雙向比較模式匹配算法

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

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

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

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

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

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

建立數組specialArray的算法描述如下:

2.2 雙向比較模式匹配算法

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

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

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

3 實 驗

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

表1 算法實驗結果

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

4 結 語

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

[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].計算機應用研究,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].華東師范大學學報(自然科學版),2009,55(4):92-97.

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

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