class="entry-body">

chives/2009/04/editor-content.html?cs=UTF-8" name=".E4.BB.80.E4.B9.88.E6.98.AFDouble_Array_Trie">

class="mw-headline">什么是Double Array Trie

• Double Array Trie是TRIE树的一种变形࿰c;它是在保证TRIE树检索速度的前提下࿰c;提高空间利用率而提出的一种class="tags" href="/tags/ShuJuJieGou.html" title=数据结构>数据结构࿰c;本质上是一个确定有限自动机(deterministic finite automaton࿰c;简称DFA)。
  
• 所谓的DFA就是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表Σ的字符࿰c;它都能根据事先给定的转移函数转移到下一个状态。
  
• 对于Double Array Trie（以下简称DAT）࿰c;每个节点代表自动机的一个状态࿰c;根据变量的不同࿰c;进行状态转移࿰c;当到达结束状态或者无法转移的时候࿰c;完成查询。
  

class="entry-more"> c" class="toc ">

class="toclevel-1">class="tocnumber">1 class="toctext">什么是Double Array Trie class="toclevel-1">class="tocnumber">2 class="toctext">DAT结构 class="toclevel-2">class="tocnumber">2.1 class="toctext">DAT定义 class="toclevel-2">class="tocnumber">2.2 class="toctext">DAT匹配 class="toclevel-2">class="tocnumber">2.3 class="toctext">DAT构造 class="toclevel-2">class="tocnumber">2.4 class="toctext">DAT改进方案 class="toclevel-1">class="tocnumber">2 class="toctext">参考资料

chives/2009/04/editor-content.html?cs=utf-8" name=".E4.BB.80.E4.B9.88.E6.98.AFDouble_Array_Trie">

class="mw-headline">什么是Double Array Trie

• Double Array Trie是TRIE树的一种变形࿰c;它是在保证TRIE树检索速度的前提下࿰c;提高空间利用率而提出的一种class="tags" href="/tags/ShuJuJieGou.html" title=数据结构>数据结构࿰c;本质上是一个确定有限自动机(deterministic finite automaton࿰c;简称DFA)。

• 所谓的DFA就是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表Σ的字符࿰c;它都能根据事先给定的转移函数转移到下一个状态。

• 对于Double Array Trie（以下简称DAT）࿰c;每个节点代表自动机的一个状态࿰c;根据变量的不同࿰c;进行状态转移࿰c;当到达结束状态或者无法转移的时候࿰c;完成查询。

chives/2009/04/editor-content.html?cs=utf-8" name="DAT.E7.BB.93.E6.9E.84">

class="mw-headline">DAT结构

chives/2009/04/editor-content.html?cs=utf-8" name="DAT.E5.AE.9A.E4.B9.89">

class="mw-headline">DAT定义

• DAT是采用两个线性数组(base[]和check[])࿰c;base和check数组拥有一致的下标࿰c;（下标）即DFA中的每一个状态࿰c;也即TRIE树中所说的节点࿰c;base数组用于确定状态的转移࿰c;check数组用于检验转移的正确性。因此࿰c;从状态s输入c到状态t的一个转移必须满足如下条件：

  base[s] + c == t
  check[base[s] + c] == s

• DAT也可如下描述：
  1. 对于给定的状态s࿰c;如果有n个状态（字符c₁,c₂,...,c_n）的转移࿰c;需要在base数组中找到一段空位t₁,t₂,...,t_n࿰c;使得t₁-c₁,t₂-c₂,...,t_n-c_n都为base数组中下标为s的值࿰c;注意此处的t₁,t₂,...,t_n不一定在base数组中连续；
  2. 对于转移的状态t₁,t₂,...,t_n࿰c;其作为下标时࿰c;check[t₁],check[t₂],...,check[t_n]的值都为状态s；
• 为了便于理解࿰c;这里有一个256叉树的图（准确的说是26叉树࿰c;但是图画得不好࿰c;暂且我们把它当作256叉树吧）。

