摘  要： AC（Aho-Corasick）自動機(jī)是經(jīng)典的多模式匹配算法,，但在模式串字符集較大的情況下,，AC自動機(jī)的存儲開銷較大。為降低存儲開銷提出了存儲優(yōu)化的多模式匹配算法SMMA,，該算法在Trie樹建立階段利用正向表來存儲每個(gè)狀態(tài)的后續(xù)狀態(tài)指針以及失配指針,，而無需存儲字符集所有字符的后繼指針，從而壓縮了每個(gè)狀態(tài)的儲存空間,。實(shí)驗(yàn)表明,，所提出的算法與AC自動機(jī)算法在時(shí)間效率上相近，但極大地降低了存儲開銷,。

　　關(guān)鍵詞： 模式匹配,；AC自動機(jī)；Trie樹

0 引言

　　模式匹配算法一直是信息領(lǐng)域的研究熱點(diǎn),，廣泛應(yīng)用于入侵檢測,、生物信息學(xué)、模式識別等領(lǐng)域[1],。模式匹配算法可以分為單模式匹配算法[2-3]和多模式匹配算法[4-8],。Aho-Corasick算法[4]（以下簡稱AC算法）是經(jīng)典的多模式匹配算法，它把所有模式串構(gòu)建成Trie樹,，并進(jìn)一步預(yù)處理得到有限狀態(tài)自動機(jī),，對主串的一次掃描即可完成所有模式串的匹配。Commentz-Walter算法（CW算法）[5]建立反向自動機(jī),，在模式匹配階段利用壞字規(guī)則和好后綴規(guī)則,，在失配時(shí)滑動最大的距離，實(shí)現(xiàn)了模式串的跳躍匹配,，減少了時(shí)間開銷。Wu-Manber（WM）算法[6]對多模式串進(jìn)行預(yù)處理,，建立三張映射表進(jìn)行部分匹配,，最后進(jìn)行全模式匹配，提高了效率,。參考文獻(xiàn)[7]提出了改進(jìn)的多模式匹配算法,，在DFSA算法的基礎(chǔ)上，結(jié)合QS算法[8]思想，利用匹配過程中匹配失敗信息,，跳過盡可能多的字符,。

　　AC算法的一個(gè)不足是需要為自動機(jī)每個(gè)狀態(tài)分配空間，在模式串字符集比較大的情況下,，算法空間復(fù)雜度比較大,。極端情況下，需要使用外存來保存匹配過程的中間信息,，嚴(yán)重影響算法效率,。為此，參考文獻(xiàn)[9]提出基于異構(gòu)隱式存儲的多模式匹配算法,，從橫向扇出壓縮與縱向路徑壓縮入手,，減少了空間開銷，但算法的空間壓縮率不高,，且算法效率有所降低,。參考文獻(xiàn)[10]通過選擇性分群減小匹配算法的空間復(fù)雜度，有效解決導(dǎo)致DFA狀態(tài)膨脹的問題,。參考文獻(xiàn)[11]提出了對DFA進(jìn)行高效存儲的方法,，從DFA狀態(tài)數(shù)目和狀態(tài)轉(zhuǎn)移數(shù)目兩方面進(jìn)行壓縮。在復(fù)合的FSM中,，利用新的正則特征,，進(jìn)一步存儲壓縮，但是算法實(shí)現(xiàn)復(fù)雜,、壓縮性能不穩(wěn)定,、時(shí)間效率不高，實(shí)際工程應(yīng)用不理想,。為了減少自動機(jī)各結(jié)點(diǎn)的存儲空間,，TUCK N等人[12]在每個(gè)結(jié)點(diǎn)中增加一個(gè)位圖數(shù)據(jù)，以記錄當(dāng)前結(jié)點(diǎn)所有的下一層結(jié)點(diǎn)的狀態(tài),，壓縮了存儲空間,。AC-bitmap[13]則將自動機(jī)的所有結(jié)點(diǎn)按模式樹結(jié)構(gòu)的層數(shù)進(jìn)行劃分，使得兩種存儲方式共存,，以壓縮算法的存儲空間,。但是，基于位圖壓縮自動機(jī)算法要求采用連續(xù)的地址空間存儲,，以加快轉(zhuǎn)移時(shí)的查找速度,，算法實(shí)現(xiàn)比較復(fù)雜，并且算法要求為每個(gè)結(jié)點(diǎn)存儲一個(gè)位圖信息,，隨著字母表的不斷增大,，其存儲空間將迅速增大。

