trie树是一种常用的词典存储逻辑结构。双数组trie树是trie树的一种性能较好的具体实现方法。
由日本学者发明，知名NLP工具CRF++的词典即是由此实现。
CRF++所用的darts是实现双数组trie树的一份代码（文档中文翻译），整个词典就是数组元素由两个int组成（即“双”数组名字的来历）。
darts-clone有与darts相同的接口，但词典数组由一个int搞定，空间减小一半的同时速度还快些。
关于trie树与双数组trie树的原理非一两句话能介绍透彻，不过好在网上的资料都比较多，不难找到。 本文想介绍一下darts-clone用了啥黑科技达到这种效果的。
darts代码里的两个int， 分别叫做base和check。base用于计算当前节点的儿子节点，即base+儿子节点对应编码=儿子节点下标。check 用于检查儿子节点的正确性，因为不同的base+不同的编码可能得到相同的下标，check一般存的是其父亲节点的base。 如果是叶子节点，base存储的即是词条对应的value。
所以看到base和check的量纲都是下标，用4个字节的int似乎也无可厚非。下面就来看看darts-clone用来哪些方法用一个int替代两个int的，并且速度还有所提升。
用异或代替加法
用base找儿子节点的下标时，使用异或。不需要进位，感觉会比加法快一些，不过不太了解现在的CPU。
用一个bit表示是否是叶子节点
是叶子节点，剩下31bit用来表示value。虽然比darts少了一个bit，不过大多数情况下是可以接受的。
非叶子节点，用一个bit表示是否自身有叶子节点
免去了根据base读一次内存的时间。
非叶子节点，用一个byte代替check的功能
通常trie树用来存字符串，一个节点对应的值是一个char，所以这个假设也可以接受。darts一个节点的值可以是int。
非叶子节点，用剩下的22个bit存储了一部分的30bit数
这一点也比较巧妙。22个bit中有一个指示位。为0的时候，剩下21bit表示一个21位的数；为1的时候，剩下21bit表示一个低9位为0，高21位可以非零的30位的数。
