谢常达?王小雨?郑伟

摘要：模式匹配在计算机应用中都有着关键的应用。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）函数算法：