汪泓才 李訓(xùn)根

(杭州電子科技大學(xué)電子信息學(xué)院 浙江 杭州 310018)

一種基于分類(lèi)存儲(chǔ)的空間高效Aho-Corasick算法

汪泓才 李訓(xùn)根

(杭州電子科技大學(xué)電子信息學(xué)院 浙江 杭州 310018)

針對(duì)經(jīng)典Aho-Corasick算法存在空間開(kāi)銷(xiāo)大，存儲(chǔ)效率低的問(wèn)題，提出一種改進(jìn)的空間高效Aho-Corasick算法。新算法在預(yù)處理階段根據(jù)狀態(tài)轉(zhuǎn)移函數(shù)、輸出函數(shù)的不同特性，靈活選擇不同的方式存儲(chǔ)狀態(tài)結(jié)點(diǎn)，實(shí)現(xiàn)對(duì)Aho-Corasick算法狀態(tài)機(jī)的壓縮。實(shí)驗(yàn)表明，新算法與經(jīng)典Aho-Corasick算法、Bitmapped AC算法相比，以匹配階段較小的時(shí)間性能為代價(jià)，極大幅度地壓縮狀態(tài)機(jī)的存儲(chǔ)空間。

AC算法 模式匹配 空間高效

0 引 言

Aho-Corasick(簡(jiǎn)稱AC)算法是一種經(jīng)典的多模式匹配算法，有著良好的時(shí)間復(fù)雜度，在許多領(lǐng)域得到了廣泛應(yīng)用。AC算法的一個(gè)典型應(yīng)用就是誤用入侵檢測(cè)。誤用入侵檢測(cè)，指的是通過(guò)監(jiān)視網(wǎng)絡(luò)或計(jì)算機(jī)內(nèi)部的流量數(shù)據(jù)，根據(jù)預(yù)先設(shè)定好的規(guī)則庫(kù)，用模式匹配算法深度檢測(cè)流量數(shù)據(jù)，判斷數(shù)據(jù)是否為惡意數(shù)據(jù)。入侵檢測(cè)系統(tǒng)的規(guī)則庫(kù)通常比較龐大。Snort是一個(gè)被廣泛使用的入侵檢測(cè)系統(tǒng)，它的規(guī)則庫(kù)就多達(dá)3 000余條。使用AC算法去匹配如此大量的規(guī)則庫(kù)，需要大量的空間開(kāi)銷(xiāo)，更難以用硬件直接實(shí)現(xiàn)?；谶@種狀況，本文提出了一種分類(lèi)存儲(chǔ)的AC算法，旨在降低算法的空間開(kāi)銷(xiāo)。

1 AC算法介紹

AC算法分為預(yù)處理與匹配兩個(gè)階段，它在預(yù)處理階段構(gòu)建一個(gè)有限狀態(tài)自動(dòng)機(jī)，然后在匹配階段用狀態(tài)間的轉(zhuǎn)移操作取代字符比較操作，減少不必要的字符比較操作[1]。

預(yù)處理的對(duì)象是模式串集合，目的是構(gòu)造有窮狀態(tài)自動(dòng)機(jī)。在構(gòu)造的狀態(tài)機(jī)中，每個(gè)狀態(tài)結(jié)點(diǎn)都有三個(gè)功能函數(shù)，分別是轉(zhuǎn)移函數(shù)goto、輸出函數(shù)output與失效函數(shù)failure[2]。如有模式串集合P={every, job, enjoy}，可以構(gòu)建圖1所示的狀態(tài)機(jī)。

圖1 {every, job, enjoy}構(gòu)建的狀態(tài)機(jī)

在圖1中，實(shí)線箭頭代表的轉(zhuǎn)移函數(shù)。轉(zhuǎn)移函數(shù)goto(src, c)= tar表示在狀態(tài)src輸入字符c，就轉(zhuǎn)移到狀態(tài)tar。在這里，狀態(tài)tar被稱為狀態(tài)src的轉(zhuǎn)移狀態(tài)。例如，當(dāng)前狀態(tài)是圖1中的“state8”，輸入字符“o”，則當(dāng)前狀態(tài)更新為“state9”。

