周延森 張維剛

1(國(guó)際關(guān)系學(xué)院網(wǎng)絡(luò)空間安全學(xué)院 北京 100091) 2(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 山東 威海 264200)

0 引 言

模式匹配算法在搜索引擎、DNA比對(duì)、入侵特征檢測(cè)中得到廣泛的應(yīng)用。根據(jù)每次參與匹配時(shí)模式串?dāng)?shù)量的不同可分為單模和多模匹配算法。單模匹配算法主要有具有線性匹配性能的KMP、BM、BMH、 BMHS和BMHS2，以及字頻和hash等匹配算法；在多模匹配算法性能改進(jìn)方面，除了增大失配時(shí)移動(dòng)距離以及減少每次匹配次數(shù)之外，大幅度減少每次參與匹配模式串?dāng)?shù)量對(duì)算法的影響尤其重要。目前，主流的多模匹配算法主要有AC和WM等算法，其中AC算法是KMP算法在多模式匹配算法中的應(yīng)用，而WM算法是BM算法在多模匹配算法中的應(yīng)用， WM算法的時(shí)間性能優(yōu)于AC算法[1]。

當(dāng)前，每一種模式匹配算法性能的改進(jìn)已經(jīng)遇到一定的瓶頸。為此，需要將各種模式匹配算法進(jìn)行組合，吸取各算法的優(yōu)點(diǎn)，從而能夠以一定幅度提高模式匹配算法的性能[2]?；诖?，本文提出一種新的改進(jìn)WM算法，該算法采用前綴表和后綴表的二次過(guò)濾以及平衡二叉樹(shù)減少了每一次參與匹配的模式串?dāng)?shù)量。為了盡快找到文本串中的失配字符，減少每次匹配字符比較次數(shù)，改進(jìn)算法引入字頻的模式匹配算法。此外，匹配窗口每次匹配失配時(shí)，改進(jìn)算法引入BMHS算法，采用了BMH和BMHS算法中較大的右移距離來(lái)移動(dòng)匹配窗口。

多模式串匹配定義：在給定長(zhǎng)度為n的文本T=T[1]T[2]…T[n]中同時(shí)查找l個(gè)模式串P={P1,P2,…,Pl}的過(guò)程。其中T[i]∈Σ(1≤i≤n)，對(duì)于?p∈Pj(1≤j≤l)，有p∈Σ(Σ為字符集)。若Pj在T中出現(xiàn)，則稱(chēng)Pj匹配成功，否則稱(chēng)Pj匹配失敗。

1 模式串預(yù)處理

假設(shè)字符串為T(mén)=″knowledge is better than money to the human″。模式串為P={blank, fund, minded, hand, than, plan, thread, this, that, think, there, these}。

模式串預(yù)處理階段的主要分為：① 通過(guò)遍歷所有模式串，計(jì)算出最短模式串的長(zhǎng)度，并將該長(zhǎng)度作為文本串匹配窗口的尺寸；② 采用匹配窗口長(zhǎng)度內(nèi)的模式串后綴字符塊對(duì)所有模式串進(jìn)行物理排序，得到一個(gè)模式串的有序序列；③ 為模式串集創(chuàng)建3個(gè)表，分別是字符塊跳躍表Shift、字符塊前綴表Prefix和字符塊后綴表Suffix[3]。

在WM算法中，只使用Suffix后綴表中對(duì)應(yīng)的模式串子集參與文本串匹配，沒(méi)有利用Prefix表進(jìn)行模式串的二次過(guò)濾，因此需要Suffix中后綴相同的所有模式串都參與匹配，匹配性能較差[4]。目前，在主要的WM的改進(jìn)算法中，主要采用基于后綴表和前綴表的二次地址過(guò)濾以及多次hash來(lái)減少每次參與匹配模式串的數(shù)量，如文獻(xiàn)[3]提出的改進(jìn)算法DHSWM。但是，當(dāng)模式串?dāng)?shù)量眾多并且存在大量前綴字符塊相同的模式串時(shí)，還會(huì)有較大數(shù)量的模式串參與每次匹配，匹配時(shí)間性能會(huì)受到較大的影響。針對(duì)文獻(xiàn)中改進(jìn)算法存在的問(wèn)題，本文在保持前綴表和后綴表兩次地址過(guò)濾的基礎(chǔ)上，提出將前綴表中的模式串采用平衡二叉樹(shù)存儲(chǔ)結(jié)構(gòu)，從而有效地減少每次匹配模式串的數(shù)量。

