每天一道算法练习题--Day18 第一章 --算法专题 --- ----------前缀树

前缀树

字典树也叫前缀树、Trie。它本身就是一个树型结构,也就是一颗多叉树,学过树的朋友应该非常容易理解,它的核心操作是插入,查找。删除很少使用,因此这个讲义不包含删除操作。

截止目前(2020-02-04) 前缀树(字典树) 在 LeetCode 一共有 17 道题目。其中 2 道简单,8 个中等,7 个困难。

简介

我们想一下用百度搜索时候,打个“一语”,搜索栏中会给出“一语道破”,“一语成谶(四声的 chen)”等推荐文本,这种叫模糊匹配,也就是给出一个模糊的 query,希望给出一个相关推荐列表,很明显,hashmap 并不容易做到模糊匹配,而 Trie 可以实现基于前缀的模糊搜索。

注意这里的模糊搜索也仅仅是基于前缀的。比如还是上面的例子,搜索“道破”就不会匹配到“一语道破”,而只能匹配“道破 xx”

基本概念

假想一个场景:给你若干单词 words 和一系列关键字 keywords,让你判断 keywords 是否在 words 中存在,或者判断 keywords 中的单词是否有 words 中的单词的前缀。比如 pre 就是 pres 的前缀之一。

朴素的想法是遍历 keywords,对于 keywords 中的每一项都遍历 words 列表判断二者是否相等,或者是否是其前缀。这种算法的时间复杂度是 O ( m ∗ n ) O(m * n) O(mn),其中 m 为 words 的平均长度,n 为 keywords 的平均长度。那么是否有可能对其进行优化呢?答案就是本文要讲的前缀树。

我们可以将 words 存储到一个树上,这棵树叫做前缀树。 一个前缀树大概是这个样子:

如图每一个节点存储一个字符,然后外加一个控制信息表示是否是单词结尾,实际使用过程可能会有细微差别,不过变化不大。

为了搞明白前缀树是如何优化暴力算法的。我们需要了解一下前缀树的基本概念和操作。

节点:

  • 根结点无实际意义
  • 每一个节点数据域存储一个字符
  • 每个节点中的控制域可以自定义,如 isWord(是否是单词),count(该前缀出现的次数)等,需实际问题实际分析需要什么。

一个可能的前缀树节点结构:

  private class TrieNode {

        int count; //表示以该处节点构成的串的个数
        int preCount; //表示以该处节点构成的前缀的字串的个数
        TrieNode[] children;

        TrieNode() {

            children = new TrieNode[26];
            count = 0;
            preCount = 0;
        }
    }

可以看出 TriNode 是一个递归的数据结构,其结构类似多叉树,只是多了几个属性记录额外信息罢了。 比如 count 可以用来判断以当前节点结束的单词个数, preCount 可以用来判断以当前节点结束的前缀个数。举个例子:比如前缀树中存了两个单词 lu 和 lucifer,那么单词 lu 有一个,lu 前缀有两个。

前缀树大概如下图:

                        l(count = 0, preCount=2)
                    u(count = 1, preCount=2)
                c(count = 0, preCount=1)
            i(count = 0, preCount=1)
        f(count = 0, preCount=1)
    e(count = 0, preCount=1)
f(count = 1, preCount=1)

Trie 的插入

构建 Trie 的核心就是插入。而插入指的就是将单词(words)全部依次插入到前缀树中。假定给出几个单词 words [she,he,her,good,god]构造出一个 Trie 如下图:
在这里插入图片描述
也就是说从根结点出发到某一粉色节点所经过的字符组成的单词,在单词列表中出现过,当然我们也可以给树的每个节点加个 count 属性,代表根结点到该节点所构成的字符串前缀出现的次数。

在这里插入图片描述
可以看出树的构造非常简单:插入新单词的时候就从根结点出发一个字符一个字符插入,有对应的字符节点就更新对应的属性,没有就创建一个!

Trie 的查询

查询更简单了,给定一个 Trie 和一个单词,和插入的过程类似,一个字符一个字符找

  • 若中途有个字符没有对应节点 →Trie 不含该单词
  • 若字符串遍历完了,都有对应节点,但最后一个字符对应的节点并不是粉色的,也就不是一个单词 →Trie 不含该单词

Trie 模版

了解了 Trie 的使用场景以及基本的 API, 那么最后就是用代码来实现了。这里我提供了 Python 和 Java 两种语言的代码。

Java Code:

class Trie {

    TrieNode root;

    public Trie() {

        root = new TrieNode();
    }

    public void insert(String word) {

        TrieNode node = root;

        for (int i = 0; i < word.length(); i++) {

            if (node.children[word.charAt(i) - 'a'] == null)
                node.children[word.charAt(i) - 'a'] = new TrieNode();

            node = node.children[word.charAt(i) - 'a'];
            node.preCount++;
        }

        node.count++;
    }

