字典树的原理以及Java实现

作者: blogchong | 分类: 原创-数据挖掘 | 评论:0人 | 浏览:

Trie树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。 典型应用是用于统计和排序大量的字符串(但不仅限于字符串), 所以经常被搜索引擎系统用于文本词频统计。

它的优点是:

利用字符串的公共前缀来节约存储空间,最大限度的减少无谓的字符串比较,查询效率比哈希表高。

比如说我们想储存3个单词,sky、skyline、skymoon。如果只是单纯的按照以前的字符数组存储的思路来存储的话,那么我们需要定义三个字符串数组。但是如果我们用字典树的话,只需要定义一个树就可以了。在这里我们就可以看到字典树的优势了。

More...