(1) 根據(jù)匹配窗口長(zhǎng)度內(nèi)的模式串后綴字符塊進(jìn)行模式串集的排序[5]。在上述模式串集合中，模式串最短長(zhǎng)度為4，因此設(shè)置匹配窗口長(zhǎng)度為4。假設(shè)字符塊B長(zhǎng)度為2，根據(jù)匹配窗口長(zhǎng)度內(nèi)的模式串最后2個(gè)字符進(jìn)行排序，則上述模式串經(jīng)過(guò)排序之后的存儲(chǔ)順序?yàn)椋?/p>

blank, plan, than, that, there, these, think, this, fund, hand, minded, thread。

假定模式串blank的存放地址為P，則plan的地址為P+1，以此類(lèi)推，最后一個(gè)模式串thread地址為P+11。這種處理能確保后綴字符相同的模式串地址是相鄰的，便于在匹配時(shí)容易實(shí)現(xiàn)模式串的地址過(guò)濾。圖1為模式串集經(jīng)過(guò)排序之后得到的有序序列。

圖1 模式串的順序結(jié)構(gòu)

上述建立的模式串順序存儲(chǔ)結(jié)構(gòu)主要針對(duì)的是英文字符環(huán)境。在中文字符匹配環(huán)境中，由于漢字采用Unicode編碼，每個(gè)漢字需要用兩個(gè)字節(jié)進(jìn)行存儲(chǔ)。通過(guò)分析漢字的雙字節(jié)碼發(fā)現(xiàn)，漢字第一個(gè)字節(jié)碼相同的概率較大，而第二個(gè)字節(jié)的編碼相同的概率相對(duì)較低[6]。例如：“蘭”的二字節(jié)編碼為：0x5170，而“江”的編碼為0x51ae?；诖?，為了適用于中文字符匹配，將采用雙漢字中每個(gè)漢字的第二字節(jié)作為B長(zhǎng)度的后綴字符塊進(jìn)行排序,建立有序的存儲(chǔ)結(jié)構(gòu)。

(2) 跳躍表Shift。跳躍表Shift存放[7]著模式串集中所有后綴塊字符在匹配時(shí)的跳躍距離，字符塊移動(dòng)距離的存放數(shù)組位置由字符塊經(jīng)過(guò)hash計(jì)算得到。假設(shè)X是模式串中連續(xù)2個(gè)字符組成的字符塊，則設(shè)計(jì)的hash函數(shù)為：hash(X)=(unsigned short) (X[0]<<8)|X[1])，此hash函數(shù)能夠保證不同的字符塊經(jīng)過(guò)hash之后不會(huì)有沖突，確保不同的后綴字符塊映射到不同的數(shù)組位置。

假設(shè)字符塊X=p[j]p[j+1]hash值為i=hash(X)，其中p[j]p[j+1]為任意字符組成的字符塊，最短模式串的長(zhǎng)度為m，則任意字符塊X跳躍距離存儲(chǔ)在ShiftP[j]P[j+1]中，其值由算法1得出。

算法1WM中求shift值算法

for(i=0;i<=255;i++)

for(j=0;j<=255;j++)

shift[i][j]=m-B+1;

for(i=1;i<=n; i++)

