双数组树过程理解(Double-arrayTrie)

简介

双数组字典树由日本人Jun-Ichi Aoe在1989年提出，它由base和check两个数组组成，状态转移的复杂度为常数。这两个数组里面存在的内容为链接数组的下标，但是为了节约空间，在数据定义以及存储上各有千秋，除非看最原始的实现方式，否则各个博客中或者教程中的版本各有那么一点的不同，而本节就是其中的一种方式。

双数组的定义

原始的双数组定义如下：

p = base[b] + c
check[p] = base[b]

需要注意的是，这两个步骤都是赋值操作，里面涉及到的参数为b、c和base[b]的取值（这两步式子可以合为check[ base[b] + c ] = base[b]。其次，c通常也是定的，一般用符对应这的hash码。所以这里面的变量只有base[b]和b的值待定，这也就成了构建双数组数的关键。

那么问题来了，这两个值是随便定义的吗，这个~，应该说视情况而定比较合适，不同的思路执行方式不同。在我们这里，base[b]的值分两种情况，如果是字符串结尾，则设定，如果不是字符串结尾，则自己指定（但要满足一定的条件）。b的值由check数组产生。这个地方比较难描述，如果看到这一段如果比较懵，先看一下下一节 双数组树的构建

双数组树的构建

这里借鉴hanlp的双数组树的构建方法，其主体流程为：

1. 定义根节点。
   为根节点分配下标0，初始化 base[0]=1; check[0]=0; 这俩个可以随便定义，看个人喜好。以根节点为最初的父节点开始深度优先遍历，每一层的兄弟节点按照字符的散列值升序排列。
   比如：“lie”、“人民”、“浙江”、“民生”，“like” ，在根节点之后的兄弟节点的排序后为：lie、like、人民、民生、浙江。最终排好的词条为：
   lie、like、人民、民生、浙江 ----->> l – 1, 人 – 2, 民 – 3, 浙 – 4, i – 5, 生 – 6, 江 – 7, e – 8, k – 9（借鉴博客双数组Trie树 Double-arrayTrie中的定义）

2. 从父节点定义子节点的check数组。在定义check数组之前，要先检查check数组的下标是否被占用，即check[i]==0,如果被占用，则将调整父节点base数组对应的值，使得check[ base[b] + c] 为空，其中base[b]为父节点base数组对应的值，所以，在这里我们要自己定义base[b]的值，使得，check[ base[b] + c]为空。c为子节点对应hash值。通过这一步，我们可以确定子节点的下表，子节点在check表中的定义，父节点的base[b]值（注意，下标b不是在这里定义的，父节点的b是通过父父节点生成check时定义的，继续看第三步可以明白）。通过check表，可以确定子与父之间的多对一的关系。

3. 检查每个子节点，是否有孩子节点
   子节点的下标已经通过第二步check数组确定，所以，这一步只需要确定base数组在当前下标中的值。

• 如果没有孩子节点：
  则将它的base值设为负值，存储他所对应单词的字典顺序。
• 如它有孩子节点：
  则跳转到第二步，确定当前节点的在base数组中的值，以保证孩子节点在check数组中为空。

理解

检索的时候：

子节点check下标 =  base[父节点下标] + c
判断 check[子节点下标] == base[父节点下标]
> 如果不相等，表示不存在，直接跳过
> 如果相等，表示存在字符，我们需要获取当前子节点在base数组中的值，
   即，base[子节点的下标]，将当前子节点看作父节点，判断孩子节点是否存在。

注意：上面为了好描述，有几个词语需要可能不是很恰当，其意思代表着：
父节点 ： 子节点的父节点，为了方便描述，暂时用A表示
子节点： 父节点的孩子节点，即A节点的孩子节点，用B表示
孩子节点： B节点的子节点

两数组的功能：
base：数组两种功能：第一，定位子节点中check数组的下标，第二，词典中的序号（词结束时，对应的词语是什么）
check数组，判断词语是否位于词典中，通过下标在base数组的值中可以定位当前节点的子节点。

流程简介：
首先通过父节点base数组定位子节点check数组，在通过子节点check数组的下标，连接到base数组，通过当前base数组值获取孩子节点check数组的下标。构成一个闭环，直到词语结束，才打断。

参考资料

1. 双数组Trie树 Double-arrayTrie
2. hanlp实现的方式