双数组Trie树与AC自动机简要总结

Trie 树

又称单词查找树，Trie 树，是一种树形结构，是一种哈希树的变种。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，能在常数时间 O(len)内实现插入和查询操作，是一种以空间换取时间的数据结构，广泛用于词频统计和输入统计领域。

Trie 树的结构一般如下图:

关于单数组 Trie 树的实现方式这里不再多讲，只需要知道在 Trie 树单数组实现过程中，每个节点均需要一个数组来存储 next 节点，非常占用存储空间，空间复杂度大。一般不予选用。而双数组 Trie 树很好地解决了这个问题，这也是我们主要要讲的。

双数组 Trie (Double-Array Trie)结构由日本人 JUN-ICHI AOE 于 1989 年提出的，是 Trie 结构的压缩形式，仅用两个线性数组来表示 Trie 树，该结构有效结合了数字搜索树(Digital Search Tree)检索时间高效的特点和链式表示的 Trie 空间结构紧凑的特点。双数组 Trie 的本质是一个确定有限状态自动机（DFA），每个节点代表自动机的一个状态，根据变量不同，进行状态转移，当到达结束状态或无法转移时，完成一次查询操作。在双数组所有键中包含的字符之间的联系都是通过简单的数学加法运算表示，不仅提高了检索速度，而且省去了链式结构中使用的大量指针，节省了存储空间。虽然双数组 Trie 树能高速 O(n)完成单串匹配，并且内存消耗可控，但是软肋在于多模式匹配，如果要匹配多个模式串，必须先实现前缀查询，然后频繁截取文本后缀才可多匹配，这样一份文本要回退扫描多遍，性能极低。

使用两个数组 base 和 check 来维护 Trie 树，base 负责记录状态，check 负责检查各个字符串是否是从同一个状态转移而来，当 check[i]为负值时，表示此状态为字符串的结束。关于双数组 Trie 树的实现，这里也不准备讲太多，java 版开源的实现可以看下:https://github.com/komiya-atsushi/darts-java，有兴趣深入学习的可以去翻一翻这篇博客，会有不少惊喜:http://www.hankcs.com/program/java/双数组trie树doublearraytriejava实现.html

AC 自动机

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

如果想看具体实现分析，可以翻翻这篇:http://www.hankcs.com/program/algorithm/implementation-and-analysis-of-aho-corasick-algorithm-in-java.html，里面有详细的讲解。

这里我们主要看一下一个开源 AC 自动机实现的介绍，开源地址为:https://github.com/robert-bor/aho-corasick

大多数自由文本搜索都基于类似于 Lucene 的方法，其中，搜索文本被解析成其各个组成部分。对于每个关键字，都会进行查找以查看其发生位置。当寻找几个关键字时，这种方法很棒，但是当搜索 100,000 个单词时，这种方法非常慢（例如，检索字典）。

查找多个单词时，Aho-Corasick 算法会发光。它使用所有关键字来构建 Trie 结构，而不是将搜索文本切碎。Aho-Corasick 的关键组件包括：

• goto 表
• fail 表
• output 表

遇到的每个字符都会呈现给 goto 结构内的一个状态对象 。如果存在匹配状态，则将其提升到新的当前状态。

但是，如果没有匹配状态，该算法将发出失败信号(fail 表)， 并退回到深度较小的状态（即匹配时间较短），然后从那里继续进行，直到找到匹配状态或达到根状态为止。

只要达到与整个关键字匹配的状态，就会将其发送到输出集(output 表)，在整个扫描完成后可以读取该输出集。

该算法为 O（n）。不管给出多少个关键字，或者搜索文本有多大，性能都会线性下降。

Aho-Corasick 算法可以帮助：

• 在文本中找到要链接到或重点强调的单词;
• 在纯文本中添加语义;
• 检查字典以查看是否存在语法错误。

关于 AC 自动机的详细实现，强烈推荐:http://www.hankcs.com/program/algorithm/implementation-and-analysis-of-aho-corasick-algorithm-in-java.html