for(j=0;j

if(shift[pi[j]][pi[j+1]]>m-j-2)

shift[pi[j]][pi[j+1]]=m-j-2;

算法1中采用BMH算法來(lái)計(jì)算字符塊在失配時(shí)向右移動(dòng)的距離。B為字符塊的長(zhǎng)度，m為最短模式串長(zhǎng)度，n為模式串的數(shù)量，m-j-2為字符塊離匹配窗口最右邊的距離。根據(jù)算法1對(duì)所有模式串的字符塊右移距離進(jìn)行計(jì)算，得到的右移距離Shift表如表1所示。

表1 模式串Shift表

在中文字符匹配環(huán)境下，跳躍表Shift采用雙漢字來(lái)設(shè)計(jì)后綴字符塊，但是只采用每個(gè)漢字的第二字節(jié)構(gòu)成長(zhǎng)度為2的字符塊，從而計(jì)算得到雙漢字后綴字符塊的跳躍距離。由于篇幅有限，在表1中沒(méi)有列出雙漢字字符塊的跳躍距離。后續(xù)的Suffix表也采用雙漢字的第二字節(jié)建立中文模式串的Suffix表。

(3) 后綴表Suffix。后綴表[8]類(lèi)似于hash查找中的拉鏈法，具有216個(gè)頭節(jié)點(diǎn)，最多有216個(gè)單鏈表將所有的模式串連接起來(lái)，每個(gè)單鏈表存放著后綴字符塊相同的模式串子集。后綴表的創(chuàng)建過(guò)程如下：對(duì)于每個(gè)模式串，計(jì)算匹配窗口內(nèi)模式串后綴字符塊的hash值，確定該模式串加入哪個(gè)單鏈表。Suffix表中某個(gè)頭節(jié)點(diǎn)如指向一個(gè)單鏈表，則該頭節(jié)點(diǎn)指針域用鏈表中的第一個(gè)模式串的地址填充，而該頭節(jié)點(diǎn)之前所有空鏈表的頭節(jié)點(diǎn)都用該地址填充。例如所有以“an”作為匹配窗口最后兩個(gè)字符的模式串，它們的地址范圍為：[suffix[hash(an)]→next, suffix[hash(an)+1]→next)，也就是需要參與匹配的模式串的地址范圍為[P,P+3)。

Suffix表如圖2所示。

圖2 Suffix表存儲(chǔ)結(jié)構(gòu)

在中文字符匹配環(huán)境下，為了建立基于雙漢字的前綴表，分別提取中文模式串的最前面兩個(gè)漢字的第二字節(jié)構(gòu)成字符塊進(jìn)行hash，建立中文模式串的Prefix表。但可能會(huì)出現(xiàn)不同雙漢字字符塊存儲(chǔ)在一個(gè)單鏈表中，造成地址沖突。沖突概率為1/216。

利用后綴表Suffix中確定后綴相同的模式串地址范圍，從前綴表中取出前綴相同的模式串時(shí)，首先取出模式串所對(duì)應(yīng)的物理地址，判斷參與匹配模式串的地址是否在后綴表確定的地址范圍之內(nèi)；如果不在，該模式串不用參與比較。但是，如果前綴表所對(duì)應(yīng)模式串過(guò)多，還會(huì)影響到NEW_WM算法的匹配性能。例如：案例中以“th”開(kāi)頭的模式串有7個(gè)可能需要參與匹配，前綴表所對(duì)應(yīng)的單鏈表過(guò)長(zhǎng)。針對(duì)此問(wèn)題，有必要引入改進(jìn)算法，將單鏈表存儲(chǔ)的模式串改為平衡二叉樹(shù)存儲(chǔ)。圖3是基于單鏈表結(jié)構(gòu)的前綴表，圖4是將圖3修改為平衡二叉樹(shù)形式的物理結(jié)構(gòu)。

圖3 基于單鏈表結(jié)構(gòu)的前綴表

圖4 基于平衡二叉樹(shù)的前綴表

在上述平衡二叉樹(shù)的前綴表中，如果需要查找“than”，采用二次地址過(guò)濾和平衡二叉樹(shù)前綴表，由于具有“an”匹配窗口后綴的模式串地址范圍為：P≤p

改進(jìn)算法時(shí)間性能分析：假設(shè)前綴表Prefix中每個(gè)單鏈表的平均長(zhǎng)度為n，如采用單鏈表物理結(jié)構(gòu)進(jìn)行模式匹配，則平均時(shí)間復(fù)雜度為O(n/2)，而采用平衡樹(shù)二叉樹(shù)存儲(chǔ)結(jié)構(gòu)之后，該二叉樹(shù)的深度為log2n，時(shí)間復(fù)雜度為O(log2n)。

2 字頻統(tǒng)計(jì)的模式匹配算法

2.1 算法思想

模式串中各個(gè)字符在文本串中出現(xiàn)的頻率差別較大。在模式匹配中，如果每一次匹配時(shí)先用模式串頻率最低的字符與文本串匹配窗口對(duì)應(yīng)的字符進(jìn)行比較，盡快找到失配位置，就能有效地減少每一次匹配時(shí)的平均比較次數(shù)[9]。

2.2 各模式串頻率最低字符位置的計(jì)算

基于字符頻率的匹配算法首先需要計(jì)算出每個(gè)模式串中最低頻率字符的位置，然后采用該位置字符與文本串匹配窗口中對(duì)應(yīng)的字符進(jìn)行比較，從而有效地減少每輪匹配字符比較次數(shù)。

根據(jù)表2統(tǒng)計(jì)的英文字符在文本串中出現(xiàn)的頻率值，按照各個(gè)字符出現(xiàn)的頻率值，采用從小到大的排列順序?yàn)椋簔qxjkvbpygfwmucldrhsnioate。根據(jù)上述字符頻率的排序，設(shè)計(jì)字符數(shù)組char CFValue[26]=″zqxjkvbpygfwmucldrhsnioate″。上述字符數(shù)組第一個(gè)字符出現(xiàn)的頻率最低，最后一個(gè)字符頻率最大。

