双数组Trie树高效构建有向无环图-白红宇

图

图是很常见的一种结构了，不管是数据结构算法中的各种图结构，还是机器学习中的概率图。图主要是由若干顶点及连接两顶点的边所构成的图形，通过它可以用来描述某些事物之间的某种特定关系。

有向无环图，即 Directed Acyclic Graph，属于有向图，图结构中不存在环，可用来表示事件之间依赖关系。

Trie 是一种搜索树，它的 key 都为字符串，通过 key 可以找到 value。能做到高效查询和插入，时间复杂度为O(k)，缺点是耗内存。它的核心思想就是减少没必要的字符比较，使查询高效率，即用空间换时间，再利用共同前缀来提高查询效率。

Trie 树的根节点不包含字符，根节点到某节点的路径连起来的字符串为该节点对应的字符串，每个节点只包含一个字符，此外，任意节点的所有子节点的字符都不相同。

比如如下，将五个词语添加到 Trie 树中，最后的结构如图所示。

TrieTree tree = new TrieTree();tree.put("美利坚");tree.put("美丽");tree.put("金币");tree.put("金子");tree.put("帝王");复制代码

Trie 树的实现可以有多种方法，主要的差异是存储结构的不同，不同的存储结构将导致占用空间不同。常见有定长数组方式、变长列表等。

而其中有一种方式能让性能和占用空间都达到较好水平，这就是双数组方式，即双数组 Trie 树。双数组意思就是由两个数组来实现存储，分别为 base 和 check 数组，它们时两个互相平行的数组。

base 数组和 check 数组记录了所有转换状态，假如接收了一个字符 c ，要从状态 s 移动到 t 的转移，则对应在双数组中的条件是：

check[base[s] + c] = sbase[s] + c = t复制代码

根据现有词典将所有状态都建立起来后，后面查询时则直接根据字与字之间的状态转换并根据 check 数组的值即可以判断是否已经完成单词的搜索，其中 base 数组主要作用是可以用来判断是否存在某些字到字的状态转换，而 check 数组则主要用来判断是否是一个完整词语。

比如对于这么个任务：存在一个大词典，要根据该词典找出一段文章包含的所有可能的词，这样就能从头到尾构建若干条路径，而且每个词对应的边都可能有不同的权重值，而最终将该段文章怎样分词取决于哪个路径的值最小或者哪个路径走到终点的概率最大。

为了构建这个有向无环图，会涉及到遍历大量数据集的问题，这正是引入双数组 Trie 树的原因，将耗时的搜索交给双数组 Trie 树，只需要从头到尾暴力匹配即能完成有向无环图的创建了。

引入 AC 自动机应该还能继续优化。

https://github.com/sea-boat/TextAnalyzer/blob/master/src/main/java/com/seaboat/text/analyzer/data/structure/DAGModel.java

-------------推荐阅读------------

跟我交流，向我提问：

欢迎关注：