AC多模匹配算法

《AC多模匹配算法》由会员分享，可在线阅读，更多相关《AC多模匹配算法（28页珍藏版）》请在金锄头文库上搜索。

1、多模匹配算法title Aho-Corasick自动机算法（简称AC自动机）1975年产生 于贝尔实验室。该算法应用有限自动机巧妙地将字符比较 转化为了状态转移。 该算法的基本思想是这样的： o 在预处理阶段，AC自动机算法建立了三个函数，转向 函数goto，失效函数failure和输出函数output，由此构 造了一个树型有限自动机。 o 在搜索查找阶段，则通过这三个函数的交叉使用扫描 文本，定位出关键字在文本中的所有出现位置。 此算法有两个特点，一个是扫描文本时完全不需要回溯， 另一个是时间复杂度为O(n)，时间复杂度与关键字的数目 和长度无关。AC算法-有限自动机的多模式匹配算法2. 树

2、型有限自动机：树型有限自动机包含一组状态，每个状态用一个数字 代表。状态机读入文本串y中的字符，然后通过产生状态 转移或者偶尔发送输出的方式来处理文本。树型有限自动 机的行为通过三个函数来指示：转向函数g，失效函数f和输出函数output。 例如：对应模式集he, she, his, hers的树型有限自动机图1 a） 转向函数g图1 b） 失效函数f 图1 c） 输出函数output 3. 转向，失效和输出函数的构建 现在说明如何根据一个关键字集建立正确的转向、失 效和输出函数。整个构建包含两个部分，在第一部分确定 状态和转向函数，在第二部分我们计算失效函数。输出函 数的计算则是穿插在第一部

3、分和第二部分中完成。为了构建转向函数，我们需要建立一个状态转移图。 开始，这个图只包含一个代表状态0。然后，通过添加一 条从起始状态出发的路径的方式，依次向图中输入每个关 键字p。新的顶点和边被加入到图表中，以致于产生了一 条能拼写出关键字p的路径。关键字p会被添加到这条路径 的终止状态的输出函数中。当然只有必要时才会在图表中 增加新的边。例如: 对关键字集he, she, his, hers建立转向函数。 向图表中添加第一个关键字，得到：从状态0到状态2的路径拼写出了关键字“he”，我们把输出 “he”和状态2相关联。 添加第二个关键字“she”，得到：输出“she”和状态5相关联。 增加第

4、三个关键字“his”，我们得到了下面这个图。注意 到当我们增加关键字“his”时，已经存在一条从状态0到状 态1标记着h的边了，所以我们不必另外添加一条同样的边。输出“his”是和状态7相关联的 添加第四个关键字“hers”，可以得到：输出“hers”和状态9相关联。在这里，我们能够使用已有的两条边：一条是从状态0到 1标记着h的边；一条是从状态1到2标记着e的边。 这样，图已经成为一棵带根的树。为了完成转向函数 的构建，我们对除了h和s外的其他每个字符，都增加一 个从状态0到状态0的循环。这样，我们得到了如图1 a) 所 示的状态转移图，这个图就代表转向函数。算法1：建立转向函数g。 输入：

5、关键字集P=p1,p2,p3,pr。 输出：转向函数g和部分的output函数。 方法:图2 建立转向函数g的伪代码失效函数是根据转向函数建立的。首先，我们定义状 态转移图中状态s的深度为从状态0到状态s的最短路径。 例如图1 a)起始状态的深度是0，状态1和3的深度是1，状 态2，4，和6的深度是2，等等。 图1 a)d(0) = 0; d(1) = d(3) = 1; d(2) = d(6) = d(4) = 2d(8) = d(7) = d(5) = 3; d(9) = 4 计算思路：先计算所有深度是1的状态的失效函数值，然后 计算所有深度为2的状态，以此类推，直到所有状态（除了状 态0