表2 IT專(zhuān)業(yè)英文字母的出現(xiàn)頻率

續(xù)表2

假設(shè)模式串?dāng)?shù)量為1個(gè)，最短模式串的長(zhǎng)度為m，i代表頻率數(shù)組元素下標(biāo)，最大值為25，j為各個(gè)模式串?dāng)?shù)組下標(biāo)，i的初值為0，j的初值為1。算法2能夠?qū)崿F(xiàn)將每個(gè)模式串字符頻率最低的位置存放在各個(gè)模式串的第1個(gè)位置上。

算法2字頻統(tǒng)計(jì)頻率最低字符位置定位算法

void GetMinFrePos(char CFValue[26], char &*pat[l])

//函數(shù)功能是確定所有模式串pat中頻率最低字符出現(xiàn)的

//位置

{

pos=0; m=4;

for(k=1;k<=l;k++)

for (i=0;i<=25;i++)

{ for (j=1;j<=m;j++)

if (CFValue[i]==pat[k][j])

{ pat[k][0]=j;

break;

}

}

在中文字符匹配環(huán)境中，提取雙漢字中的第二字節(jié)組成二維數(shù)組，可以采用雙漢字組成詞的詞頻進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)各個(gè)詞語(yǔ)的使用頻率，但會(huì)導(dǎo)致表2的字符塊的個(gè)數(shù)為216。另外，如果需要計(jì)算每個(gè)中文模式串各自的最低詞頻的位置，則需要設(shè)置三維數(shù)組，如果有1 000條中文字符模式串，則存儲(chǔ)空間為1 000×216，約等于65 MB內(nèi)存空間。

3 改進(jìn)算法NEW_WM

3.1 失配時(shí)移動(dòng)距離的改進(jìn)

WM算法在失配時(shí)采用BMH算法實(shí)現(xiàn)匹配窗口的移動(dòng)。如果在失配時(shí)有更大的跳躍距離，則能夠提高模式匹配算法的性能[10]。

雙字符數(shù)組跳躍距離Skip[c1][c2]的計(jì)算過(guò)程為：先將任意兩個(gè)字符組成的字符塊的跳躍值初始化為模式集中最短模式的長(zhǎng)度加1，即m+1；若文本匹配窗口最右端的下一個(gè)字符與任一模式串中的第一個(gè)字符相同，為避免漏掉模式串的匹配，將此種情況下的B字符塊的跳躍值初始化為最短模式的長(zhǎng)度m；對(duì)于出現(xiàn)在模式串集中的B字符塊，通過(guò)遍歷所有的模式串，計(jì)算出該字符塊在模式集中的最右端位置，然后用最短模式串長(zhǎng)度m減去該位置，從而得到該字符塊的最終跳躍值。初始化跳躍數(shù)組skip[i][j]的主要算法描述如算法3所示，為了簡(jiǎn)化計(jì)算，采用B=2情況進(jìn)行塊字符處理。

算法3雙字符數(shù)組跳躍距離Skip[][]的計(jì)算

while(i=0;i<256;i++)

while(j=0;j<256;j++)

skip[i][j]=m+1;

//將所有字符塊的跳躍值初始化

for(k=1 ;k<=N; k++)

//N模式集合中的模式串的數(shù)量

