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

謝常達?王小雨?鄭偉

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

關鍵詞：AC算法；檢測系統；網絡安全

1、引言

互聯網被廣泛應用的軍事領域也存在著各種干擾和破壞網絡的現象，從而產生了網絡戰。本文主要介紹了一種空間高效的AC改進算法。

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

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

2.1狀態實現方法

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

2.2函數的實現

各函數的實現算法如下。

（1） Ne（i）函數算法：

輸入：i是一個節點；輸出：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）函數算法：

輸入：i是一個節點；輸出：節點i的地址。

Le表示一條邊數據結構的長度

表示Ne（i）

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

返回 ad

（3）Failure（i， a）函數算法：

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

表示Ne（i）

如果x=1，那么返回根節點

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

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

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

3、結論

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

參考文獻：

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

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