class="mt-enclosure mt-enclosure-image" style="display:inline">class="mt-image-left" alt="256x_tree.png" src="http://my.huhoo.net/archives/assets_c/2009/04/256x_tree-thumb-400x192.png" width="400" height="192" style="margin:0pt 20px 20px 0pt; float:left" />

• 图中最顶端有256的父节点࿰c;每个父节点都有256个子节点；那么无论汉字和字母࿰c;都可以分布在256个子节点上࿰c;但是如果词语只有app和class="tags" href="/tags/APPLE.html" title=apple>apple以及banana三个词语࿰c;那么256个父节点显得有些浪费࿰c;实际上只需要2个父节点就可以了。
  • 如果节点的类型为整型࿰c;我们把所有的节点进行编号的话࿰c;且直接采用词语的首字母ascii码来直接作为节点࿰c;97,98这两个父节点会使用到࿰c;其余的父节点是多余的࿰c;使用一个空指针即可。
  • 根据256叉树的定义࿰c;97和98也会有256个子节点࿰c;但是词语的第二个字母显示࿰c;97的下一个节点只有一个p(112)节点࿰c;98的下一个节点只有一个a(97)节点࿰c;则其余的节点仍然为空࿰c;这样࿰c;由于树型的算法的复杂度为O_n࿰c;即最多n次匹配即可完成一次查找࿰c;而我们可以省略不用的节点࿰c;降低空间的空闲率。

chives/2009/04/editor-content.html?cs=utf-8" name="DAT.E5.8C.B9.E9.85.8D">

class="mw-headline">DAT匹配

基于上述定义࿰c;DAT的匹配过程如下：假设当前状态为s࿰c;对于输入的字符c有：

  t = base[s] + c;
  if check[t] = s then
       next state = t;
  else
       fail;
  endif

DAT匹配的过程相对简单࿰c;很容易理解。

chives/2009/04/editor-content.html?cs=utf-8" name="DAT.E6.9E.84.E9.80.A0">

class="mw-headline">DAT构造

• 首先我们需要了解一下DAT的内存管理
  • 在DAT的构造过程当中࿰c;一般有两种构造方法：
    1. 已知所有词语࿰c;静态构造双数组；
       • 此方法构建时࿰c;是将所有词语全部放入到内存࿰c;对词语中所有的父节点和其下的子节点分别进行排序（一般为ASCII码排序）࿰c;找出最初的父节点数目和有多少个不同的子节点数࿰c;方便对内存进行分配。这样的优点是找到放置子节点空间完全能够容纳子节点࿰c;以后不需要进行扩充࿰c;相对复杂度较低࿰c;且构建速度相对很快。缺点是以后添加词语不太灵活࿰c;每次需要重新构建；
    2. 动态输入词语࿰c;动态构造双数组。
       • 当n条词语准备构建双数组时࿰c;先以添加一条词语color:red">cat为例࿰c;双数组中base[1024]数组根节点为0（默认值࿰c;当然根据“个人爱好”可以随意指定）࿰c;下标为0࿰c;为词语cat的首字符"c“(99)找一个合适的位置࿰c;比如位置100࿰c;即：

       •    base[0] = 100;

       • 此处那么在base[100]的位置下࿰c;加上字符"c"的ascii值得到下一个状态(t)的位置(199)࿰c;然后在一个合适的位置（空闲的位置）197࿰c;使得

       •    base[199]+'a'=197;

       • 那么状态(t)࿰c;即base[199]的值可以通过上述公式得到仍然为100
       • 值得注意是࿰c;在状态(f)࿰c;目前即字符"t"࿰c;结束时࿰c;其value值可以做如下处理࿰c;如果状态(f)结束࿰c;没有子节点࿰c;则

       •    base(f)=-1 * f;

       • 如果状态(t)结束࿰c;仍然有多个子节点࿰c;那么其base数组标记为

       •    base(f)=-1 * base(f);

       • 当输入第二条词语color:red">camera时࿰c;仍然按照上述方式进行࿰c;当进行到字符a时࿰c;字符a位置的下标为197࿰c;检查check[base[197]+'m']是否为空位。
         • 如果为空位࿰c;则base[197]的值仍然可以为100；
         • 否则需要重新寻找两个空位位置Ψ(base[197]+'m')࿰c;λ（base[197]+'t'）࿰c;使得 base[base[197]+'m']=-1(-1标记为空位状态࿰c;"m"为camera的第三个字符)和 base[base[197]+'t']=-1（"t"为cat的第三个字符）࿰c;即第二级节点a后面的两个新节点能有位置存放新的偏移量࿰c;并使得 check[base[197]+'m']=197和check[base[197]+'t']=197即可࿰c;那么base[197]的值需重新指向到新的位置(Ψ+λ-'m'-'t')/2。
       • 接着继续重新构建下面新两个节点的DAT结构࿰c;且第一个节点的结构构造完成后࿰c;需要清除原来的构建。
       • 动态构造双数组能够很方便的动态插入词语࿰c;不需要重新构造整个TRIE树࿰c;但是实现的逻辑相对复杂一些。
  • 若初始状态申请的数组大小不足时࿰c;需要进行扩充࿰c;并将原来的数组拷贝到新增大的数组上࿰c;且原来的数组一般需要进行内存释放࿰c;如下图：

