数据结构与算法之美
王争
前 Google 工程师
283752 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

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

查询:O(k)
构建:O(n)
替换成其他数据结构
数组存储子节点指针
散列表和红黑树适用于精确匹配的字符串查找
时间复杂度低,但内存消耗较大
Trie树适用于前缀匹配的字符串查找
自动输入补全
搜索关键词提示功能
散列表和红黑树的优点
适用场景
缩点优化
替换数据结构优化空间消耗
存储空间可能浪费
时间复杂度
存储方式
查找字符串
插入字符串
利用字符串公共前缀合并重复前缀
解决字符串匹配问题
字典树
总结
Trie树的应用
Trie树与散列表、红黑树的比较
Trie树的内存消耗问题
如何实现一棵Trie树?
什么是Trie树?
Trie树

该思维导图由 AI 生成,仅供参考

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

什么是“Trie 树”?

Trie 树,也叫“字典树”。顾名思义,它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。
当然,这样一个问题可以有多种解决方法,比如散列表、红黑树,或者我们前面几节讲到的一些字符串匹配算法,但是,Trie 树在这个问题的解决上,有它特有的优点。不仅如此,Trie 树能解决的问题也不限于此,我们一会儿慢慢分析。
现在,我们先来看下,Trie 树到底长什么样子。
我举个简单的例子来说明一下。我们有 6 个字符串,它们分别是:how,hi,her,hello,so,see。我们希望在里面多次查找某个字符串是否存在。如果每次查找,都是拿要查找的字符串跟这 6 个字符串依次进行字符串匹配,那效率就比较低,有没有更高效的方法呢?
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

Trie树,又称字典树,是一种用于解决字符串匹配问题的高效数据结构。本文介绍了Trie树的基本概念和实现方法,包括构造Trie树和字符串查找的时间复杂度。Trie树能够快速查找字符串是否存在于给定的字符串集合中,并通过合并重复的前缀来构建高效的数据结构。虽然Trie树在某些情况下可能会浪费内存,但它在搜索引擎的搜索关键词提示功能等场景中表现出色。文章还对Trie树与散列表、红黑树进行了比较,并指出Trie树更适合于查找前缀匹配的字符串。此外,文章还探讨了Trie树在搜索关键词提示功能和自动输入补全等领域的应用。总之,Trie树是一种高效的数据结构,尤其适用于频繁查询字符串的场景,能够极大地提升搜索效率。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(128)

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

    作者回复: 👍

    2018-12-28
    14
    244
  • kepmov
    trie树实际项目中由于内存问题用的不是很多,老师可以讲解下DAT(双数组trie树)的具体实现吗

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

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

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

    2018-12-12
    2
    19
  • ZX
    老师,字符串匹配这里,还差后缀树没讲,很多场合需要用到这种结构,希望老师可以讲一讲

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

    2018-12-17
    4
    17
  • 忽忽
    请问下老师,这些图是什么工具画的呀?

    作者回复: paper

    2018-12-25
    15
  • 蚂蚁内推+v
    老师 红黑树 如何实现字符串查找 方便王老师稍微点拨下吗

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

    2018-12-12
    11
  • 想当上帝的司机
    26个字符的话TrieNode不要data也可以吧 数组下标就是data

    作者回复: 嗯嗯 是的

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

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

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

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

    2019-01-04
    3
    4
  • 莫弹弹
    想起来上一次需求是做敏感词检测,需要匹配到指定动词和指定名词才会触发屏蔽,经过实验,暴力for循环是最快的("▔㉨▔) trie太复杂了写完怕别人看不懂

    作者回复: 这个数据量小的话 确实暴力最快

    2018-12-14
    4
收起评论
显示
设置
留言
99+
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部