数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?

王争 2018-12-12
搜索引擎的搜索关键词提示功能,我想你应该不陌生吧?为了方便快速输入,当你在搜索引擎的搜索框中,输入要搜索的文字的某一部分的时候,搜索引擎就会自动弹出下拉框,里面是各种关键词提示。你可以直接从下拉框中选择你要搜索的东西,而不用把所有内容都输入进去,一定程度上节省了我们的搜索时间。
尽管这个功能我们几乎天天在用,作为一名工程师,你是否思考过,它是怎么实现的呢?它底层使用的是哪种数据结构和算法呢?
像 Google、百度这样的搜索引擎,它们的关键词提示功能非常全面和精准,肯定做了很多优化,但万变不离其宗,底层最基本的原理就是今天要讲的这种数据结构:Trie 树。

什么是“Trie 树”?

Trie 树,也叫“字典树”。顾名思义,它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。
当然,这样一个问题可以有多种解决方法,比如散列表、红黑树,或者我们前面几节讲到的一些字符串匹配算法,但是,Trie 树在这个问题的解决上,有它特有的优点。不仅如此,Trie 树能解决的问题也不限于此,我们一会儿慢慢分析。
现在,我们先来看下,Trie 树到底长什么样子。
我举个简单的例子来说明一下。我们有 6 个字符串,它们分别是:how,hi,her,hello,so,see。我们希望在里面多次查找某个字符串是否存在。如果每次查找,都是拿要查找的字符串跟这 6 个字符串依次进行字符串匹配,那效率就比较低,有没有更高效的方法呢?
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(74)

  • Jerry银银
    找到了一个Trie树的开源库:Apache Commons,里面有关于Trie的实现

    作者回复: 👍

    2018-12-28
    6
    46
  • ban
    上面代码里: p.isEndingChar = true; 应该是放在for循环的外面吧?
    不然如果hello,那不就变成 h e l l o 都是叶子节点?
    2018-12-13
    1
    22
  • Smallfly
    思考题:

    依次读取每个字符串的字符构建 Trie 树,用散列表来存储每一个节点。每一层树的所有散列表的元素用一个链表串联起来,
    求某一长度的前缀重合,在对应树层级上遍历该层链表,求链表长度,除以字符集大小,值越小前缀重合率越高。

    遍历所有树层级的链表,存入散列表,最后散列表包含元素的个数,就代表字符集的大小。
    2018-12-12
    1
    21
  • 传说中的成大大
    今天的课程比上两节的课程理解起来容易多了 总体觉得就像是构造出来的多叉树,相同的前缀字符串就是同一棵树下来的不同分之
    2018-12-13
    13
  • kepmov
    trie树实际项目中由于内存问题用的不是很多,老师可以讲解下DAT(双数组trie树)的具体实现吗

    作者回复: 这个还是自己研究吧 内容太多了 文章有限。或者后面我收集下 统一写几篇加餐文章吧

    2018-12-12
    11
  • 等风来
    if (p.isEndingChar == false) return false; // 不能完全匹配,只是前缀
    else return true; // 找到 pattern
    这小段代码有点不大牛.^_^
    return p.isEndingChar;就好了

    作者回复: 嗯嗯 怕看不懂嘛

    2018-12-12
    10
  • 王鸿运
    isEndingChar可以修改成uint型字段,这样不仅够可以判断是否包含该字符串,还可以进行字符串出现次数
    2018-12-29
    7
  • ZX
    老师,字符串匹配这里,还差后缀树没讲,很多场合需要用到这种结构,希望老师可以讲一讲

    作者回复: 那个更高级 不讲了 自学吧亲

    2018-12-17
    7
  • feifei
    如何统计字符串的字符集大小,以及前缀重合的程度呢?

    统计字符集的大小,这个问题,其实就是在求字符的最小值以及最大值的问题。
    我的解决办法
    1,遍历字符串集合
    2,将每个字符转化为int数字
    3,设置最小以及最大的变量,当字符中比最大字符的变量大的时候,将最大字符变量改为当前字符,或者比最小字符小,就修改最小字符
    4,遍历完成后,所求得的最大值与最小值的差,就是字符集的大小

    前缀重合的程度,这个问题的求解,其实就是做字符的统计问题
    我的解决办法:
    使用哈希表来记录下统计数,key为字符,value为统计计数
    遍历每条记录,假如每条记录中仅包含一个单词(如果多单词,多一步分隔操作,分隔成一个一个的单词)
    统计计数算法,就是从前到后遍历,遇到存在的,加1,不存在,则存入hash表
    比如hello这个单词,在哈希表中存储就为
    h 1
    he 1
    hel 1
    hell 1
    hello 1
    当再将出现,比如he
    就会变成
    h 2
    he 2
    hel 1
    hell 1
    hello 1

    统计数据完成后,对这个结果计算重合的字符数与整个字符的占比,
    具体计算公式为: count(value > 1) / count(all)
    但我的算法复杂度有点高,是m*n,m表示整个字符的长度,n表示单个单表的长度。

    2018-12-16
    7
  • Jerry银银
    老师帮忙推荐一些包含Trie树实现的优秀的开源库呗,好让我们深入研究
    2018-12-28
    4
  • 忽忽
    请问下老师,这些图是什么工具画的呀?

    作者回复: paper

    2018-12-25
    4
  • Lisa Li
    “而 Trie 树中用到了指针,所以,对缓存并不友好,性能上会打个折扣。” 可以解释一下为什么吗?

    作者回复: 用指针串起来的数据在内存中是不连续的 对cpu缓存来说 不友好 你可以看下链表那一节

    2018-12-18
    4
  • 追风者
    王老师,关于Trie树有两点疑问。
    1.文中用‘he’和‘her’构建Trie树,当我要查询‘he’的时候怎么办?
    2.像jieba分词这种切词工具,为什么要用Trie树呢?

    作者回复: 1. he的e节点也会被标记为结尾字符节点
    2. jieba分词不怎么了解呢。。。

    2019-01-04
    3
  • 起点·终站
    看完后发现我们项目的屏蔽字检测就是用trie树写的。。666
    2018-12-17
    3
  • 小美
    老师 红黑树 如何实现字符串查找 方便王老师稍微点拨下吗

    作者回复: 把字符串整体当做一个数据 存储在节点里

    2018-12-12
    3
  • 夏洛克的救赎
    问题思考:
    1 中文转换成ASCII码?
    2 根据以往用户搜索记录,选择占比最高的
    3 从词库检索匹配?
    2018-12-12
    3
  • 掸尘
    C 版本代码:

    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0

    typedef int Status;

    typedef struct Node {
        char data;
        struct Node *children[26];
        Status end;
    } Trie, *TriePtr;

    void Init(TriePtr *T)
    {
        (*T) = (TriePtr)malloc(sizeof(Trie));
        (*T)->data = '/';
        (*T)->end = FALSE;
    }

    void Insert(TriePtr T, char *str) {

        int index;
        char c;

        while(c = *str++)
        {
            index = c - 'a';
            if (T->children[index] == NULL)
            {
                TriePtr Node;
                Node = (TriePtr)malloc(sizeof(Trie));
                Node->data = c;
                Node->end = FALSE;
                T->children[index] = Node;
            }

            T = T->children[index];
        }

        T->end = TRUE;
    }


    Status Search(TriePtr T, char *str) {

        int index;
        char c;

        while(c = *str++)
        {
            index = c - 'a';
            if (T->children[index] == NULL)
            {
                return FALSE;
            }

            T = T->children[index];
        }

        if (T->end) {
            return TRUE;
        } else {
            return FALSE;
        }
    }
    2019-05-09
    1
    2
  • Li Yao
    p = p.children[index];
    p.isEndingChar = true;
    是不是应该放到for循环外面? 否则每个节点都会被标记为endingChar?

    作者回复: 已经改正 多谢🙏

    2018-12-17
    2
  • TryTs
    老师,麻烦请问一下您请问一下对于一些新的领域,没有现成的书,教程你会通过什么方法跟途径或者说平台去体系的学习?还有我就是想请教一下老师您对AR的看法?

    作者回复: 没有现成的教程 书。只能自己摸索了。多看看别人分享的文章 自己理个知识大纲 然后再查缺补漏吧

    2018-12-12
    2
  • freeland
    以太坊上header里的transaction .root ,state root,receipt root用的是Merkle-PatriciaTrie(MPT),和今天的这个是一个么

    作者回复: 思路差不多 更高级点

    2018-12-12
    2
收起评论
74
返回
顶部