　　為更好地優(yōu)化多模式匹配算法的空間復(fù)雜度，本文提出了基于存儲優(yōu)化的多模式匹配算法（Storage-optimized Multi-pattern Matching Algorithm,，SMMA）,。該算法在建立Trie樹時(shí)，動態(tài)建立自動機(jī)上每個(gè)狀態(tài)結(jié)點(diǎn)的字符集,，只保留Trie樹上的有效路徑信息,，以保證用最小的空間代價(jià)存儲模式串的所有信息，避免了無效字符路徑的創(chuàng)建,，壓縮了儲存空間,。在模式匹配階段，通過在自動機(jī)上的狀態(tài)轉(zhuǎn)移完成匹配,。在保持算法時(shí)間復(fù)雜度不變的情況下,，顯著降低了算法的空間開銷。

1 相關(guān)概念

　　定義1 設(shè)p為Trie樹的一個(gè)結(jié)點(diǎn),，則Trie樹中從根結(jié)點(diǎn)到結(jié)點(diǎn)p的簡單路徑上所有字符組成的字符序列稱為結(jié)點(diǎn)p的路徑,，記為path（p）。構(gòu)成path（p）中字符的個(gè)數(shù)稱為結(jié)點(diǎn)p的路徑長度,，記為Len（p）,。

　　定義2 設(shè)p為Trie樹的一個(gè)結(jié)點(diǎn)，若結(jié)點(diǎn)p的路徑path（p）是一個(gè)模式串,，則稱結(jié)點(diǎn)p為匹配點(diǎn),，否則稱為非匹配點(diǎn)。

　　定義3 自動機(jī)M是一個(gè)五元組：M=（Q,，?撞,，g，q0,，F(xiàn)）,。其中：Q是有窮狀態(tài)集；?撞是字母表,；g是轉(zhuǎn)移函數(shù),，轉(zhuǎn)向下一個(gè)狀態(tài)；q0是初始狀態(tài),；F是自動機(jī)M上的終止?fàn)顟B(tài)集,。

　　定義4 設(shè)pa、p為自動機(jī)上的狀態(tài)結(jié)點(diǎn),，c為字符集中的一個(gè)字符,，若?堝p，pa,，c，path（p）=c+path（pa），p∈Q,，pa∈Q,，c∈（sigma），則稱pa為p的后綴結(jié)點(diǎn),，記為S（p）,。

　　定義5 設(shè)p為Trie樹的一個(gè)結(jié)點(diǎn)，當(dāng)且僅當(dāng)結(jié)點(diǎn)p或其后綴結(jié)點(diǎn)為匹配點(diǎn),，結(jié)點(diǎn)p具有匹配性,。

　　定義6 設(shè)p為自動機(jī)上的一個(gè)狀態(tài)結(jié)點(diǎn)，則稱Len（S（p））為結(jié)點(diǎn)p的匹配長度,。

2 SMMA模式匹配算法

　　2.1 SMMA算法的基本思想

　　SMMA算法包括三個(gè)階段：建立Trie樹階段,、建立自動機(jī)階段和模式匹配階段。SMMA算法在建立Trie樹時(shí),，并不像傳統(tǒng)的AC自動機(jī)那樣為每一個(gè)結(jié)點(diǎn)開辟字符集大小的后繼指針空間,，而是根據(jù)具體的模式串信息動態(tài)地?cái)U(kuò)增Trie樹結(jié)點(diǎn)的后繼指針空間，因此只保留Trie樹上的有效路徑信息,，避免了無效字符路徑的創(chuàng)建,，壓縮了儲存空間。在實(shí)現(xiàn)時(shí),，SMMA用正向表來存儲Trie樹,。

