Horspool擴(kuò)展算法在方塊苗文模式匹配中的應(yīng)用*

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

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

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

1 Horspool算法

1.1 算法原理

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

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

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

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

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

1.2 算法分析

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

1.3 算法示例

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

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

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

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

2 方塊苗文及其字符串查找的特點(diǎn)

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

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

3.1 擴(kuò)展算法的基本原理

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

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

3.2 擴(kuò)展算法應(yīng)用于方塊苗文字符串模式匹配的示例

假設(shè)當(dāng)前待處理的方塊苗文文本T和方塊苗文模式串P分別為

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

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

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

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

4 方塊苗文模式串匹配實(shí)驗(yàn)

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

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

表3 方塊苗文模式串匹配實(shí)驗(yàn)結(jié)果

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

表4 不同長(zhǎng)度模式串匹配的正確率及所耗費(fèi)時(shí)間

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

5 結(jié)語

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