详解Java前缀树Trie的原理及代码实现

目录
  • Trie的概念
  • Trie的实现
    • 基本结构
    • 构建Trie
    • 查找字符串
  • Trie的总结

Trie的概念

Trie(发音类似 “try”)又被称为前缀树、字典树。Trie利用字符串的公共前缀来高效地存储和检索字符串数据集中的关键词,最大限度地减少无谓的字符串比较,其核心思想是用空间换时间。

Trie树可被用来实现字符串查询、前缀查询、词频统计、自动拼写、补完检查等等功能。

Trie树的三个性质:

  • 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
  • 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
  • 每个节点的所有子节点包含的字符都不相同。

Trie的实现

Trie是一颗非典型的多叉树形结构,多叉树是因为一个节点可以有多个字节点,而非典型在于节点中没有专门的字段直接保存此节点的值,而是通过一个数组或者map保存了当前节点的所有下层子节点的值,也正是因此,根节点不表示任何字符。

基本结构

最简单的前缀树的结构如下:

  • 内部包含一个哈希表next,存储着子节点的值到对应的节点的映射关系。
  • 还有一个布尔值isEnd,用来标识该节点是否是一个字符串的结束。
  • 调用无参构造器将会初始化这两个属性。

实际上,还可以包含其他的属性以实现特定的功能,例如加入count表示以当前单词结尾的单词数量,加入prefix表示以该处节点之前的字符串为前缀的单词数量。

另外,对于下层子节点的存储,如果字符串仅包含小写字母,或者固定范围的字符,那么我们可以使用定长(例如26)的数组来表示next,这样省去了hash操作的开销,但同样可能造成空间的浪费。

class Trie {
    /**
* 经过该节点的字符串的下层节点
*/
    Map<Character, Trie> next;
    /**
* 该节点是否是一个字符串的结束
*/
    boolean isEnd;

    public Trie() {
        this.next = new HashMap<>();
        this.isEnd = false;
    }

}

构建Trie

通过调用构造器初始化一个Trie的根节点,通过insert操作向前缀树中插入关键词字符串(模式串)。

可以看到其实现的方法比较简单:将字符串转换为char数组,顺序遍历char数组的每个字符,然后从根节点开始判断该节点的下层子节点映射next:

  • 如果不包含此字符,那么加入一个新子节点进去,值对应着当前字符。然后使用该子节点,进入下一次循环判断下一个字符。
  • 如果包含此字符或者新插入了节点,那么当前字符获取对应的子节点,进入下一次循环判断下一个字符。

循环完毕,我们完成了当前字符串的Trie构建,那么还需要将最后一个节点的isEnd改为true,表示该节点是一个字符串的结束。

public void insert(String word) {
    //初始默认为根节点,根节点不包含任何字符
    Trie cur = this;
    //遍历该字符串的字符数组
    for (char c : word.toCharArray()) {
        //如果该节点的下层不包含此字符,那么加入一个新节点进去
        if (!cur.next.containsKey(c)) {
            cur.next.put(c, new Trie());
        }
        //查找下一层节点
        cur = cur.next.get(c);
    }
    //遍历字符串完毕,最后的节点isEnd置为true,表示一个字符串的结束
    cur.isEnd = true;
}

查找字符串

基于Trie结构可以查找字符串、匹配前缀、查找出现次数等等,这里我们给出查找字符串和查找前缀的方法。

比较简单,我们从字典树的根开始,查找前缀:

  • 如果子节点存在。沿着指针移动到子节点,继续搜索下一个字符。
  • 如果子节点不存在。说明字典树中不包含该前缀,返回空指针。

可以看到查找字符串相比于匹配前缀,仅仅是多了一个最下层子节点是否是一个字符串的结束的判断而已。

/**
 * 查找字符串
 */
public boolean search(String word) {
    Trie end = searchPrefix(word);
    return end != null && end.isEnd;
}

/**
 * 匹配前缀
 */
public boolean startsWith(String prefix) {
    return searchPrefix(prefix) != null;
}

private Trie searchPrefix(String prefix) {
    //初始默认为根节点,根节点不包含任何字符
    Trie cur = this;
    //遍历该字符串的字符数组
    for (char c : prefix.toCharArray()) {
        //如果该节点的下层不包含此字符,那么直接返回null
        if (!cur.next.containsKey(c)) {
            return null;
        }
        //查找下一层节点
        cur = cur.next.get(c);
    }
    return cur;
}

Trie的总结

假设我们加入了she、he、his、her这四个字符串,那么Trie的结构如下,其中红色节点表示其属于某个字符串的尾部节点。

Trie时间复杂度:初始化为O(1),每次操作为O(N),N为插入或查找的字符串的长度。

Trie空间复杂度:O(N),N表示Trie结点数量,或者说所有插入字符串的长度之和(减去相同前缀长度)。如果是采用定长数组表示next,那么空间复杂度为O(N*M),M表示字符集的大小,即数组长度。

可以看到,使用Trie的数据结构使得插入、查询全词、查询前缀的时间复杂度与已插入的单词数目和长度无关,这是它的一个优点。

