详解字典树Trie结构及其Python代码实现
作者:hackbuteer1 发布时间:2023-07-07 18:18:41
字典树(Trie)可以保存一些字符串->值的对应关系。基本上,它跟 Java 的 HashMap 功能相同,都是 key-value 映射,只不过 Trie 的 key 只能是字符串。
Trie 的强大之处就在于它的时间复杂度。它的插入和查询时间复杂度都为 O(k) ,其中 k 为 key 的长度,与 Trie 中保存了多少个元素无关。Hash 表号称是 O(1) 的,但在计算 hash 的时候就肯定会是 O(k) ,而且还有碰撞之类的问题;Trie 的缺点是空间消耗很高。
至于Trie树的实现,可以用数组,也可以用指针动态分配,我做题时为了方便就用了数组,静态分配空间。
Trie树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
Trie树中每个单词都是通过character by character方法进行存储,相同前缀单词共享前缀节点.
可以看到,每条路径组成一个单词.上面这颗树存了to/tea/ted/ten/inn这些词.
Trie树的基本性质可以归纳为:
(1)根节点不包含字符,除根节点意外每个节点只包含一个字符。
(2)从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。
(3)每个节点的所有子节点包含的字符串不相同。
性质
(1)根节点不包含字符,除根节点外的每个节点只包含一个字符。
(2)从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。
(3)每个节点的所有子节点包含的字符串不相同。
基本思想(以字母树为例):
1、插入过程
对于一个单词,从根开始,沿着单词的各个字母所对应的树中的节点分支向下走,直到单词遍历完,将最后的节点标记为红色,表示该单词已插入Trie树。
2、查询过程
同样的,从根开始按照单词的字母顺序向下遍历trie树,一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色,则表示该单词不存在,若最后的节点标记为红色,表示该单词存在。
应用
(1)词频统计
比直接用hash节省空间
(2)搜索提示
输入前缀的时候提示可以构成的词
(3)作为辅助结构
如后缀树,AC自动机等的辅助结构
实现
虽然Python没有指针,但是可以用嵌套字典来实现树结构.对于非ascii的单词,统一用unicode编码来插入与搜索.
#coding=utf-8
class Trie:
root = {}
END = '/'
def add(self, word):
#从根节点遍历单词,char by char,如果不存在则新增,最后加上一个单词结束标志
node = self.root
for c in word:
node=node.setdefault(c,{})
node[self.END] = None
def find(self, word):
node = self.root
for c in word:
if c not in node:
return False
node = node[c]
return self.END in node
猜你喜欢
- 本文实例讲述了golang基于websocket实现的简易聊天室。分享给大家供大家参考,具体如下:先说点无关的,最近忙于工作没有更新博客,今
- 本文记录了windows下python的安装,供大家参考,具体内容如下—–因为我是个真小白,网上的大多入门教程并不适合我这种超级超级小白,有
- ES Module导出仅导出named exports: 命名导出,每次可以导出一个或者多个。default exports: 默认导出,每
- Python中默认安装的ftplib模块定义了FTP类,可用来实现简单的ftp客户端,用于上传或下载文件。ftp登陆连接from ftpli
- 随机数和蒙特卡洛模拟求解单一变量非线性方程求解线性系统方程函数的数学积分常微分方程的数值解等势线绘图和曲线:等势线 import
- 实现代码/// <summary>/// 去除HTML标记/// </summary&
- 快排是python经典算法之一。1、下面讲解的是什么是快排和快排的图示。2、快排是一种解决排序问题的运算方法。3、快排的原理:在数组中任意选
- YSlow是yahoo美国开发的一个页面评分插件,非常的棒,从中我们可以看出我们页面上的很多不足,并且可以知道我们改怎么却改进和优化。仔细研
- 本文实例讲述了python追加元素到列表的方法。分享给大家供大家参考。具体实现方法如下:scores = ["1",&q
- 引言python中的模块、库、包有什么区别?module:一个 .py 文件就是个 modulelib:抽象概念,和另外两个不是一类,只要你
- 此BUG最初是在《前端观察》网站刊登,这里再描述一下,代码如下:<style>*{ padding:0; m
- 前言golang实现定时任务很简单,只须要简单几步代码即可以完成,最近在做了几个定时任务,想研究一下它内部是怎么实现的,所以将源码过了一遍,
- 安装正常情况,只需pip install PIL==1.1.7或者pip install Pillow==2.9.0即可。但需留意安装后的输
- 1.分包背景这里首先介绍下MultiDex的产生背景。当Android系统安装一个应用的时候,有一步是对Dex进行优化,这个过程有一个专门的
- 开发的很多场景中都会用到手机号的校验和验证码的校验,具体实现如下<div> <input type="text&
- 1 lambda函数函数格式是lambda keys:express 匿名函数lambda是一个表达式函数,接受ke
- 目录前言什么是pip再说 pip, 它就像应用宝下面给我们的手机安装应用宝Centos 安装pip for python2试用pip来安装库
- opencv-python打开USB或笔记本前置摄像头代码其中video_index是摄像头编号,一般前置摄像头为0,USB摄像头为1或2.
- 一、MatplotlibMatplotlib是Python中众多数据可视化库的鼻祖,其设计风格与20世纪80年代设计的商业化程序语言MATL
- php redis断线重连,pconnect连接失败问题介绍在swoole ,workerman等cli长连接模式下,遇到Redis异常断开