35AC自动机：如何用多模式串匹配实现敏感词过滤功能

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

很多网站，大都有敏感词过滤功能。其实这些功能的基本原理是字符串匹配算法，也就是通过维护一个敏感词的字典，当用户输入一段文字内容后，通过字符串匹配算法，来查找用户输入的这段文字，是否包含敏感词。如果有，就用“*”把它替代掉。

虽然前面讲过好几种字符串匹配算法，都可以处理这些问题。但是这些算法对于这个应用场景效率很低。那如何才能实现一个高性能的敏感词过滤系统呢？这就要用到今天的多模式串匹配算法。

基于单模式串和 Trie 树实现的敏感词过滤

单模式串匹配算法，是在一个模式串和一个主串之间进行匹配，也就是说，在一个主串中查找一个模式串。多模式串匹配算法，就是在多个模式串和一个主串之间做匹配，也就是说，在一个主串中查找多个模式串。

前面讲的BF 算法、RK 算法、BM 算法、KMP 算法，都是单模式串匹配算法，而后面讲的Trie树是多模式串匹配算法。

单模式串匹配算法也能完成多模式串的匹配工作。例如，对于开篇的思考题，针对每个敏感词，通过单模式串匹配算法（比如 KMP 算法）与用户输入的文字内容进行匹配。但这样每个匹配过程都要扫描一遍用户输入的内容。这种处理方式很低效。

与单模式匹配算法相比，多模式匹配算法在这个问题的处理上就很高效。它只需要扫描一遍主串，就能在主串中一次性查找多个模式串是否存在，从而大大提高匹配效率。那怎么使用多模式串匹配算法——Trie树来实现敏感词过滤功能呢？

我们可以对敏感词进行预处理，构建成Trie树结构。这个预处理的操作只需要做一次，如果敏感词字典动态更新了，比如删除、添加了一个敏感词，那只需要动态更新一下 Trie 树就可以了。

当用户输入一个文本内容后，我们把用户输入的内容作为主串，从第一个字符（假设是字符 C）开始，在 Trie 树中匹配。当匹配到 Trie 树的叶子节点，或者中途遇到不匹配字符的时候，我们将主串的开始匹配位置后移一位，也就是从字符 C 的下一个字符开始，重新在 Trie 树中匹配。

基于 Trie 树的这种处理方法，有点类似单模式串匹配的 BF 算法。我们知道，单模式串匹配算法中，KMP 算法对 BF 算法进行改进，引入了 next 数组，让匹配失败时，尽可能将模式串往后多滑动几位。借鉴单模式串的优化改进方法，能否对多模式串 Trie 树进行改进，进一步提高 Trie 树的效率呢？这就要用到 AC 自动机算法了。

经典的多模式串匹配算法：AC 自动机

AC 自动机算法，全称是 Aho-Corasick 算法。AC 自动机实际上就是在 Trie 树之上，加了类似 KMP 的 next 数组，只不过此处的 next 数组是构建在树上罢了。对应的代码如下：

public class AcNode {
  public char data; 
  public AcNode[] children = new AcNode[26]; // 字符集只包含a~z这26个字符
  public boolean isEndingChar = false; // 结尾字符为true
  public int length = -1; // 当isEndingChar=true时，记录模式串长度
  public AcNode fail; // 失败指针
  public AcNode(char data) {
    this.data = data;
  }
}

所以，AC 自动机的构建，包含两个操作：

将多个模式串构建成 Trie 树；
在 Trie 树上构建失败指针（相当于 KMP 中的失效函数 next 数组）。

构建好 Trie 树之后，如何在它之上构建失败指针？

举一个例子，这里有 4 个模式串，分别是 c，bc，bcd，abcd；主串是 abcd。

Trie 树中的每一个节点都有一个失败指针，它的作用和构建过程，跟 KMP 算法中的 next 数组极其相似。所以要想看懂这节内容，你要先理解 KMP 算法中 next 数组的构建过程。

假设沿 Trie 树走到 p 节点，也就是下图中的紫色节点，那 p 的失败指针就是从 root 走到紫色节点形成的字符串 abc，跟所有模式串前缀匹配的最长可匹配后缀子串，就是箭头指的 bc 模式串。

这里的最长可匹配后缀子串，稍微解释一下。字符串 abc 的后缀子串有两个 bc，c，拿它们与其他模式串匹配，如果某个后缀子串可以匹配某个模式串的前缀，那就把这个后缀子串叫作可匹配后缀子串。