　　建立自動機(jī)和模式匹配階段都有查詢當(dāng)前結(jié)點(diǎn)cur的某個(gè)后繼ch的操作goto（cur，ch）,。若當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)不存在,，則繼續(xù)查詢goto（fail[cur]，ch）,。為了快速求得所需的后繼結(jié)點(diǎn),，本文用Next（cur，ch）函數(shù)獲得后繼結(jié)點(diǎn)編號,，Next（）函數(shù)的實(shí)現(xiàn)在2.3節(jié)介紹,。

　　2.2 正向表

　　正向表是一種邊表，空間代價(jià)與鄰接表相當(dāng),，由于正向表沒有使用指針而減少了一部分結(jié)構(gòu)性開銷,，在存儲樹和稀疏圖時(shí)具有巨大優(yōu)勢。將正向表應(yīng)用于AC自動機(jī)多模式匹配算法,，可以壓縮所需的存儲空間,，減少算法空間開銷。

　　2.3 結(jié)點(diǎn)后繼獲得函數(shù)Next（）

　　算法1 結(jié)點(diǎn)后繼獲得函數(shù)Next（x,，c）

　　輸入：當(dāng)前結(jié)點(diǎn)編號x,，轉(zhuǎn)移字符c

　　輸出：當(dāng)前結(jié)點(diǎn)x以字符c為轉(zhuǎn)移條件的后繼結(jié)點(diǎn)編號

　?、俪跏蓟呏羔榠←head[x]；

　?、谌暨呏羔榠為空,，則轉(zhuǎn)到⑤；

　?、廴鬳dge[i].ch==c,，則返回edge[i].to結(jié)點(diǎn)的編號；

　?、苓呏羔榠指向下一條邊：i←edge[i].next,，并轉(zhuǎn)到②；

　?、萑艚Y(jié)點(diǎn)x為根結(jié)點(diǎn),，則返回0（根結(jié)點(diǎn)編號）；

　?、捱f歸調(diào)用結(jié)點(diǎn)后繼獲得函數(shù),，返回Next（tree[x].fail，c）,。

　　2.4 建立Trie樹階段

　　算法2 模式串插入算法

　　輸入：待插入字符串a(chǎn)rr[],，待插入字符串的標(biāo)號index

　　輸出：將字符串a(chǎn)rr[]插入Trie樹

　　①初始化字符指針i←0,，設(shè)置當(dāng)前結(jié)點(diǎn)指針cur←0（Trie樹根結(jié)點(diǎn)）,，計(jì)算字符串長度len←strlen（arr）；

　?、谌鬷≥len,，則轉(zhuǎn)到{13}；

　?、鄢跏蓟呏羔榡←head[cur],；

　　④若邊指針j為空,，則轉(zhuǎn)到⑦,；

　　⑤若edge[j].ch==arr[i],，則轉(zhuǎn)到⑦,；

　　⑥邊指針j指向下一條邊：j←edge[j].next,，并轉(zhuǎn)到④,；

　　⑦若邊指針j非空,，則轉(zhuǎn)到⑨,；

　?、嗲蹇战Y(jié)點(diǎn)編號為nodeNo的結(jié)點(diǎn)，增加一條以cur為源點(diǎn),，以nodeNo為終點(diǎn),，邊上的字符為arr[i]的有向邊，并依次設(shè)置cur←nodeNo,，nodeNo←nodeNo+1，轉(zhuǎn)到⑩,；

　?、釋dge[j].to結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)：cur←edge[j].to；

　?、馊鬷!=len-1,，則轉(zhuǎn)到{12}；

　　{11}更新當(dāng)前結(jié)點(diǎn)信息：tree[cur].end←index,，tree[cur].len←len,，tree[cur].isDanger←True；

　　{12}設(shè)置i←i+1,，轉(zhuǎn)到②,；

