AC自动机-2（AhoCorasickDoubleArrayTrie）

本文主要是介绍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方法。

这篇关于AC自动机-2（AhoCorasickDoubleArrayTrie）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---