曾 磊，莫禮平，劉筆余，唐澳斌，莫春望，尹 娟

(吉首大學信息科學與工程學院，湖南 吉首 416000)

模式匹配用于解決從目標文本中查找給定模式串的問題，目前廣泛應用于信息檢索、模式識別、事件檢測、生物計算等領(lǐng)域.假設待處理文本為T[0:n-1](長度為n的目標文本)，給定子串為P[0:m-1](長度為m的模式)，那么從T中找出與P相同的所有子串的問題就是模式匹配問題[1-2].模式匹配可以分為單模式匹配和多模式匹配.單模式匹配是從文本T中查找一個模式P，多模式匹配則是從文本T中一次性查找多個模式串P1，P2…，Pq.英文字符串的單模式匹配是最常見的字符串匹配問題，可用線性或亞線性的KMP，BM和Horspool算法等高效的模式匹配算法來解決.KMP算法[3]是一種消除了樸素模式匹配算法中的回溯問題的前綴匹配算法，該算法屬于穩(wěn)定算法，即使在最壞情況下也能保持線性查找過程，其時間復雜度為O(n+m)[3-4].BM算法[5]是一種后綴匹配算法，采用從右向左比較字符和從左向右“跳躍式”移動模式串的方法，同時應用2種啟發(fā)式規(guī)則(壞字符規(guī)則和好后綴規(guī)則)計算移動量，并從中選擇最大值來決定模式串向右跳躍的距離[5].該算法又屬于貪心算法，其時間復雜度在平均、最壞和最優(yōu)3種情況下分別為O(n)，O(m×n)和O(n/m).在實際應用中，其性能優(yōu)于KMP算法3～5倍[6].BM算法被提出以后，中外學者針對此算法進行了優(yōu)化，提出了許多基于BM的改進算法[7-13]，Horspool算法便是其中最有效的算法之一.Horspool算法以BM算法為基礎(chǔ)，但僅利用BM算法的壞字符規(guī)則來計算模式串的移動量，固定將匹配窗口的最后1個字符作為壞字符.筆者以Horspool算法為基礎(chǔ)，對Horspool算法所處理的字符單位進行擴展，設計了一種適用于方塊苗文信息檢索的字符串模式匹配算法.

1 Horspool算法

1.1 算法原理

圖1 Horspool算法原理Fig. 1 Schematic Diagram of Principle of Horspool Algorithm

為描述方便，將待處理文本T中用于與模式串P進行匹配的文本子串(匹配窗口)記為T[i],…,T[i+m-1](i為子串的起始位置，0≤i≤n-m),T[i+j]和P[j]分別表示文本串和模式串中的當前處理字符(0≤j≤m-1).Horspool算法的基本思想是取匹配窗口的最后一個字符T[i+m-1]為壞字符，將其與模式串的最后一個字符P[m-1]進行比較.如果匹配，就繼續(xù)從右向左對T和P中的字符逐個進行比較，直到完全相等或者在某個字符處不匹配為止；如果不匹配,就以T[i+m-1]為壞字符，找到壞字符在P中出現(xiàn)的最后位置k(-1≤k≤m-2)，將P右移，使T[i+m-1]和P[k]對齊后進行再次匹配.

為了實現(xiàn)模式串的移動，須事先記錄各個字符在P中出現(xiàn)的最后位置k及其到P[m-1]的距離.該距離記為Shift[P[k]]，表示以T[i+m-1]為壞字符時P的移動量，

Shift[P[k]]=m-1-k-1≤k≤m-2.

當k=-1時，表示當前字符不出現(xiàn)在模式串中，模式串的移動量為m.Horspool算法原理如圖1所示.

1.2 算法分析

Horspool算法同BM算法一樣，在平均、最壞和最優(yōu)3種情況下時間復雜度分別為O(n)，O(m×n)和O(n/m).因為Horspool算法僅使用壞字符規(guī)則來計算模式串的移動量，避免了BM算法使用好字符規(guī)則來計算模式串移動量和選擇移動量最大值的工作，所以在實際應用中Horspool算法的效率要高于BM算法[10].

1.3 算法示例

假設當前待處理匹配串T為“abcbcsdLinac-codcbcac”，模式串P為“cbcac”，匹配串長度為21，模式串長度為5.表1給出了T中各個字符在P中出現(xiàn)的最后位置，以及根據(jù)Horspool算法得到的P的移動量Shift.

