空間高效的AC改進算法的研究

謝常達?王小雨?鄭偉

摘要：模式匹配在計算機應(yīng)用中都有著關(guān)鍵的應(yīng)用。AC算法在深度包檢測系統(tǒng)和病毒防治系統(tǒng)中是核心模塊。為了更好的提高網(wǎng)絡(luò)安全，本文提出了一種空間高效的AC改進算法。

關(guān)鍵詞：AC算法；檢測系統(tǒng)；網(wǎng)絡(luò)安全

1、引言

互聯(lián)網(wǎng)被廣泛應(yīng)用的軍事領(lǐng)域也存在著各種干擾和破壞網(wǎng)絡(luò)的現(xiàn)象，從而產(chǎn)生了網(wǎng)絡(luò)戰(zhàn)。本文主要介紹了一種空間高效的AC改進算法。

2、空間高效的AC改進算法

模式匹配[1，2]在計算機應(yīng)用中都有著關(guān)鍵的應(yīng)用。Aho-Corasick算法（AC算法） 在深度包檢測系統(tǒng)和病毒防治系統(tǒng)中是核心模塊。

2.1狀態(tài)實現(xiàn)方法

節(jié)點首先被劃分成兩個組，G0和G1，在組G0中包含了所有邊集合不為空且節(jié)點的失敗值等于根節(jié)點的節(jié)點，G1包含了其余的節(jié)點。第二步，每個組中的節(jié)點根據(jù)每個節(jié)點的邊數(shù)目被進一步劃分成若干個組。本方法使用G來表示有j條邊的屬于組Gi的節(jié)點集合，其中的0≤j≤σ。這樣通過節(jié)點分組，AC自動機的初步表示就能夠被壓縮了。AC自動機節(jié)點被存儲在連續(xù)的存儲器中，節(jié)點v的地址用A（v）表示。節(jié)點按照如下的順序進行存儲。給定兩個節(jié)點v和v，其中v∈G并且v∈G。如果i >i，那么A（v）< A（v）；如果i =i，那么如果j>j，則A（v）< A（v）。對任一節(jié)點v來說，v的索引號（指針）是存儲在v前面節(jié)點的數(shù)目，用Id（v）表示。

2.2函數(shù)的實現(xiàn)

各函數(shù)的實現(xiàn)算法如下。

（1） Ne（i）函數(shù)算法：

輸入：i是一個節(jié)點；輸出：x和z，其中i∈G。

如果i< I_G1，那么x=0，否則x=1

在T_Gx中搜索z，其中T_Gx[z].i≤i≤T_Gx[z+1].i

返回< x， z>

（2）Id_Ad（i）函數(shù)算法：

輸入：i是一個節(jié)點；輸出：節(jié)點i的地址。

Le表示一條邊數(shù)據(jù)結(jié)構(gòu)的長度

表示Ne（i）

ad= T_Gx[z].a+（i- T_Gx[z].i）*z*le

返回 ad

（3）Failure（i， a）函數(shù)算法：

輸入：i是一個節(jié)點，a是節(jié)點i的地址；輸出：i的失敗節(jié)點

表示Ne（i）

如果x=1，那么返回根節(jié)點

否則返回 地址a存放的指針

指定跳轉(zhuǎn)函數(shù)可以由以上的函數(shù)來實現(xiàn)。給定節(jié)點i和一個字母a，i的邊數(shù)目能夠通過Ne（i）函數(shù)計算得出。i的地址能夠通過Id_Ad（i）函數(shù)計算得出。因此如果存在這樣的邊，通過搜索程序本方法能夠通過a找到有標簽的邊。如果沒有這樣的邊，通過Failure（i）函數(shù)本方法能計算出i的失敗值。

通過Ne（i）函數(shù)能夠確定第一類終端節(jié)點。第二類節(jié)點是有邊的節(jié)點，本方法可以使用另一種方式來確定它們。把節(jié)點i設(shè)定為第二類節(jié)點，i節(jié)點的最后一條邊用c來作為標簽。本方法創(chuàng)建一個沒有邊的新節(jié)點，用ti來表示，同時ti∈G<1， 0>這個集合。然后給i增加一條邊，用c來作為標簽同時該邊指向ti。那么在特定跳轉(zhuǎn)函數(shù)Goto（i）中，通過校驗i是否有一條復(fù)制的最后邊來知道i是否是一個第二類終端節(jié)點。通過上述的方法，當(dāng)一個模式出現(xiàn)，本方法可以到達一個沒有邊的節(jié)點，然后計算出被匹配模式的ID。這些模式按照在集合G<1， 0>中的順序來排序。對于集合G<1， 0>中的節(jié)點i并且i是集合G<1， 0>中第d個節(jié)點，i表示ID號為d的模式。

3、結(jié)論

由于該改進算法通過刪除表T_G0和表T_G1從而壓縮了數(shù)據(jù)結(jié)構(gòu)的運算空間，提高了算法的執(zhí)行率，但是會增加搜索時間。在后期的研究中將對搜索時間進行改進，以期達到空間和時間的同步優(yōu)化，最大程度的優(yōu)化算法的效率。

參考文獻：

[1]余恩運、申德榮、張旭、王廣奇、于戈. 一種基于模式結(jié)構(gòu)和已有匹配知識的模式匹配模型[J].計算機科學(xué)，2007.11.

[2]潘峰、李慶忠、董永權(quán). 一種模式匹配和實體統(tǒng)一相互促進的方法[J].計算機與數(shù)字工程，2009.11.