一種基于漢字編碼特征的中文多模式匹配算法

黃　宇,　侯整風,　余　虎,　劉春暉

(合肥工業大學 計算機與信息學院,安徽 合肥　230009)

?

一種基于漢字編碼特征的中文多模式匹配算法

黃宇,侯整風,余虎,劉春暉

(合肥工業大學 計算機與信息學院,安徽 合肥230009)

對于大規模中文模式串匹配,由于漢字的散度較高,導致AC算法有限狀態自動機中的零狀態過長,算法的效率急劇下降。文章提出了一種基于漢字編碼特征的改進算法,考慮到漢字的首字節范圍比尾字節的小,先查找首字節,再查找尾字節,若失敗則直接跳轉,降低了查找時間。該算法通過給零狀態中字符設置標記,有效避免重復匹配和部分匹配,提高了匹配效率。

AC算法;多模式匹配;漢字編碼特征;標記

模式匹配算法是信息領域的重要內容,廣泛應用于搜索引擎[1]、網絡入侵檢查系統[2-3]、DNA序列匹配[4]等領域。單模式匹配中,BM (Brute-Force)算法[5]運用壞字符規則和好后綴規則來計算模式串右移距離,實現了模式串的跳躍式匹配。BMH (Brute-Force-Horspol)算法[6]是對BM算法的改進,該算法僅考慮壞字符規則,簡化預處理,提高了匹配效率;AC (Aho-Corasick) 算法[7]是一種經典的多模式匹配算法,該算法基于有限狀態自動機,通過狀態轉移,掃描一遍文本串可匹配多個模式串。AC_BM算法[8]是AC算法的改進,其結合BM算法的模式串的跳躍式移動的思想,可跳躍式匹配,但跳轉距離過于保守,平均跳轉距離較小。文獻[9]利用Tuned BM算法的思想計算平均跳轉距離,提出AC_Tuned BM算法;文獻[10]提出的IACBM算法利用BMH和QS算法的思想計算平均跳轉距離。 上述方法在一定程度上增加了平均跳轉距離,但沒有考慮到有限狀態自動機的存儲結構對跳躍式匹配過程的影響。

由于漢字字符的散度較高,隨著模式串的增加,基于AC算法的中文多模式匹配算法需要巨大的空間開銷,從而導致goto狀態轉移函數計算量大,算法的時間復雜度急劇增加,不適合大規模中文模式匹配。采用Hash表[11]和壓縮稀疏矩陣[12]存儲有限狀態機,雖然在一定程度上有所改善,但當模式串的數量巨大時,Hash表存儲方式由于內存消耗過大,算法效率下降;稀疏矩陣的存儲方式壓縮率也不是很高,所需存儲空間仍然較大,Cache命中率下降,頻繁進行缺頁中斷操作。文獻[13]采用狀態編碼以消除不必要轉移,試圖減小存儲空間開銷,但對中文模式匹配,這種“不必要轉移”較少,存儲空間開銷依然巨大,導致算法的效率依然不是很高;文獻[14]嘗試用位圖壓縮來存儲,對中文模式串壓縮率約為25%,沒有從根本上解決內存消耗過大、Cache命中率下降問題；文獻[15]提出的鄰接鏈表存儲方式,雖然考慮到存儲結構對模式匹配的影響,但是由于零狀態過長,查找效果依然不是很理想。

本文提出一種基于漢字編碼特征的改進算法,建立首字節桶和匹配桶,首先查找首字節,查找成功則查找尾字節;并設置標記,減少了查找跳轉距離次數,有效避免了重復匹配和部分匹配。與傳統的AC算法及其改進算法相比,本文算法降低了算法的時間復雜度。

1　AC算法

1.1預處理

(1) 構造有限狀態自動機。設模式串集合P={p1,p2,…，pi，…，pn}。對P中的每個模式串pi,初始狀態設為0。每次添加都是從狀態0開始,逐個取出pi中的每一個字符;如果從當前狀態出發發現已存在標注該字符的矢線,則將矢線所指的狀態作為當前狀態;否則,添加1個新狀態作為當前狀態,新狀態為已有的最大狀態加1。當處理完P中的所有字符串,最后添加一條始于狀態0止于狀態0的自反線,并標注始于狀態0的字符集。例如P={what,how,where,when},有限狀態自動機如圖1所示。