Horspool算法應用于英文字符串匹配的過程如圖2所示.圖2a可知，匹配窗口在位置3處出現(xiàn)不匹配，壞字符“c”對應Shift為2，故將模式串向右移動2個位置.由圖2b可知，匹配窗口在位置4處出現(xiàn)不匹配，壞字符“d”對應Shift為5，故將模式串向右移動5個位置.由圖2c可知，匹配窗口在位置2處出現(xiàn)不匹配，壞字符“c”對應Shift為2，故將模式串向右移動2個位置.由圖2d可知，匹配窗口在位置3處出現(xiàn)不匹配，壞字符“c”對應Shift為2，故將模式串向右移動2個位置.由圖2e可知，匹配窗口在位置4處出現(xiàn)不匹配，壞字符“d”對應Shift為5，故將模式串向右移動5個位置.由圖2f可知，主串匹配窗口和模式串完全相等，模式串查找成功.

表1 T 中各英文字符在P 中出現(xiàn)的最后位置及P 的移動量

圖2 英文字符串匹配過程示例Fig. 2 Example of English String Matching Process

2 方塊苗文及其字符串查找的特點

方塊苗文是一種仿漢字結(jié)構(gòu)的方塊文字，幾乎全是合體字.它以假借漢字為主，創(chuàng)造性地運用了形聲、會意、假借、象形等手段進行造字，直接取一些易認和易記的漢字、漢字部首和極個別無音無義的純粹符號(如“～”“X”)作為義符、聲符或形符構(gòu)件，采用一字一音節(jié)的方法來標記1個語素或詞.[14-16]根據(jù)構(gòu)字方式，方塊苗文的1個字就代表1個語素或詞.實際應用中，方塊苗文的詞以單字詞和雙字詞為主，有少量的3～5字詞，5字詞及以上的極少出現(xiàn).此外，據(jù)已收集的資料可知，方塊苗文通常出現(xiàn)在以漢字為主體的苗文歌本和劇本中，并與漢字混合出現(xiàn).方塊苗文字符串匹配主要是從苗漢混合文本中查找一個有意義的方塊苗文字符串.相對于英文單詞，方塊苗文字符串重復出現(xiàn)在苗漢混合文本中的概率非常低，因此模式匹配時，匹配窗口中的字符串子串包含方塊苗文且這些苗文正好出現(xiàn)在模式串中的概率很低，匹配失敗的次數(shù)遠遠多于匹配成功的次數(shù).一般將某種語言包含的所有文字的集合稱為該語言的字母表，1個文字就是1個字符.如果將收集到的所有方塊苗文組成的集合視為字母表，那么每個方塊苗文都是1個字符.目前已收集到的方塊苗文超過1 000個，相對于英文26個字母而言，方塊苗文是大字母表環(huán)境.大字母表環(huán)境中，字母表中字符的重復度遠比英文單詞中字母的重復度低，有利于產(chǎn)生更大的模式串移動距離.Horspool算法適用于大字母表環(huán)境，顯然，將Horspool算法用于解決方塊苗文的字符串查找問題是合適的.

3 適用于方塊苗文模式匹配的Horspool擴展算法

3.1 擴展算法的基本原理

根據(jù)方塊苗文字符串查找的特點可知，將Horspool算法應用于方塊苗文字符串匹配能夠產(chǎn)生較大的模式串移動距離，從而有效提高匹配速度.然而，方塊苗文采用Unicode格式進行編碼，同漢字一樣，1個方塊苗字由2個字節(jié)組成.若把方塊苗文按單字節(jié)處理，則因字母表最大為256而導致文本中的重復度大大提高，單字節(jié)匹配成功的概率加大.此時采用Horspool優(yōu)化算法不但沒有優(yōu)勢，而且可能出現(xiàn)假匹配情況.因此，將Horspool算法應用于方塊苗文字符串匹配時，需要對算法進行調(diào)整.

筆者使用最簡單的方法對算法進行調(diào)整，即直接將模式匹配中的字符概念擴展到字，把苗文的2個字節(jié)作為一個整體進行處理，只有2個字節(jié)完全相等時才視作1個苗字匹配.因此，根據(jù)方塊苗文字符串匹配的實際需要，在編程實現(xiàn)Horspool算法時，可直接將模式串P和文本串T的類型定義由char*改為word*，并將字符的比較和移動都改為以字為單位.計算機對char和word類型數(shù)據(jù)的處理時間相同，故Horspool擴展算法的時間復雜度保持不變.

3.2 擴展算法應用于方塊苗文字符串模式匹配的示例

假設當前待處理的方塊苗文文本T和方塊苗文模式串P分別為

表2給出了T中各個字符在P中出現(xiàn)的最后位置以及根據(jù)Horspool擴展算法得到的P的移動量Shift.

表2 T 中各方塊苗文字符在P 中出現(xiàn)的最后位置及P 的移動量