圖1中的虛線箭頭代表的是失效函數(shù)。失效函數(shù)處理匹配過(guò)程中使用轉(zhuǎn)移函數(shù)失敗的情況。若狀態(tài)tar與狀態(tài)src滿足failure(src)= tar，即狀態(tài)tar是狀態(tài)src的供給狀態(tài)，則表示如果在狀態(tài)src輸入某個(gè)字符后無(wú)對(duì)應(yīng)的轉(zhuǎn)移函數(shù)，就更新?tīng)顟B(tài)為tar。例如，當(dāng)前狀態(tài)是圖1中的“state8”，輸入字符“a”，無(wú)法使用轉(zhuǎn)移函數(shù)更新?tīng)顟B(tài)，就必須使用失效函數(shù)更新?tīng)顟B(tài)為“state11”。還需說(shuō)明的是，在狀態(tài)機(jī)的構(gòu)建中，狀態(tài)的默認(rèn)供給狀態(tài)為初始狀態(tài)。為了簡(jiǎn)潔起見(jiàn)，圖1沒(méi)有繪制這種默認(rèn)的供給關(guān)系。

輸出函數(shù)output(s)={pattern}則意味著在狀態(tài)s匹配到了模式串pattern。

AC算法匹配階段的實(shí)現(xiàn)高效而簡(jiǎn)潔，具體邏輯為：從狀態(tài)機(jī)的初始狀態(tài)出發(fā)，依次讀入被搜索文本的字符，根據(jù)讀入的字符，選擇使用轉(zhuǎn)移函數(shù)或失效函數(shù)更新?tīng)顟B(tài)，如果使用了轉(zhuǎn)移函數(shù)更新為新的狀態(tài)，還需要檢查新的狀態(tài)是否有輸出，若有，則輸出的模式串就是被匹配的。

AC算法時(shí)間復(fù)雜度較低，即使同時(shí)匹配大量的模式串，搜索階段的時(shí)間開(kāi)銷(xiāo)也比較穩(wěn)定。另一方面，AC算法的空間開(kāi)銷(xiāo)與模式串的總長(zhǎng)度呈非線性正比的關(guān)系，這就使得在一些模式串總長(zhǎng)度較長(zhǎng)的場(chǎng)景，狀態(tài)機(jī)的空間占用過(guò)大[3]。

2 AC算法的存儲(chǔ)效率及其改進(jìn)

在AC算法的狀態(tài)機(jī)中，每個(gè)狀態(tài)節(jié)點(diǎn)都需要存儲(chǔ)轉(zhuǎn)移函數(shù)、失效函數(shù)與輸出函數(shù)的信息。轉(zhuǎn)移函數(shù)的信息可以用表格保存，這張表格稱為轉(zhuǎn)移表。表1是圖1中“state1”的轉(zhuǎn)移表。在這張轉(zhuǎn)移表中，字符“n”與“v”的ASCII值為110與118，對(duì)應(yīng)在轉(zhuǎn)移表中編號(hào)為110與118的項(xiàng)存儲(chǔ)goto(state1, “n”)與goto(state1, “v”)的值。對(duì)于“state1”，輸入除“n”與“v”以外的其他字符，都不存在相應(yīng)的轉(zhuǎn)移函數(shù)，對(duì)應(yīng)轉(zhuǎn)移表中其余項(xiàng)的值為一個(gè)特殊的無(wú)效值，用以表示使用轉(zhuǎn)移函數(shù)失敗。在表1中，這個(gè)無(wú)效值為“0”。

表1 “state1”的轉(zhuǎn)移表