　　{13}插入完成，返回,。

　　2.5 建立自動機(jī)階段

　　建立自動機(jī)是實(shí)現(xiàn)SMMA算法的關(guān)鍵,。建立自動機(jī)時(shí)，需要對Trie樹進(jìn)行廣度優(yōu)先遍歷（Breadth First Search,，BFS）,，預(yù)處理Trie樹上每個(gè)結(jié)點(diǎn)的后綴結(jié)點(diǎn)、匹配性等信息,，以便在模式匹配階段快速轉(zhuǎn)移狀態(tài),，在失配時(shí)，能根據(jù)建立自動機(jī)階段預(yù)處理出的信息快速確定所需要的后繼狀態(tài),。利用Next（）函數(shù)快速返回其后綴結(jié)點(diǎn)的編號,。

　　算法3 自動機(jī)建立算法

　　輸入：Trie樹Tree[]

　　輸出：建立自動機(jī)

　　①初始化隊(duì)列Q的隊(duì)頭指針l和隊(duì)尾指針h：l←0,，h←0,，并設(shè)置邊指針i←head[0]；

　?、谌暨呏羔榠為空,，則轉(zhuǎn)到⑤；

　?、蹖dge[i].to結(jié)點(diǎn)放入隊(duì)尾：Q[h]←edge[i].to,，h←h+1,，并設(shè)置edge[i].to結(jié)點(diǎn)的后綴結(jié)點(diǎn)為自動機(jī)的起始結(jié)點(diǎn)：tree[edge[i].to].fail←0；

　?、苓呏羔榠指向下一條邊：i←edge[i].next,，并轉(zhuǎn)到②；

　?、萑鬺≥h,，則轉(zhuǎn)到⑩；

　?、拊O(shè)置當(dāng)前結(jié)點(diǎn)指針cur：cur←Q[l],，l←l+1，并設(shè)置邊指針i←head[cur],；

　?、呷暨呏羔槥榭眨瑒t轉(zhuǎn)到⑤,；

　?、嗬媒Y(jié)點(diǎn)后繼獲得函數(shù)計(jì)算edge[i].to結(jié)點(diǎn)的后綴結(jié)點(diǎn)：tree[edge[i].to].fail←child（tree[cur].fail，edge[i].ch）,，更新edge[i].to結(jié)點(diǎn)的信息并將該結(jié)點(diǎn)放入隊(duì)尾：tree[edge[i].to].isDanger←tree[edge[i].to].isDanger|tree[tree[edge[i].to].fail].isDanger,，Q[h]←edge[i].to，h←h+1,；

　?、徇呏羔榠指向下一條邊：i←edge[i].next，并轉(zhuǎn)到⑦,；

　?、庾詣訖C(jī)建立完成，返回,。

　　2.6 模式匹配階段

　　從自動機(jī)的初始狀態(tài)結(jié)點(diǎn)開始,，以主串中各字符為轉(zhuǎn)移條件，用Next（）函數(shù)返回當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn),，再將當(dāng)前結(jié)點(diǎn)指針cur轉(zhuǎn)移到該后繼結(jié)點(diǎn)上,。若該結(jié)點(diǎn)未被訪問并且具有匹配性，則設(shè)置臨時(shí)結(jié)點(diǎn)指針p,，并賦初值為cur,，同時(shí)標(biāo)記該結(jié)點(diǎn)為已訪問的結(jié)點(diǎn)，根據(jù)具體需要獲取數(shù)據(jù)信息,，再將結(jié)點(diǎn)指針p轉(zhuǎn)移到結(jié)點(diǎn)p的后綴結(jié)點(diǎn)上,。

3 算法的時(shí)空復(fù)雜度

　　設(shè)自動機(jī)的狀態(tài)結(jié)點(diǎn)個(gè)數(shù)為N，字符集規(guī)模為∑,，文本主串長度為L,，模式串集合大小為P,，模式串集合的總規(guī)模為，其中,，l（i）為第i個(gè)模式串的長度,。