从可匹配后缀子串中，找出最长的一个，就是刚刚讲到的最长可匹配后缀子串。将 p 节点的失败指针指向那个最长匹配后缀子串对应的模式串的前缀的最后一个节点，就是下图中箭头指向的节点。

计算每个节点的失败指针这个过程看起来有些复杂。其实，如果把树中相同深度的节点放到同一层，那么某个节点的失败指针只有可能出现在它所在层的上一层。

可以像 KMP 算法那样，当要求某个节点的失败指针的时候，通过已经求得的、深度更小的那些节点的失败指针来推导。也就是说，可以逐层依次来求解每个节点的失败指针。所以，失败指针的构建过程，是一个按层遍历树的过程。

首先 root 的失败指针为 NULL，也就是指向自己。当已经求得某个节点 p 的失败指针之后，如何寻找它的子节点的失败指针呢？

假设节点 p 的失败指针指向节点 q，看节点 p 的子节点 pc 对应的字符，是否也可以在节点 q 的子节点中找到。如果找到了节点 q 的一个子节点 qc，对应的字符跟节点 pc 对应的字符相同，则将节点 pc 的失败指针指向节点 qc。

如果节点 q 中没有子节点的字符等于节点 pc 包含的字符，则令 q=q->fail（fail 表示失败指针，这里有没有很像 KMP 算法里求 next 的过程？），继续上面的查找，直到 q 是 root 为止，如果还没有找到相同字符的子节点，就让节点 pc 的失败指针指向 root。

构建失败指针的代码如下，构建 Trie 树的代码并没有贴出来

public void buildFailurePointer() {
  Queue<AcNode> queue = new LinkedList<>();
  root.fail = null;
  queue.add(root);
  while (!queue.isEmpty()) {
    AcNode p = queue.remove();
    for (int i = 0; i < 26; ++i) {
      AcNode pc = p.children[i];
      if (pc == null) continue;
      if (p == root) {
        pc.fail = root;
      } else {
        AcNode q = p.fail;
        while (q != null) {
          AcNode qc = q.children[pc.data - 'a'];
          if (qc != null) {
            pc.fail = qc;
            break;
          }
          q = q.fail;
        }
        if (q == null) {
          pc.fail = root;
        }
      }
      queue.add(pc);
    }
  }
}

通过按层来计算每个节点的子节点的失效指针，刚刚举的那个例子，最后构建完成之后的 AC 自动机就是下面这个样子：

AC 自动机到此就构建完成了。现在来看下，如何在 AC 自动机上匹配主串？

还是拿之前的例子来讲解。在匹配过程中，主串从 i=0 开始，AC 自动机从指针 p=root 开始，假设模式串是 b，主串是 a。

如果 p 指向的节点有一个等于 b[i]的子节点 x，就更新 p 指向 x，这个时候需要通过失败指针，检测一系列失败指针为结尾的路径是否是模式串。这一句不好理解，你可以结合代码看。处理完之后，将 i 加一，继续这两个过程；
如果 p 指向的节点没有等于 b[i]的子节点，那失败指针就派上用场了，让 p=p->fail，然后继续这两个过程。

关于匹配的这部分，文字描述不如代码看得清楚，所以把代码贴了出来，非常简短，并且添加了详细的注释，你可以对照着看下。这段代码输出的就是，在主串中每个可以匹配的模式串出现的位置。

public void match(char[] text) { // text是主串
  int n = text.length;
  AcNode p = root;
  for (int i = 0; i < n; ++i) {
    int idx = text[i] - 'a';
    while (p.children[idx] == null && p != root) {
      p = p.fail; // 失败指针发挥作用的地方
    }
    p = p.children[idx];
    if (p == null) p = root; // 如果没有匹配的，从root开始重新匹配
    AcNode tmp = p;
    while (tmp != root) { // 打印出可以匹配的模式串
      if (tmp.isEndingChar == true) {
        int pos = i-tmp.length+1;
        System.out.println("匹配起始下标" + pos + "; 长度" + tmp.length);
      }
      tmp = tmp.fail;
    }
  }
}

解答开篇

