详解字典树Trie结构及其Python代码实现
字典树（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
相关推荐
-
Trie树(字典树)的介绍及Java实现
简介 Trie树,又称为前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串.与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定.一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串. 它的主要特点如下: 根节点不包含字符,除根节点外的每一个节点都只包含一个字符. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串. 每个节点的所有子节点包含的字符都不相同. 如下是一棵典型的Trie树: Trie的来源是Retrie
-
C# TrieTree介绍及实现方法
在自然语言处理(NLP)研究中,NGram是最基本但也是最有用的一种比对方式,这里的N是需要比对的字符串的长度,而今天我介绍的TrieTree,正是和NGram密切相关的一种数据结构,有人称之为字典树.TrieTree简单的说是一种多叉树,每个节点保存一个字符,这么做的好处是当我们要做NGram比对时,只需要直接从树的根节点开始沿着某个树叉遍历下去,就能完成比对:如果没找到,停止本次遍历.这话讲得有些抽象,我们来看一个实际的例子. 假设我们现在词库里面有以下一些词: 上海市 上海滩 上海人 上海
-
TrieTree服务-组件构成及其作用介绍
上一篇中我们对TrieTree服务有了一个整体的了解,不知道大家下载完之后有没有真正玩过这个TrieTree服务,如果你还没有玩过,没关系,本文将一步步教你配置和使用TrieTree服务. TrieTree服务由几大组件组成,如下图 Dictionary组件是核心库,主要提供基本数据定义.配置信息定义,数据结构表示,同时也提供了POSType(参考Pangu的Part of Speech定义).由于TrieTree是利用内存来加载数据的,所以这个组件的设计直接决定了内存的占用大小和数据查询性能.
-
Java中实现双数组Trie树实例
传统的Trie实现简单,但是占用的空间实在是难以接受,特别是当字符集不仅限于英文26个字符的时候,爆炸起来的空间根本无法接受. 双数组Trie就是优化了空间的Trie树,原理本文就不讲了,请参考An Efficient Implementation of Trie Structures,本程序的编写也是参考这篇论文的. 关于几点论文没有提及的细节和与论文不一一致的实现: 1.对于插入字符串,如果有一个字符串是另一个字符串的子串的话,我是将结束符也作为一条边,产生一个新的结点,这个结点新节点的Ba
-
Trie树_字典树(字符串排序)简介及实现
1.综述 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种.典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计.它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高. Trie树结构的优点在于:1) 不限制子节点的数量: 2) 自定义的输入序列化,突破了具体语言.应用的限制,成为一个通用的框架: 3) 可以进行最大Tokens序列长度的限制:4) 根据已定阈值输出重复的字符串:5) 提
-
Python Trie树实现字典排序
一般语言都提供了按字典排序的API,比如跟微信公众平台对接时就需要用到字典排序.按字典排序有很多种算法,最容易想到的就是字符串搜索的方式,但这种方式实现起来很麻烦,性能也不太好.Trie树是一种很常用的树结构,它被广泛用于各个方面,比如字符串检索.中文分词.求字符串最长公共前缀和字典排序等等,而且在输入法中也能看到Trie树的身影. 什么是Trie树 Trie树通常又称为字典树.单词查找树或前缀树,是一种用于快速检索的多叉树结构.如图数字的字典是一个10叉树: 同理小写英文字母或大写英文字母的字
-
详解字典树Trie结构及其Python代码实现
字典树(Trie)可以保存一些字符串->值的对应关系.基本上,它跟 Java 的 HashMap 功能相同,都是 key-value 映射,只不过 Trie 的 key 只能是字符串. Trie 的强大之处就在于它的时间复杂度.它的插入和查询时间复杂度都为 O(k) ,其中 k 为 key 的长度,与 Trie 中保存了多少个元素无关.Hash 表号称是 O(1) 的,但在计算 hash 的时候就肯定会是 O(k) ,而且还有碰撞之类的问题:Trie 的缺点是空间消耗很高. 至于Trie树的实现
-
详解Java中字典树(Trie树)的图解与实现
目录 简介 工作过程 数据结构 初始化 构建字典树 应用 匹配有效单词 关键词提示 总结 简介 Trie又称为前缀树或字典树,是一种有序树,它是一种专门用来处理串匹配的数据结构,用来解决一组字符中快速查找某个字符串的问题.Google搜索的关键字提示功能相信大家都不陌生,我们在输入框中进行搜索的时候,会下拉出一系列候选关键词. 上面这个关键词提示功能,底层最基本的原理就是我们今天说的数据结构:Trie树 我们先看看Tire树长什么样子,以单纯的单词匹配为例,首先它是一棵多叉树结构,根节点是一个空
-
详解Java前缀树Trie的原理及代码实现
目录 Trie的概念 Trie的实现 基本结构 构建Trie 查找字符串 Trie的总结 Trie的概念 Trie(发音类似 “try”)又被称为前缀树.字典树.Trie利用字符串的公共前缀来高效地存储和检索字符串数据集中的关键词,最大限度地减少无谓的字符串比较,其核心思想是用空间换时间. Trie树可被用来实现字符串查询.前缀查询.词频统计.自动拼写.补完检查等等功能. Trie树的三个性质: 根节点不包含字符,除根节点外每一个节点都只包含一个字符. 从根节点到某一节点,路径上经过的字符连接起
-
PHP字典树(Trie树)定义与实现方法示例
本文实例讲述了PHP字典树(Trie树)定义与实现方法.分享给大家供大家参考,具体如下: Trie树的概念(百度的解释):字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种.典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计.它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高. 我的理解是用来做字符串搜索的,每个节点只包含一个字符,比如录入单词"world",则树的结构
-
详解Bagging算法的原理及Python实现
目录 一.什么是集成学习 二.Bagging算法 三.Bagging用于分类 四.Bagging用于回归 一.什么是集成学习 集成学习是一种技术框架,它本身不是一个单独的机器学习算法,而是通过构建并结合多个机器学习器来完成学习任务,一般结构是:先产生一组"个体学习器",再用某种策略将它们结合起来,目前,有三种常见的集成学习框架(策略):bagging,boosting和stacking 也就是说,集成学习有两个主要的问题需要解决,第一是如何得到若干个个体学习器,第二是如何选择一种结合策
-
详解利用上下文管理器扩展Python计时器
目录 一个 Python 定时器上下文管理器 了解 Python 中的上下文管理器 理解并使用 contextlib 创建 Python 计时器上下文管理器 使用 Python 定时器上下文管理器 写在最后 上文中,我们一起学习了手把手教你实现一个 Python 计时器.本文中,云朵君将和大家一起了解什么是上下文管理器 和 Python 的 with 语句,以及如何完成自定义.然后扩展 Timer 以便它也可以用作上下文管理器.最后,使用 Timer 作为上下文管理器如何简化我们自己的代码. 上
-
图文详解梯度下降算法的原理及Python实现
目录 1.引例 2.数值解法 3.梯度下降算法 4.代码实战:Logistic回归 1.引例 给定如图所示的某个函数,如何通过计算机算法编程求f(x)min? 2.数值解法 传统方法是数值解法,如图所示 按照以下步骤迭代循环直至最优: ① 任意给定一个初值x0: ② 随机生成增量方向,结合步长生成Δx: ③ 计算比较f(x0)与f(x0+Δx)的大小,若f(x0+Δx)<f(x0)则更新位置,否则重新生成Δx: ④ 重复②③直至收敛到最优f(x)min. 数值解法最大的优点是编程简明,但缺陷也很
-
图文详解牛顿迭代算法原理及Python实现
目录 1.引例 2.牛顿迭代算法求根 3.牛顿迭代优化 4 代码实战:Logistic回归 1.引例 给定如图所示的某个函数,如何计算函数零点x0 在数学上我们如何处理这个问题? 最简单的办法是解方程f(x)=0,在代数学上还有著名的零点判定定理 如果函数y=f(x)在区间[a,b]上的图象是连续不断的一条曲线,并且有f(a)⋅f(b)<0,那么函数y=f(x)在区间(a,b)内有零点,即至少存在一个c∈(a,b),使得f(c)=0,这个c也就是方程f(x)=0的根. 然而,数学上的方法并不一定
-
详解小白之KMP算法及python实现
在看子串匹配问题的时候,书上的关于KMP的算法的介绍总是理解不了.看了一遍代码总是很快的忘掉,后来决定好好分解一下KMP算法,算是给自己加深印象. 在将KMP字串匹配问题的时候,我们先来回顾一下字串匹配的暴力解法: 假设字符串str为: "abcgbabcdh", 字串substr为: "abcd" 从第一个字符开始比较,显然两个字符串的第一个字符相等('a'=='a'),然后比较第二个字符也相等('b'=='b'),继续下去,我们发现第4个字符不相等了('g'!
-
详解如何在Java中调用Python程序
Java中调用Python程序 1.新建一个Maven工程,导入如下依赖 <dependency> <groupId>org.python</groupId> <artifactId>jython-standalone</artifactId> <version>2.7.0</version> </dependency> 2.在java中直接执行python代码片段 import org.python.util