Horspool擴展算法應用于方塊苗文字符串匹配的過程如圖3所示.由圖3a可知，匹配窗口在P[1]處出現(xiàn)不匹配，壞字符T[i+5]對應Shift為4，故將P右移4個位置；由圖3b可知，匹配窗口在P[5]處出現(xiàn)不匹配，壞字符T[i+5]對應Shift為1，故將P右移1個位置；由圖3c可知，匹配窗口在P[3]處出現(xiàn)不匹配，壞字符T[i+5]對應Shift為4，故將P右移4個位置；由圖3d可知，匹配窗口在P[5]處出現(xiàn)不匹配，壞字符T[i+5]對應Shift為2，故將P右動2個位置；由圖3e可知，主串匹配窗口和模式串完全相等，模式串查找成功.

圖3 方塊苗文字符串匹配過程示例Fig. 3 Example of a Square Hmong Characters String Matching Process

4 方塊苗文模式串匹配實驗

為了測試算法的性能，選用3段長度分別為8 728，34 079，147 380字的苗漢混合文本作為測試文本T1，T2和T3，針對文本中出現(xiàn)的單字詞、雙字詞、3字詞、4字詞和5字詞這5種情況進行方塊苗文字符串的模式匹配實驗.實驗中選擇單字、雙字及多字詞模式串的原則為模式串在已收集到的苗漢混合真實文本中均具有一定的出現(xiàn)頻率.

在Intel(R) Core(TM) i5-3470 CPU @ 3.20 GHz，4G內(nèi)存，Win7操作系統(tǒng)條件下進行實驗，用C++編程實現(xiàn)算法.針對5種情況分別取10個模式串，進行1 500次實驗，實驗結(jié)果列于表3.表3中TextNo，PatternLen，PatternNum，AvgOccurNum，AvgSucMatNum，AvgCompNum，AvgShiftNum和AvgTime，分別表示測試文本編號、模式串長度(對應方塊苗文的詞類型)、模式串測試個數(shù)、模式串出現(xiàn)次數(shù)的平均值、模式串成功匹配次數(shù)的平均值、模式串字符比較次數(shù)的平均值、模式串移動次數(shù)的平均值和模式串匹配所耗費時間的平均值.

表3 方塊苗文模式串匹配實驗結(jié)果

根據(jù)表3中的實驗結(jié)果，結(jié)合測試文本T1，T2和T3的文本長度之比，對不同長度模式串進行匹配的正確率及所耗費時間進行比較，結(jié)果列于表4.表4中CompTextNo，TextLengthRate，AccuracyRate，TimeRate和AvgTimeRate，分別表示對比文本編號、文本長度比率、匹配正確率、匹配所耗費時間比率和匹配所耗費平均時間比率.

表4 不同長度模式串匹配的正確率及所耗費時間

由表4可知：對3個測試文本中出現(xiàn)的5種長度模式串進行方塊苗文字符串模式匹配，Horspool擴展算法均保證了100%的正確匹配率；對應于T1/T2，T1/T3，T2/T3的文本長度之比24.290 6%，5.616 8%和23.123 2%，5種長度模式串所耗費的匹配時間的平均值之比為23.868 2%，5.345 5%和22.396 0%.此結(jié)果表明，不同長度字詞的模式串，匹配所耗費的時間與測試文本長度均呈線性關(guān)系，且耗費時間的降低率快于測試文本長度的增長率.從上述實驗數(shù)據(jù)還可以看出，即使是在10萬字以上的苗漢混合文本中進行單字詞、雙字詞和多字詞的方塊苗文字符串模式匹配，Horspool擴展算法的性能也能得到較好的發(fā)揮.

5 結(jié)語

當今信息時代，隨著計算機及網(wǎng)絡技術(shù)的不斷發(fā)展，人們對文本檢索效率提出了更高的要求.方塊苗文字符串匹配算法是實現(xiàn)方塊苗文信息快速檢索的關(guān)鍵.結(jié)合方塊苗文信息的查找特點和存儲格式提出高效率的方塊苗文字符串匹配算法，對方塊苗文的信息化具有很好的理論意義和現(xiàn)實價值.筆者提出的Horspool擴展算法具有思想簡單、容易實現(xiàn)的特點.方塊苗文字符串的匹配實驗數(shù)據(jù)表明，Horspool擴展算法能夠成功應用于方塊苗文字符串的模式匹配.下一步擬以該算法為基礎(chǔ)，將其與DFA和Petri網(wǎng)建模技術(shù)相結(jié)合，研究方塊苗文多模式匹配算法及其優(yōu)化技術(shù)，以解決苗漢混合文本中方塊苗文的并行檢索問題.