AC 自动机


引入

我知道,很多人在第一次看到这个东西的时侯是非常兴奋的。(别问我为什么知道)不过这个自动机啊它叫作 Automaton,不是 Automation,让萌新失望啦。切入正题。似乎在初学自动机相关的内容时,许多人难以建立对自动机的初步印象,尤其是在自学的时侯。而这篇文章就是为你们打造的。笔者在自学 AC 自动机后花费两天时间制作若干的 gif,呈现出一个相对直观的自动机形态。尽管这个图似乎不太可读,但这绝对是在作者自学的时侯,画得最认真的 gif 了。另外有些小伙伴问这个 gif 拿什么画的。笔者用 Windows 画图软件制作。

概述

AC 自动机是 以 Trie 的结构为基础,结合 KMP 的思想 建立的。

解释

简单来说,建立一个 AC 自动机有两个步骤:

  1. 基础的 Trie 结构:将所有的模式串构成一棵 Trie。
  2. KMP 的思想:对 Trie 树上所有的结点构造失配指针。

然后就可以利用它进行多模式匹配了。

字典树构建

AC 自动机在初始时会将若干个模式串丢到一个 Trie 里,然后在 Trie 上建立 AC 自动机。这个 Trie 就是普通的 Trie,该怎么建怎么建。

这里需要仔细解释一下 Trie 的结点的含义,尽管这很小儿科,但在之后的理解中极其重要。Trie 中的结点表示的是某个模式串的前缀。我们在后文也将其称作状态。一个结点表示一个状态,Trie 的边就是状态的转移。

形式化地说,对于若干个模式串 ,将它们构建一棵字典树后的所有状态的集合记作

失配指针

AC 自动机利用一个 fail 指针来辅助多模式串的匹配。

状态 的 fail 指针指向另一个状态 ,其中 ,且 的最长后缀(即在若干个后缀状态中取最长的一个作为 fail 指针)。对于学过 KMP 的朋友,我在这里简单对比一下这里的 fail 指针与 KMP 中的 next 指针:

  1. 共同点:两者同样是在失配的时候用于跳转的指针。
  2. 不同点:next 指针求的是最长 Border(即最长的相同前后缀),而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。

因为 KMP 只对一个模式串做匹配,而 AC 自动机要对多个模式串做匹配。有可能 fail 指针指向的结点对应着另一个模式串,两者前缀不同。

没看懂上面的对比不要急(也许我的脑回路和泥萌不一样是吧),你只需要知道,AC 自动机的失配指针指向当前状态的最长后缀状态即可。

AC 自动机在做匹配时,同一位上可匹配多个模式串。

构建指针

下面介绍构建 fail 指针的 基础思想:(强调!基础思想!基础!)

构建 fail 指针,可以参考 KMP 中构造 Next 指针的思想。

考虑字典树中当前的结点 的父结点是 通过字符 c 的边指向 ,即 。假设深度小于 的所有结点的 fail 指针都已求得。

  1. 如果 存在:则让 u 的 fail 指针指向 。相当于在 后面加一个字符 c,分别对应
  2. 如果 不存在:那么我们继续找到 。重复 1 的判断过程,一直跳 fail 指针直到根结点。
  3. 如果真的没有,就让 fail 指针指向根结点。

如此即完成了 的构建。

例子

下面放一张 GIF 帮助大家理解。对字符串 i he his she hers 组成的字典树构建 fail 指针:

  1. 黄色结点:当前的结点
  2. 绿色结点:表示已经 BFS 遍历完毕的结点,
  3. 橙色的边:fail 指针。
  4. 红色的边:当前求出的 fail 指针。

AC_automation_gif_b_3.gif

我们重点分析结点 6 的 fail 指针构建:

AC_automation_6_9.png

找到 6 的父结点 5,。然而 10 结点没有字母 s 连出的边;继续跳到 10 的 fail 指针,。发现 0 结点有字母 s 连出的边,指向 7 结点;所以 。最后放一张建出来的图

finish

字典树与字典图

