Aho–Corasick 算法,AC 自动机


AHO 算法,或者叫 AC 自动机、又或者叫 Aho–Corasick string matching algorithm,是一个高效的多模式匹配算法,它的特点是可以同时匹配多个模式串。

最常见的应用就是病毒扫描 : 把所有病毒的特征码(类似一段字符串)构造成一个 AC 自动机,把用户的文件或者网络数据流作为输入文本,只要在输入文本中找到了任何一个特征码,那么就表示有病毒存在。

对于这样的一个应用场景,我们最希望的功能就是只扫描一遍输入文本,找出所有的病毒,而 AC 自动机恰恰就有这样的能力。

一般使用 AC 自动机需要以下三步:

  1. 根据待匹配的字符串 P1, P2, Pn 建立 Trie
  2. 给 Trie 添加失败路径,实际上是生成了一个自动机。
  3. 将输入文本 str 的字符逐个通过自动机,在 O(n) 的时间复杂度内找出 P1, P2 … Pn 是否存在于 str 内。

举例

假设我们有模式字符串 { fat, fare, hat, are }, 输入的文本为 “fatehatfare”。

显然,所有的模式串都出现在了我们的输入文本中。我们的目标就是只扫描一遍文本串,找出所有的模式串。

建立 Trie

首先根据模式串建立起一个 trie,一般来说每个节点的结构大概是这样:

Node {
	Node * children[26]; /* 指向子节点的指针 */
	Node * parent;       /* 指向父节点的指针 */ 
	Node * fail;         /* 失败指针 */
	bool   terminate;    /* 是否是一个终结节点,即一个串的最后一个字符 */
}

Trie 建立好之后大概是这个样子:

aho1

给每个节点添加失败指针

这是非常核心的一步,整体的思路是这样的。

构造失败指针的方法:假设当前节点上的字母为 ‘a’,沿着父节点的失败指针走,直到走到一个节点,他的子节点中也有字母为 ‘a’ 的节点。然后把当前节点的失败指针指向那个子节点。如果一直走到了root都没找到,那就把失败指针指向root。

那么再具体一点,有以下几个步骤。

  • 对于整个 Trie 树,使用广度优先搜索 BFS 来处理每个节点。
  • root 节点的子节点特殊处理, 先将 root 的子节点的失败路径直接指向 root 节点。

算法结构:

  1. 先把 root 节点加入队列。
  2. 进入 while 循环,直到 队列为空
  3. 取队列头元素,构造它的失败指针
  4. 再将它的子节点加入队列

aho1

一个添加了失败指针的 Trie 树如上图所示。

在输入文本中搜索

  • 从root节点开始,根据输入文本的字符沿着自动机向下移动。
  • 读入的字符在当前节点没有指向的子节点时,走失败路径。
  • 如果走失败路径走到了root节点,则跳过该字符,处理下一个字符。
  • 如果当前节点有终结符,则表明命中了一个模式串。(这一步可以优化为是否最长匹配)

实现

最后给出一个我自己的 Go 语言实现,最近学习了一下 Golang, 顺便拿来练练手。

aho.go

一个简单的 test 代码检验结果是否正确。

func TestBasic(t *testing.T) {
    trie := New()
    trie.Add("fat", 1)
    trie.Add("fare", 1)
    trie.Add("hat", 1)
    trie.Add("are", 1)

    trie.AhoBuilder()

    trie.Find("fatehatfare")
}

AHO 的优化

优化要么就是时间,要么就是空间。 Trie 的实现就有链表指针方式,三数组实现,双数组实现,HAT,burst trie等。

具体可以参考下面列出的资料,等我有空再来深入研究 :-)

前一篇        返回首页        后一篇

| Copyright 2009 - 2018 by Runz |