一種WM多模匹配算法的研究與改進

周延森 張維剛

1(國際關系學院網絡空間安全學院 北京 100091) 2(哈爾濱工業大學計算機科學與技術學院 山東 威海 264200)

0 引 言

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

當前，每一種模式匹配算法性能的改進已經遇到一定的瓶頸。為此，需要將各種模式匹配算法進行組合，吸取各算法的優點，從而能夠以一定幅度提高模式匹配算法的性能[2]。基于此，本文提出一種新的改進WM算法，該算法采用前綴表和后綴表的二次過濾以及平衡二叉樹減少了每一次參與匹配的模式串數量。為了盡快找到文本串中的失配字符，減少每次匹配字符比較次數，改進算法引入字頻的模式匹配算法。此外，匹配窗口每次匹配失配時，改進算法引入BMHS算法，采用了BMH和BMHS算法中較大的右移距離來移動匹配窗口。

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

1 模式串預處理

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

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

在WM算法中，只使用Suffix后綴表中對應的模式串子集參與文本串匹配，沒有利用Prefix表進行模式串的二次過濾，因此需要Suffix中后綴相同的所有模式串都參與匹配，匹配性能較差[4]。目前，在主要的WM的改進算法中，主要采用基于后綴表和前綴表的二次地址過濾以及多次hash來減少每次參與匹配模式串的數量，如文獻[3]提出的改進算法DHSWM。但是，當模式串數量眾多并且存在大量前綴字符塊相同的模式串時，還會有較大數量的模式串參與每次匹配，匹配時間性能會受到較大的影響。針對文獻中改進算法存在的問題，本文在保持前綴表和后綴表兩次地址過濾的基礎上，提出將前綴表中的模式串采用平衡二叉樹存儲結構，從而有效地減少每次匹配模式串的數量。

(1) 根據匹配窗口長度內的模式串后綴字符塊進行模式串集的排序[5]。在上述模式串集合中，模式串最短長度為4，因此設置匹配窗口長度為4。假設字符塊B長度為2，根據匹配窗口長度內的模式串最后2個字符進行排序，則上述模式串經過排序之后的存儲順序為：

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

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

圖1 模式串的順序結構

上述建立的模式串順序存儲結構主要針對的是英文字符環境。在中文字符匹配環境中，由于漢字采用Unicode編碼，每個漢字需要用兩個字節進行存儲。通過分析漢字的雙字節碼發現，漢字第一個字節碼相同的概率較大，而第二個字節的編碼相同的概率相對較低[6]。例如：“蘭”的二字節編碼為：0x5170，而“江”的編碼為0x51ae。基于此，為了適用于中文字符匹配，將采用雙漢字中每個漢字的第二字節作為B長度的后綴字符塊進行排序,建立有序的存儲結構。

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

假設字符塊X=p[j]p[j+1]hash值為i=hash(X)，其中p[j]p[j+1]為任意字符組成的字符塊，最短模式串的長度為m，則任意字符塊X跳躍距離存儲在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算法來計算字符塊在失配時向右移動的距離。B為字符塊的長度，m為最短模式串長度，n為模式串的數量，m-j-2為字符塊離匹配窗口最右邊的距離。根據算法1對所有模式串的字符塊右移距離進行計算，得到的右移距離Shift表如表1所示。

表1 模式串Shift表

在中文字符匹配環境下，跳躍表Shift采用雙漢字來設計后綴字符塊，但是只采用每個漢字的第二字節構成長度為2的字符塊，從而計算得到雙漢字后綴字符塊的跳躍距離。由于篇幅有限，在表1中沒有列出雙漢字字符塊的跳躍距離。后續的Suffix表也采用雙漢字的第二字節建立中文模式串的Suffix表。

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

Suffix表如圖2所示。

圖2 Suffix表存儲結構

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

利用后綴表Suffix中確定后綴相同的模式串地址范圍，從前綴表中取出前綴相同的模式串時，首先取出模式串所對應的物理地址，判斷參與匹配模式串的地址是否在后綴表確定的地址范圍之內；如果不在，該模式串不用參與比較。但是，如果前綴表所對應模式串過多，還會影響到NEW_WM算法的匹配性能。例如：案例中以“th”開頭的模式串有7個可能需要參與匹配，前綴表所對應的單鏈表過長。針對此問題，有必要引入改進算法，將單鏈表存儲的模式串改為平衡二叉樹存儲。圖3是基于單鏈表結構的前綴表，圖4是將圖3修改為平衡二叉樹形式的物理結構。

圖3 基于單鏈表結構的前綴表

圖4 基于平衡二叉樹的前綴表

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

改進算法時間性能分析：假設前綴表Prefix中每個單鏈表的平均長度為n，如采用單鏈表物理結構進行模式匹配，則平均時間復雜度為O(n/2)，而采用平衡樹二叉樹存儲結構之后，該二叉樹的深度為log2n，時間復雜度為O(log2n)。

2 字頻統計的模式匹配算法

2.1 算法思想

模式串中各個字符在文本串中出現的頻率差別較大。在模式匹配中，如果每一次匹配時先用模式串頻率最低的字符與文本串匹配窗口對應的字符進行比較，盡快找到失配位置，就能有效地減少每一次匹配時的平均比較次數[9]。

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

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

