Trie树

概述

在Google中随意搜索,如下所示:

他会自动显示相关的搜索,不知道有没有想过这个功能是如何实现的呢?面对海量的数据,它怎么能在我输入的同时,如此快速的检索到相关内容呢?当我查找资料后,就遇到了它,Trie树。

What?

Trie树是个什么玩意呢?为啥他能快速进行检索?Trie树也叫字典树。因为它的结构和我们用到的字典基本差不多。

想想,你在字典中差“how”这个单词的动作是怎样的?先找到h,然后在h的基础上找o,再找w。用树来存储这个过程就是这样的:

没毛病。如果存储:how, hello, kan, know这几个单词,如下所示:

简单易懂。在其中查找字符,就跟查字典一样,一级一级往下找就行了。

比如查找单词,“ho”,当找到o时,发现o不是叶子节点,说明“ho”是某个单词的前缀,并不是完整的单词。

看到有人拿Trie树和红黑树、哈希表做对比,红黑树我还没整明白,但是哈希表我知道啊。这俩有可比性么?我觉得没有,完全就是两种数据结构,打眼一看,就知道他们的侧重点不同。很明显Trie树适合进行前缀匹配,而哈希表适合进行精确匹配啊。哦,还有一个,哈希表很多语言都有现成的实现,如HashMap,但Trie树貌似没有。

How

Trie树看着挺厉害的。那如何实现呢?刚才说了,哈希表很多有现成的实现,但Trie树没有,所以要想使用,就得自己来实现。

Trie树说到底还是树结构。其结构体如下:

struct TrieNode{    char  data; // 保存字符    TrieNode children[26]; // 子节点}

使用Python写一个简单实现,其他语言也大同小异吧。都需要实现什么功能呢?

  1. 将字符串加入
  2. 匹配字符串
class Trie:
    class TrieNode:        """        树的节点        """        def __init__(self, data):            self.data = data            self.children = {}
    def __init__(self):        self.root = self.TrieNode(None)
    def insert_str(self, string):        """        讲字符串添加进trie树中        :param string: 字符串        """        tmp_trie_node = self.root        for c in list(string):            # 这里使用字母的顺序作为key,方便查找            index = ord(c) - ord('a')            if not tmp_trie_node.children.get(index):                tmp_trie_node.children[index] = self.TrieNode(c)            tmp_trie_node = tmp_trie_node.children[index]
    def is_match_str(self, string):        """        查询字符串是否在树中        :param string:        :return:        """        tmp_trie_node = self.root        for c in list(string):            index = ord(c) - ord('a')            if not tmp_trie_node.children.get(index):                return False            tmp_trie_node = tmp_trie_node.children[index]        return True

if __name__ == '__main__':    trie = Trie()    for string in ['how', 'hello', 'kan', 'know']:        trie.insert_str(string)    print(trie.is_match_str('hello'))    print(trie.is_match_str('hess'))

很简单的一个小demo

可以看的出来,Trie树在构建的时候,需要扫描所有字符串,但是在查找的时候就很快速了。

why

说了半天,Trie树算是简单的说完了。回到开篇的问题上,使用Trie树是如何进行搜索的?

比如我们输入“h”,就可以把“h”为前缀的单词展示出来,再输入“he”,就把“he”为前缀的单词展示出来。

输入单词后,展示相关的搜索句子,也是同样的道理。当然,搜索引擎会对其进行优化,比如匹配的相关内容有很多,从中选择哪些?等等。以上只是一个雏形的雏形。

Trie树不光可以用在搜索上,类似的场景有很多,比如输入法的自动补全、IDE的自动补全等等。怎么都是自动补全,应该还是有其他场景的,只是我只想到了这些。

本文分享自微信公众号 - 烟草的香味(hujing-bc),作者:胡靖哥哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 代码整洁之道-函数

    什么是一个好的函数或者叫方法,只要能让函数明确的表达其意图,让读者能够一眼看出是一个怎样的函数,其接收什么参数,返回什么结果,做了什么事情。能做到这,大概就能算...

    烟草的香味
  • 缓存在高并发场景下的常见问题

    当数据时效性要求很高时,需要保证缓存中的数据与数据库中的保持一致,而且需要保证缓存节点和副本中的数据也保持一致,不能出现差异现象。这就比较依赖缓存的过期和更新策...

    烟草的香味
  • Java集合之ArrayList源码分析

    ArrayList可以理解为动态数组, 根据MSDN的说法, 就是Array的复杂版本. 与数组相比, 它的容量能动态增长. ArrayList是List接口的...

    烟草的香味
  • GTX1080 安装 CUDA 7.5

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/zhangjunhit/article/de...

    用户1148525
  • [无聊的软件安装] 从零搭建深度学习环境简明教程

    前方图片已沦陷,建议后台回复 环境 获取word版,下载到电脑上方便查看。 主要包括以下内容: 1. 安装Ubuntu 16.04 系统 2.安装Ubuntu系...

    用户1622570
  • 解决python3项目中无法使用supervisor的问题

    简单、
  • 什么是MongoDB?简介、架构、功能和示例

    什么是MongoDB?MongoDB是一个面向文档的NoSQL数据库,用于大容量数据存储。MongoDB是2000年代中期出现的一个数据库,属于NoSQL数据库...

    MongoDB中文社区
  • zerotier的下载、安装、配置与使用(win10、ubuntu)

    2020年,由于“野味肺炎”的影响,笔者要开始在家办公,需要远程连接公司的电脑和设备。

    chenjx85
  • MongoDB

       MongoDB时一个高性能,开源,无模式的文档型数据库,时当前NoSQL数据库中比较热门的一种。它在需要场景下可用于替代传统的关系型数据库或键/值存储方式

    莫问今朝
  • Mac Java 开发环境搭建清单(不断更新中)

    在任何的操作系统中,首先你需要做一件事就是更新系统,点击窗口左上角的  > 关于本机 > 软件更新 。此外,如果这是一部新的电脑,你还需要到系统设置进行一些适...

    九州暮云

扫码关注云+社区

领取腾讯云代金券