双数组TRIE树 原理.ppt

1、双数组TRIE树 原理,Double-Array Retrieval Tree BySevnsson McM,字符串处理中词汇查找算法,单个词查找 全字匹配查找n2 strstr () CString:find() KMP算法去GOOGLE查 单个词汇,字符回朔 多个词查找 整词二分法 逐字二分法 Retrieval Tree (Trie树),Trie树是一种用于快速检索的多叉树结构,Trie的性能,在trie树中查找一个关键字的时间和树中包含的结点数无关，而取决于组成关键字的字符数。而二叉查找树的查找时间和树中的结点数有关O(log2n)。 如果要查找的关键字可以分解成字符序列且不是很长，利

2、用trie树查找速度优于二叉查找树。如：若关键字长度最大是5，则利用trie树，利用5次(log26n)比较可以从26511881376个可能的关键字中检索出指定的关键字。而利用二叉查找树至少要进行log2265=23.5次比较。,Trie DFA (有向状态机 形式语言),它实际上是一种(DFA) .在此树结构中，每个节点对应一个 DFA状态, 每个从父节点指向子节点的有向线对应一个DFA转换. 词表：啊，阿根廷，阿胶，阿拉伯，阿拉伯人，埃及,1,2,3,4,11,7,5,8,6,9,11,啊,阿,埃,及,根,胶,拉,廷,伯,人,三数组Trie (Tripple-array Trie),一个

3、DFA压缩可以使用3个线性数组来完成,名字是base,next, check. 因此一个Trie可以使用3个arrays来表示. 3数组结构组成: base. 其中的每个元素对应trie上的一个节点.对于节点s,bases 是next和check的在转换表中的起始位置.如果basei为负值或没有next转换，表示该状态为一个词语。 next. 这个数组被叫做check, provides a pool for the allocation of 稀少的行向量在转换表中. 从每个节点的转换向量数据,存储在此数组中 check. 此数组和next平行。它标示了每个表格的拥有者在next.,三数组T

4、rie 示例,编码(C):啊-1，阿-2，埃-3，根-4，胶-5，拉-6，及-7，廷-8，伯-9，人-10 从状态 S - 阿 到状态 T1 阿根 T2 阿胶 T3 阿拉 nextbases +c=t checkbases +c=s nextbaseS +4= T1 (阿根) checkbaseS +4=S (阿) nextbaseS +6= T3 (阿拉) checkbaseS +6=S (阿),三数组Trie调整迁移(Re-Locate),Procedure Relocate(s : state; b : base_index) Move base for state s to a new

5、 place beginning at b begin foreach input character c for the state s i.e. foreach c such that checkbases + c = s begin checkb + c := s; mark owner nextb + c := nextbases + c; copy data checkbases + c := none free the cell end; bases := b end,在某些必要的时候，我们需要对一个状态s所对应的所有转换可能 编码c1 c2 cn-1 cn 进行数组状态存储位置的

6、迁移 构造中发生冲突(某个转换状态T(s, ci ) 使用过程中进行数据插入而发生冲突,三数组Trie next check 数组空间浪费,数组空间存在缝隙 三个数组功能的比较 将base 与 next 进行功能归并 通俗的说就是把base数组中的表示穿插在next中进行表示,而next中有数值的项目直接表示为base内容 双数组TRIE,双数组Trie(Double-Array Trie),双数组TRIE,三数组TRIE,双数组Trie(Double-Array Trie),s,t,c,base,check,t,c,Bases,s,双数组Trie调整迁移(Re-Locate),Procedu

7、re Relocate(s : state; b : base_index) Move base for state s to a new place beginning at b begin for each input character c for the state s i.e. for each c such that checkbases + c = s begin checkb + c := s; mark owner baseb + c := basebases + c; copy data the node bases + c is to be moved to b + c;

8、 Hence, for any i for which checki = bases + c, update checki to b + c for each input character d for the node bases + c begin checkbasebases + c + d := b + c end; checkbases + c := none free the cell end; bases := b end 过程要要相对于三数组情况复杂 (时空转换定理),base,check,b,bases,s,t,t,baset,u,c,c,d,双数组Trie 一种构造结果,词表：啊，阿根廷，阿胶，阿拉伯，阿拉伯人，埃及,双数组TRIE,编码(C):啊-1，阿-2，埃-3，根-4，胶-5，拉-6，及-7，廷-8，伯-9，人-10,双数组Trie