但是,Trie又名前缀树,因为它只能基于前缀匹配实现某些功能。另一些功能,例如判断一段字符串中是否包含某些关键词,不需要前缀匹配,此时就无法使用Trie了。

相关题目如下:208. 实现 Trie (前缀树)

完整实现如下:

class Trie {
    /**
     * 经过该节点的字符串的下层节点
     */
    Map<Character, Trie> next;
    /**
     * 该节点是否是一个字符串的结束
     */
    boolean isEnd;

    public Trie() {
        this.next = new HashMap<>();
        this.isEnd = false;
    }

    public void insert(String word) {
        //初始默认为根节点,根节点不包含任何字符
        Trie cur = this;
        //遍历该字符串的字符数组
        for (char c : word.toCharArray()) {
            //如果该节点的下层不包含此字符,那么加入一个新节点进去
            if (!cur.next.containsKey(c)) {
                cur.next.put(c, new Trie());
            }
            //查找下一层节点
            cur = cur.next.get(c);
        }
        //遍历字符串完毕,最后的节点isEnd置为true,表示一个字符串的结束
        cur.isEnd = true;
    }

    /**
     * 查找字符串
     */
    public boolean search(String word) {
        Trie end = searchPrefix(word);
        return end != null && end.isEnd;
    }

    /**
     * 匹配前缀
     */
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        //初始默认为根节点,根节点不包含任何字符
        Trie cur = this;
        //遍历该字符串的字符数组
        for (char c : prefix.toCharArray()) {
            //如果该节点的下层不包含此字符,那么直接返回null
            if (!cur.next.containsKey(c)) {
                return null;
            }
            //查找下一层节点
            cur = cur.next.get(c);
        }
        return cur;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("你是xxl吗?");
    }
}

以上就是详解Java前缀树Trie的原理及代码实现的详细内容,更多关于Java前缀树Trie的资料请关注我们其它相关文章!

(0)