　　3.1 空間復(fù)雜度分析

　　在建立自動機(jī)階段，AC算法需要對每個(gè)狀態(tài)結(jié)點(diǎn)建立字符集大小的空間,，空間復(fù)雜度為O（N*?撞）,。SMMA算法對于自動機(jī)的每個(gè)狀態(tài)結(jié)點(diǎn)只保留必要的結(jié)點(diǎn)信息，其所占用的存儲空間大小與自動機(jī)的結(jié)點(diǎn)個(gè)數(shù)呈線性相關(guān),，因此SMMA算法存儲自動機(jī)的空間復(fù)雜度為O（N）,。AC算法和SMMA算法都需要存儲待匹配的文本主串和各模式串的信息，存儲待匹配的文本主串的空間復(fù)雜度為O（L）,，存儲模式串集合具體信息的空間復(fù)雜度為）。

　　因此,，AC算法的總空間復(fù)雜度為∑+L）,，SMMA算法的總空間復(fù)雜度為+L）。但隨著字符集規(guī)?！坪湍Ｊ酱螾的增大,，AC算法的空間消耗的增長速度遠(yuǎn)快于SMMA算法。

　　3.2 時(shí)間復(fù)雜度分析

　　在建立Trie樹階段,，在插入模式串的每個(gè)字符時(shí)都需要遍歷當(dāng)前結(jié)點(diǎn)的所有后繼結(jié)點(diǎn),，該階段最差時(shí)間復(fù)雜度為。

　　在建立自動機(jī)階段,，SMMA算法需要通過BFS序遍歷所有結(jié)點(diǎn),，預(yù)處理出每個(gè)狀態(tài)結(jié)點(diǎn)的后綴結(jié)點(diǎn)、匹配性等重要信息,，對于Trie樹上的每一條從根到葉的路徑上的結(jié)點(diǎn)來說,，它們的后綴結(jié)點(diǎn)離根的距離一般是逐層增長的，若不是,，則進(jìn)行多次回溯,，而回溯的總次數(shù)不會大于路徑上的結(jié)點(diǎn)個(gè)數(shù)，其平均時(shí)間復(fù)雜度為O（l（i）*∑）,，所以建立自動機(jī)階段的最差時(shí)間復(fù)雜度為O（N*∑）,。

　　在主串匹配階段，SMMA算法轉(zhuǎn)移所需的時(shí)間復(fù)雜度為O（∑）,。由于可能出現(xiàn)主串失配的情況而需要多次回溯查找后繼結(jié)點(diǎn),，但每次失配時(shí)，回溯查詢的次數(shù)最多僅為當(dāng)前結(jié)點(diǎn)所在層的深度,。因此最壞情況下進(jìn)行了主串長度次回溯,，其平均時(shí)間復(fù)雜度為O（L*∑）,，而設(shè)立臨時(shí)結(jié)點(diǎn)指針回溯查詢具有相同后綴的模式串的次數(shù)不會超過自動機(jī)的狀態(tài)結(jié)點(diǎn)數(shù)，其最差時(shí)間復(fù)雜度為O（N）,，因此主串匹配階段的總時(shí)間復(fù)雜度為O（L*∑+N）,。

　　AC算法在建立Trie樹階段的時(shí)間復(fù)雜度為，在建立自動機(jī)階段的時(shí)間復(fù)雜度為O（N*∑）,，在主串匹配階段的時(shí)間復(fù)雜度為O（L）,。

　　綜上所述，SMMA的總時(shí)間復(fù)雜度為O（∑（l（i）*∑）+N*∑+L*∑+N）,，在字符集規(guī)模?撞和模式串集合P不斷增大的情況下,，SMMA算法和AC算法的時(shí)間開銷具有相同數(shù)量級的增長速度。

4 實(shí)驗(yàn)仿真