(2) goto函數。goto函數用于計算當前狀態的下一狀態。若能從當前狀態出發可以找到標注字符 “c” 的矢線,則goto函數返回矢線所指的狀態,否則返回跳轉失敗狀態fail。由圖1可知,goto(0,w)=1,goto(2,e)=8,goto(1,a)=fail。

(3) failure函數。failure函數是在字符匹配失敗時跳轉的依據。狀態s的深度depth(s)定義為從狀態0到狀態s的最短路徑長度。由圖1可知,狀態1和狀態5的深度為1。設狀態r的父狀態為s,標注的字符為“c”。若depth(s)=0,則failure(r)=0;否則 failure(r)=goto(failure(s),c)。由圖1可知,failure(5)=0,failure(2)=goto(0,h)=5。

圖1　有限狀態自動機

(4) output函數。output函數用來輸出成功匹配的模式串。在構造有限狀態自動機的過程中,當處理完一個模式串pi后,將該模式串pi加入到當前狀態的輸出函數中。

在計算失效函數過程中,若failure(r)=r′,則output(r)=output(r)∪output(r′)。由圖1可知,output(7)={how},output(4)={what}。

1.2匹配過程

(1) 將當前狀態r置為0,文本串指針指向文本串的首字符。

(2) 若文本串的當前指針不為空,則取出指向的字符“c”;否則匹配過程結束。

(3) 計算r′=goto(r,a)。若r′≠fail,則r=r′,文本串指針向右移動1位,計算output函數,若output(r)=NULL,轉步驟(2);否則,輸出output(r)的值,表示有模式串匹配成功,轉步驟(2)。

(4) 若r′=fail,調用failure函數,即當前狀態r=failure(r′),轉步驟(3)。

2　存儲結構

2.1常用存儲結構

(1) 狀態矩陣存儲方式。狀態矩陣為每個狀態s建立一個數組As,As中的值表示匹配成功時所跳轉的狀態。所有的As組成一個二維矩陣N[0…i][0…j],其中,0…i表示狀態;0…j表示所有模式串中不重復的字符。由于漢字的散度較高,隨著模式串的增大,這種存儲結構所需存儲空間迅速增加。

(2) 完全哈希表存儲方式。對于單字節的英文字符,其完全哈希表所占用的空間為Num(state)×256,其中Num(state)為狀態數目,對于中文字符串,占用的空間為Num(state)×256×256。隨著模式串數目的增大,狀態數隨之增大,導致內存消耗過大。

(3) 鄰接鏈表存儲方式。對于鄰接鏈表存儲方式,雖然占用的存儲空間比狀態矩陣和完全哈希表存儲方式有所降低,但是零狀態過長,增加了查找時間,導致算法的時間效率依然不是很高。

2.2帶標記的混合存儲結構

本文采用混合存儲結構，算法的匹配效率不僅由跳轉距離決定,有限狀態機的存儲方式對匹配亦有影響,并考慮到重復匹配和部分匹配以及重復查找跳轉距離帶來的時間開銷,增加跳轉標記和匹配標記,使算法效率得到提高。

2.2.1混合存儲結構

漢字的散度較高,使用鄰接鏈表存儲時,導致零狀態過長,基于這一特征,本文采用首字節桶和匹配桶存儲零狀態字符。每個漢字存儲占用2個字節,如GBK編碼,首字節的范圍是81—FE,126個,尾字節的范圍是40—FE,190個。

首先建立一個首字節桶,其大小為126字節,依次編號81,82,…,FE,每字節存儲的內容與其編號相同,存儲所有零狀態中字符的首字節,且不重復存放。例如模式串集P={好聲音,熱播,平凡人,奇跡,理念},各模式串首字符的首字節存儲方式如圖2所示。

圖2　首字節桶

再建立190個匹配桶,編號40,41,…,FE。每個桶由2個域組成,首字節域保存某一字符尾字節對應的首字節,跳轉狀態域保存跳轉到頭結點表中的位置。例如模式串集P={好聲音,熱播,平凡人,奇跡,理念},各模式串首字符的匹配桶如圖3所示。圖3中,“首域”指首字節域,“跳域”指跳轉狀態域。當匹配桶中含有不止1個字符的首字節時,每增加1個字符就在桶中增加1組首字節域、跳轉狀態域。

圖3　匹配桶