6、，因为它的深度没有定义）的失效函数值都被计算出。 计算方法：用于计算某个状态失效函数值的算法在概念上 是非常简单的。首先，令所有深度为1的状态s的函数值为f(s) = 0。假设所有深度小于d的状态的f值都已经被算出了，那么 深度为d的状态的失效函数值将根据深度小于d的状态的失效 函数值来计算。 为了计算深度为d状态的失效函数值，我们考虑每个深度 为d-1的状态r，执行以下步骤： Step1：如果对所有状态a的g(r, a) = fail，那么什么都不做 Step2：否则，对每个使得g(r, a) = s存在的状态s，执行以 下操作 记state = f(r)。 零次或者多次令state = f

7、(state)，直到出现一个状态使得 g(state, a) != fail（注意到，因为对任意字符a，g(0, a) != fail，所以这种状态一定能够找到） Step2：记f(s) = g(state, a)以图1 a)为例说明计算的失效函数f； 先令f(1) = f(3) = 0，因为1和3是深度为1的状态。 计算深度为2的状态2，6和4的失效函数。 计算f(2)，令state = f(1) = 0；由于g(0, a) = 0，得到f(2) = 0。 计算f(6)，令state = f(1) = 0；由于g(0, i) = 0，得到f(6) = 0 。 计算f(4)，令state =

8、f(3) = 0； 由于g(0, h) = 1，得到f(4) = 1。 按这种方式继续，最终得到了如图1 b) 所示的失效函数f。 在计算失效函数的过程中，也更新了输出函数。当求出 f(s) = s，时，我们把状态s的输出和状态s，的输出合并到一起 。对于上文中的例子，从图1 a) 我们求出f(5) = 2。这时，把状 态2的输出集，也就是he，增加到状态5的输出集中，这样就 得到了新的输出集合he, she。最终各状态的非空输出集如 图1 c) 所示。 算法2：建立失效函数f。 输入：转向函数g和部分的输出函数output。 输出：失效函数f和完整的输出函数output。 方法:图3 建立失

9、效函数f的伪代码4. 转向函数的构建 图1中树型自动机的状态有0, 1, , 9。某个状态（通常 是0状态）被指定为起始状态。转向函数把一个由状态和输入字符组成的二元组映射成另 一个状态或者一条失败消息。图1 a) 的状态图代表转向函数g。比如,从0到1标记着h 的边表示g(0, h) = 1，如果缺省箭头则表示失败。可见，对除e 和i之外的其他输入字符，都有g(1, h) = fail。所有的树型有限 自动机都有一个共同的特点，即对任何输入字符a, 都有g(0, a) != fail。我们将看到，转向函数在0状态上的这种性质确保 每个输入字符都可以在状态机的一个操作循环内被处理。 举个例子，

10、记树型有限自动机为状态机M。状态机M利用图1的 函数去处理输入文本“ushers”，图4显示了M在处理文本串时 产生的状态转移情况。考虑M在状态4，且当前输入字符为e时的操作循环。由于g(4, e) = 5，状态机进入状态5，文本指针将前进到下一个输入字 符，并且输出output(5)。这个输出表明状态机已经发现输入 文本的第四个位置是“she”和“he”出现的结束位置。在状态5 上输入字符r，状态机M在此次操作循环中将产生两次状态转 移。由于g(5, r) = fail，M进入状态2 = f(5)。然后因为g(2, r) = 8，M进入状态8，同时前进到下一个输入字符。在这次操作 循环中没有

11、输出产生。图4 扫描“ushers”时的状态转换序列 记s为状态机的当前状态，a为输入文本y的当前输入字 符。树型有限自动机的一次操作循环可以定义如下： 1. 如果g(s, a) = s，那么树型有限自动机将做一个转向动 作。自动机进入状态s，而且y的下一个字符变成当前的 输入字符。另外，如果output( s，)不为空，那么状态机 将输出与当前输入字符位置相对应的一组关键字。2. 如果g(s, a) = fail，状态机将询问失效函数f并且进行失 效转移。如果 f(s) = s，那么状态机将以s，作为当前 状态，a为当前输入字符重复这个操作循环。 算法3：树型有限状态机。 输入：一个字符串y

