详解字典树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
猜你喜欢
- 本文实例讲述了Flask框架单例模式实现方法。分享给大家供大家参考,具体如下:单例模式:程序运行时只能生成一个实例,避免对同一资源产生冲突的
- 以前工作的时候由于Oracle8i数据库经常出现用户过多的错误,由于数据量大,经常出现ORA:12500错误,但主要原因是访问过多而引起的,
- 此文仅当学习笔记用.这个实例是在Python环境下如何爬取弹出窗口的内容,有些时候我们要在页面中通过点击,然后在弹出窗口中才有我们要的信息,
- MySQL由于它本身的小巧和操作的高效, 在数据库应用中越来越多的被采用.我在开发一个P2P应用的时候曾经使用MySQL来保存P2P节点,由
- 一、创建excel代码备注:封装好了(可直接调用)"""-*- coding:utf-8 -*-@Time :
- #!/usr/bin/env python# coding=utf-8#----------------------------------
- 前言之前学python时在网上找了好多小程序,由于年代久远,已经忘记出自哪里了,给代码加了点注释,再稍微修改了一下,让代码的可读性更好,如有
- 内容有些啰嗦,内容记载了当时遇到了bug以及解决问题的思路。业务场景简述:前端做配置化组件,通过url内的唯一标识,请求后端sql 哪取页面
- if xxx 和if xxx is None的区别一、 if xxxNone,’’,0,[],{},
- 我们常常看到一个这样的表达式 A=lambda x:x+1可能会一头雾水不知道怎么计算 最基本的理解就是def A(x):retu
- 本文实例讲述了Python按行读取文件的实现方法。分享给大家供大家参考,具体如下:小文件:#coding=utf-8#author: wal
- 本文实例讲述了Python使用scrapy采集数据过程中放回下载过大页面的方法。分享给大家供大家参考。具体分析如下:添加以下代码到setti
- 今天的主题!最近很多朋友问起pyecharts,尤其是地理坐标图的制作,都说被其图形之美给吸引到了。刚好今天也有同事问起来,那么今天就以py
- 1. 图信号处理知识图卷积神经网络涉及到图信号处理的相关知识,也是由图信号处理领域的知识推导发展而来,了解图信号处理的知识是理解图卷积神经网
- 以下备忘升级至 Vue CLI 3.x 版本后,将项目目录改为新结构时所需做的一些改动。1. 卸载与安装npm uninstall vue-
- 用asp程序进行网页设计,大多因为需要访问数据库,然后再将数据显示到页面,如果数据很多的话,页面的访问速度也就变慢了,为了解决这个问题,可以
- %r用rper()方法处理对象%s用str()方法处理对象相同结果有些情况下,两者处理的结果是一样的,比如说处理int型对象。例:print
- 数据采集我们上一篇介绍了,如何采集电影评论,看看这个电影好不好看.今天,我们来采集大家熟悉的百度贴吧的排行榜。发送请求我们首先确定我们的目标
- 关于SQL UNION 操作符 UNION 操作符用于合并两个或多个 SELECT 语句的结果集。 注意: 1.UNION 内部的 SELE
- 我就废话不多说了,大家还是直接看代码吧!def pro_mgr(): """ 获取当前