模式串集P={好聲音,熱播,平凡人,奇跡,理念}的混合存儲結構如圖4所示。其中,首字節桶如圖2所示,匹配桶如圖3所示。

圖4　混合存儲結構

在查找時首先在首字節桶中查找,如果成功則查找匹配桶,失敗則跳轉。查找成功時則根據跳轉狀態域信息在頭結點表中找到某狀態，然后繼續匹配，此舉降低了goto函數的計算時間,提高了算法效率。

2.2.2跳轉標記及匹配標記

(1) 跳轉標記。考慮到漢字散度較高,本文在構造跳轉距離表時借鑒了BMH算法,構建鏈表時添加1列跳轉距離標記,能同步完成狀態查詢和跳轉距離查詢,提高了時間效率。

設當前模式串的長度為l,最短模式串長度為m,字符“c”在有限狀態自動機中的狀態為s,在模式串中的位置為p。字符“c”的跳轉距離d(c)=l-p(c),初始時跳轉距離表為空,查詢跳轉距離表,依次取出模式串中的每個字符；若字符“c”未出現在跳轉距離表中,則將跳轉距離和狀態s寫入到跳轉距離表中;否則,將查詢到的跳轉距離d′(c)與d(c)的較小者和狀態s寫入到跳轉距離表中。模式串的尾字符跳轉距離設為l,未在模式串中出現的字符(統一用*表示)跳轉距離取為m。模式串集P={好聲音,熱播,平凡人,奇跡,理念}的跳轉距離見表1所列。

表1　跳轉距離表

在鏈表中設置跳轉標記,可以同步完成狀態查詢和跳轉距離查詢,避免了重復多次查找帶來的時間開銷,提高了算法的時間效率。

(2) 匹配標記。由于模式串中的字符在文本串中往往不止1次出現,會造成模式串重復匹配的情況,也會出現模式串的首字符或前幾個字符匹配,但后面字符匹配失敗的情況,即半匹配。設置匹配標記,能有效避免重復匹配和部分匹配導致的時間開銷,隨著匹配的進行,標記的作用越來越明顯。

在匹配桶中為每個字符后增加1項匹配標記,用于記錄字符在模式串中出現的次數。匹配標記是動態的,每成功匹配1個模式串,對應的標記位減1,當某零狀態的標記為0時則直接跳過,不再匹配該模式串。模式串集P={好聲音,熱播,平凡人,奇跡,理念},各模式串首字符帶標記的匹配桶如圖5所示,其中“首域”指首字節域,“跳域”指跳轉狀態域,“匹域”指匹配標記域。

圖5　帶匹配標記的匹配桶

模式串集P={好聲音,熱播,平凡人,奇跡,理念}的混合存儲結構如圖6所示,其中,首字節桶如圖2所示,匹配桶如圖5所示。

圖6　帶標記的混合存儲結構

3　本文的多模式匹配算法

本文基于漢字編碼特征,提出一種優化查找方法,首先查找首字節桶，僅當查找成功時才查找匹配桶，減少了匹配桶查找次數。此外,設置標記,減少重復匹配和部分匹配以及重復查找跳轉距離帶來的時間開銷。

3.1預處理

預處理需構造有限狀態自動機及計算轉移函數goto、失效函數failure和輸出函數output,根據有限狀態自動機建立帶標記的鏈表,并建立首字節桶和匹配桶。

設模式串集合P={p1,p2,…,pi,…,pn},模式串pi的長度為li,字符 “c”在有限狀態自動機對應的狀態為s,在pi中的位置為local (c)。

(1) 有限狀態自動機的構造過程與AC算法一樣。

(2) 構建初始鏈表。建立頭節點表v,用于記錄單鏈表頭地址。對于模式串集中的每個模式串pi,初始狀態為狀態0。逐個取出模式串pi中的每個字符,搜索首個頭節點表v后面的單鏈表的字符域;若找到字符域為該字符的節點,則將該節點的狀態域的值i作為當前狀態,并跳轉到v[i];否則,添加1個新頭節點,新節點的狀態域為已有的最大狀態加1,字符域為當前讀入的模式串的字符,繼續對pi中的下一個字符進行處理。

