cnangel手记: April 2009的归档

什么是Double Array Trie

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

一个经典的问题：
有1000瓶药物，但是其中有一瓶是有毒的，小白鼠吃了一个星期以后就会死掉，请问，在一个星期内找出有毒的药物，最少需要多少只小白鼠？
如果一个人考虑问题是二进制的考虑方法，那么肯定好不犹豫的会说10只，为什么呢？因为小白鼠能够有两种状态，1代表生，0代表死，那么10只能表示2的10次方种状态，那么也就是说能表示1024种状态，那么答案也就是10只。关于小白鼠如何吃药，读者可以仔细去想想 :)