轉(zhuǎn)移表通常用指針數(shù)組實(shí)現(xiàn)。在32位機(jī)中，存儲(chǔ)一張規(guī)模為256的轉(zhuǎn)移表需要使用1 024個(gè)字節(jié)。而在實(shí)際應(yīng)用中，這張轉(zhuǎn)移表通常只有少數(shù)的幾個(gè)有效值。過(guò)多的無(wú)效值占據(jù)了大量的空間，造成了AC算法狀態(tài)機(jī)存儲(chǔ)效率低下。為了解決這一問(wèn)題，已有大量的工作嘗試通過(guò)壓縮轉(zhuǎn)移函數(shù)信息以提高AC算法的存儲(chǔ)效率。

2.1 基于稀疏向量壓縮的改進(jìn)

基于稀疏向量壓縮的思想，Norton提出了Banded-Row AC算法[4]。Banded-Row AC算法在AC算法的基礎(chǔ)上，壓縮了轉(zhuǎn)移表中首尾的無(wú)效值。Banded-Row格式的轉(zhuǎn)移表可以使用向量表示，“state1”對(duì)應(yīng)的Banded-Row格式向量為{9, 110, state7, 0, 0, 0, 0, 0, 0, 0, state2}。這個(gè)向量分為三部分解讀。從第三個(gè)元素開(kāi)始的內(nèi)容，即“state7, 0, 0, 0, 0, 0, 0, 0, state2”，被稱為一個(gè)的“有效元素帶”。向量的第一個(gè)元素“9”表示這個(gè)“帶”的長(zhǎng)度為9。向量第二個(gè)元素“110”表示這個(gè)“帶”首個(gè)元素在轉(zhuǎn)移表的第110項(xiàng)。按這種規(guī)則構(gòu)造的Banded-Row格式向量用于替代轉(zhuǎn)移表，能夠顯著降低存儲(chǔ)需求。

Banded-Row AC算法能夠壓縮表中首尾的無(wú)效值，但是，每個(gè)Banded-row格式的向量只有一個(gè)“帶”，無(wú)法壓縮“帶”中間的無(wú)效值。Sparse-Bands AC算法解決了這一問(wèn)題。Sparse-Bands格式的向量與Banded-Row格式的向量相似，但前者在構(gòu)造時(shí)還加入一個(gè)策略：當(dāng)“帶”中間連續(xù)的無(wú)效值個(gè)數(shù)超過(guò)指定的閾值，這個(gè)“帶”將被分成前后兩個(gè)“帶”。這就壓縮了轉(zhuǎn)移表中間的無(wú)效值。

徐紅等提出的雙重壓縮AC算法，在Sparse-Bands AC的基礎(chǔ)上做了進(jìn)一步的改進(jìn)[5]。雙重壓縮AC算法將狀態(tài)機(jī)所有N個(gè)狀態(tài)的轉(zhuǎn)移表視為一張N×256的矩陣。將矩陣中的全為0的列刪除，記入其對(duì)應(yīng)的字符為未用字符，然后再對(duì)各行進(jìn)行Sparse-Bands格式壓縮。在匹配時(shí)，每次使用轉(zhuǎn)移函數(shù)，需判斷輸入字符是否為未用字符，若是，則使用轉(zhuǎn)移函數(shù)失敗。

基于稀疏向量壓縮改進(jìn)的算法相對(duì)于AC算法，存儲(chǔ)效率都有著明顯的提高，但在匹配階段，每次用到轉(zhuǎn)移函數(shù)，都需要額外的計(jì)算[6]。

2.2 位圖AC算法

同樣基于降低存儲(chǔ)開(kāi)銷(xiāo)這一目的，Tuck等提出了位圖AC(BitmappedAC)算法[7]。圖2給出了位圖AC中狀態(tài)的存儲(chǔ)結(jié)構(gòu)。位圖AC的狀態(tài)節(jié)點(diǎn)引入了位圖用以判斷輸入字符是否存在有效的轉(zhuǎn)移函數(shù)值，引入了結(jié)構(gòu)數(shù)組用以存儲(chǔ)有效的轉(zhuǎn)移字符及對(duì)應(yīng)的狀態(tài)結(jié)點(diǎn)地址。在位圖中，每一個(gè)位的值由轉(zhuǎn)移表中每一項(xiàng)的值一一映射得到。若轉(zhuǎn)移表中第k項(xiàng)為一個(gè)有效值，則位圖的第k位為“1”；否則，位圖的第k位為“0”。在匹配階段使用轉(zhuǎn)移函數(shù)，先檢查輸入字符對(duì)應(yīng)位的位圖值是否為“1”。若是“1”，則從結(jié)構(gòu)數(shù)組中讀取下一個(gè)狀態(tài)；若是“0”，則接下來(lái)調(diào)用失效函數(shù)。

