空間高效的AC改進(jìn)算法的研究

謝常達(dá)?王小雨?鄭偉

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

關(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改進(jìn)算法。

2、空間高效的AC改進(jìn)算法

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

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

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

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

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

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

輸入：i是一個(gè)節(jié)點(diǎn)；輸出：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是一個(gè)節(jié)點(diǎn)；輸出：節(jié)點(diǎn)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是一個(gè)節(jié)點(diǎn)，a是節(jié)點(diǎn)i的地址；輸出：i的失敗節(jié)點(diǎn)

表示Ne（i）

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

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

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

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

3、結(jié)論

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

參考文獻(xiàn)：

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

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