(3) 構建帶標記的鏈表。首先,構造跳轉距離表。在頭節點表狀態列后增加1列,根據跳轉距離表，將跳轉標記加上去。然后,設置初始匹配標記。在構建鏈表時,新的表節點中的匹配標記域設為1,當零狀態中再次出現已存在的字符,其匹配標記域加1,匹配標記記錄模式串中字符在零狀態中出現的次數。

(4) 計算failure函數及output函數。計算過程同AC 算法。

(5) 構建首字節桶和匹配桶。

3.2匹配過程

(1) 將當前狀態s初始化為0,文本串指針指向文本串的首字符。

(2) 若文本串指針不為空,則取出所指的字符“c”,否則匹配過程結束。

(3) 利用狀態轉移函數,計算s′=goto(s,c)。若s=0,首先查找首字節桶,如果查找成功則繼續查找匹配桶,根據匹配桶中的跳轉狀態域值跳轉到鏈表中繼續匹配,同時查看匹配標記，如果為0則跳轉;如果查找失敗則跳轉。

(4) 若s′≠fail,則s=s′;否則,轉步驟(5)。若output(s)=NULL,轉步驟(2);如果output(s)≠NULL,輸出output(s)的值,表示有模式串匹配成功,將模式串中字符對應的匹配標記減1，轉步驟(2)。

(5) 調用failure函數,計算當前狀態s=failure(s)。

(6) 若s≠0,根據當前狀態s直接在帶跳轉標記的頭節點鏈表中的“跳轉距離域”得到跳轉距離d,文本串指針向右移動d位,轉步驟(2)。

例如,模式串集P={好聲音,熱播,平凡人,奇跡,理念},文本串為“中國好聲音的熱播再次將平凡人創造奇跡的選秀理念推向高潮”，匹配過程見表2所列。

表2　匹配過程表

4　時間復雜度分析

基于有限狀態自動機的多模式匹配算法的時間開銷主要分為計算goto狀態轉移函數和跳躍式匹配過程2個部分。

(1) goto狀態轉移函數時間復雜度。帶標記位的鏈表存儲方式計算goto狀態轉移函數，實質上是2次直接存取,首先在首字節桶中查找,再查找匹配桶,首字節桶的大小為126,匹配桶一共190個,根據漢字編碼特征,匹配桶中最多只有126組數據,3次都是常量級的查找,所以時間復雜度為O(1)。

(2) 跳躍式匹配時間復雜度。跳躍式匹配的時間復雜度與各個字符出現的概率有關。文獻[5]中提出了一種概率模式,即通過發現失配字符所花的代價和能夠跳轉的距離之比來計算跳躍式匹配的時間復雜度,計算公式為:

時間復雜度=

(1)

其中,m表示模式串在長度為m處失配;cost()為搜索所花的代價；prob()為發生失配的概率;k為失配時可跳轉的距離;skip(m,k)為失配后可跳轉的概率。

考慮到有限狀態自動機對跳躍式匹配過程的影響,本文對這一模型進行拓展,計算公式為:

時間復雜度=

(2)

其中,seanum(k)表示為得到跳轉距離k,在跳轉距離表中搜索的次數;n為重復匹配和半匹配的次數。通常,不同的跳躍式匹配算法的cost(m)、prob(m)及skip(m,k)基本相同,本文算法可同時完成狀態和跳轉距離的查詢,seanum(k)為1,而其他跳躍式匹配算法如AC_BM、IACBM等需搜索跳轉距離表,seanum(k)遠大于1。同時,在文本串中與模式串中首字符相同的字符常不止1處,因此n常大于1。而本文算法n=1,因此,本文算法跳躍式匹配過程的時間性能最優。

5　測試結果與分析

測試環境:CPU為Intel(R) Core(TM) i5-3210M,2.50 GHz,內存2 G,操作系統為Microsoft Windows 7 Professional Service Pack 1,VC++6.0語言實現。

為了驗證算法的有效性,選取AC_BM、IACBM、AC_Tuned BM算法進行對比。4種算法的平均跳轉距離如圖7所示。

圖7　4種不同算法的平均跳轉距離

模式串集取自百度過濾關鍵詞集,關鍵詞集中二字詞、三字詞、四字詞、多字詞約占61.8%、12.7%、22.6%、2.9%。每次實驗從中隨機取出一定數量的中文模式串。測試文本為5個不同的中文文本(約為13 M),每個文本測試10次,最后取其平均值。從圖7可知,隨著模式串的增加,本文算法跳轉距離約為AC_BM算法平均跳轉距離的1.6倍,AC_Tuned BM算法的1.4倍,IACBM算法的1.3倍。跳躍式匹配算法的時間性能很大程度上取決于平均跳轉距離，平均跳轉距離越大，則時間性能越好，因此，本文算法的時間性能最優。

