[奇怪但有用的数据结构]Trie前缀树

想象一个这样的情景,有一个很大的字典包含了很多的单词,需要判断一个新单词是否在字典中,最直接也最快的办法就是使用哈希表了。现在添加一个条件,判断字典里是否存在单词以新单词为前缀,这时候哈希表就不合适了,因为存在单词在字典中但其前缀不在字典中的情况,例如[‘apple’, 'application','append']这个字典并不包含他们的公共前缀'app','ap'和‘a’。所以我们需要一种新的数据结构和算法来处理这类问题。

很显然如果我们知道哪些单词是以字母'a'开头的,就可以很方便的判断是否有单词是以'ap'为前缀的,从而不必理会以其他字母开头的单词。再进一步,我们可以从'ap'开头的单词中找是否有单词是以‘app’为前缀的,从'ab'开头的单词中找是否有单词一'aba'为前缀。于是这样的树形结构就构造出来了。

树形结构

我们可以很容易地看出来这棵树中包含四个单词abc, apple, bad和bat。也可以轻松判断出存在单词以'app'为前缀,而没有'ad'开头的单词。

Trie前缀树

这样的树形结构就是前缀树(Trie),也叫单词查找树,典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。它的基本性质如下:

  1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

构造前缀树

首先我们要定义一下节点的数据结构。每一个节点可以跟着若干个子节点,因为都是字符,所以可以用哈希表来保存子节点。并且要有一个标记来表示这个字符是不是一个单词的最后一个字符,不然以上图为例,无法知晓单词'app'是否在这个字典中。这是我设计的Node类(__repr__方法用于清晰的展示节点的结构)。

class Node:
    def __init__(self):
        self.is_last = False
        self.children = {}
    def __repr__(self):
        return 'Node({},[{}])'.format(self.is_last, 
            ','.join('{}:{}'.format(x, repr(self.children[x])) for x in self.children))

接下来就是构造前缀树了,很自然的会有一个Node类型的根节点root:

class Trie:
    def __init__(self):
        self.root = Node()

然后是在合适的位置插入新单词(去掉已有前缀的部分):

class Trie:
    def __init__(self):
        self.root = Node()
        
    def generate_node(self, word:str) -> Node:
        node = Node()
        if len(word) > 0:
            node.children[word[0]] = self.generate_node(word[1:])
        else:
            node.is_last = True
        return node
    

对于后续的操作(insert, search, startsWith)来说,寻找前缀是第一步,我这里使用的是一个get_node_rest方法,获得一个单词在前缀树中最长前缀的尾节点和剩余的字符。

class Trie:
    def __init__(self):
        self.root = Node()
        
    def generate_node(self, word:str) -> Node:
        #...
        
    
    def get_node_rest(self, root:Node, word:str)-> tuple:
        if not word:
            return root, ''
        elif word[0] in root.children:
            return self.get_node_rest(root.children[word[0]], word[1:])
        else:
            return root, word

获取了一个单词的node和rest,插入操作就是在node节点插入rest部分的字符,判断是否是前缀(startsWith)就是判断rest是否为空,如果node的is_last也同时为真的话就是存在这个单词了(search)。完整的代码如下:

#前缀树
class Node:
    def __init__(self):
        self.is_last = False
        self.children = {}
    def __repr__(self):
        return 'Node({},[{}])'.format(self.is_last,
            ','.join('{}:{}'.format(x, repr(self.children[x])) for x in self.children))

        

class Trie:
    def __init__(self):
        self.root = Node()
        
    def generate_node(self, word:str) -> Node:
        node = Node()
        if len(word) > 0:
            node.children[word[0]] = self.generate_node(word[1:])
        else:
            node.is_last = True
        return node
        
    def get_node_rest(self, root:Node, word:str)-> tuple:
        if not word:
            return root, ''
        elif word[0] in root.children:
            return self.get_node_rest(root.children[word[0]], word[1:])
        else:
            return root, word
    
    def insert(self, word):
        node, rest = self.get_node_rest(self.root, word)
        if rest:
            node.children[rest[0]] = self.generate_node(rest[1:])
        else:
            node.is_last = True
    
    def search(self, word):
        node, rest = self.get_node_rest(self.root, word)
        return rest == '' and node.is_last
    
    def startsWith(self, word):
        _, rest = self.get_node_rest(self.root, word)
        return len(rest) == 0

我们可以看一下Trie类的使用。

Trie类的使用

结语

本文简单介绍了前缀树的定义和用途,并用Python实现了一个简单的Trie类,希望能够给予大家一些启发和帮助。

最后祝大家享受生活,享受代码。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python爱好者

Java基础笔记02

742
来自专栏逸鹏说道

小白眼中的AI之~Numpy基础

引入一下 Numpy模块, Numpy的数组使用可以查看一下帮助文档, Numpy的 array数组类型必须是一致的(后面会讲)

11410
来自专栏韦弦的微信小程序

Swift 字符串中的第一个唯一字符 - LeetCode

1、将字符串转为数组 2、循环字符串数组,将字符作为键,索引作为值存入字典 3、存入字典时先判断是否已经存在,已存在则将值置位-1 4、循环字典,拿到所有...

651
来自专栏数据结构与算法

#103. 子串查找

内存限制:256 MiB时间限制:500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: 匿名 提交提交记录统计讨论测试数据 题目描述 这是一道模...

2647
来自专栏deed博客

day02笔记

1252
来自专栏猿人谷

判断二叉树是不是平衡

平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超...

1866
来自专栏程序员叨叨叨

8.1 函数第 8 章 函数与程序设计

通过第 5 章到第 7 章的阅读,我们已经知道了怎么声明变量(第 5 章),怎么写表达式和语句(第 6 章),怎么将输入 \ 输出参数绑定到语义词(第 7 章)...

752
来自专栏blackheart的专栏

[程序设计语言]-[核心概念]-04:数据类型

0. 概述 为何高级语言需要类型系统这个概念?在汇编时代是没有完整的数据类型系统的,结构化编程引入了结构化的控制流、为结构化设计的子程序,随之这种结构化的代码所...

1746
来自专栏xx_Cc的学习总结专栏

iOS-RunTime,不再只是听说

2777
来自专栏web前端教室

javascript 红皮高程(17)-- 按位异或(XOR)

不吐槽了,继续研究JS,今天是按位异或这个操作符,它用符号(^)表示,它也是有二个操作数,这二个数当然也是十进制转成二进制之后的数。 它的规则就是,二个数的数值...

1726

扫码关注云+社区