李莉

（福州職業(yè)技術(shù)學(xué)院信息技術(shù)工程系，福州 350100）

0 引言

在當(dāng)今大數(shù)據(jù)時代，數(shù)據(jù)信息量在迅速膨大，如何快速準(zhǔn)確地找到特定的信息是大數(shù)據(jù)領(lǐng)域研究的重點。不管是生物信息領(lǐng)域、航海領(lǐng)域、金融領(lǐng)域、文學(xué)領(lǐng)域還是計算機領(lǐng)域，文本都是必不可少的信息組成元素，模式匹配算法不僅應(yīng)用在模式識別領(lǐng)域，也廣泛應(yīng)用于文本挖掘、網(wǎng)絡(luò)入侵檢測系統(tǒng)（NIDS）等領(lǐng)域，所以尋找精確而有效的模式匹配算法已成為研究的焦點之一[1-2]。

本文研究的算法是基于字符比較的單模式匹配算法。BM（Boyer-Moore）算法[3]是經(jīng)典的單模式匹配算法，基于BM算法的改進算法有BMH算法[4]、QS算法[5]、FQS算法[6]等，I_BMH2C算法[7]和QSP算法[8]是基于QS算法提出的兩種改進算法。本文在QS算法基礎(chǔ)上提出一種新的改進算法 QS_I（QS Improvement）算法，并將QS_I算法與QS算法、I_BMH2C算法和QSP算法的性能做了對比，理論與實驗均證明QS_I算法的性能均高于 QS、I_BMH2C、QSP 算法。

1 相關(guān)算法分析

本文中的文本以T=T[0...n-1]表示，長度為n；模式串以P=P[0...m-1]表示，長度為m；且滿足條件n>=m。按照單模式匹配算法的定義，找出文本T中所有匹配的模式串P的起始位置j:T[j]=P[0],T[j+1]=P[1]......T[j+m-1]=P[m-1]。

1.1 QS算法

Horspool在1980年提出改進與簡化BM算法BMH算法[4]，1990年Sunday在BMH算法的基礎(chǔ)上提出新的改進算法BMHS算法，簡稱QS算法[5]。QS算法的改進思路：預(yù)處理部分只引用壞字符跳躍規(guī)則進行匹配，在當(dāng)前匹配窗口出現(xiàn)不匹配時，模式串必然右移，末字符的下一字符（T[j+m]）是下次匹配窗口的處理對象，使用字符T[j+m]決定模式串當(dāng)前的右移量，若字符T[j+m]未在模式P中出現(xiàn)時，窗口右移量為m+1，大于BM算法的最大右移量m。QS算法預(yù)處理部分的壞字符規(guī)則略有改進，公式如下：

以文本串T=“DCBDADBCDBDCCADCCBADACDC”和模式串P=“CBADACDC”為例，匹配過程如表1所示。預(yù)處理后得到數(shù)組QBCp的值為：QBCp[A,B,C,D]=[4,7,1,2]。

表1 QS匹配過程

1.2 I_BMH 2 C算法和QSP算法

2014年王艷霞在BMH2C算法[9]的基礎(chǔ)上提出一種改進算法——I_BMH2C算法[7]，BMH2C算法使用末字符（T[j+m-1]）和下一字符（T[j+m]）兩個字符作為子串來決定右移量，但BMH2C算法并沒有考慮雙字符在模式串中重復(fù)出現(xiàn)的情況。I_BMH2C算法的改進思路：分析雙字符在模式串中出現(xiàn)0次、1次和1次以上三種情況，利用兩個右移數(shù)組和一個模式串預(yù)處理數(shù)組，在匹配過程中通過判斷字符T[k+2]與模式串預(yù)處理數(shù)組中相應(yīng)字符是否相等，再選擇右移數(shù)組之一的對應(yīng)值作為當(dāng)前窗口的右移量[9]。

2016年LI結(jié)合BMH2C算法和I_BMH2C算法的不足之處，提出一種改進算法——QSP算法[8]，QSP算法預(yù)處理部分只從單字符的角度進行考慮，找出模式串中出現(xiàn)1次以上的單字符，計算出這些字符的跳轉(zhuǎn)期望值差，得到最大差值和相應(yīng)字符P[maxPos]，并修改第二跳轉(zhuǎn)數(shù)組的值；在匹配部分先比較P[maxPos]和T[j+maxPos]，再選擇相應(yīng)的跳轉(zhuǎn)數(shù)組進行右移。

