关于Double Array Trie的理解

在只有根节点完美散列的前缀树中，其余节点都在用二分查找。当存在c个子节点时，每次状态转移的复杂度为 O(log c )。当c 很大时，依然很慢。
双数组字典树（Double Array Trie，DAT）就是一种状态转移复杂度为常熟的数据结构，双数组字典树由日本人Jun-Ichi Aoe于1989年提出

DAT 如其名，维护着两个数组——base 和 check。

DAT中，每个节点都表示一种状态，这个状态是词的生成流程
如 “自然人” 这个词的状态生成过程可以表示为：

其中方框代表了一种状态，在上一状态的基础上，加上一个变量，就会过渡到下一状态。

对于一个节点P，假设其子节点为 [n₁, n₂]，则需要寻找一个正整数（一般为从小到大遍历），使得check[base[b] + s_i.code] == 0（默认check中为0的空间表示空闲）。这里的意思是选定一个下标 b，将节点P的状态（也可以理解为关于节点P的父子关系）保存到 base 和 check 数组的下标 b 的空间，而且以状态P为前继的子节点（子状态）的状态存到了数组中，并且存储它们的位置，是与其父节点P的状态所存位置的值有关。这样就将子节点都与父节点相联，通过父节点的 base产生了关系。

然后依次检查子节点，如果有孩子节点，则表明这个词还能继续拓展，则重复进行递归拓展；如果没有孩子节点，则表示这个词可以生成，此时父节点的base和子节点的check均填充完毕，下一步该填充子节点的base（父节点的check在生成父节点时完成填充）。记子节点们的起始下标 h （子节点们在双数组中的最小的下标），则将所有子节点的base填充为 h。这样就将子节点之间关联了起来，因为他们共享一个 h 。

例：

父节点P的状态保存在index为1的空间中，其具有三个子结点，分别表示为s₁，s₂，s₃，其中s₃是可以生成词的节点，其词典序（词典数组的下标）为 -7，从父节点P拓展到状态s₁的变量的散列值为1，拓展到状态s₂的变量的哈希值为2，拓展到状态s₃的变量的哈希值为3。初始时base和check全为0：

找到一个正整数 b = 2，使得check[base[2] + s_i.code] == 0 (i=1, 2, 3)，则父节点P的base为2，子节点们的index为2+各自变量的散列值，分别为2+1、2+2、2+3，且将s_i的check填充为父节点的base，将其与父节点关联（这里b选2是为了与index作区别，更容易理解）

子节点们的下标为3、4、5，所以最小值为3，而后由于s₁和s₂有后继节点，所以他们两个的base填充为3，s₃的base填充为其表示的词的词典序的倒数 -3

思路来自 《自然语言处理入门》——何唅 ，加入了自己的理解后作上。

最后

以上就是沉静猫咪为你收集整理的关于Double Array Trie的理解的全部内容，希望文章能够帮你解决关于Double Array Trie的理解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。