    public boolean search(String word) {

        TrieNode node = root;

        for (int i = 0; i < word.length(); i++) {

            if (node.children[word.charAt(i) - 'a'] == null)
                return false;

            node = node.children[word.charAt(i) - 'a'];
        }

        return node.count > 0;
    }

    public boolean startsWith(String prefix) {

        TrieNode node = root;

        for (int i = 0; i < prefix.length(); i++) {

            if (node.children[prefix.charAt(i) - 'a'] == null)
                return false;
            node = node.children[prefix.charAt(i) - 'a'];
        }

        return node.preCount > 0;
    }

    private class TrieNode {

        int count; //表示以该处节点构成的串的个数
        int preCount; //表示以该处节点构成的前缀的字串的个数
        TrieNode[] children;

        TrieNode() {

            children = new TrieNode[26];
            count = 0;
            preCount = 0;
        }
    }
}

Python Code:

class TrieNode:
    def __init__(self):
        self.count = 0 # 表示以该处节点构成的串的个数
        self.preCount = 0 # 表示以该处节点构成的前缀的字串的个数
        self.children = {}

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
            node.preCount += 1
        node.count += 1

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.count > 0

    def startsWith(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.preCount > 0

复杂度分析

  • 插入和查询的时间复杂度自然是 O ( l e n ( k e y ) ) O(len(key)) O(len(key)),key 是待插入(查找)的字串.
  • 建树的最坏空间复杂度是 O ( m n ) O(m^{n}) O(mn), m 是字符集中字符个数,n 是字符串长度。

回答开头的问题

前面我们抛出了一个问题:给你若干单词 words 和一系列关键字 keywords,让你判断 keywords 是否在 words 中存在,或者判断 keywords 中的单词是否有 words 中的单词的前缀。比如 pre 就是 pres 的前缀之一。

如果使用 Trie 来解,会怎么样呢?首先我们需要建立 Trie,这部分的时间复杂度是 O ( t ) O(t) O(t),其中 t 为 words 的总字符。预处理完毕之后就是查询了。对于查询,由于树的高度是 O ( m ) O(m) O(m),其中 m 为 words 的平均长度,因此查询基本操作的次数不会大于 m m m。当然查询的基本操作次数也不会大于 k k k,其中 k 为被查询单词 keyword 的长度,因此对于查询来说,时间复杂度为 O ( m i n ( m , k ) ) O(min(m, k)) O(min(m,k))。时间上优化的代价是空间上的消耗,对于空间来说则是预处理的消耗,空间复杂度为 O ( t ) O(t) O(t)

前缀树的特点

简单来说, 前缀树就是一个树。前缀树一般是将一系列的单词记录到树上, 如果这些单词没有公共前缀,则和直接用数组存没有任何区别。而如果有公共前缀, 则公共前缀仅会被存储一次。可以想象,如果一系列单词的公共前缀很多, 则会有效减少空间消耗。

而前缀树的意义实际上是空间换时间,这和哈希表,动态规划等的初衷是一样的。

其原理也很简单,正如我前面所言,其公共前缀仅会被存储一次,因此如果我想在一堆单词中找某个单词或者某个前缀是否出现,我无需进行完整遍历,而是遍历前缀树即可。本质上,使用前缀树和不使用前缀树减少的时间就是公共前缀的数目。也就是说,一堆单词没有公共前缀,使用前缀树没有任何意义。

知道了前缀树的特点,接下来我们自己实现一个前缀树。关于实现可以参考 0208.implement-trie-prefix-tree

应用场景及分析

正如上面所说,前缀树的核心思想是用空间换时间,利用字符串公共前缀来降低查询的时间开销。

比如给你一个字符串 query,问你这个字符串是否在字符串集合中出现过,这样我们就可以将字符串集合建树,建好之后来匹配 query 是否出现,那有的朋友肯定会问,之前讲过的 hashmap 岂不是更好?

因此,这里我的理解是:上述精确查找只是模糊查找一个特例,模糊查找 hashmap 显然做不到,并且如果在精确查找问题中,hashmap 出现过多冲突,效率还不一定比 Trie 高,有兴趣的朋友可以做一下测试,看看哪个快。

再比如给你一个长句和一堆敏感词,找出长句中所有敏感词出现的所有位置(想下,有时候我们口吐芬芳,结果发送出去却变成了****,懂了吧)

小提示:实际上 AC 自动机就利用了 trie 的性质来实现敏感词的匹配,性能非常好。以至于很多编辑器都是用的 AC 自动机的算法。

可以参考:https://blog.csdn.net/bestsort/article/details/82947639

ac自动机,就是在tire树的基础上,增加一个fail指针,如果当前点匹配失败,则将指针转移到fail指针指向的地方,这样就不用回溯,而可以路匹配下去了.(当前模式串后缀和fail指针指向的模式串部分前缀相同,如abce和bcd,我们找到c发现下一个要找的不是e,就跳到bcd中的c处,看看此处的下一个字符(d)是不是应该找的那一个)

还有些其他场景,这里不过多讨论,有兴趣的可以 google 一下。

总结

前缀树的核心思想是用空间换时间,利用字符串的公共前缀来降低查询的时间开销。因此如果题目中公共前缀比较多,就可以考虑使用前缀树来优化。

前缀树的基本操作就是插入和查询,其中查询可以完整查询,也可以前缀查询,其中基于前缀查询才是前缀树的灵魂,也是其名字的来源。

最后给大家提供了两种语言的前缀树模板,大家如果需要用,直接将其封装成标准 API 调用即可。

基于前缀树的题目变化通常不大, 使用模板就可以解决。如何知道该使用前缀树优化是一个难点,不过大家只要牢牢记一点即可,那就是算法的复杂度瓶颈在字符串查找,并且字符串有很多公共前缀,就可以用前缀树优化

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/17258.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于R语言APSIM模型应用

随着数字农业和智慧农业的发展&#xff0c;基于过程的农业生产系统模型在模拟作物对气候变化的响应与适应、农田管理优化、作物品种和株型筛选、农田固碳和温室气体排放等领域扮演着越来越重要的作用。APSIM (Agricultural Production Systems sIMulator)模型是世界知名的作物生…

净利润下滑13%,帅丰电器已掉队?

近年来&#xff0c;随着市场竞争加剧&#xff0c;厨电行业加速洗牌&#xff0c;超60%杂牌或被淘汰出局&#xff0c;三类品牌全部被清退。而作为毛利最高的厨电细分市场&#xff0c;集成灶行业吸引了大批企业涌入&#xff0c;市场渗透率快速提升&#xff0c;已经超过30%&#xf…

华为MPLS跨域——后门链路实验配置

目录 配置PE与CE设备对接命令&#xff08;通过OSPF对接&#xff09; 配置后门链路 可以使用任意方式来跑跨域MPLS&#xff08;A、B、C1、C2都可以&#xff09;&#xff0c;不过关于传递Vpnv4路由的配置此处不做介绍&#xff1b;此处只介绍关于PE和CE对接的配置和关于后门链路…

数据存储系统概要

可靠、可扩展与可维护性 现在有很多都属于数据密集型&#xff0c;而不是计算密集型。对于这些类型应用&#xff0c;CPU的处理能力往往不是第一限制性因素&#xff0c;关键在于数据量、数据的复杂度及数据的快速多边形。 数据密集型应用模块&#xff1a; 数据库&#xff1a;存…

对标世界一流|从Just in time到Just in case ——汽车行业供应链管理经验借鉴

01 丰田汽车精益生产 作为最复杂和最成熟的供应链之一&#xff0c;汽车行业供应链无疑是供应链领域集大成者&#xff0c;而提起汽车行业供应链&#xff0c;就不得不提到丰田汽车&#xff1b;提到丰田汽车&#xff0c;就肯定离不开大名鼎鼎的精益生产以及JIT模式。 JIT模式由丰…

云服务器部署python项目

前言&#xff1a;相信看到这篇文章的小伙伴都或多或少有一些编程基础&#xff0c;懂得一些linux的基本命令了吧&#xff0c;本篇文章将带领大家服务器如何部署一个使用django框架开发的一个网站进行云服务器端的部署。 文章使用到的的工具 Python&#xff1a;一种编程语言&…

SpringBoot+Shiro+Jwt+Vue+elementUI实现前后端分离单体系统Demo

记录一下使用SpringBoot集成Shiro框架和Jwt框架实现前后端分离Web项目的过程&#xff0c;后端使用SpringBoot整合ShiroJwt(auth0)&#xff0c;前端使用vueelementUI框架&#xff0c;前后端的交互使用的是jwt的token&#xff0c;shiro的会话关闭&#xff0c;后端只需要使用Shiro…

在Linux上搭建gitlab以及自动化编译部署的完整流程

一、安装gitlab 首先下载gitlab的安装包&#xff0c;地址如下&#xff1a; https://mirrors.tuna.tsinghua.edu.cn/gitlab-ce/ubuntu/pool/bionic/main/g/gitlab-ce/ 然后安装下载的包即可&#xff0c;一般还需要安装openssh-server等依赖包&#xff0c;在安装gitlab包之前可以…

睡眠经济2.0时代来了,老巨头们有护城河吗?

在第23个世界睡眠日&#xff0c;中国睡眠研究会等机构发布了《中国睡眠研究报告2023》&#xff0c;近半数人每晚平均睡眠时长不足8小时&#xff0c;“失眠”已成为了当代人的生活常态。 越是睡不好&#xff0c;越要想办法。年轻人纷纷求助于好的寝具、好的助眠产品乃至保健品&…

【Halcon】找到设备上的 标识牌

如图&#xff0c;找到设备上的 标识牌 。 标识牌最明显的特征是比其他区域亮&#xff0c; 二值化选择出亮区域&#xff0c;再通过面积选择出目标区域。 先显示图片 *获取图片的大小 get_image_size(Image,Width,Height)*关闭窗口 dev_close_window()*打开窗口 dev_open_win…

java错题总结(19-21页)

链接&#xff1a;关于Java中的ClassLoader下面的哪些描述是错误的_用友笔试题_牛客网 来源&#xff1a;牛客网 B&#xff1a;先讲一下双亲委派机制&#xff0c;简单来说&#xff0c;就是加载一个类的时候&#xff0c;会往上找他的父类加载器&#xff0c;父类加载器找它的父类加…

Centos系统安装RabbitMQ消息中间件

记录一下在centos7.x下面安装RabbitMQ消息中间件 RabbitMQ是一个开源而且遵循 AMQP协议实现的基于 Erlang语言编写&#xff0c;因此安装RabbitMQ之前是需要部署安装Erlang环境的 先安装Erlang https://packagecloud.io/rabbitmq/ 点进去可以看到 因为使用的centos是7.x版本的…

架构设计-数据库篇

大家好&#xff0c;我是易安&#xff01; 之前我们讲过架构设计的一些原则&#xff0c;和架构设计的方法论&#xff0c;今天我们谈谈高性能数据库集群的设计与应用。 读写分离原理 读写分离的基本原理是将数据库读写操作分散到不同的节点上&#xff0c;下面是其基本架构图。 读…

【Python系列】一个简单的抽奖小程序

序言 很开心你能在万千博文中打开这一篇&#xff0c;希望能给你带来一定的帮助&#xff01;&#x1f44d;&#x1f3fb; 如果有什么问题&#xff0c;都可以添加下方我的联系方式&#xff0c;联系我噢~&#x1f601; ⭐️⭐️⭐️⭐️⭐️沟通交流&#xff0c;一起成为技术达人&…

电视机顶盒哪个牌子好?数码小编盘点电视机顶盒排行榜

电视机顶盒哪个牌子好&#xff1f;这是困扰新手们的一大难题&#xff0c;部分产品被爆出虚标高配、偷工减料&#xff0c;面对众多的机顶盒品牌和型号&#xff0c;怎么选择才好&#xff1f;小编以销量和用户评价为标准&#xff0c;盘点了电视机顶盒排行榜&#xff0c;跟着我一起…

【Linux】进程学习(1)---理解进程概念

文章目录 冯诺依曼体系结构理解冯诺依曼体系结构 操作系统概念与定位概念计算机管理模型计算机的软硬件体系结构图系统调用和库函数概念 进程基本概念描述进程--PCBtask_struct内容分类组织进程 冯诺依曼体系结构 数学家冯诺依曼提出了计算机制造的三个基本原则&#xff0c;即采…

代码随想录算法训练营第四十八天| 198.打家劫舍、213.打家劫舍II、337.打家劫舍III

文章目录 198.打家劫舍213.打家劫舍II337.打家劫舍III 198.打家劫舍 题目链接&#xff1a;代码随想录 解题思路&#xff1a; 1.dp[i]&#xff1a;考虑下标i&#xff08;包括i&#xff09;以内的房屋&#xff0c;最多可以偷窃的金额为dp[i] 只是考虑&#xff0c;不一定偷 2.递推…

GPT-4等大语言模型对教育的未来意味着什么?

‍ ‍ shadow Mixlab这些年举办了非常多的活动和workshop&#xff0c;都带有很强的教育属性。今天我抽空学习了可汗学院的《AI-for-Education》课程&#xff0c;非常有启发。我记录了精华内容&#xff0c;分享给大家。 课程地址&#xff1a; www.khanacademy.org/college-caree…

设计模式——观察者模式

导航&#xff1a; 【黑马Java笔记踩坑汇总】JavaSEJavaWebSSMSpringBoot瑞吉外卖SpringCloud黑马旅游谷粒商城学成在线设计模式牛客面试题 目录 观察者模式 1、天气预报需求 2、天气预报需求方案之普通方案 3、观察者模式介绍 4、观察者模式优化天气预报案例 5、JDK 的O…

销售数据分析怎么做?这篇文章说清楚了

如何分析销售数据&#xff1f;分析销售数据有哪些指标&#xff1f;销售数据分析有什么作用&#xff1f; 销售数据是不是得通过数据分析软件啊&#xff1f; 本文将为您解答疑惑—— 一、分析销售数据的指标 从两个层面上来讲&#xff0c;一个是对销售情况的整体把控&#xf…
最新文章