I_BMH2C算法分析T[j+m-1]和T[j+m]雙子字符和T[k+2]字符，在預(yù)處理部分計算復(fù)雜度高，雙字符在模式串中出現(xiàn)1次以上的情況比單字符重復(fù)出現(xiàn)的概率低，每次右移量并不能最大優(yōu)化，QSP算法的運行效率明顯高于I_BMH2C算法。QSP算法在匹配階段，先只匹配P[maxPos]和T[j+maxPos]，不是與文本一一進行比較，在相等的情況下，ESi的值如果大于QS預(yù)處理規(guī)則的距離，窗口的右移量將得到提升，但QSP算法窗口最大右移量只為m+1，與QS算法的最大右移量一致，QSP算法的最壞時間復(fù)雜度為O(n*m),最好的時間復(fù)雜度為O(n/m)。綜上所述，以上兩種改進算法都有待進一步提升[10-11]。

2 QS_I算法

2.1 QS_I算法思路

QSP算法的運行效率比QS算法好，但QSP算法的最大右移量只為m+1，具有一定的局限性。本文結(jié)合QSP算法的不足之處，提出一種新的改進算法QS_I算法，QS_I算法是基于模式串單字符的QS改進算法，它的改進之處在于預(yù)處理考慮模式串中重復(fù)出現(xiàn)的單字符，計算出所有單字符距離前部分最近出現(xiàn)同樣字符的距離，獲取距離最遠的單字符p[pfi]（下文用P_WORD表示）、此字符在模式串中的位置pfi值和模式串初步右移量SHIFT_1，在匹配階段只用模式串的單字符P_WORD與相應(yīng)的文本字符（T[j+pfi]）進行對比，兩字符不匹配，預(yù)測模式串初步移動SHIFT_1距離后模式串和文本依舊不匹配，再根據(jù)跳轉(zhuǎn)數(shù)組shift決定模式串第二次右移的距離為shift[s[j+SHIFT_1+m]，QS_I算法的最大右移量為m+1+SHIFT_1，大于QSP算法。

QS_I算法分為預(yù)處理階段和匹配階段兩部分，QS_I算法的流程圖如圖1：

圖1 QS_I算法流程圖

2.2 預(yù)處理階段

QS_I算法的預(yù)處理部分結(jié)合QS算法的預(yù)處理，并作相應(yīng)的改進，預(yù)處理部分得到的是距離最遠的單字符P_WORD的位置pfi值、模式串初步右移量SHIFT_1和shift數(shù)組。shift數(shù)組仍采用QS算法的預(yù)處理規(guī)則(公式1)，shift數(shù)組在QS_I算法中的作用是計算模式串末字符對應(yīng)文本位置的下一個字符的跳轉(zhuǎn)距離；QS_I算法預(yù)處理的改進部分體現(xiàn)在得到P_WORD值的過程中，整體分析模式串，計算出所有單字符距離前期最近出現(xiàn)同樣字符的距離，比較得出最大的距離SHIFT_1值和單字符P_WORD的位置pfi值。預(yù)處理部分算法的時間復(fù)雜度為O(m*m)。

預(yù)處理過程的主要改進偽代碼如下：

int ds=-1,SHIFT_1=0,flag=0;

int pfi=m-1;//默認是模式串的末字符

for(i=1;i

{

for(j=0;j

{

if(x[j]==x[i])//找最右邊出現(xiàn)的同樣字符

{

ds=i-j;//計算單字符距離前部分最近出現(xiàn)同樣字符的距離

}

}

if(ds>=SHIFT_1)//比較得出最大的距離SHIFT_1值和單字符P_WORD的位置pfi值

{SHIFT_1=ds;

flag=1;

pfi=i;

}

ds=-1;//重置ds

}

同樣以模式串P=“CBADACDC”為例,引用公式（1）計算得出shift數(shù)組的值為：shift[A,B,C,D]=[4,7,1,2]。引用上面的偽代碼進行計算，得出相應(yīng)的值為P_WORD=P[5]='C'，pfi=5,SHIFT_1=5-0=5,計算過程如表2所示：

表2 QS_I預(yù)處理過程

2.3 匹配階段

QS_I算法的匹配階段分為兩個步驟，具體核心代碼如下：

int SHIFT_1=preQs_IBc(p,m);//計算模式串初步的右移量

char PM_WORD=p[pfi];//模式串中間字符

while(j

{

//1.模式串的單字符P_WORD與相應(yīng)的文本字符

（T[j+pfi]）不相等

while(T[j+pfi]!=P_WORD)

{

//指針j右移距離=初步的移動距離+再次的右移量

j=j+SHIFT_1+shift[T[j+SHIFT_1+m]];

if(j>n-m)

{

return

}

}

//2.兩字符若相等，則引用QS算法匹配過程

compare P[0…,m-1]and T[j,…j+m-1]

if all matched then do

output j

end if

j=j+shift1[T[j+m]];//指針j的距離直接引用QS算法規(guī)則計算

}

匹配階段的改進思路：先直接比較模式串單字符P_WORD與相對應(yīng)的文本字符T[j+pfi]，若兩字符不等，且字符P_WORD距離左邊SHIFT_1的距離又重復(fù)出現(xiàn)，那么模式串移動SHIFT_1后，模式串顯然不匹配當(dāng)前對應(yīng)的文本字符串，再引用shift數(shù)組，計算相對應(yīng)的文本下一字符(T[j+SHIFT_1+m])的右移量SHIFT_2（shift[T[j+SHIFT_1+m]]），指針j跳轉(zhuǎn)距離為SHIFT_1+SHIFT_2；單字符P_WORD沒有在模式串前部分出現(xiàn)過，SHIFT_1=0，SHIFT_2=T[j+SHIFT_1+m]=T[j+m]，表示直接引用QS規(guī)則進行右移。若兩字符相等，說明在當(dāng)前指針j位置，存在全匹配的可能性，再進行一一比較。

在匹配過程中，QS_I算法的最壞搜索時間復(fù)雜度為O(m*n)，最好時間復(fù)雜度為O(m/n)[12]。

同樣以文本串 T=“DCBDADBCDBDCCADCCBA?DACDC”和模式串P=“CBADACDC”為例，預(yù)處理后得到的值為 pfi=5，P_WORD='C'，SHIFT_1=5，數(shù)組 shift的值為：shift[A,B,C,D]=[4,7,1,2]。

匹配過程如表3所示。

表3 QS_I匹配過程

如表3所示，在第一次匹配窗口中，文本指針j=0,因為 P[5]≠T[0+5]即'D'!='C'，所以 j=j+SHIFT_1+shift[T[j+SHIFT_1+m]]=0+5+shift[T[13]]=5+4=9;在第二次匹配窗口中，P[5]≠T[9+5]，j=9+5+shift[9+5+8]=14+2=16；在第三次匹配窗口中，P[5]=T[16+5]，則進入搜索全匹配模式串階段，并找到一個全匹配模式串P，輸出當(dāng)前指針j=16。

QSP算法的匹配過程如表4所示：

表4 QSP匹配過程

圖2 bible文本運行時間圖

從表1、表3、表4可以看出，QS算法、QSP算法和QS_I算法的匹配窗口次數(shù)分別是6次、5次和3次，QS_I算法的比較窗口次數(shù)明顯低于QS算法和QSP算法的窗口次數(shù)。通過以下的實驗證明QS_I算法的匹配效率確實高于QS算法和QSP算法。

3 實驗結(jié)果

本文針對QS算法、I_BMH2C算法、QSP算法和QS_I算法進行對比實驗分析。算法是在Visual C++6.0編譯器上實現(xiàn)，并運行在CPU為Intel 2.30GHz，內(nèi)存為4GB的計算機上，算法采用C語言實現(xiàn)。

本文實驗的文本是bible.txt和100M128.txt，bible.txt文本來源于坎特伯雷語料（http://corpus.canterbury.ac.nz/），字符集大小分別為 63，100M128.txt是隨機生成的100MB大小的文本，字符集大小為128。實驗隨機構(gòu)建長度為m(5<=m<=50)模式串，長度間隔為5，每組測試的次數(shù)為10次取平均值，執(zhí)行上述算法程序，統(tǒng)計出模式串不同長度時各算法的運行時間。

四種算法的運行時間圖如下：

圖3 100M文本運行時間圖

從圖2和圖3的運行時間圖可以看出，在字符集不大于128時，QS_I算法的運行時間明顯低于QS算法、I_BMH2C算法和QSP算法，說明在此區(qū)域中，QS_I算法窗口平均右移量高于其他三個算法。QS_I算法預(yù)處理和匹配階段的計算復(fù)雜度比I_BMH2C算法和QSP算法簡單，在匹配階段先只用模式串單字符P_WORD和文本字符T[j+pfi]進行比較，若不匹配可右移SHIFT_1+SHIFT_2兩步，若兩字符相等再引用QS匹配規(guī)則，所以QS_I算法的最大右移量為m+1+SHIFT_1。

4 結(jié)語

本文通過分析QS算法、I_BMH2C算法、QSP算法,并在QS算法的基礎(chǔ)上提出一種改進算法——QS_I算法，QS_I算法不僅用單字符考慮當(dāng)前窗口不匹配的可能性，還預(yù)測下次窗口移動的距離，模式串最大右移量為m+1+SHIFT_1，通過實驗證明在字符集不大于128時，QS_I算法的運行效率明顯高于其他算法。綜上所述，QS_I算法提高了匹配效率，具有一定的應(yīng)用前景。