根據表2統計的英文字符在文本串中出現的頻率值，按照各個字符出現的頻率值，采用從小到大的排列順序為：zqxjkvbpygfwmucldrhsnioate。根據上述字符頻率的排序，設計字符數組char CFValue[26]=″zqxjkvbpygfwmucldrhsnioate″。上述字符數組第一個字符出現的頻率最低，最后一個字符頻率最大。

表2 IT專業英文字母的出現頻率

續表2

假設模式串數量為1個，最短模式串的長度為m，i代表頻率數組元素下標，最大值為25，j為各個模式串數組下標，i的初值為0，j的初值為1。算法2能夠實現將每個模式串字符頻率最低的位置存放在各個模式串的第1個位置上。

算法2字頻統計頻率最低字符位置定位算法

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

//函數功能是確定所有模式串pat中頻率最低字符出現的

//位置

{

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;

}

}

在中文字符匹配環境中，提取雙漢字中的第二字節組成二維數組，可以采用雙漢字組成詞的詞頻進行統計，統計各個詞語的使用頻率，但會導致表2的字符塊的個數為216。另外，如果需要計算每個中文模式串各自的最低詞頻的位置，則需要設置三維數組，如果有1 000條中文字符模式串，則存儲空間為1 000×216，約等于65 MB內存空間。

3 改進算法NEW_WM

3.1 失配時移動距離的改進

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

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

算法3雙字符數組跳躍距離Skip[][]的計算

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

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

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

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

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

//N模式集合中的模式串的數量

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;

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

//字符相同，如跳躍距離為m+1，則將跳躍距離調整為m

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

在中文匹配過程中，skip的二維數組下標來自于雙漢字的每個漢字第二字節，從而實現skip數組的計算。

3.2 改進算法的流程

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

改進算法流程如下。

假定匹配窗口尺寸為4個字符，即m=4，字符塊包含兩個字符，即B=2，文本串長度為n，改進算法匹配過程如下：

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

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

(3) 計算當前文本串匹配窗口中后綴塊字符的hash值hash(scb)，查跳躍表Shift得到該塊字符對應的跳躍距離Shift[hash(scb)]。如果Shift[hash(scb)]==0，轉步驟(4)執行；否則(也就是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) 設置指針變量p=Suffix[hash(scb)]，指針變量p指向鏈表中第一個模式串地址，并得到指針變量p的地址取值范圍為：Suffix[hash(scb)]≤p

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

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

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

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

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

3.3 算法實現

算法4改進算法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)

//沒有相同前綴的模式串

else

{

while(p!=NULL)

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

{

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

//在后綴地址范圍之內

{

k=p->data[0];

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

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

//頻率最低字符失配

p=next(p)

//指向下一層模式串

else

//頻率最低字符匹配

{

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

//窮舉當前模式串所有字符進行匹配

{

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

continue;

else

//如有失配

p=next(p);

}

if(j>m)

//找到匹配模式串

{

postion[k++]=i;

move(i);

break;

}

}

}

else

//模式串不在地址范圍之內

p=next(p);

//不在地址范圍之內，p指向下一層模式串

}

if(p==NULL)

//在前綴表中沒有找到匹配的模式串

i=move(i);

}

int move(int ti)

//匹配窗口移動距離的計算函數

{

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指向下一層模式串函數

{

if(p->data

p=p->lchild;

else

p=p->rchild；

return p;

}

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

3.4 改進算法匹配實例

下面將通過一個匹配實例來說明NEW_WM算法的匹配過程，假設匹配窗口尺寸為4，塊字符大小為2。

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

計算″ow″的散列值hash(ow)，查表Shift得到Shift[hash(ow)]=3，表明當前匹配窗口沒有模式串與其匹配，然后查詢BMHS算法中的skip[w][l]的值為5>Shift[hash(ow)]=3,匹配窗口向后移動5個位置:

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

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

4 實驗測試分析

為了驗證改進算法的時間性能是否得到提高，采用了WM和DHSWM兩種匹配算法作對比，分別在模式串數量和長度變化兩種情況下進行時間性能對比。待測目標文本串為某科技互聯網網站下載的10 MB的信息技術專業的相關文檔，模式串從信息技術專業文件中隨機抽取。

實驗測試環境：為保證測試實驗數據的準確和有效性，WM、DHSWM和NEW_WM算法均使用 Visual Studio 2017 集成開發工具，采用C++語言進行編程實現。測試主機的配置為：Intel? CoreTMi7-7500U CPU，3.10 GHz主頻，16 GB內存，Windows 10操作系統，使用精確到微秒的時間函數clock()。

4.1 模式串集數量對算法時間性能影響

測試數據:模式串長度為40個字符，待匹配的文本串長度為10 MB。

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

表3 模式串數量變化時匹配時間 ms

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

4.2 模式串長度對算法時間性能的影響

測試數據:固定模式串數目為2 000個，固定待匹配的文本串為10 MB。

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

表4 模式長度與算法性能關系表 ms

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

5 結 語

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