12、=y1y2y3yn（其中yi是一个输入字符）； 一台 包含上述转向函数g，失效函数f和输出函数output的树型 有限自动机。 输出：关键字在y中出现的位置。图5 建立树型有限自动机的算法伪代码5. AC自动机 预处理阶段：转向函数把一个由状态和输入字符组成的二元组映射成 另一个状态或者一条失败消息。失效函数把一个状态映射成另一个状态。当转向函数报 告失效时，失效函数就会被询问。输出状态，它们表示已经有一组关键字被发现。输出函 数通过把一组关键字集（可能是空集）和每个状态相联系的 方法，使得这种输出状态的概念形式化。 搜索查找阶段：文本扫描开始时，初始状态置为状态机的当前状态，而 输入文本y的

13、首字符作为当前输入字符。然后，树型有限自 动机通过对每个文本串的字符都做一次操作循环的方式来处 理文本。 经典的多模式匹配算法- AC自动机。在预处理阶段，AC自动机算法建立了三个函数，转向函 数goto，失效函数failure和输出函数output，由此构造了一 个树型有限自动机。在搜索查找阶段，则通过这三个函数的交叉使用扫描 文本，定位出关键字在文本中的所有出现位置。此算法有两个特点，一个是扫描文本时完全不需要回 溯，另一个是时间复杂度为O(n)，时间复杂度与关键字的 数目和长度无关。1975年，Aho和Corasick提出基于确定性有限自动机 (DFA) 理论的模式匹配算法，这又是模式匹

14、配问题中一个 经典的算法。实际上，多模式匹配算法中，有很大一部分 都是基于自动机理论的，而且有不少都是基于对AC75算法 的改进。1979年，Commentz和Walter.B 发明的算法（简称CW79 算法）结合了BM算法，在AC75的自动机算法上实现了跳跃 扫描文本。除了自动机这种主流多模式匹配思想外还有一种很有 效的想法。这就是哈希（Hashing），Hashing方法的串查 寻最早是在1971年被Harrison介绍，之后得到了充分地分 析。1992年到1996年，台湾人Sun Wu和他的导师Udi Manber发表了一系列的论文 ，详细地介绍了他们设计的匹 配算法，并用此算法实现了一

15、个Unix下类似fgrep的工具： agrep。 AC和QS结合的反向自动机 o 王永成等人受FW92（一种融合了BM的自 动机算法），提出的相类似的结合QS的反 向自动机多模式匹配算法，而且是针对纯 中文的处理算法。 Wu.Sum和Udi.manber的agrep o 92年台湾学者吴升发明的agrep是多模式中最 位著名的快速匹配算法之一，对处理大规模的 多关键字匹配问题有很好的效果。 DAWG-MATCH o DAWG是一种后缀自动机（Suffix Automaton ），是建立在模式集P上，能够辨认出模式集 P中所有关键字后缀的确定型自动机。这种思 想主要是AC和RF的结合结果。 Ra

16、ffinot的MultiBDM o 在上述的AC和DAWG两种自动机扫描思想上产 生的多模匹配算法。根据匹配过程中使用时刻 的不同，作者提出了两种改进。在作者的实验 中，处理大规模的多关键字匹配问题中有较好 的优势。 SumKim99 o 一种使用HashTable和Bit-Parallel的算法。它 的处理过程比较特别，先对模式数值化压缩存 储，然后使用HashTable直接定位出当前读入 的字符将可能匹配上的关键字的范围，接着再 用位运算对可能匹配上的关键字逐个比较，判 定文本中是否有关键字出现。参考文献1、一种针对网络流式文本数据的匹配算法 2、改进的中文串多模式匹配算法 3、Snort入侵检测系统