段惠超，韓建民，邱　晟（浙江師范大學(xué)　數(shù)理與信息工程學(xué)院，浙江　金華 321004）

一種存儲(chǔ)優(yōu)化的多模式匹配算法*

段惠超，韓建民，邱晟
（浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華 321004）

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

模式匹配；AC自動(dòng)機(jī)；Trie樹

0　引言

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

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

為更好地優(yōu)化多模式匹配算法的空間復(fù)雜度，本文提出了基于存儲(chǔ)優(yōu)化的多模式匹配算法 （Storage-optimized Multi-pattern Matching Algorithm，SMMA）。該算法在建立 Trie樹時(shí)，動(dòng)態(tài)建立自動(dòng)機(jī)上每個(gè)狀態(tài)結(jié)點(diǎn)的字符集，只保留 Trie樹上的有效路徑信息，以保證用最小的空間代價(jià)存儲(chǔ)模式串的所有信息，避免了無效字符路徑的創(chuàng)建，壓縮了儲(chǔ)存空間。在模式匹配階段，通過在自動(dò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自動(dòng)機(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是自動(dòng)機(jī)M上的終止?fàn)顟B(tài)集。

定義4設(shè)pa、p為自動(dòng)機(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為自動(dòng)機(jī)上的一個(gè)狀態(tài)結(jié)點(diǎn)，則稱Len （S（p））為結(jié)點(diǎn)p的匹配長度。

2　SMMA模式匹配算法

2.1SMMA算法的基本思想

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

建立自動(dòng)機(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)編號(hào)，Next（）函數(shù)的實(shí)現(xiàn)在2.3節(jié)介紹。

2.2正向表

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

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

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

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

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

①初始化邊指針i←head［x］；

②若邊指針i為空，則轉(zhuǎn)到⑤；

③若edge［i］.ch==c，則返回 edge［i］.to結(jié)點(diǎn)的編號(hào)；

④邊指針i指向下一條邊：i←edge［i］.next，并轉(zhuǎn)到②；

⑤若結(jié)點(diǎn)x為根結(jié)點(diǎn)，則返回0（根結(jié)點(diǎn)編號(hào)）；

⑥遞歸調(diào)用結(jié)點(diǎn)后繼獲得函數(shù)，返回 Next（tree［x］. fail，c）。

2.4建立Trie樹階段

算法2模式串插入算法

輸入：待插入字符串 arr［］，待插入字符串的標(biāo)號(hà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）；

③初始化邊指針j←head［cur］；

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

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

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

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

⑧清空結(jié)點(diǎn)編號(hào)為nodeNo的結(jié)點(diǎn)，增加一條以cur為源點(diǎn)，以 nodeNo為終點(diǎn)，邊上的字符為 arr［i］的有向邊，并依次設(shè)置cur←nodeNo，nodeNo←nodeNo+1，轉(zhuǎn)到⑩；

⑨將edge［j］.to結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)：cur←edge［j］.to；

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

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

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

輸入：Trie樹Tree［］

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

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

②若邊指針i為空，則轉(zhuǎn)到⑤；

③將edge［i］.to結(jié)點(diǎn)放入隊(duì)尾：Q［h］←edge［i］.to，h←h+1，并設(shè)置 edge［i］.to結(jié)點(diǎn)的后綴結(jié)點(diǎn)為自動(dòng)機(jī)的起始結(jié)點(diǎn)：tree［edge［i］.to］.fail←0；

④邊指針i指向下一條邊：i←edge［i］.next，并轉(zhuǎn)到②；

⑤若 l≥h，則轉(zhuǎn)到⑩；

⑥設(shè)置當(dāng)前結(jié)點(diǎn)指針 cur：cur←Q［l］，l←l+1，并設(shè)置邊指針i←head［cur］；

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

⑧利用結(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指向下一條邊：i←edge［i］.next，并轉(zhuǎn)到⑦；

⑩自動(dòng)機(jī)建立完成，返回。

2.6模式匹配階段

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

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

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

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

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

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

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ī)模，∑為字符集大小。

圖1　實(shí)驗(yàn)結(jié)果（∑=10）

圖2　實(shí)驗(yàn)結(jié)果（∑=10）

圖3　實(shí)驗(yàn)結(jié)果（∑=100）

圖4　實(shí)驗(yàn)結(jié)果（∑=100）

圖5　實(shí)驗(yàn)結(jié)果（∑=1 000）

圖6　實(shí)驗(yàn)結(jié)果（∑=1 000）

分析可見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)建，壓縮了多模式匹配算法的儲(chǔ)存空間，優(yōu)化了空間效率，有效地改進(jìn)了AC算法在存儲(chǔ)空間上的缺陷。實(shí)驗(yàn)結(jié)果表明，SMMA算法具有高效的時(shí)空效率，在模式串規(guī)模與字符集規(guī)模增大的情況下，優(yōu)勢更加明顯。

［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)隱式存儲(chǔ)的多模式匹配算法［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).一組提高存儲(chǔ)效率的深度包檢測算法［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．

A storage-optimized multi-pattern matching algorithm

Duan Huichao，Han Jianmin，Qiu Sheng
（College of Mathematics，Physics and Information Engineering，Zhejiang Normal University，Jinhua 321004，China）

Aho-Corasick automaton is a classic multi-pattern matching algorithm；however，when the character set of patterns becomes rather large，its storage overhead correspondingly will be much higher.To solve this problem，this paper proposes a storage-optimized multi-pattern matching algorithm（SMMA）.In build-up phase of Trie，the subsequent state pointer and mismatching pointer of each state will be kept in storage based on the indexed table.The algorithm won′t store the subsequent state pointer for entire character set of each state，which contributes to the reduction of storage space.The experiments show that the SMMA can reduce the storage overhead greatly while maintaining its efficiency similar to that of AC automation algorithm.

pattern matching；AC automata；Trie tree

TP391.4

A

1674-7720（2015）02-0014-04

國家自然科學(xué)基金（61170108）；國家級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目（201310345005）

（2014-09-25）

段惠超（1993－），男，本科，主要研究方向：模式匹配算法。

韓建民（1969－），男，博士，教授，主要研究方向：信息安全、軟件工程。