相关推荐

  • Trie树(字典树)的介绍及Java实现

    简介 Trie树,又称为前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串.与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定.一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串. 它的主要特点如下: 根节点不包含字符,除根节点外的每一个节点都只包含一个字符. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串. 每个节点的所有子节点包含的字符都不相同. 如下是一棵典型的Trie树: Trie的来源是Retrie

  • 详解Java中字典树(Trie树)的图解与实现

    目录 简介 工作过程 数据结构 初始化 构建字典树 应用 匹配有效单词 关键词提示 总结 简介 Trie又称为前缀树或字典树,是一种有序树,它是一种专门用来处理串匹配的数据结构,用来解决一组字符中快速查找某个字符串的问题.Google搜索的关键字提示功能相信大家都不陌生,我们在输入框中进行搜索的时候,会下拉出一系列候选关键词. 上面这个关键词提示功能,底层最基本的原理就是我们今天说的数据结构:Trie树 我们先看看Tire树长什么样子,以单纯的单词匹配为例,首先它是一棵多叉树结构,根节点是一个空

  • Java中实现双数组Trie树实例

    传统的Trie实现简单,但是占用的空间实在是难以接受,特别是当字符集不仅限于英文26个字符的时候,爆炸起来的空间根本无法接受. 双数组Trie就是优化了空间的Trie树,原理本文就不讲了,请参考An Efficient Implementation of Trie Structures,本程序的编写也是参考这篇论文的. 关于几点论文没有提及的细节和与论文不一一致的实现: 1.对于插入字符串,如果有一个字符串是另一个字符串的子串的话,我是将结束符也作为一条边,产生一个新的结点,这个结点新节点的Ba

  • 详解Java前缀树Trie的原理及代码实现

    目录 Trie的概念 Trie的实现 基本结构 构建Trie 查找字符串 Trie的总结 Trie的概念 Trie(发音类似 “try”)又被称为前缀树.字典树.Trie利用字符串的公共前缀来高效地存储和检索字符串数据集中的关键词,最大限度地减少无谓的字符串比较,其核心思想是用空间换时间. Trie树可被用来实现字符串查询.前缀查询.词频统计.自动拼写.补完检查等等功能. Trie树的三个性质: 根节点不包含字符,除根节点外每一个节点都只包含一个字符. 从根节点到某一节点,路径上经过的字符连接起

  • 详解Java中AC自动机的原理与实现

    目录 简介 工作过程 数据结构 初始化 构建字典树 构建失败指针 匹配 执行结果 简介 AC自动机是一个多模式匹配算法,在模式匹配领域被广泛应用,举一个经典的例子,违禁词查找并替换为***.AC自动机其实是Trie树和KMP 算法的结合,首先将多模式串建立一个Tire树,然后结合KMP算法前缀与后缀匹配可以减少不必要比较的思想达到高效找到字符串中出现的匹配串. 如果不知道什么是Tire树,可以先查看:详解Java中字典树(Trie树)的图解与实现 如果不知道KMP算法,可以先查看:详解Java中

  • 详解Java volatile 内存屏障底层原理语义

    目录 一.volatile关键字介绍及底层原理 1.volatile的特性(内存语义) 2.volatile底层原理 二.volatile--可见性 三.volatile--无法保证原子性 四.volatile--禁止指令重排 1.指令重排 2.as-if-serial语义 五.volatile与内存屏障(Memory Barrier) 1.内存屏障(Memory Barrier) 2.volatile的内存语义实现 六.JMM对volatile的特殊规则定义 一.volatile关键字介绍及底

  • 详解Java线程池和Executor原理的分析

    详解Java线程池和Executor原理的分析 线程池作用与基本知识 在开始之前,我们先来讨论下"线程池"这个概念."线程池",顾名思义就是一个线程缓存.它是一个或者多个线程的集合,用户可以把需要执行的任务简单地扔给线程池,而不用过多的纠结与执行的细节.那么线程池有哪些作用?或者说与直接用Thread相比,有什么优势?我简单总结了以下几点: 减小线程创建和销毁带来的消耗 对于Java Thread的实现,我在前面的一篇blog中进行了分析.Java Thread与内

  • 详解Java 中泛型的实现原理

    泛型是 Java 开发中常用的技术,了解泛型的几种形式和实现泛型的基本原理,有助于写出更优质的代码.本文总结了 Java 泛型的三种形式以及泛型实现原理. 泛型 泛型的本质是对类型进行参数化,在代码逻辑不关注具体的数据类型时使用.例如:实现一个通用的排序算法,此时关注的是算法本身,而非排序的对象的类型. 泛型方法 如下定义了一个泛型方法, 声明了一个类型变量,它可以应用于参数,返回值,和方法内的代码逻辑. class GenericMethod{ public <T> T[] sort(T[]

  • 详解Java TCC分布式事务实现原理

    概述 之前网上看到很多写分布式事务的文章,不过大多都是将分布式事务各种技术方案简单介绍一下.很多朋友看了还是不知道分布式事务到底怎么回事,在项目里到底如何使用. 所以这篇文章,就用大白话+手工绘图,并结合一个电商系统的案例实践,来给大家讲清楚到底什么是 TCC 分布式事务. 业务场景介绍 咱们先来看看业务场景,假设你现在有一个电商系统,里面有一个支付订单的场景. 那对一个订单支付之后,我们需要做下面的步骤: 更改订单的状态为"已支付" 扣减商品库存 给会员增加积分 创建销售出库单通知仓

  • 详解Java单例模式的实现与原理剖析

    目录 一.什么是单例模式 二.哪些地方用到了单例模式 三.单例模式的优缺点 优点 缺点 四.手写单例模式 饿汉式 枚举饿汉式 DCL懒汉式 双检锁懒汉式 内部类懒汉式 小结 一.什么是单例模式 单例模式(Singleton Pattern)是 Java 中最简单的设计模式之一.这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式. 这种模式涉及到一个单一的类,该类负责创建自己的对象,同时确保只有单个对象被创建.这个类提供了一种访问其唯一的对象的方式,可以直接访问,不需要实例化该类的对

  • 详解Java面向对象之多态的原理与实现

    目录 何为多态 代码实现 多态理解 何为多态 定义: 多态是指不同的子类在继承父类后分别都重写覆盖了父类的方法,即父类同一个方法,在继承的子类中表现出不同的形式.系统在运行时(而非编译时),能够根据其类型确定调用哪个重载的成员函数的能力,称为多态性. 特点: (1)多态是面向对象的重要特性,简单点说:“一个接口,多种实现”,就是同一种事物表现出的多种形态. (2)多态就是抽象化的一种体现,把一系列具体事物的共同点抽象出来, 再通过这个抽象的事物, 与不同的具体事物进行对话. (3)对不同类的对象

  • 详解Java ReentrantReadWriteLock读写锁的原理与实现

    目录 概述 原理概述 加锁原理 图解过程 源码解析 解锁原理 图解过程 源码解析 概述 ReentrantReadWriteLock读写锁是使用AQS的集大成者,用了独占模式和共享模式.本文和大家一起理解下ReentrantReadWriteLock读写锁的实现原理.在这之前建议大家阅读下下面3篇关联文章: 深入浅出理解Java并发AQS的独占锁模式 深入浅出理解Java并发AQS的共享锁模式 通俗易懂读写锁ReentrantReadWriteLock的使用 原理概述 上图是ReentrantR

  • 详解Java中跳跃表的原理和实现

    目录 一.跳跃表的引入 二.算法分析 1.时间复杂度 2.空间复杂度 三.跳跃表介绍 四.跳跃表的实现 1.数据结构定义 2.查找 3.插入 4.删除 五.实战 1.代码 2.测试结果 一.跳跃表的引入 对有序顺序表可以采用二分查找,查找的时间复杂度为O (logn),插入.删除的时间复杂度为 O(n ).但是对有序链表不可以采用二分查找,查找.插入和删除的时间复杂度均为O (n). 有序链表如下图所示,若查找 8,则必须从第 1 个节点开始,依次比较 8 次才能查找成功. 如何利用链表的有序性

随机推荐