圖2 位圖AC狀態(tài)機(jī)中狀態(tài)的存儲(chǔ)結(jié)構(gòu)

位圖的引入降低了算法的存儲(chǔ)需求，提高了cache性能[8]，同時(shí)保持了轉(zhuǎn)移表隨機(jī)訪問(wèn)的特性，在空間性能與時(shí)間性能之間取得了平衡。

3 基于分類(lèi)存儲(chǔ)的AC算法

無(wú)論是AC算法，還是眾多基于AC提高存儲(chǔ)效率的改進(jìn)算法，都使用了單一的方式存儲(chǔ)狀態(tài)結(jié)點(diǎn)。本文介紹一種分類(lèi)存儲(chǔ)狀態(tài)結(jié)點(diǎn)的AC算法。該算法根據(jù)狀態(tài)機(jī)不同特性，靈活選擇不同的方式存儲(chǔ)狀態(tài)結(jié)點(diǎn)。尤為可貴的是，新算法不但能基于經(jīng)典的AC算法改進(jìn)，還能應(yīng)用于Banded-RowAC、位圖AC等多種改進(jìn)算法上，實(shí)現(xiàn)在這些算法的基礎(chǔ)上進(jìn)一步提高空間存儲(chǔ)效率。

3.1 存儲(chǔ)方式

在AC狀態(tài)機(jī)中，大量的狀態(tài)節(jié)點(diǎn)沒(méi)有轉(zhuǎn)移狀態(tài)或者只有一個(gè)轉(zhuǎn)移狀態(tài)。對(duì)于這類(lèi)狀態(tài)結(jié)點(diǎn)，如果直接存儲(chǔ)有效的轉(zhuǎn)移字符及對(duì)應(yīng)轉(zhuǎn)移狀態(tài)的地址，能夠進(jìn)一步降低狀態(tài)機(jī)的空間需求。

基于這種樸素的想法，新算法根據(jù)狀態(tài)的轉(zhuǎn)移函數(shù)有效值個(gè)數(shù)是否大于1這一條件，將狀態(tài)分為兩類(lèi)。第一類(lèi)狀態(tài)是轉(zhuǎn)移函數(shù)的有效值至少有2個(gè)的狀態(tài)，這一類(lèi)狀態(tài)依舊采取原有的轉(zhuǎn)移表或位圖等方式存儲(chǔ)轉(zhuǎn)移函數(shù)的信息。第二類(lèi)狀態(tài)是轉(zhuǎn)移函數(shù)有效值最多只有一個(gè)狀態(tài)，采用直接存儲(chǔ)有效的轉(zhuǎn)移字符nextChar與對(duì)應(yīng)轉(zhuǎn)移狀態(tài)nextNode的方式記錄轉(zhuǎn)移函數(shù)信息。同時(shí)，將nextChar為“0”作為轉(zhuǎn)移函數(shù)有效值個(gè)數(shù)為0的標(biāo)志。圖3展示了使用分類(lèi)存儲(chǔ)后AC算法狀態(tài)存儲(chǔ)結(jié)構(gòu)的變化。為了能夠在匹配階段識(shí)別狀態(tài)結(jié)點(diǎn)的存儲(chǔ)方式，還引入占用一個(gè)字節(jié)大小的標(biāo)識(shí)符flag。