for(i=1;i

if ((m-i)

skip [Pk[i]][Pk[i+1]]=m-i;

for(k=0;k

for(i=0;i<=255;i++)

if (skip [i] [Pk[0]]=m+1)

skip [i] [Pk[0]]=m;

//模式串的第一個(gè)字符與文本串匹配窗口最右端的下一個(gè)

//字符相同，如跳躍距離為m+1，則將跳躍距離調(diào)整為m

由于WM算法已經(jīng)有一個(gè)Shift數(shù)組存放著基于BMH字符塊的跳躍數(shù)組SHIFT，在改進(jìn)算法中建立基于BMHS算法的另外一個(gè)跳躍表skip，此表用來(lái)存放文本串匹配窗口最后B-1個(gè)字符與匹配窗口下一個(gè)字符組成的字符塊B的右移距離，每次失配時(shí)采用上述跳躍數(shù)組的較大者。

在中文匹配過(guò)程中，skip的二維數(shù)組下標(biāo)來(lái)自于雙漢字的每個(gè)漢字第二字節(jié)，從而實(shí)現(xiàn)skip數(shù)組的計(jì)算。

3.2 改進(jìn)算法的流程

NEW_WM的改進(jìn)主要在以下三個(gè)方面：① 采用后綴表和前綴表進(jìn)行模式串地址過(guò)濾以及對(duì)前綴表存放采用平衡二叉樹(shù)存儲(chǔ)結(jié)構(gòu)，減少了每次需參與匹配模式串的數(shù)量；② 對(duì)參與匹配的模式串采用字頻匹配，盡快找到失配字符，減少模式串的字符比較次數(shù)；③ 在失配時(shí)將匹配窗口采用BMH和BMHS算法中的較大距離向右移動(dòng)。

改進(jìn)算法流程如下。

假定匹配窗口尺寸為4個(gè)字符，即m=4，字符塊包含兩個(gè)字符，即B=2，文本串長(zhǎng)度為n，改進(jìn)算法匹配過(guò)程如下：

(1) 首先從文本串的前端取出m個(gè)字符作為初始匹配窗口字符，將文本串匹配指針Tp指向當(dāng)前匹配窗口中的第一個(gè)字符。

(2) 如果Tp>n-m+1，結(jié)束整個(gè)文本串的匹配，否則，轉(zhuǎn)向步驟(3)執(zhí)行。

(3) 計(jì)算當(dāng)前文本串匹配窗口中后綴塊字符的hash值hash(scb)，查跳躍表Shift得到該塊字符對(duì)應(yīng)的跳躍距離Shift[hash(scb)]。如果Shift[hash(scb)]==0，轉(zhuǎn)步驟(4)執(zhí)行；否則(也就是Shift[hash(scb)]>0)，判斷skip[Tp+m-1][Tp+m]是否大于Shift[hash(scb)]，如果大于，則Tp=Tp+skip[Tp+m-1][Tp+m]，否則Tp=Tp+Shift[hash(scb)]，返回到步驟(2)。

(4) 設(shè)置指針變量p=Suffix[hash(scb)]，指針變量p指向鏈表中第一個(gè)模式串地址，并得到指針變量p的地址取值范圍為：Suffix[hash(scb)]≤p

(5) 計(jì)算文本串匹配窗口內(nèi)前綴塊字符的hash值hash(pcb)，查表頭節(jié)點(diǎn)Prefix[hash[pcb]]元素值，該值指向平衡二叉樹(shù)的根節(jié)點(diǎn)，p=Prefix[hash[pcb]]→next。如果p為空，則意味著在模式串中找不到與文本串相同的前綴，轉(zhuǎn)步驟(8)；如果p非空，轉(zhuǎn)步驟(6)。

(6) 判斷p所指的節(jié)點(diǎn)指針域存放的模式串地址是否在[Suffix[hash(scb)]，Suffix[hash(scb)+1]區(qū)間之間。如果地址指針pSuffix[hash(scb)+1]，則該指針p所指向的模式串不用匹配，轉(zhuǎn)步驟(7);如果p在此區(qū)間中，則將p所指模式串頻率最低字符與文本串匹配窗口對(duì)應(yīng)字符比較，如果不同，轉(zhuǎn)步驟(7)，如果相同，則將p所指向模式串的剩余字符與匹配窗口對(duì)應(yīng)字符逐一匹配，過(guò)程中如不匹配，轉(zhuǎn)步驟(7),如果匹配成功，則返回成功匹配位置Tp，轉(zhuǎn)步驟(8)。

(7) 將文本串匹配窗口子串與p所指的模式串進(jìn)行大小比較，如果子串值小于模式串，p=p→lchild;否則p=p→rchild；然后判斷p是否為空，如果為空，轉(zhuǎn)步驟(8)，否則轉(zhuǎn)步驟(6)。

(8) 判斷skip[Tp+m-1][Tp+m]是否大于1，如果大于，則Tp=Tp+skip[Tp+m-1][Tp+m]，否則Tp=Tp+1，然后執(zhí)行步驟(2)。

在上述匹配過(guò)程中，參與匹配的模式串經(jīng)過(guò)了后綴表和前綴表的兩次過(guò)濾和前綴表平衡二叉樹(shù)的設(shè)計(jì)，相對(duì)于WM算法，每次需要匹配的模式串?dāng)?shù)量進(jìn)一步減少；另外，在每次失配時(shí)，采用BMH和BMSH算法較大的向右跳躍距離，加快了模式串向后移動(dòng)的速度。改進(jìn)算法的性能得到了一定幅度的提高。

3.3 算法實(shí)現(xiàn)

算法4改進(jìn)算法NEW_WM的匹配算法

ti=0;

while(ti

{

x=shift[ti+m-2] [ti+m-1];

if(x==0)

//匹配窗口最右端字符塊在模式串的右端

{

low=suffix[hash([ti+m-2] [ti+m-1])];

high=suffix[hash([ti+m-2] [ti+m-1]))+1];

p=prefix[hash([ti] [ti+1])]->next;

if(p==0) move(ti)

//沒(méi)有相同前綴的模式串

else

{

while(p!=NULL)

//窮舉所有前綴相同的模式串

{

if( low<=p->next&& p->next

//在后綴地址范圍之內(nèi)

{

k=p->data[0];

//找到p所指模式串頻率最低字符位置

if(t[i+k]!=p->data[k])

//頻率最低字符失配

p=next(p)

//指向下一層模式串

else

//頻率最低字符匹配

{

for(j=3;j<=m;j++)

//窮舉當(dāng)前模式串所有字符進(jìn)行匹配

{

if(p->data[j]==t[i+j-1])

continue;

else

//如有失配

p=next(p);

}

if(j>m)

//找到匹配模式串

{

postion[k++]=i;

move(i);

break;

}

}

}

else

//模式串不在地址范圍之內(nèi)

p=next(p);

//不在地址范圍之內(nèi)，p指向下一層模式串

}

if(p==NULL)

//在前綴表中沒(méi)有找到匹配的模式串

i=move(i);

}

int move(int ti)

//匹配窗口移動(dòng)距離的計(jì)算函數(shù)

{

if(skip[ti+m-1][ti+m])>shift[ti+m-2][ti+m-1])

ti=ti+skip[ti+m-1][ti+m];

else

ti+=shift[ti+m-2][ti+m-1];

return ti;

}

Link *next(Link p)

//p指向下一層模式串函數(shù)

{

if(p->data

p=p->lchild;

else

p=p->rchild；

return p;

}

為了將上述算法的思想在中文匹配中實(shí)現(xiàn)，需要進(jìn)行一定的改動(dòng)。當(dāng)計(jì)算得到skip[i][j]等于0時(shí)，還需要對(duì)雙漢字中每個(gè)漢字的第一個(gè)字節(jié)進(jìn)行匹配，只有這兩個(gè)字節(jié)相同，才需要進(jìn)行完全匹配；否則，需要將文本串匹配窗口根據(jù)計(jì)算好的skip數(shù)組向右移動(dòng)。

3.4 改進(jìn)算法匹配實(shí)例

下面將通過(guò)一個(gè)匹配實(shí)例來(lái)說(shuō)明NEW_WM算法的匹配過(guò)程，假設(shè)匹配窗口尺寸為4，塊字符大小為2。

(1) 開(kāi)始時(shí)匹配窗口位于文本串的前端，后綴塊字符為″ow″:

計(jì)算″ow″的散列值hash(ow)，查表Shift得到Shift[hash(ow)]=3，表明當(dāng)前匹配窗口沒(méi)有模式串與其匹配，然后查詢(xún)BMHS算法中的skip[w][l]的值為5>Shift[hash(ow)]=3,匹配窗口向后移動(dòng)5個(gè)位置:

(2) 匹配窗口最后兩個(gè)字符為“e”,Shift[“e”]=3,skip[e][]=5，匹配窗口向后移動(dòng)5個(gè)位置:

經(jīng)過(guò)5輪匹配之后，匹配窗口內(nèi)字符串為“than”，查詢(xún)Shift[hash(an)]=0，說(shuō)明“an”在模式串中存在，通過(guò)后綴表Suffix[hash(an)]得到具有后綴“an”模式串的地址p范圍滿(mǎn)足以下關(guān)系：Suffix4[hash(an)] ≤p

4 實(shí)驗(yàn)測(cè)試分析

為了驗(yàn)證改進(jìn)算法的時(shí)間性能是否得到提高，采用了WM和DHSWM兩種匹配算法作對(duì)比，分別在模式串?dāng)?shù)量和長(zhǎng)度變化兩種情況下進(jìn)行時(shí)間性能對(duì)比。待測(cè)目標(biāo)文本串為某科技互聯(lián)網(wǎng)網(wǎng)站下載的10 MB的信息技術(shù)專(zhuān)業(yè)的相關(guān)文檔，模式串從信息技術(shù)專(zhuān)業(yè)文件中隨機(jī)抽取。

實(shí)驗(yàn)測(cè)試環(huán)境：為保證測(cè)試實(shí)驗(yàn)數(shù)據(jù)的準(zhǔn)確和有效性，WM、DHSWM和NEW_WM算法均使用 Visual Studio 2017 集成開(kāi)發(fā)工具，采用C++語(yǔ)言進(jìn)行編程實(shí)現(xiàn)。測(cè)試主機(jī)的配置為：Intel? CoreTMi7-7500U CPU，3.10 GHz主頻，16 GB內(nèi)存，Windows 10操作系統(tǒng)，使用精確到微秒的時(shí)間函數(shù)clock()。

4.1 模式串集數(shù)量對(duì)算法時(shí)間性能影響

測(cè)試數(shù)據(jù):模式串長(zhǎng)度為40個(gè)字符，待匹配的文本串長(zhǎng)度為10 MB。

測(cè)試方案:依次選取100、200、500、1 000和2 000個(gè)模式串，分別測(cè)試WM、DHSWM和NEW_WM算法的時(shí)間性能，時(shí)間性能與文本匹配完成所需時(shí)間成反比。

表3 模式串?dāng)?shù)量變化時(shí)匹配時(shí)間 ms

從表3可以看出NEW_WM算法的匹配性能相對(duì)于WM提高了18%左右，相對(duì)于DHSWM算法而言，匹配時(shí)間性能提高了10%左右。這說(shuō)明了NEW_WM算法的改進(jìn)方面發(fā)揮了作用。隨著模式串?dāng)?shù)量的增加，NEW_WM算法的時(shí)間性能改善越明顯，二次模式串過(guò)濾機(jī)制和平衡二叉樹(shù)發(fā)揮的作用更加明顯，原因是隨著模式串?dāng)?shù)量增加，WM算法中的后綴表Prefix形成長(zhǎng)鏈表的概率增加，而采用雙表二次過(guò)濾以及平衡二叉樹(shù)減少了每次需要匹配的模式串的數(shù)量。因此模式串?dāng)?shù)量越多，改進(jìn)算法的時(shí)間性能提高得越明顯。

