字典树（Tire）
一、概述
字典树，又称单词查找树，Tire树，是一种树形结构，是一种的哈希树的变种。
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
- 优点：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
- 核心思想：是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
二、基本性质
- 根节点不包含字符，除了根节点外的每一个子节点都包含一个字符
- 从根节点到某一个节点，路径上经过的字符连接起来，级市该节点的对应的字符串
- 每个节点的所有子节点包含的字符都不同
三、Tire 树定义
- 在不同情景下，每个节点有若干（26个英文字母）指向下个节点的指针；
- 仅靠判断节点是否是叶子节点来判断单词是否查询完成是不可行的，因为有些单词本身就是其他单词的一部分[如: pan 是 panda 的一部分]，故添加 boolean 值 isWord 来判断当前的节点是否代表一个单词的结尾；
class Node {
/* 是否标记为单词 */
public boolean isWord;
/* 表示每一层的单词种类(可通过多种方式实现) */
public TreeMap<Character, Node> next;
public Node(boolean isWord) {
this.isWord = isWord;
next = new TreeMap<>();
}
public Node() {
this(false);
}
}
四、Tire 建树
// 向Trie中添加一个新的单词 word
public void add(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null)
cur.next.put(c, new Node());
cur = cur.next.get(c);
}
if (!cur.isWord) {
cur.isWord = true;
size++;
}
}
五、Tire 搜索
/**
* 查询单词word是否在Trie中
* @param word 单词
* @return
*/
public boolean contains(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null)
return false;
cur = cur.next.get(c);
}
return cur.isWord;
}
/**
* 查询是否在Trie中有单词以prefix为前缀
* @param prefix 前缀
* @return
*/
public boolean isPrefix(String prefix) {
Node cur = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (cur.next.get(c) == null)
return false;
cur = cur.next.get(c);
}
return true;
}
六、完整代码示例
https://github.com/perkinls/java-summary/
关注公众号 ，专注于java大数据领域离线、实时技术干货定期分享！如有问题随时沟通交流！ www.lllpan.top
正文到此结束
