敏感词过滤的算法原理之 Aho-Corasick 算法

左手的ㄟ右手 2021-06-26 16:06 437阅读 0赞

## 简介 ##

`Aho-Corasick`算法简称`AC`算法，通过将模式串预处理为确定有限状态自动机，扫描文本一遍就能结束。其复杂度为`O(n)`，即与模式串的数量和长度无关。

### 思想 ###

自动机按照文本字符顺序，接受字符，并发生状态转移。这些状态缓存了“按照字符转移成功（但不是模式串的结尾）”、“按照字符转移成功（是模式串的结尾）”、“按照字符转移失败”三种情况下的跳转与输出情况，因而降低了复杂度。

### 基本构造 ###

AC算法中有三个核心函数，分别是：

*  `success`; 成功转移到另一个状态（也称`goto`表或`success`表）
 *  `failure`;不可顺着字符串跳转的话，则跳转到一个特定的节点（也称`failure`表），从根节点到这个特定的节点的路径恰好是失败前的文本的一部分。
 *  `emits`; 命中一个模式串（也称`output`表）

## 举例 ##

以经典的`ushers`为例，模式串是`he/ she/ his /hers`，文本为“`ushers`”。构建的自动机如图：  
![在这里插入图片描述][20201118175957417.png]  
其实上图省略了到根节点的`fail`边，完整的自动机如下图：  
![在这里插入图片描述][20201118180012947.png]

## 匹配过程 ##

自动机从根节点`0`出发

首先尝试按`success`表转移（图中实线）。按照文本的指示转移，也就是接收一个`u`。此时`success`表中并没有相应路线，转移失败。

失败了则按照`failure`表回去（图中虚线）。按照文本指示，这次接收一个`s`，转移到状态`3`。

成功了继续按`success`表转移，直到失败跳转步骤`2`，或者遇到`output`表中标明的“可输出状态”（图中红色状态）。此时输出匹配到的模式串，然后将此状态视作普通的状态继续转移。

算法高效之处在于，当自动机接受了“`ushe`”之后，再接受一个`r`会导致无法按照`success`表转移，此时自动机会聪明地按照`failure`表转移到`2`号状态，并经过几次转移后输出“`hers`”。来到`2`号状态的路不止一条，从根节点一路往下，“`h→e`”也可以到达。而这个“`he`”恰好是“`ushe`”的结尾，状态机就仿佛是压根就没失败过（没有接受`r`），也没有接受过中间的字符“`us`”，直接就从初始状态按照“`he`”的路径走过来一样（到达同一节点，状态完全相同）。

## 构造过程 ##

看来这三个表很厉害，不过，它们是怎么计算出来的呢？

### `goto`表 ###

很简单，了解一点`trie`树知识的话就能一眼看穿，`goto`表就是一棵`trie`树。把上图的虚线去掉，实线部分就是一棵`trie`树了。  
![在这里插入图片描述][20201118180035515.png]

### `output`表 ###

`output`表也很简单，与`trie`树里面代表这个节点是否是单词结尾的结构很像。不过`trie`树只有叶节点才有“`output`”，并且一个叶节点只有一个`output`。下图却违背了这两点，这是为什么呢？其实下图的`output`会在建立`failure`表的时候进行一次拓充。  
![在这里插入图片描述][20201118180047692.png]  
以上两个表通过一个`dfs`就可以构造出来。关于`trie`树的更详细内容，请参考：**《Ansj分词双数组Trie树实现与arrays.dic词典格式》，《Trie树分词》，《双数组Trie树(DoubleArrayTrie)Java实现》**。

### `failure`表 ###

这个表是`trie`树没有的，加了这个表，AC自动机就看起来不像一棵树，而像一个图了。`failure`表是状态与状态的一对一关系，别看图中虚线乱糟糟的，不过你仔细看看，就会发现节点只会发出一条虚线，它们严格一对一。

这个表的构造方法是：

1.  首先规定与状态0距离为1（即深度为1）的所有状态的fail值都为0。
2.  然后设当前状态是`S1`，求`fail(S1)`。我们知道，`S1`的前一状态必定是唯一的（刚才说的一对一），设S1的前一状态是S2，S2转换到S1的条件为接受字符`C`，测试`S3= goto(fail(S2), C)`。
3.  如果成功，则`fail(S1) = goto(fail(S2), C) = S3`。
4.  如果不成功，继续测试`S4 = goto(fail(S3),C)`是否成功，如此重复，直到转换到某个有效的状态`Sn`，令`fail(S1) = Sn`。