圖3 使用分類(lèi)存儲(chǔ)后AC算法狀態(tài)存儲(chǔ)結(jié)構(gòu)的變化

使用圖3展示的存儲(chǔ)結(jié)構(gòu)，每次使用轉(zhuǎn)移函數(shù)或失效函數(shù)更新為新的狀態(tài)，都必須讀取標(biāo)識(shí)符檢查狀態(tài)的存儲(chǔ)類(lèi)型，存在額外的時(shí)間開(kāi)銷(xiāo)。為了降低這一部分時(shí)間開(kāi)銷(xiāo)，新算法還采用了兩個(gè)措施。

措施一是將原先的兩種存儲(chǔ)方式根據(jù)輸出函數(shù)值是否是空值，進(jìn)一步細(xì)分為四種，若輸出函數(shù)值是空值，則不再存儲(chǔ)這一個(gè)空值。圖4展示了這四種存儲(chǔ)結(jié)構(gòu)。措施一的引入保證了在匹配階段更新為第三類(lèi)或第四類(lèi)狀態(tài)時(shí)，可以直接通過(guò)讀取標(biāo)識(shí)符判斷輸出函數(shù)為空值，減少使用輸出函數(shù)的次數(shù)。

圖4 采用措施一后狀態(tài)存儲(chǔ)結(jié)構(gòu)的變化

措施二是供給狀態(tài)只能為第一類(lèi)或第三類(lèi)狀態(tài)。只有滿足轉(zhuǎn)移函數(shù)有效值個(gè)數(shù)不超過(guò)一個(gè)且不是供給狀態(tài)的狀態(tài)，才能歸為第二類(lèi)或第四類(lèi)狀態(tài)。這就保證了在匹配階段，使用失效函數(shù)更新為新?tīng)顟B(tài)時(shí)，新?tīng)顟B(tài)只可能為第一類(lèi)或第三類(lèi)狀態(tài)，無(wú)需重新讀取標(biāo)志符識(shí)別當(dāng)前狀態(tài)轉(zhuǎn)移函數(shù)的存儲(chǔ)方式。表2展示了采用措施二后四類(lèi)狀態(tài)的使用條件。

表2 四類(lèi)狀態(tài)的使用條件

上述兩個(gè)措施降低了使用分類(lèi)存儲(chǔ)在匹配階段額外的時(shí)間開(kāi)銷(xiāo)。相比于原算法，新算法在每次使用轉(zhuǎn)移函數(shù)到新?tīng)顟B(tài)后，多了檢查存儲(chǔ)類(lèi)型這一操作，但對(duì)于大多數(shù)無(wú)輸出的狀態(tài)，不再需要調(diào)用輸出函數(shù)。

分類(lèi)存儲(chǔ)同樣可以應(yīng)用于Banded-RowAC、Sparse-BandsAC、位圖AC等多種改進(jìn)的AC算法上。要將新算法應(yīng)用于這些改進(jìn)的AC算法，只需要調(diào)整新算法中第一類(lèi)與第三類(lèi)狀態(tài)的轉(zhuǎn)移函數(shù)存儲(chǔ)方式。如將分類(lèi)存儲(chǔ)應(yīng)用于位圖AC算法上，就將第一類(lèi)與第三類(lèi)狀態(tài)中的轉(zhuǎn)移表替換為相應(yīng)的位圖和結(jié)構(gòu)數(shù)組，其余的存儲(chǔ)結(jié)構(gòu)均保持不變。

3.2 預(yù)處理與匹配

新算法的狀態(tài)機(jī)可以在原有算法狀態(tài)機(jī)的基礎(chǔ)上構(gòu)建。遍歷原有算法狀態(tài)機(jī)所有的狀態(tài)結(jié)點(diǎn)，根據(jù)表2所示的使用條件，重新建立相應(yīng)類(lèi)型的狀態(tài)結(jié)點(diǎn)，即可得到新算法的狀態(tài)機(jī)。

