《双数组trie树原理》由会员分享，可在线阅读，更多相关《双数组trie树原理（15页珍藏版）》请在金锄头文库上搜索。
1、双数组TRIE树 原理,Double-Array Retrieval Tree By Sevnsson 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平行。它标示了每个表格的拥有者在n
4、ext.,三数组Trie 示例,编码(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
5、base for state s to a new 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 所对应的所有转换可能 编码
6、c1 c2 cn-1 cn 进行数组状态存储位置的迁移 构造中发生冲突(某个转换状态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,双
7、数组Trie 调整迁移(Re-Locate),Procedure 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 base
8、s + c is to be moved to b + c; 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 优缺点,优点: 查询动作 时间复杂度空间复杂度 最优 中科院相关资料见右缺点: 构造调整过程中，每个状态都依赖于其他状态，所以当在词典插入或删除词语的时候，往往需要对双数组结构进行全局调整，灵活性较差。,感谢,http:/ 中科院计算技术研究所 浙江工商大学ACM协会,