实际上，上面贴出来的代码，已经是一个敏感词过滤的原型代码了。它可以找到所有敏感词出现的位置（在用户输入的文本中的起始下标）。只需要稍加改造，再遍历一遍文本内容（主串），就可以将文本中的所有敏感词替换成***。

AC 自动机实现的敏感词过滤系统，是否比单模式串匹配方法更高效呢？

首先，需要将敏感词构建成 AC 自动机，包括构建 Trie 树以及构建失败指针。

上一节讲过，Trie 树构建的时间复杂度是 $O(m*len)$，其中 len 表示敏感词的平均长度，m 表示敏感词的个数。那构建失败指针的时间复杂度是多少呢？这里给出一个不是很紧确的上界。

假设 Trie 树中总的节点个数是 k，每个节点构建失败指针的时候，（可以看下代码）最耗时的环节是 while 循环中的 q=q->fail，每运行一次这个语句，q 指向节点的深度都会减少 1，而树的高度最高也不会超过 len，所以每个节点构建失败指针的时间复杂度是 $O(len)$。整个失败指针的构建过程就是 $O(k*len)$。

不过，AC 自动机的构建过程都是预先处理好的，构建好之后，并不会频繁地更新，所以不会影响到敏感词过滤的运行效率。

再来看下，用 AC 自动机做匹配的时间复杂度是多少？

跟刚刚构建失败指针的分析类似，for 循环依次遍历主串中的每个字符，for 循环内部最耗时的部分也是 while 循环，而这一部分的时间复杂度也是 $O(len)$，所以总的匹配的时间复杂度就是 $O(n*len)$。因为敏感词并不会很长，而且这个时间复杂度只是一个非常宽泛的上限，实际情况下，可能近似于 $O(n)$，所以 AC 自动机做敏感词过滤，性能非常高。

你可能会说，从时间复杂度上看，AC 自动机匹配的效率跟 Trie 树一样啊。实际上，因为失效指针可能大部分情况下都指向 root 节点，所以绝大部分情况下，在 AC 自动机上做匹配的效率要远高于刚刚计算出的比较宽泛的时间复杂度。只有在极端情况下，如图所示，AC 自动机的性能才会退化的跟 Trie 树一样。

内容小结

本节讲了多模式串匹配算法，AC 自动机。单模式串匹配算法是为了快速在主串中查找一个模式串，而多模式串匹配算法是为了快速在主串中查找多个模式串。

AC 自动机是基于 Trie 树的一种改进算法，它跟 Trie 树的关系，就像单模式串中，KMP 算法与 BF 算法的关系一样。KMP 算法中有一个非常关键的 next 数组，类比到 AC 自动机中就是失败指针。而且，AC 自动机失败指针的构建过程，跟 KMP 算法中计算 next 数组极其相似。所以，要理解 AC 自动机，最好先掌握 KMP 算法，因为 AC 自动机其实就是 KMP 算法在多模式串上的改造。

整个 AC 自动机算法包含两个部分，第一部分是将多个模式串构建成 AC 自动机，第二部分是在 AC 自动机中匹配主串。第一部分又分为两个小的步骤，一个是将模式串构建成 Trie 树，另一个是在 Trie 树上构建失败指针。

课后思考

到此为止，字符串匹配算法我们全都讲完了，你能试着分析总结一下，各个字符串匹配算法的特点和比较适合的应用场景吗？

答：

一、单模式串匹配：

BF：简单场景，主串和模式串都不太长，$O(m*n)$
KP：字符集范围不要太大且模式串不要太长，否则hash值可能冲突，$O(n)$
naive-BM：模式串最好不要太长（因为预处理较重），比如IDE编辑器里的查找场景；预处理$O(m*m)$，匹配$O(n)$，实现较复杂，需要较多额外空间.
KMP：适合所有场景，整体实现起来也比BM简单，$O(n+m)$，仅需一个next数组的O(n)额外空间；但统计意义下似乎BM更快，原因不明.
另外查资料的时候还看到一种比BM/KMP更快，且实现+理解起来都更容易的的Sunday算法，有兴趣的可以看这里:
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm
https://www.jianshu.com/p/2e6eb7386cd3

二、多模式串匹配：

naive-Trie: 适合多模式串公共前缀较多的匹配($O(n*k)$) 或者根据公共前缀进行查找($O(k)$)的场景，比如搜索框的自动补全提示。
AC自动机: 适合大量文本中多模式串的精确匹配查找, 可以到$O(n)$。