详解字典树Trie结构及其Python代码实现

yipeiwu_com6年前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 

相关文章

python快速编写单行注释多行注释的方法

python快速编写单行注释多行注释的方法

在python代码编写过程中,养成注释的习惯非常有用,可以让自己或别人后续在阅读代码时,轻松理解代码的含义。 如果只是简单的单行注释,可直接用“#”号开头,放于代码前面。 单行注释也可...

python存储16bit和32bit图像的实例

笔记:python中存储16bit和32bit图像的方法。 说明:主要是利用scipy库和pillow库,比较其中的不同。 ''' 测试16bit和32bit图像的python存储方...

利用python实现命令行有道词典的方法示例

利用python实现命令行有道词典的方法示例

前言 由于一直用Linux系统,对于词典的支持特别不好,对于我这英语渣渣的人来说,当看英文文档就一直卡壳,之前用惯了有道词典,感觉很不错,虽然有网页版的但是对于全站英文的网页来说并不支持...

利用pyinstaller打包exe文件的基本教程

前言 PyInstaller可以用来打包python应用程序,打包完的程序就可以在没有安装Python解释器的机器上运行了。PyInstaller支持Python 2.7和Python...

Python3字符串学习教程

字符串类型是python里面最常见的类型,是不可变类型,支持单引号、双引号、三引号,三引号是一对连续的单引号或者双引号,允许一个字符串跨多行。 字符串连接:前面提到的+操作符可用于字符串...