![在这里插入图片描述][20201118180100193.png]

## Java实现 ##

原理谁都可以说几句的，可是优雅健壮的代码却不是那么容易写的。我考察了Git上几个AC算法的实现，发现`robert-bor`的实现非常好。一趟代码看下来，学到了不少设计上的知识。我`fork`了下来，针对`Ascii`做了优化，添加了中文注释。

另外，我实现了基于双数组`Trie`树的AC自动机：**《Aho Corasick自动机结合DoubleArrayTrie极速多模式匹配》**。性能更高，内存可控。

### 开源项目 ###

开源在`https://github.com/hankcs/aho-corasick`。

调用方法

Trie trie = new Trie();
    trie.addKeyword("hers");
    trie.addKeyword("his");
    trie.addKeyword("she");
    trie.addKeyword("he");
    Collection<Emit> emits = trie.parseText("ushers");
    System.out.println(emits);

输出：

[2:3=he, 1:3=she, 2:5=hers]

此外，还有一些配置选项：

/** * 大小写敏感 * @return */
    public Trie caseInsensitive()
    { 
        this.trieConfig.setCaseInsensitive(true);
        return this;
    }
     
    /** * 不允许模式串在位置上前后重叠 * @return */
    public Trie removeOverlaps()
    { 
        this.trieConfig.setAllowOverlaps(false);
        return this;
    }
     
    /** * 只匹配完整单词 * @return */
    public Trie onlyWholeWords()
    { 
        this.trieConfig.setOnlyWholeWords(true);
        return this;
    }

### `org.ahocorasick.trie`包 ###

这里封装了`Trie`树，其中比较重要的类是`Trie`树的节点`State`：  
![在这里插入图片描述][20201118181536552.png]

我重构了`State`，将其异化为`UnicodeState`和`AsciiState`类。其中`UnicodeState`类使用 `Map<Character, State>` 来储存`goto`表，而`AsciiState`类使用数组 `State[] success = new State[256]`来储存，这样在`Ascii`表上面，`AsciiState`的匹配要稍微快一些，相应的在构建时会慢一些，内存占用也会多一些。  
![在这里插入图片描述][20201118181548460.png]

从对万字的英语词典的测试结果来看，`AsciiState`的确有那么一点优势：

asciiTrie adding time:1013ms
    unicodeTrie adding time:96ms
     
    asciiTrie building time:903ms
    unicodeTrie building time:312ms
     
    asciiTrie parsing time:355ms
    unicodeTrie parsing time:463ms

### `org.ahocorasick.interval`包 ###

这里封装了一棵线段树，关于线段树的介绍请查看：线段树。

线段树用于修饰最后的匹配结果，匹配结果中有一些可能会重叠，比如`she`和`he`，这棵线段树对匹配结果（一系列区间）进行索引，能够在`log(n)`时间内判断一个区间与另一个是否重叠。详细的实现请看代码，都有中文注释，应该很好懂。

## 基于双数组`Trie`树的`Aho Corasick`自动机 ##

AC自动机能高速完成多模式匹配，然而具体实现聪明与否决定最终性能高低。大部分实现都是一个`Map<Character, State>`了事，无论是`TreeMap`的对数复杂度，还是`HashMap`的巨额空间复杂度与哈希函数的性能消耗，都会降低整体性能。

双数组`Trie`树能高速`O(n)`完成单串匹配，并且内存消耗可控，然而软肋在于多模式匹配，如果要匹配多个模式串，必须先实现前缀查询，然后频繁截取文本后缀才可多匹配，这样一份文本要回退扫描多遍，性能极低。

如果能用双数组`Trie`树表达`AC`自动机，就能集合两者的优点，得到一种近乎完美的数据结构。具体实现请参考\*\*《Aho Corasick自动机结合DoubleArrayTrie极速多模式匹配》\*\*。

[20201118175957417.png]: /images/20210626/93c25ad9e87e4a44b10d56532d069e79.png
[20201118180012947.png]: /images/20210626/56cfbff32e424106852c4ac089db9c0c.png
[20201118180035515.png]: /images/20210626/52b8c807cde44283ad491ee3b3e7e51b.png
[20201118180047692.png]: /images/20210626/821a7341e80b42a5ad1a8863b59cf3d4.png
[20201118180100193.png]: /images/20210626/f597ec246a524c3081bf5dc73cf8e9c2.png
[20201118181536552.png]: /images/20210626/e9d6132c6e4446aeb6484eff67abefb7.png
[20201118181548460.png]: /images/20210626/87c2305ddc50417b9c66509c057b44ad.png