本文主要用来学习Double-Array trie的相关知识。
Double-Array trie是Trie结构的压缩形式，仅用两个数组来表示Trie，这个结构有效的结合数字搜索树(Digital Search Tree)检索时间高效的特点和链式表示的Trie空间结构紧凑的特点。双数组Trie的本质是一个确定有限状态自动机(DFA)，每个节点代表自动机的一个状态，根据不同的变量，进行状态转移，当到达结束状态或无法转移时，完成一次查询操作。在双数组所有键中，包含的字符之间的联系都是通过简单的数学加法运算表示的，不仅提高了检索速度，而且省去了链式结构中使用的大量指针，节省了存储空间。
在了解Double-Array trie之前，我们先了解一下“确定有限状态自动机”。在数学理论中，确定有限状态自动机或确定有限自动机（deterministic finite automation, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表的字符，它能够根据实现给定的函数转移到下一个状态。简单的说，就是当前状态根据一个公式和状态的确定值，能够到达另外一个状态，而且要到达的状态是确定的。如图：
确定有限自动状态机
图中的每个字代表一个状态，并且每个状态都有一个固定的变量。
在了解了确定优先状态自动机之后，我们来了解一下Double-Array trie。Double-Array trie的核心是使用两个整型数组base和check来分别存储状态以及前驱状态。说的简单一些，base用来存储状态，check用来验证。在状态的转移过程中，有如下公式：
上面的公式表示 base[s]的值 + 状态的变量 = t下标，check[t]的值 = s下标。
举例来说明：
在学习Douoble-Array trie和看DoubleArrayTrie源码的时候，参考了以下文章，在此表示感谢：
双数组Trie树(DoubleArrayTrie)Java实现
Double Array Trie