栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Tire 字典树

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Tire 字典树

一、概述

字典树,又称单词查找树,Tire树,是一种树形结构,是一种的哈希树的变种。

典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。

  • 优点:最大限度地减少无谓的字符串比较,查询效率比哈希表高。
  • 核心思想:是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
二、基本性质
  1. 根节点不包含字符,除了根节点外的每一个子节点都包含一个字符
  2. 从根节点到某一个节点,路径上经过的字符连接起来,级市该节点的对应的字符串
  3. 每个节点的所有子节点包含的字符都不同
三、Tire 树定义
  1. 在不同情景下,每个节点有若干(26个英文字母)指向下个节点的指针;
  2. 仅靠判断节点是否是叶子节点来判断单词是否查询完成是不可行的,因为有些单词本身就是其他单词的一部分[如: pan 是 panda 的一部分],故添加 boolean 值 isWord 来判断当前的节点是否代表一个单词的结尾;
class Node {
    
    public boolean isWord;
    
    public TreeMap 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 搜索
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;
}


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

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/972592.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号