程序员的自我修养
Home » Java语言, 算法拾遗 » Trie树

Trie树

0条评论3,154次浏览

前几天与学弟聊到他最近的面试题中有一题需要计算两个字符串的最长公共子字符串。当时想到了KMP算法可能可以解决,但仔细想想可能是个比较复杂的任务。后来在网上看到有不少人说用trie树来解决。然后我就糊涂了,记忆中trie树貌似只能解决最长公共前缀的问题吧。于是复习一遍Trie树。

简介

Trie树百度百科解释如下:又称单词查找树,字典树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。

Trie树的直观结构如图所示:
trie tree

图中红色的点代表此处有字符串在此结束,上图中共有7个字符串:abc、abcd、abd、b、bcd、efg、hij(百科中的图,空白边就算作j好了)。

Trie树的使用场景

  • 字符串检索,词频统计,搜索引擎的热门查询。
  • 字符串最长公共前缀。
  • 字符串排序。
  • 作为其他数据结构和算法的辅助结构,如后缀树,AC自动机等。

至于“计算两个字符串的最长公共子字符串”这样的需求无法采用trie树实现,就算能实现也需要大量的改变。

Trie树的缺陷

Trie树占用内存较大,例如:处理最大长度为20、全部为小写字母的一组字符串,则可能需要 \(26^{20}\) 个节点来保存数据。而这样的树实际上稀疏的十分厉害,可以采用左儿子右兄弟的方式来改善,也可以采用需要多少子节点则添加多少子节点来解决(不要类似网上的示例,每个节点初始化时就申请一个长度为26的数组)。

Wiki上提到了采用三数组Trie(Tripple-Array Trie)和二数组Trie(Double-Array Trie)来解决该问题,此外还有压缩等方式来缓解该问题。

Java代码示例

网上相关的示例很多,但没有可以做到排序统计词频获取最长公共前缀的,且都是采用长度为26的数组来保存信息。内存浪费且无法处理带有特殊字符或者数字的字符串。现实现一版没有以上缺点的Java版本。

运行结果:

参考文献

(转载本站文章请注明作者和出处 程序员的自我修养 – SelfUp.cn ,请勿用于任何商业用途)
标签:,
发表评论


profile
  • 文章总数:78篇
  • 评论总数:252条
  • 分类总数:31个
  • 标签总数:43个
  • 运行时间:946天

大家好,欢迎来到selfup.cn。

这不是一个只谈技术的博客,这里记录我成长的点点滴滴,coding、riding and everthing!

最新评论
  • pacificLee: :twisted:
  • 小码: 为什么没有后面的呢,只有前10个
  • Anonymous: :lol:
  • Anonymous: :razz: 楼主是属于会聊天的。 我想问,sqoop发了几个版本了,应该没这些问题了吧。
  • Anonymous: Config.kafkaConfig.kafkaGroupI d 这个是指自己配置的group id 还是从 import org.apache.kafka.common.config .Config 这个类...
  • Anonymous: ZkUtils.getPartitionsForTopics (zkClient, Config.kafkaConfig.topic) 那个方法是在 spark-streaming_2.10 中 kafka...
  • Anonymous: ZkUtils.getPartitionsForTopics (zkClient, Config.kafkaConfig.topic) 你确定 kafka 里面有这个类 ? 个人在kafka 最新 稳定版...
  • Anonymous: :roll:
  • Anonymous: 很不错,试问有java版的吗?
  • Anonymous: 赞
  • Anonymous: 哈哈 看楼主的吐槽乐死了 where子句是可以写的 同样找不到资料 一点点试出来的 select id from xxxx where ${CONDITIONS} and 1=1 and 2=2 limit 4
  • EVIL: 我在运行完C4.5的代码后,显示 defined object DecisionTreeTest 是什么意思?这是有错误吗?运行结果在哪里看?
  • sf: 楼主的问题,我都遇到。。。没办法项目已经定型了,最后都硬着头 皮一个一个的改了源码
  • zz: 我去,楼主你真及时,我们今天上了新的HTTP2 push之后也发现速度曲线很奇怪,开始有200k/min,跟 另一台老的推送协议速度差不多,但是过了一会,立马降到只有几k /min,百思不得其解,我们还用了一个海外代理,在...
  • qi365: :mad: 很可恶,百度助纣为虐~
  • qi365: :? :shock: haha~ very good~
  • 张是大: 《深入浅出Spark机器学习实战(用户行为分析)》 课程网盘下载:http://pan.baidu.com/s/ 1mixvUli 密码:1pfn
  • Anonymous: :???:
  • Anonymous: 我用着sqoop感觉还可以,select 几十个字段也没事,估计是版本低。。
  • Anonymous: :grin: