AC自动机
AC自动机：Aho-Corasick automation，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。一个常见的例子就是打游戏聊天时，你说的一些铭感词会变成‘*’。要搞懂AC自动机，先得有模式树（字典树）Trie和KMP模式匹配算法的基础知识。KMP算法是单模式串的字符匹配算法，AC自动机是多模式串的字符匹配算法。
基于单模式串和Trie树实现的敏感词过滤
字符串匹配算法中：BF算法、RK算法、BM算法、KMP算法 是单模式串匹配算法。 而 Trie树是多模式串匹配算法。
单模式串匹配算法：是在一个模式串和一个主串之间进行匹配，也就是说，在一个主串中查找一个模式串。
多模式串匹配算法：是在多个模式串和一个主串之间做匹配，也就是说，在一个主串中查找多个模式串。
尽管，单模式串匹配算法也能完成多模式串的匹配工作。但是效率是比较低的。
如：我们可以针对每个敏感词，通过单模式串匹配算法(比如KMP算法)与用户输入的 文字内容进行匹配。但是，这样做的话，每个匹配过程都需要扫描一遍用户输入的内容。整个过程下来就要扫描很多遍用户输入的内容。如果敏感词很多，比如 几千个，并且用户输入的内容很长，假如有上千个字符，那我们就需要扫描几千遍这样的输入内容。很显然，这种处理思路比较低效。
与单模式匹配算法相比，多模式匹配算法在这个问题的处理上就很高效了。它只需要扫描一遍主串，就能在主串中一次性查找多个模式串是否存在，从而大大提 高匹配效率。我们知道，Trie树就是一种多模式串匹配算法。那如何用Trie树实现敏感词过滤功能呢?
我们可以对敏感词字典进行预处理，构建成Trie树结构。这个预处理的操作只需要做一次，如果敏感词字典动态更新了，比如删除、添加了一个敏感词，那我们只 需要动态更新一下Trie树就可以了。
当用户输入一个文本内容后，我们把用户输入的内容作为主串，从第一个字符(假设是字符C)开始，在Trie树中匹配。当匹配到Trie树的叶子节点，或者中途遇 到不匹配字符的时候，我们将主串的开始匹配位置后移一位，也就是从字符C的下一个字符开始，重新在Trie树中匹配。
基于Trie树的这种处理方法，有点类似单模式串匹配的BF算法。单模式串匹配算法中，KMP算法对BF算法进行改进，引入了next数组，让匹配失败 时，尽可能将模式串往后多滑动几位。想借鉴单模式串的优化改进方法，对多模式串Trie树进行改进，进一步提高Trie树的效率，这就需要AC自动机了。
AC自动机节点定义
public static class AcTrieNode {
public char data;
public AcTrieNode[] children = new AcTrieNode[26];// 字符集只包含 a-z 26个英文字母
public boolean isEndingChar = false; //结尾字符标识
public int length = -1; //当isEndingChar 为 true 时， 记录模式串长度
public AcTrieNode fail;// 失败指针
public AcTrieNode(char data) {
this.data = data;
}
}
Trie树跟AC自动机之间的关系，就像单串匹配中朴素的串匹配算法，跟KMP算法之间的关系一样，只不过前者针对的是多模式串而已。所以，AC自动机实际上就是在Trie树之上，加了类似KMP的next数组，只不过此处的next数组是构建在树上罢了。
AC自动机的构建，包含两个操作:
-
将多个模式串构建成Trie树.
-
在Trie树上构建失败指针(相当于KMP中的失效函数next数组)。
AC自动机关键点一：字典树的构建过程
关于如何构建Trie树点这里
AC自动机关键点二：找Fail指针
在KMP算法中，当我们比较到一个字符发现失配的时候我们会通过next数组，找到下一个开始匹配的位置，然后进行字符串匹配，KMP算法是用与单模式匹配。
AC自动机,在tire树的基础上,增加一个fail指针,如果当前点匹配失败,则将指针转移到fail指针指向的地方,这样就不用回溯,而可以源路匹配下去了.(当前模式串后缀和fail指针指向的模式串部分前缀相同,如abce和bcd,我们找到c,需要c的下一个节点e,但是e不是我们想要的,就跳到bcd中的c处,看看此处的下一个字符(d)是不是应该找的那一个)
例：
这里有4个模式串，分别是c，bc，bcd，abcd;主串是abcd。
trie.png
计算每个节点的失败指针这个过程看起来有些复杂。其实，如果我们把树中相同深度的节点放到同一层，那么某个节点的失败指针只有可能出现在它所在层的上
一层。
我们可以像KMP算法那样，当我们要求某个节点的失败指针的时候，我们通过已经求得的、深度更小的那些节点的失败指针来推导。也就是说，我们可以逐层依 次来求解每个节点的失败指针。所以，失败指针的构建过程，是一个按层遍历树的过程。
假设节点p的失败指针指向节点q，我们看节点p的子节点pc对应的字符，是否也可以在节点q的子节点中找到。如果找到了节点q的一个子节点qc，对应的字符 跟节点pc对应的字符相同，则将节点pc的失败指针指向节点qc。
image.png
如果节点q中没有子节点的字符等于节点pc包含的字符，需要找q->fail->fail 这个节点，直到root为止，如果还没有找到相同字符的子节点，就让节点pc的失败指针指向root。
/**
* 构建fail指针
*/
public void buildFailurePointer() {
Queue<AcTrieNode> queue = new LinkedList<>();
this.root.fail = null;
queue.add(root);
while (!queue.isEmpty()) {
AcTrieNode p = queue.remove(); // 出队
for (int i = 0; i < 26; i++) {
AcTrieNode pc = p.children[i];
if (pc == null) {
continue;
}
if (p == root) {
pc.fail = root;
} else {
AcTrieNode q = p.fail;
while (q != null) {
AcTrieNode 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);
}
}
}
假设我们改变下trie的元素，失败指针可得到如下图：
image.png
最终4个模式串，c，bc，bcd，abcd;生成的AC自动机图如下：
image.png
AC自动机关键点三：匹配
在匹配过程中，主串从i=0开始，AC自动机从指针p=root开始，假设模式串是b，主串是a。
如果p指向的节点有一个等于b[i]的子节点x，我们就更新p指向x，这个时候我们需要通过失败指针，检测一系列失败指针为结尾的路径是否是模式串。这一 句不好理解，你可以结合代码看。处理完之后，我们将i加一，继续这两个过程;
如果p指向的节点没有等于b[i]的子节点，那失败指针就派上用场了，我们让p=p->fail，找p->fail->fail这个节点，然后继续这两个过程。
看下实现代码会更清晰。
/**
* 文本匹配
*
* @param text 输入的文本
* @return 返回已起始位置为key, 匹配长度为value的map
*/
public Map<Integer, Integer> match(char[] text) {
Map<Integer, Integer> resMap = new HashMap<>();
int n = text.length;
AcTrieNode 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 重新开始
}
AcTrieNode tmp = p;
while (tmp != root) { // 打印出可以匹配的模式串
if (tmp.isEndingChar) {
int pos = i - tmp.length + 1;
System.out.println("匹配起始下标" + pos + ";长度" + tmp.length);
resMap.put(pos, tmp.length);
}
tmp = tmp.fail;
}
}
return resMap;
}
时间复杂度分析
构建时间复杂度
Trie树
Trie树构建的时间复杂度是O(mlen)，其中len表示敏感词的平均长度，m表示敏感词的个数。
失败指针
一个不是很严谨的上届，假设Trie树中总的节点个数是k，每个节点构建失败指针的时候，(你可以看下代码)最耗时的环节是while循环中的q=q->fail，每运行一次这个语句，q指向节点的
深度都会减少1，而树的高度最高也不会超过len，所以每个节点构建失败指针的时间复杂度是O(len)。整个失败指针的构建过程就是O(klen)。 不过，AC自动机的构建过程都是预先处理好的，构建好之后，并不会频繁地更新，所以不会影响到敏感词过滤的运行效率。
匹配时间复杂度
for循环依次遍历主串中的每个字符，for循环内部最耗时的部分也是while循环，而这一部分的时间复杂度也是O(len)，所以总的 匹配的时间复杂度就是O(n*len)。因为敏感词并不会很长，而且这个时间复杂度只是一个非常宽泛的上限，实际情况下，可能近似于O(n)，所以AC自动机做敏感 词过滤，性能非常高。
从时间复杂度上看，AC自动机匹配的效率跟Trie树一样啊。实际上，因为失效指针可能大部分情况下都指向root节点，所以绝大部分情况下， 在AC自动机上做匹配的效率要远高于刚刚计算出的比较宽泛的时间复杂度。只有在极端情况下，如图所示，AC自动机的性能才会退化的跟Trie树一样。
image.png
小结
单模式串匹配算法是为了快速在主串中查找一个模式串，而多模式串匹配算法是为了快速在主串中查找多个模式 串。
AC自动机是基于Trie树的一种改进算法，它跟Trie树的关系，就像单模式串中，KMP算法与BF算法的关系一样。KMP算法中有一个非常关键的next数组，类比 到AC自动机中就是失败指针。而且，AC自动机失败指针的构建过程，跟KMP算法中计算next数组极其相似。所以，要理解AC自动机，最好先掌握KMP算法，因
为AC自动机其实就是KMP算法在多模式串上的改造。 整个AC自动机算法包含两个部分，第一部分是将多个模式串构建成AC自动机，第二部分是在AC自动机中匹配主串。第一部分又分为两个小的步骤，一个是将模式串构建成Trie树，另一个是在Trie树上构建失败指针。
package test;
import java.util.*;
public class AC {
/**
* 节点
*/
public static class AcTrieNode {
public char data;
public AcTrieNode[] children = new AcTrieNode[26];// 字符集只包含 a-z 26个英文字母
public boolean isEndingChar = false; //结尾字符标识
public int length = -1; //当isEndingChar 为 true 时， 记录模式串长度
public AcTrieNode fail;// 失败指针
public AcTrieNode(char data) {
this.data = data;
}
}
public static class AcTrie {
private AcTrieNode root = new AcTrieNode('/');
/**
* 插入数据生成，Trie树
*
* @param text
*/
public void insert(char[] text) {
AcTrieNode p = root;
for (char v : text) {
int idx = v - 'a';// 'a' 等于 95 ，'b'-'a' = 1 这里计算出 v 应该存储的索引
if (p.children[idx] == null) { // 该节点不存在
p.children[idx] = new AcTrieNode(v);
}
p = p.children[idx]; // 走向下一个节点
}
p.isEndingChar = true;
p.length = text.length;
}
/**
* 构建fail指针
*/
public void buildFailurePointer() {
Queue<AcTrieNode> queue = new LinkedList<>();
this.root.fail = null;
queue.add(root);
while (!queue.isEmpty()) {
AcTrieNode p = queue.remove(); // 出队
for (int i = 0; i < 26; i++) {
AcTrieNode pc = p.children[i];
if (pc == null) {
continue;
}
if (p == root) {
pc.fail = root;
} else {
AcTrieNode q = p.fail;
while (q != null) {
AcTrieNode 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);
}
}
}
/**
* 文本匹配
*
* @param text 输入的文本
* @return 返回已起始位置为key, 匹配长度为value的map
*/
public Map<Integer, Integer> match(char[] text) {
Map<Integer, Integer> resMap = new HashMap<>();
int n = text.length;
AcTrieNode 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 重新开始
}
AcTrieNode tmp = p;
while (tmp != root) { // 打印出可以匹配的模式串
if (tmp.isEndingChar) {
int pos = i - tmp.length + 1;
System.out.println("匹配起始下标" + pos + ";长度" + tmp.length);
resMap.put(pos, tmp.length);
}
tmp = tmp.fail;
}
}
return resMap;
}
/**
* 查询指定的文本是否存在
*
* @param text
* @return
*/
public boolean find(char[] text) {
AcTrieNode p = root;
for (char v : text) {
int idx = v - 'a';
if (p.children[idx] == null) {
return false; //没找到
}
p = p.children[idx]; // 走向下一个节点
}
return p.isEndingChar; // 是结束字符，表示找到了，反之则表示没找到
}
/**
* 输入前缀，提示预设的完整词
*
* @param text
* @return
*/
public List<String> likeFind(char[] text) {
List<String> resList = new ArrayList<>();
AcTrieNode p = root;
for (char v : text) {
int idx = v - 'a';// 'a' 等于 95 ，'b'-'a' = 1 这里计算出 v 应该存储的索引
if (p.children[idx] == null) {
return resList;
}
p = p.children[idx];// 走向下一个节点
}
if (p.isEndingChar) {
resList.add(new String(text));
}
like(p, resList, new String(text));
return resList;
}
public String like(AcTrieNode p, List<String> resList, String path) {
for (AcTrieNode v : p.children) {
if (v != null) {
path += v.data;
path = like(v, resList, path);
}
}
if (p.isEndingChar) {
resList.add(path);
}
path = path.substring(0, path.length() - 1);
return path;
}
}
public static void main(String[] args) {
System.out.println("========== hello Trie ============");
AcTrie trie = new AcTrie();
trie.insert("how".toCharArray());
trie.insert("hi".toCharArray());
trie.insert("her".toCharArray());
trie.insert("hello".toCharArray());
trie.insert("so".toCharArray());
trie.insert("see".toCharArray());
trie.insert("word".toCharArray());
trie.insert("fuck".toCharArray());
for (String v : new String[]{"hello", "baozi", "see", "li", "hai", "le", "word", "ge"}) {
System.out.printf("find %s ,%s \n", v, trie.find(v.toCharArray()));
}
System.out.println("\n========== 神奇的分割线 =============\n\n");
for (String v : new String[]{"h", "he", "hi", "s"}) {
List<String> strings = trie.likeFind(v.toCharArray());
System.out.printf("输入：%s , 提示：%s\n", v, strings);
}
System.out.println("\n========== Ac Trie 神奇的分割线 =============\n\n");
trie.buildFailurePointer();
for (String v : new String[]{"seeifuckyou", "lihailewordge"}) {
char[] valChars = v.toCharArray();
Map<Integer, Integer> match = trie.match(valChars);
for (Integer star : match.keySet()) {
Integer end = match.get(star);
for (int i = 0; i < valChars.length; i++) {
if (i >= star && i < star + end) {
valChars[i] = '*';
}
}
}
System.out.println("输入：" + v + "\n输出：" + new String(valChars) + "\n");
}
}
}
网友评论