双数组trie树原理

上传人:ji****n 文档编号:54719465 上传时间:2018-09-18 格式:PPT 页数:15 大小:121.50KB
返回 下载 相关 举报
双数组trie树原理_第1页
第1页 / 共15页
双数组trie树原理_第2页
第2页 / 共15页
双数组trie树原理_第3页
第3页 / 共15页
双数组trie树原理_第4页
第4页 / 共15页
双数组trie树原理_第5页
第5页 / 共15页
点击查看更多>>
资源描述

《双数组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协会,

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 生活休闲 > 社会民生

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号