在匹配階段，從狀態(tài)機(jī)的初始狀態(tài)出發(fā)，依次讀入被搜索文本的字符。每次使用轉(zhuǎn)移函數(shù)更新?tīng)顟B(tài)后，先檢查標(biāo)識(shí)符，決定是否需要調(diào)用輸出函數(shù)以及如何調(diào)用轉(zhuǎn)移函數(shù)。轉(zhuǎn)移函數(shù)的使用有兩種方式，一是使用相應(yīng)原算法的轉(zhuǎn)移方式，如轉(zhuǎn)移表，Banded-Row向量，位圖等；二是直接讀取nextChar，并嘗試轉(zhuǎn)移到nextNode。每次使用失效函數(shù)更新?tīng)顟B(tài)后，不需要檢查標(biāo)識(shí)符，直接嘗試使用轉(zhuǎn)移函數(shù)，若成功則轉(zhuǎn)移到下一狀態(tài)，若失敗則再次使用失效函數(shù)更新到下一狀態(tài)。

4 實(shí)驗(yàn)與分析

為了證明基于分類(lèi)存儲(chǔ)的AC算法在空間開(kāi)銷(xiāo)方面的優(yōu)勢(shì)，在同一臺(tái)計(jì)算機(jī)上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)的對(duì)象共有四個(gè)，分別是經(jīng)典AC算法、基于分類(lèi)存儲(chǔ)的AC算法、位圖AC算法、基于分類(lèi)存儲(chǔ)的位圖AC算法。將實(shí)驗(yàn)對(duì)象分為2組進(jìn)行對(duì)比，第一組是經(jīng)典AC算法與基于分類(lèi)存儲(chǔ)的AC算法，第二組是位圖AC算法與基于分類(lèi)存儲(chǔ)的位圖AC算法。實(shí)驗(yàn)從狀態(tài)機(jī)的存儲(chǔ)開(kāi)銷(xiāo)與匹配階段時(shí)間開(kāi)銷(xiāo)兩方面評(píng)估算法的性能。實(shí)驗(yàn)的所有算法均用C++實(shí)現(xiàn)，在windows10運(yùn)行，配置為Intel(R)Core(TM)i7 4700HQ2.4GHzCPU，8GB內(nèi)存。

實(shí)驗(yàn)的第一部分是測(cè)試狀態(tài)機(jī)的存儲(chǔ)空間大小。使用四種算法預(yù)處理Snort2.9規(guī)則集中的3348條模式串，分別建立狀態(tài)機(jī)。圖5展示了四種算法建立的狀態(tài)機(jī)的存儲(chǔ)空間。狀態(tài)機(jī)的存儲(chǔ)空間為構(gòu)造完?duì)顟B(tài)機(jī)后使用內(nèi)存與未構(gòu)造狀態(tài)機(jī)前使用內(nèi)存之差。實(shí)驗(yàn)結(jié)果顯示，在經(jīng)典AC算法與位圖AC算法上使用分類(lèi)存儲(chǔ)，狀態(tài)機(jī)的空間僅為原來(lái)的14.9%與36.7%。

圖5 狀態(tài)機(jī)存儲(chǔ)開(kāi)銷(xiāo)的對(duì)比

實(shí)驗(yàn)的第二部分是測(cè)試四種算法的匹配速度。被匹配的文本是來(lái)源于互聯(lián)網(wǎng)的10MB英文文本。直接使用實(shí)驗(yàn)一中的4個(gè)狀態(tài)機(jī)對(duì)文本各進(jìn)行5次匹配，取平均值為最終的測(cè)試數(shù)據(jù)。四種狀態(tài)機(jī)匹配用時(shí)如圖6所示。使用分類(lèi)存儲(chǔ)后的AC算法與位圖AC算法，匹配階段用時(shí)平均增加8.3%和7.9%。

圖6 匹配階段時(shí)間開(kāi)銷(xiāo)的對(duì)比