我们直接上代码吧。字典树插入的代码就不分析了(后面完整代码里有),先来看构建函数 build(),该函数的目标有两个,一个是构建 fail 指针,一个是构建自动机。参数如下:

  1. tr[u,c]:有两种理解方式。我们可以简单理解为字典树上的一条边,即 ;也可以理解为从状态(结点) 后加一个字符 c 到达的状态(结点),即一个状态转移函数 。下文中我们将用第二种理解方式继续讲解。
  2. 队列 q:用于 BFS 遍历字典树。
  3. fail[u]:结点 的 fail 指针。

=== "C++"

```cpp
void build() {
  for (int i = 0; i < 26; i++)
    if (tr[0][i]) q.push(tr[0][i]);
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u][i])
        fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
      else
        tr[u][i] = tr[fail[u]][i];
    }
  }
}
```

=== "Python"

```python
def build():
    for i in range(0, 26):
        if tr[0][i] == 1:
            q.append(tr[0][i])
    while len(q) > 0:
        u = q[0]
        q.pop()
        for i in range(0, 26):
            if tr[u][i] == 1:
                fail[tr[u][i]] = tr[fail[u]][i]
                q.append(tr[u][i])
            else:
                tr[u][i] = tr[fail[u]][i]
```

解释

解释一下上面的代码:build 函数将结点按 BFS 顺序入队,依次求 fail 指针。这里的字典树根结点为 0,我们将根结点的子结点一一入队。若将根结点入队,则在第一次 BFS 的时候,会将根结点儿子的 fail 指针标记为本身。因此我们将根结点的儿子一一入队,而不是将根结点入队。

然后开始 BFS:每次取出队首的结点 u( 在之前的 BFS 过程中已求得),然后遍历字符集(这里是 0-25,对应 a-z,即 的各个子节点):

  1. 如果 存在,我们就将 的 fail 指针赋值为 。这里似乎有一个问题。根据之前的讲解,我们应该用 while 循环,不停的跳 fail 指针,判断是否存在字符 i 对应的结点,然后赋值,但是这里通过特殊处理简化了这些代码。
  2. 否则,令 指向 的状态。

这里的处理是,通过 else 语句的代码修改字典树的结构。没错,它将不存在的字典树的状态链接到了失配指针的对应状态。在原字典树中,每一个结点代表一个字符串 ,是某个模式串的前缀。而在修改字典树结构后,尽管增加了许多转移关系,但结点(状态)所代表的字符串是不变的。

相当于是在 后添加一个字符 c 变成另一个状态 。如果 存在,说明存在一个模式串的前缀是 ,否则我们让 指向 。由于 对应的字符串是 的后缀,因此 对应的字符串也是 的后缀。

换言之在 Trie 上跳转的时侯,我们只会从 跳转到 ,相当于匹配了一个 ;但在 AC 自动机上跳转的时侯,我们会从 跳转到 的后缀,也就是说我们匹配一个字符 c,然后舍弃 的部分前缀。舍弃前缀显然是能匹配的。那么 fail 指针呢?它也是在舍弃前缀啊!试想一下,如果文本串能匹配 ,显然它也能匹配 的后缀。所谓的 fail 指针其实就是 的一个后缀集合。

tr 数组还有另一种比较简单的理解方式:如果在位置 失配,我们会跳转到 的位置。所以我们可能沿着 fail 数组跳转多次才能来到下一个能匹配的位置。所以我们可以用 tr 数组直接记录记录下一个能匹配的位置,这样就能节省下很多时间。

这样修改字典树的结构,使得匹配转移更加完善。同时它将 fail 指针跳转的路径做了压缩(就像并查集的路径压缩),使得本来需要跳很多次 fail 指针变成跳一次。

过程

好的,我知道大家都受不了长篇叙述。上图!我们将之前的 GIF 图改一下:

