鸽鸽经验网

 找回密码
 立即注册
搜索
热搜: 经验 技巧 心得
开启左侧

仅仅Trie树

[复制链接]
msmkmm2012VIP会员 发表于 2019-7-13 07:45 | 显示全部楼层 |阅读模式

综述  码蚁之家
又称单词查找树,T树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。
T树结构的优点在于:) 不限制子节点的数量; ) 自定义的输入序列化,突破了具体语言、应用的限制,成为一个通用的框架; ) 可以进行最大T序列长度的限制;) 根据已定阈值输出重复的字符串;) 提供单个字符串频度查找功能;) 速度快,在两分钟内完成年月份人民日报(行)的重复字符串抽取工作。
性质
它有个基本性质: ) 根节点不包含字符,除根节点外每一个节点都只包含一个字符。 ) 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。) 每个节点的所有子节点包含的字符都不相同。
基本操作
其基本操作有查找、插入和删除,当然删除操作比较少见我在这里只是实现了对整个树的删除操作,至于单个的删除操作也很简单
实现方法
搜索字典项目的方法为:  () 从根结点开始一次搜索;   () 取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索;   () 在相应的子树上,取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。   () 迭代过程…… () 在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。 其他操作类似处理 T原理——T的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。代码实现复制代码 代码如下  N = ; 声明常量 ; T_{ S; 记录此处是否构成一个串。 T_*[N];指向各个子树的指针,下标-代表字符 T_()S() { (,NULL,()); }}; T{ T(); ( * ); (* ); T(T_ *);  T(T_ *);   T_* ;};TT(){  = T_();} T( * ){ T_* = ; (*) { (-&;[*-''] == NULL)不存在则建立 { T_ * =  T_(); -&;[*-''] = ; }   = -&;[*-'']; 每插入一步,相当于有一个新串经过,指针要向下移动 ++; } -&;S = ; 到达尾部,标记一个串} T( *){ T_* = ; (*&& ) { = -&;[*-'']; ++; } (!=NULL && -&;S);} TT(T_ *){ ( =;  &; N; ++) { (-&;[]!= NULL) { T(-&;[]); } } ;} () 简单测试{ T ; ("");  ("");  * = ""; (); (""); (("")) { ("\"); 已经插入了 }}有时,我们会碰到对字符串的排序,若采用一些经典的排序算法,则时间复杂度一般为O(*),但若采用T树,则时间复杂度仅为O()。 T树又名字典树,从字面意思即可理解,这种树的结构像英文字典一样,相邻的单词一般前缀相同,之所以时间复杂度低,是因为其采用了以空间换取时间的策略。 下图为一个针对字符串排序的T树(我们假设在这里字符串都是小写字母),每个结点有个分支,每个分支代表一个字母,结点存放的是从节点到达此结点的路经上的字符组成的字符串。 将每个字符串插入到树中,到达特定的结尾节点时,在这个节点上进行标记,如插入"",第一个字母为,沿着往下,然后第二个字母为,沿着往下,第三个为,沿着往下,由于字符串最后一个字符为'\',因而结束,不再往下了,然后在这个节点上标记++,即其个数增加 之后,通过前序遍历此树,即可得到字符串从小到大的顺序。实现代码如下(++、VC++都编译通过):复制代码 代码如下# &;&;# &;&;  ;# NUM  N{  ; 记录该处字符串个数 N* _[NUM]; 分支 * _; 记录到达此处的路径上的所有字母组成的字符串 N();}; T{ N* ; T();  (* );  (N* &, ** , & );};程序未考虑动态内存 (){ **  =  *[]; [] = ""; [] = ""; [] = ""; [] = ""; [] = ""; [] = ""; [] = ""; [] = ""; [] = ""; [] = ""; [] = ""; [] = ""; 建立树 T*  =  T(); (  = ;  &; ; ++) -&;([]);   = ; -&;(-&;, , ); (  = ;  &; ; ++) &;&;[]&;&;;  ;}NN(){  = ; (  = ;  &; NUM; ++) _[] = NULL; _ =  []; _[] = '\';}TT(){  =  N();} T(* ){   = ; N*  = ; 将[]插入到树中 ([] != '\') { 如果包含[]的分支存在,则新建此分支 (-&;_[[] - ''] == NULL) { -&;_[[] - ''] =  N(); 将父节点中的字符串添加到当前节点的字符串中 (-&;_[[] - '']-&;_, -&;_);  _[]; _[] = []; _[] = '\'; 将[]添加到当前节点的字符串中 (-&;_[[] - '']-&;_, _);  = -&;_[[] - '']; }  {  = -&;_[[] - '']; } ++; } -&;++;}采用前序遍历 T(N* &, ** , & ){ ( != NULL) { (-&; != ) { (  = ;  &; -&;; ++) [++] = -&;_; } (  = ;  &; NUM; ++) { (-&;_[], , ); } }}
            
            
您可能感兴趣的文章J中实现双数组T树实例P T树实现字典排序C# TT介绍及实现方法TT服务-组件构成及其作用介绍详解字典树T结构及其P代码实现T树(字典树)的介绍及J实现
回复

使用道具 举报

免责声明|联系我们|鸽鸽经验网 ( 豫ICP备17031277号 )

GMT+8, 2019-10-21 18:21

Powered by Discuz! 7.0

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表