實(shí)驗(yàn)結(jié)果表明，基于分類(lèi)存儲(chǔ)的AC算法相對(duì)于經(jīng)典AC算法，以匹配階段用時(shí)增加8.3%的代價(jià)，將狀態(tài)機(jī)的空間開(kāi)銷(xiāo)減少為原來(lái)的14.9%。即使是在空間高效的位圖AC算法上使用分類(lèi)存儲(chǔ)，依舊能以匹配階段用時(shí)增加7.9%的代價(jià)，將狀態(tài)機(jī)的空間開(kāi)銷(xiāo)減少為原來(lái)的36.7%。

5 結(jié) 語(yǔ)

基于分類(lèi)存儲(chǔ)的AC算法，與前人的位圖AC，Banded-RowAC等算法的目的相同，都旨在于提高狀態(tài)機(jī)的存儲(chǔ)效率。但相比這些算法，基于分類(lèi)存儲(chǔ)的AC算法的優(yōu)勢(shì)在于它的第一類(lèi)狀態(tài)與第三類(lèi)狀態(tài)能靈活選用轉(zhuǎn)移表，位圖或Banded-Row向量等方式存儲(chǔ)轉(zhuǎn)移函數(shù)的信息，實(shí)現(xiàn)在這些算法的基礎(chǔ)上進(jìn)一步降低存儲(chǔ)開(kāi)銷(xiāo)。但是，在當(dāng)前實(shí)現(xiàn)的算法中，分類(lèi)存儲(chǔ)的方式還比較簡(jiǎn)單，選用存儲(chǔ)方式的條件也是固定的，還可以進(jìn)一步引入其他的存儲(chǔ)方式，并系統(tǒng)性地調(diào)整選取不同存儲(chǔ)方式的條件，評(píng)估不同方式下的時(shí)間性能與空間性能。這將是下一步工作的方向。

[1] Aho A V,Corasick M J.Efficient string matching:an aid to bibliographic search[J].Communications of the ACM,1975,18(6):333-340.

[2] Navarro G,Raffinot M.Flexible pattern matching in strings:practical on-line search algorithms for texts and biological sequences[M].New York,NY,USA:Cambridge University Press,2002:221.

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

[4] Norton M.Optimizing pattern matching for intrusion detection[R].Columbia,MD,USA:Sourcefire Inc,2004.

[5] 徐紅,秦志光.一種面向入侵檢測(cè)的改進(jìn)AC算法[J].微電子學(xué)與計(jì)算機(jī),2010,27(11):109-112.

[6] 董世博,李訓(xùn)根,殷珍珍.一種改進(jìn)的字符串多模式匹配算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(8):133-137.

[7] Tuck N,Sherwood T,Calder B,et al.Deterministic memory-efficient string matching algorithms for intrusion detection[C]//Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies.IEEE,2004:2628-2639.

[8] Wen Y,Chen Z,Ma G,et al.SECOMPAX:a bitmap index compression algorithm[C]//Computer Communication and Networks (ICCCN),2014 23rd International Conference on.IEEE,2014:1-7.

A SPACE-EFFICIENT AHO-CORASICK ALGORITHM BASED ON CLASSIFICATION STORAGE

Wang Hongcai Li Xungen

(SchoolofElectronicsandInformation,HangzhouDianziUniversity,Hangzhou310018,Zhejiang,China)

Aiming at the problem that the classical Aho-Corasick algorithm has large space overhead and low storage efficiency, an improved space-efficient Aho-Corasick algorithm is proposed. In the preprocessing stage, the new algorithm chooses different storage state nodes flexibly according to the different characteristics of the state transfer function and the output function, and achieves the compression of the Aho-Corasick algorithm state machine. Experiments show that compared with the classical Aho-Corasick algorithm and Bitmapped AC algorithm, the new algorithm can greatly reduce the storage space of the state machine at the cost of matching small time performance.

Aho-Corasick algorithm Pattern matching Space-efficient

2016-04-05。汪泓才，碩士生，主研領(lǐng)域：模式匹配。李訓(xùn)根，副教授。

TP301

A

10.3969/j.issn.1000-386x.2017.05.048