AC自动机-2（AhoCorasickDoubleArrayTrie）
Aho-Corasick Double Array Trie (AC DAT) 是一种结合了Aho-Corasick算法和Double Array Trie的数据结构，DAT保证了较高的存储效率，AC保证了多模式字符串匹配效率。
一个经典的实现是hanlp的Java实现：AhoCorasickDoubleArrayTrie。
主要构造过程如下：
public void build(Map<String, V> map){// 把值保存下来v = (V[]) map.values().toArray();l = new int[v.length];Set<String> keySet = map.keySet();// 构建二分trie树addAllKeyword(keySet);// 在二分trie树的基础上构建双数组trie树buildDoubleArrayTrie(keySet.size());used = null;// 构建failure表并且合并output表constructFailureStates();rootState = null;loseWeight();}可以看到，其构建过程首先构造了一个普通的Trie树，然后基于这个普通Trie树构建了DAT，在构建DAT的过程中，也给先前构建好的普通Trie树添加了DAT的索引
sibling.getValue().setIndex(begin + sibling.getKey());构造完DAT之后，又基于普通Trie树构造fail表（普通Trie树中上一步构建DAT时添加了DAT索引），构造完成后，将所有辅助数据结构删除，包括普通Trie树，例如上述代码中的 和
, 最后又压缩了DAT了，loseWeight();，实际是一个为尾压缩的方法。
AhoCorasickDoubleArrayTrie的构建可能会消耗大量内存，在实际使用中，可以先在一个大内存的机器上构建好AC DAT，序列化成文件，然后在使用的节点上直接反序列进行使用，正如 hanlp实现中的save和load方法。