AC_automation_gif_b_pro3.gif

  1. 蓝色结点:BFS 遍历到的结点 u
  2. 蓝色的边:当前结点下,AC 自动机修改字典树结构连出的边。
  3. 黑色的边:AC 自动机修改字典树结构连出的边。
  4. 红色的边:当前结点求出的 fail 指针
  5. 黄色的边:fail 指针
  6. 灰色的边:字典树的边

可以发现,众多交错的黑色边将字典树变成了 字典图。图中省略了连向根结点的黑边(否则会更乱)。我们重点分析一下结点 5 遍历时的情况。我们求 的 fail 指针:

AC_automation_b_7.png

本来的策略是找 fail 指针,于是我们跳到 发现没有 s 连出的字典树的边,于是跳到 ,发现有 ,于是 ;但是有了黑边、蓝边,我们跳到 之后直接走 就走到 号结点了。

这就是 build 完成的两件事:构建 fail 指针和建立字典图。这个字典图也会在查询的时候起到关键作用。

多模式匹配

接下来分析匹配函数 query()

实现

=== "C++"

```cpp
int query(char *t) {
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u][t[i] - 'a'];  // 转移
    for (int j = u; j && e[j] != -1; j = fail[j]) {
      res += e[j], e[j] = -1;
    }
  }
  return res;
}
```

=== "Python"

```python
def query(t):
    u, res = 0, 0
    i = 1
    while t[i] == False:
        u = tr[u][t[i] - ord('a')]
        j = u
        while j == True and e[j] != -1:
            res += e[j]
            e[j] = -1
            j = fail[j]
        i += 1
    return res
```

解释

这里 作为字典树上当前匹配到的结点,res 即返回的答案。循环遍历匹配串, 在字典树上跟踪当前字符。利用 fail 指针找出所有匹配的模式串,累加到答案中。然后清零。在上文中我们分析过,字典树的结构其实就是一个 trans 函数,而构建好这个函数后,在匹配字符串的过程中,我们会舍弃部分前缀达到最低限度的匹配。fail 指针则指向了更多的匹配状态。最后上一份图。对于刚才的自动机:

AC_automation_b_13.png

我们从根结点开始尝试匹配 ushersheishis,那么 的变化将是:

AC_automation_gif_c.gif

  1. 红色结点: 结点
  2. 粉色箭头: 在自动机上的跳转,
  3. 蓝色的边:成功匹配的模式串
  4. 蓝色结点:示跳 fail 指针时的结点(状态)。

总结

希望大家看懂了文章。

时间复杂度:定义 是模板串的长度, 是文本串的长度, 是字符集的大小(常数,一般为 26)。如果连了 trie 图,时间复杂度就是 ,其中 是 AC 自动机中结点的数目,并且最大可以达到 。如果不连 trie 图,并且在构建 fail 指针的时候避免遍历到空儿子,时间复杂度就是

拓展

确定有限状态自动机

如果大家理解了上面的讲解,那么作为拓展延伸,文末我们简单介绍一下自动机与 KMP 自动机。(现在你再去看百科上自动机的定义就会好懂很多啦)

有限状态自动机(deterministic finite automaton,DFA)是由

  1. 状态集合
  2. 字符集
  3. 状态转移函数 ,即
  4. 一个开始状态
  5. 一个接收的状态集合

组成的五元组

那这东西你用 AC 自动机理解,状态集合就是字典树(图)的结点;字符集就是 az(或者更多);状态转移函数就是 的函数(即 );开始状态就是字典树的根结点;接收状态就是你在字典树中标记的字符串结尾结点组成的集合。

KMP 自动机

KMP 自动机就是一个不断读入待匹配串,每次匹配时走到接受状态的 DFA。如果共有 个状态,第 个状态表示已经匹配了前 个字符。那么我们定义 表示状态 读入字符 后到达的状态, 表示

prefix function,则有:

(约定

我们发现 只依赖于之前的值,所以可以跟

KMP 一起求出来。(一些细节:走到接受状态之后立即转移到该状态的 next)

时间和空间复杂度:

对比之下,AC 自动机其实就是 Trie 上的自动机。(虽然一开始丢给你这句话可能不知所措)

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组