双数组trie树的构建

NLP中trie树常用于做快速查询，但普通的trie树由于要保存大量的节点信息，当储存的词量非常大时，不仅所占空间巨大，而且查询的速度也不够快。而双数组trie树就可以比较好的解决这两个问题。

之所以叫双数组trie树，是因为它只用base[]和check[]两个数组就将整个trie的信息储存了起来，这两个数组的构建规则是：
$\begin{aligned} &base[i] + code(x) = j\\ &check[j] = i \end{aligned}$
其中i，j都是base array的index，base array的长度是trie树中节点的个数，每个节点在base array中都有一个对应的index。

base[]数组用于记录跳转结构， base array中index为i的那个节点，如果按照字符x转移，会转移到index为j的节点
check[]数组用于 标识出 base array 中每个状态的前一个状态，其主要作用是检验按base做转移的转移正确性
code(x)是字符x的编码，现实中为了方便通常直接用char code

构建base array

下面我们看一个例子来学习base array的构建方法：

现在有“清华”、“清华大学”、“清新”、“中华”、“华人”五个词，构成的trie树如下图所示：
在这里插入图片描述
假设例树的字符编码表为：

char	清	华	大	学	新	中	人
code	1	2	3	4	5	6	7

初始化root的base index为0，base值记为1。首先看root的所有子节点"清，中，华"：

base[0] + code(清) = 2，此时位置2空闲，因此“清”放入位置2
base[0] + code(中) = 7，此时位置7空闲，因此“中”放入位置7
base[0] + code(华) = 3，此时位置3空闲，因此“中”放入位置3

目前base array的情况如下：

position	0	1	2	3	4	5	6	7	8	9	10
char	root		清	华				中
base	1

每次遍历完一个节点的所有子节点，只可以确认当前节点的base值，以及它的子节点的index位置
子节点的base值此时会默认继承当前节点的base值，但在遍历子节点的子节点时，一旦有冲突，子节点的base值就会做相应修改

接下来遍历第二层的节点"华，新，华，人"：

base[2] + code(华) = 3，冲突！因此 base[2] 修改为2；base[2] + code(华) = 4，可用，因此 “清华” 放入位置4
base[2] + code(新) = 7，冲突！因此 base[2] 修改为3；base[2] + code(新) = 8，可用，因此 “清新” 放入位置8
因为base[2] 再次北被修改，所以“清华”的位置要重新计算：base[2] + code(华) = 5，可用，因此 “清华” 放入位置5
base[7] + code(华) = 3，冲突！因此 base[7] 修改为2；base[7] + code(华) = 4，可用，因此 “中华” 放入位置4
base[3] + code(人) = 8，冲突！因此 base[3] 修改为2；base[3] + code(人) = 9，可用，因此 “华人” 放入位置9

目前base array的情况如下：

position	0	1	2	3	4	5	6	7	8	9	10
char	root		清	华	中华	清华		中	清新	华人
base	1		3	2				2

接下来遍历第三层的节点"大"：

base[5] + code(大) = 6，可用；因此 “清华大” 放入位置6

目前base array的情况如下：

position	0	1	2	3	4	5	6	7	8	9	10
char	root		清	华	中华	清华	清华大	中	清新	华人
base	1		3	2				2	3

接下来遍历第四层的节点"学"：

base[6] + code(学) = 7，冲突！base[6] 修改为4；base[6] + code(学) = 8，还是冲突！base[6] 修改为5；base[6] + code(学) = 9，还是冲突！base[6] 修改为6；base[6] + code(学) = 10，可用，因此 “清华大学” 放入位置10

目前base array的情况如下：