class="mt-enclosure mt-enclosure-image" style="display:inline">class="mt-image-left" alt="dat.png" src="http://my.huhoo.net/archives/assets_c/2009/04/dat-thumb-400x213.png" width="400" height="213" style="margin:0pt 20px 20px 0pt; float:left" />

• DAT构造中࿰c;check数组需要指向父节点࿰c;即base数组中父节点的下标即可࿰c;这里有一副简图࿰c;描述了构造DAT双数组的方式：

class="mt-enclosure mt-enclosure-image" style="display:inline">class="mt-image-left" alt="trie.png" src="http://my.huhoo.net/archives/assets_c/2009/04/trie-thumb-550x380.png" width="550" height="380" style="margin:0pt 20px 20px 0pt; float:left" />

chives/2009/04/editor-content.html?cs=utf-8" name="DAT.E6.94.B9.E8.BF.9B.E6.96.B9.E6.A1.88">

class="mw-headline">DAT改进方案

• DAT相对普通TRIE树来说࿰c;提高了空间的利用率࿰c;但是空间利用率还不是最好的。
• 比如单词elephant(8个字符)࿰c;如果所有词语当中只有一个以e开头的词语࿰c;一般我们实现trie的结构写成

   class="tags" href="/tags/STRUCT.html" title=struct>struct BC_st
   {   
       int base;
       int check;
   };

• 那么整个词语在DAT中占用的空间是4*2*8=64字节。其实class="tags" href="/tags/CunChu.html" title=存储>存储没有必要浪费那么多空间࿰c;在DAT结构里面࿰c;完全可以以7个字节来class="tags" href="/tags/CunChu.html" title=存储>存储lephant࿰c;查询的时候lephant实现字节查找就可以了。
• DAT是一个树型的结构࿰c;不断发散的结构࿰c;如果在对面实现一个同样的结构࿰c;相对来说࿰c;会减少一半的空间体积࿰c;如图所示：

class="mt-enclosure mt-enclosure-image" style="display:inline">class="mt-image-left" alt="reversedat.png" src="http://my.huhoo.net/archives/assets_c/2009/04/reversedat-thumb-550x237.png" width="550" height="237" style="margin:0pt 20px 20px 0pt; float:left" />

• 当然上述的结构已经有人实现过࿰c;实现比较复杂。
• 另外࿰c;在DAT双数组当中࿰c;有很多的空闲空间未得到充分利用࿰c;可以通过链表将未使用的空间串联起来࿰c;更加合理的利用࿰c;提高数据密集程度。

chives/2009/04/editor-content.html?cs=utf-8" name=".E5.8F.82.E8.80.83.E8.BF.9E.E6.8E.A5">

class="mw-headline">参考连接

• http://linux.thai.net/~thep/datrie/datrie.html