4.2 模式串長(zhǎng)度對(duì)算法時(shí)間性能的影響

測(cè)試數(shù)據(jù):固定模式串?dāng)?shù)目為2 000個(gè)，固定待匹配的文本串為10 MB。

測(cè)試方案:依次選取長(zhǎng)度為20、40、60、80、100、120、140的模式串，分別測(cè)試WM、DHSWM和NEW_WM匹配算法的時(shí)間性能，時(shí)間性能與文本匹配完成所需時(shí)間成反比。

表4 模式長(zhǎng)度與算法性能關(guān)系表 ms

從表4可以看出，WM、DHSWM和NEW_WM算法會(huì)隨著模式長(zhǎng)度的增加，時(shí)間性能都會(huì)逐漸提高，NEW_WM算法較WM算法性能提高了20%左右，較DHSWM算法性能提高了8%左右。

5 結(jié) 語(yǔ)

NEW_WM算法在匹配過(guò)程中采用了后綴表和前綴表的模式串的二次過(guò)濾以及平衡二叉樹(shù)，減少了每次匹配模式串的數(shù)量，在文本串匹配窗口匹配時(shí)采用最低頻率字符先進(jìn)行比較，并在失配時(shí)采用BMH和BMHS算法計(jì)算得到的模式串向后移動(dòng)的較大距離。相對(duì)于WM和DHSWM算法來(lái)說(shuō)，減少了每次參與匹配模式串匹配的數(shù)量，也減少了每個(gè)模式串比較字符次數(shù)，并在失配時(shí)加快了模式串向后移動(dòng)的速度，因此，時(shí)間性能得到了一定幅度的提高。