6　結　　論

考慮到漢字的散度較高,本文對零狀態的查找做了優化處理,加快了查找速度;同時設置跳轉標記和匹配標記,有效降低了查找跳轉距離和重復匹配以及部分匹配帶來的時間開銷。最后對不同匹配算法的平均跳轉距離進行了測試,測試結果及分析表明,本文算法的平均跳轉距離和時間性能都優于AC_BM算法、AC_Tuned BM算法及IACBM算法。

[1]趙珂,逯鵬,李永強.基于 Lucene 的搜索引擎設計與實現[J].計算機工程,2011,37(16):39-41.

[2]董明明,鞏青歌,張琦.入侵檢測系統中模式匹配算法的改進 [J].計算機應用與軟件,2011,28(5): 272-274.

[3]鄭禮良,吳國鳳,胡曉明,等.基于Snort的入侵檢測系統的研究與改進[J].合肥工業大學學報(自然科學版),2011,34(4):529-532.

[4]WHEELER D L,CHAPPEY C,LASH A E,et al.Database resources of the National Center for Biotechnology Information[J].Nucleic Acids Research,2007,28(1):10-14.

[5]BOYER R S,MOORE J S.A fast string searching algorithm[J].Communications of the ACM,1977,20(10):762-772.

[6]HORSPOOL R N.Practical fast searching in strings[J].Software：Practice and Experience,1980,10(6):501-506.

[7]AHO A V,CORASICK M J.Efficient string matching: an aid to biographic search[J].Communications of the ACM,1975,18(6):333-340.

[8]COMMENTZ-WALTER B.A string matching algorithm fast on the average [C]//Proceedings of 6th ICALP,1979:118-132.

[9]殷麗華,方濱興,張宏莉.快速的多模式匹配算法[J].哈爾濱工業大學學報,2007,39(12):1925-1929.

[10]陳牮華.網絡入侵檢測系統中的模式匹配算法優化研究[J].計算機仿真,2011,28(2):160-162.

[11]王永成,沈州,許一震.改進的多模式匹配算法[J].計算機研究與發展,2002,39(1):55-60.

[12]NORTON M.Optimizing pattern matching for intrusion detection [EB/OL].(2006-05-11)[2015-03-10].https://static.aminer.org/pdf/PDF/000/309/890/optimizing-pattern-matching.pdf.

[13]杜文超,陳庶樵.一種基于雙重狀態編碼的多模式匹配算法[J].計算機應用研究,2012,29(5):1887-1890.

[14]張元競,張偉哲.一種基于位圖的多模式匹配算法[J].哈爾濱工業大學學報,2010,42(2):277-280.

[15]侯整風,楊波,朱曉玲.一種節約內存的中文多模式匹配算法[J].微型機與應用,2013,32(13):53-57.

(責任編輯張淑艷)

A Chinese multi-pattern matching algorithm based on the characteristic of Chinese character coding

HUANG Yu, HOU Zhengfeng, YU Hu, LIU Chunhui

(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

For large-scale patterns in Chinese string matching, the higher divergence of Chinese characters makes zero state in finite state automata of AC algorithm overlong, and this leads to sharp decline in the efficiency of algorithm. For this problem, a new algorithm based on the characteristic of Chinese character coding is proposed. Considering the range of the first byte in characters is smaller than that of the trail byte, this algorithm finds the first byte first, and then searches the trail byte, if fails, jump directly, reducing the search time. Through setting tags to characters of zero state, reduplicate and partial matching can be avoided effectively, which improves the matching efficiency.

AC algorithm; multi-pattern matching; characteristic of Chinese character coding; tag

2015-03-27；

2015-04-21

教育部廣東省產學研資助項目(2009B090200049)

黃宇(1988-),男,安徽淮南人,合肥工業大學碩士生;

侯整風(1958-),男,安徽和縣人,合肥工業大學教授,碩士生導師.

10.3969/j.issn.1003-5060.2016.08.011

TP393.08

A

1003-5060(2016)08-1060-06