　　實(shí)驗(yàn)部分測試了SMMA算法,，同時(shí)比較SMMA算法和AC算法,、AC_bitmap算法的時(shí)間開銷和空間開銷。本文隨機(jī)產(chǎn)生100 KB文本主串,，并給出不同字符集大小的模式串集合,，各模式串長度均為100 B，程序運(yùn)行結(jié)果：處理模式串集合,，給出每個(gè)模式串與主串的關(guān)系信息,，例如模式串是否匹配、模式串在主串中的位置等,。實(shí)驗(yàn)所得數(shù)據(jù)如圖1~圖6所示,，其中P為模式串規(guī)模，∑為字符集大小,。

　　分析可見SMMA算法在漸近時(shí)間復(fù)雜度上與AC算法相同,，僅在常數(shù)上有所增加，在模式串規(guī)模擴(kuò)大,、字符集大小增大的情況下,，SMMA算法極大地減少了多模式匹配算法的空間消耗。SMMA算法與AC_bitmap算法的時(shí)空效率十分接近,，平均情況下,，SMMA算法的時(shí)間效率比AC_bitmap算法提升了5.8%，空間消耗減少了16.3%,。但隨著模式串規(guī)模和字符集大小的增加,，SMMA算法的優(yōu)勢更加明顯。

5 結(jié)論

　　本文提出的SMMA算法避免了無效字符路徑的創(chuàng)建,，壓縮了多模式匹配算法的儲存空間,，優(yōu)化了空間效率，有效地改進(jìn)了AC算法在存儲空間上的缺陷。實(shí)驗(yàn)結(jié)果表明,，SMMA算法具有高效的時(shí)空效率,，在模式串規(guī)模與字符集規(guī)模增大的情況下，優(yōu)勢更加明顯,。

　　參考文獻(xiàn)

　　[1] 王培鳳,，李莉.基于Aho-Corasick算法的多模式匹配算法研究[J].計(jì)算機(jī)應(yīng)用研究，2011,，28（4）：1251-1259.

　　[2] KNUTH D E,， MORRIS J H. Pattern matching in strings[J]. SIAM Journal on Computing，1977,，6（2）：323-350.

　　[3] BOYER R S,， MOORE J S. A fast string searching algorithm [J]. Communications of the ACM， 1988,，20（10）：762-772.

　　[4] AHO A V,， CORASICK M J. Efficient string matching： an aid to bibliographic search[J]. Communications of the ACM，1975,，18（6）：330-340.

　　[5] COMMENTS W R. A string matching algorithm fast on the average[C]. Proceedings of the 6th Colloquium on Automata,， Language and Programming[S.1.]： Springer-Verlag， 1979.

　　[6] Wu Sun,， MANBER U. A fast algorithm for multi-pattern searching[Z]. Taiwan， China： Department of Computer Science,， Chung-Cheng University,， 1994.

　　[7] 王永成，沈州,，許一震.改進(jìn)的多模式匹配算法[J].計(jì)算機(jī)研究與發(fā)展,，2002，39（1）：55-60.

　　[8] SUNDAY D M. A very fast substring search algorithm[J]. Communications of the ACM,， 1990,，33（8）：132-142.

　　[9] 李志東，楊武,，張汝波,，等.基于異構(gòu)隱式存儲的多模式匹配算法[J].通信學(xué)報(bào)，2009,，30（3）：119-124.

　　[10] 徐乾,，鄂躍鵬，葛敬國,，等.深度包檢測中一種高效的正則表達(dá)式壓縮算法[J].軟件學(xué)報(bào),，2009，20（8）：2214-2226.

　　[11] 于強(qiáng)，霍紅衛(wèi).一組提高存儲效率的深度包檢測算法[J].軟件學(xué)報(bào),，2011,，22（1）：149-163.

　　[12] TUCK N， SHERWOOD T,， CALDER T,， et al. Deterministic memory efficient string matching algorithms for intrusion detection[C]. Proceedings of the 23rd Annual Joint Conference of IEEE Computer and Communications Societies， New Jersey： IEEE Press,， 2004： 2628-2639．

　　[13] 張?jiān)?，張偉?一種基于位圖的多模式匹配算法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2010,，42（2）：277-280．