空间高效的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.