李莉

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

0 引言

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

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

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

本文中的文本以T=T[0...n-1]表示，長(zhǎng)度為n；模式串以P=P[0...m-1]表示，長(zhǎng)度為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年提出改進(jìn)與簡(jiǎn)化BM算法BMH算法[4]，1990年Sunday在BMH算法的基礎(chǔ)上提出新的改進(jìn)算法BMHS算法，簡(jiǎn)稱QS算法[5]。QS算法的改進(jìn)思路：預(yù)處理部分只引用壞字符跳躍規(guī)則進(jìn)行匹配，在當(dāng)前匹配窗口出現(xiàn)不匹配時(shí)，模式串必然右移，末字符的下一字符（T[j+m]）是下次匹配窗口的處理對(duì)象，使用字符T[j+m]決定模式串當(dāng)前的右移量，若字符T[j+m]未在模式P中出現(xiàn)時(shí)，窗口右移量為m+1，大于BM算法的最大右移量m。QS算法預(yù)處理部分的壞字符規(guī)則略有改進(jìn)，公式如下：

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

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

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

2 QS_I算法

2.1 QS_I算法思路

QSP算法的運(yùn)行效率比QS算法好，但QSP算法的最大右移量只為m+1，具有一定的局限性。本文結(jié)合QSP算法的不足之處，提出一種新的改進(jìn)算法QS_I算法，QS_I算法是基于模式串單字符的QS改進(jìn)算法，它的改進(jìn)之處在于預(yù)處理考慮模式串中重復(fù)出現(xiàn)的單字符，計(jì)算出所有單字符距離前部分最近出現(xiàn)同樣字符的距離，獲取距離最遠(yuǎn)的單字符p[pfi]（下文用P_WORD表示）、此字符在模式串中的位置pfi值和模式串初步右移量SHIFT_1，在匹配階段只用模式串的單字符P_WORD與相應(yīng)的文本字符（T[j+pfi]）進(jìn)行對(duì)比，兩字符不匹配，預(yù)測(cè)模式串初步移動(dòng)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)的改進(jìn)，預(yù)處理部分得到的是距離最遠(yuǎn)的單字符P_WORD的位置pfi值、模式串初步右移量SHIFT_1和shift數(shù)組。shift數(shù)組仍采用QS算法的預(yù)處理規(guī)則(公式1)，shift數(shù)組在QS_I算法中的作用是計(jì)算模式串末字符對(duì)應(yīng)文本位置的下一個(gè)字符的跳轉(zhuǎn)距離；QS_I算法預(yù)處理的改進(jìn)部分體現(xiàn)在得到P_WORD值的過程中，整體分析模式串，計(jì)算出所有單字符距離前期最近出現(xiàn)同樣字符的距離，比較得出最大的距離SHIFT_1值和單字符P_WORD的位置pfi值。預(yù)處理部分算法的時(shí)間復(fù)雜度為O(m*m)。

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

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

int pfi=m-1;//默認(rèn)是模式串的末字符

for(i=1;i

{

for(j=0;j

{

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

{

ds=i-j;//計(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）計(jì)算得出shift數(shù)組的值為：shift[A,B,C,D]=[4,7,1,2]。引用上面的偽代碼進(jìn)行計(jì)算，得出相應(yīng)的值為P_WORD=P[5]='C'，pfi=5,SHIFT_1=5-0=5,計(jì)算過程如表2所示：

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

2.3 匹配階段

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

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

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

while(j

{

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

（T[j+pfi]）不相等

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

{

//指針j右移距離=初步的移動(dòng)距離+再次的右移量

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ī)則計(jì)算

}

匹配階段的改進(jìn)思路：先直接比較模式串單字符P_WORD與相對(duì)應(yīng)的文本字符T[j+pfi]，若兩字符不等，且字符P_WORD距離左邊SHIFT_1的距離又重復(fù)出現(xiàn)，那么模式串移動(dòng)SHIFT_1后，模式串顯然不匹配當(dāng)前對(duì)應(yīng)的文本字符串，再引用shift數(shù)組，計(jì)算相對(duì)應(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ī)則進(jìn)行右移。若兩字符相等，說明在當(dāng)前指針j位置，存在全匹配的可能性，再進(jìn)行一一比較。

在匹配過程中，QS_I算法的最壞搜索時(shí)間復(fù)雜度為O(m*n)，最好時(shí)間復(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,因?yàn)?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]，則進(jìn)入搜索全匹配模式串階段，并找到一個(gè)全匹配模式串P，輸出當(dāng)前指針j=16。

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

表4 QSP匹配過程

圖2 bible文本運(yùn)行時(shí)間圖

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

3 實(shí)驗(yàn)結(jié)果

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

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

四種算法的運(yùn)行時(shí)間圖如下：

圖3 100M文本運(yùn)行時(shí)間圖

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

4 結(jié)語

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