如何做网站吸引广告商,dedecms网站版权信息,深圳保障性住房申请,营销网站建设费用来源 | 码海责编 | Carol封图 | CSDN 付费下载于视觉中国我们几乎每天都在用搜索引擎搜索信息#xff0c;相信大家肯定有注意过这样一个细节:当输入某个字符的时候#xff0c;搜索引框底下会出现多个推荐词#xff0c;如下#xff0c;输入「python」后#xff0c;底下会出… 来源 | 码海责编 | Carol封图 | CSDN 付费下载于视觉中国我们几乎每天都在用搜索引擎搜索信息相信大家肯定有注意过这样一个细节:当输入某个字符的时候搜索引框底下会出现多个推荐词如下输入「python」后底下会出现挺多以python 为前缀的推荐搜索文本它是如何实现的呢文章标题已经给出答案了没错用 Trie 树。本文将会从以下几个方面来简述一下 Trie 树的原理以让大家对 Trie 树有一个比较全面的认识。什么是 Trie 树Trie 树的实现如何实现搜索字符串自动提示再谈 Trie 树相信大家看了肯定有收获什么是 Trie 树Trie 树又称前缀树字典树或单词查找树是一种树形结构也是哈希表的变种它是一种专门处理字段串匹配的数据结构用来解决在一组字符串集合中快速查找某个字符串的问题主要被搜索引擎用来做文本词频的统计。画重点快速字符串匹配词频统计。1、快速字符串匹配假设想要在一串字符串如 a, to, tea, ted, ten, i, in, inn 中多次查找某个字符串是否存在该怎么做呢很直观的想法是用 hash这种确实没问题如果 hash 函数设计得好的话如果 hash 函数设计得不好很容易产生冲突进而退化成字符串间的比较另外在英文中其实有很多单词有共同的前缀比如中 tea, ted, ten 这三个单词有共同的前缀 te, 如果用 hash 的话无疑这些共同前缀相当于重复存了多次比较费空间。如果用 Trie 树的话能解决以上两个问题先来看下 trie 树是如何表示的以以上的一组字符串 a, to, tea, ted, ten, i, in, inn 为例它们组成的 Trie 树如下如果要查找某个字符串的话从根节点出发每次取待查找字符串中的一个字符往下遍历即可找到可以看到它的查找时间复杂度为 O(N) (N 为字符串长度)还是很快的(英文单词普遍比较短)。2、词频统计 只要在每个结点上加一个计数器遍历单词时所有字符串的最后一个字符对应结点的计算器都加 1 如以 aanand 构造的 Trie 树如下每个结点计算器都为 1代表以此结点存储字符为终止字符的单词分别为 1 个。从前面 Trie 树的图解可以看到 Trie 树的本质就是前缀树通过提取出字符串的公共前缀(如果有的话)以达到快速匹配字符串的目的。通过前缀匹配使用 Trie 树查找字符串的效率大大提高从以上 Trie 树的图解我们可以得出 Trie 树的以下几个特点根节点不包含字符除根节点外每个节点只包含一个字符从根节点到某一节点路径上经过的字符连接起来为该节点对应的字符串。如上图中从根节点到结点 o经过的字符为「t」和「o」,所以它表示单词 to。每个节点的所有子节点包含的字符都不相同这一点也就保证了相同的前缀能够得到复用。那么 Trie 树该怎么表示呢Trie 树的实现从上文我们对 Trie 树的剖析可以很明显地看到 Trie 树是一颗多叉树那么多叉树该怎么表示呢假设字符串都是由 26 个小写字母组成则显然 Trie 树应该是一颗 26 叉树每个节点包含 26 个子节点如下上图可以看出26 个子节点我们可以用大小为 26 的数组表示所以 Trie 树表示如下/** * 26 个字母 */static final int ALPHABET_SIZE 26;/** * Trie 树的节点表示 */static class TriedNode {/** * 根节点专用存储 / */public char val;/** * 以此结点字符为终止字符的字符串的个数 */public int frequency;/** * 节点指向的子节点 */ TriedNode[] children new TriedNode[ALPHABET_SIZE];public TriedNode(char val) {this.val val; }}/** * Trie 树 */static class TrieTree {private TriedNode root new TriedNode(/); // 根节点}Trie 树的表现有了现在我们来看下 Trie 树的两个主要操作根据一组字符串构造 Trie 树在 Trie 树中查找字符串是否存在先来看如何根据一组字符串构造 Trie 树首先如何根据一个单词来构造 Trie 树呢假设我们以单词 「and」 为例来看下 Trie 树的表现形式注图中的数字表示数组的元素位置可以看到构建 Trie 树的主要步骤如下构建根节点此时根节点存有一个元素大小为 26 的数组遍历字符串「and」遍历第一个字符 a 时将上述数组的第一个元素赋值为一个 TriedNode 实例(假设其名为 A)当遍历第二个字符 n 时将 A 结点 TriedNode 数组下标为 n-a 13 (a 的 ascii 为 97n 的 ascii 码为 110) 的元素赋值为一个 TriedNode 实例(假设其名为 N)同理当遍历第三个字符 d 时将 N 结点 TriedNode 数组的第 4 个元素(下标为 3)赋值为一个 TriedNode 实例(假设其名为 D)同时也将其结点的 frequency 加一代表以此字符为终止字符的字符串多了一个。由以上分析不难写出根据字符串构建 Trie 树的代码如下/** * Trie 树 */static class TrieTree {private TriedNode root new TriedNode(/); // 根节点/** * 以 String 为条件构建 Trie 树 * param s */public void insertString(String s) { TriedNode p root;for (int i 0; i char c s.charAt(i);int index c-a;if (p.children[index] null) { p.children[index] new TriedNode(c); } p p.children[index];//Process char } p.frequency; }}Trie 树构造好了再在 Trie 树中查找某字符串是否存在就简单很多了遍历字符串查看每个字符在相应层级的数组位置的元素是否为空即可如果是说明不存在如果不是则继续遍历字符查找直到遍历完成代码如下/** * 查找字符串是否在原字符串集合中 * param s * return boolean */public boolean findStr(String s) { TriedNode p root;for (int i 0; i // 当前被遍历的字符char c s.charAt(i);int index c-a;if (p.children[index] null) {// 如果字符对应位置的数组元素为空说明肯定不存在此字符终止之后的字符遍历return false; }// 如果存在则继续往后遍历字符串 p p.children[index]; }return true;}由于在节点中也用 frequency 保存了单词数所以如果在 Trie 树中最终发现字符串存在也可以随便查找出此字符串的个数。如何实现搜索字符串自动提示功能有了 Trie 树相信大家不难解决开篇的这个问题首先搜索引擎根据用户的搜索词构建一颗 Trie 树假设这个搜索词库是 a, to, tea, ted, ten, i, in, inn则构建的 Trie 树为那么当用户在搜索框输入「te」的时候根据 Trie 树的特性得知以 te 为前缀的字符串有 teatedten则应该在搜索框提示词中展示这三个字符串。这里有一个小问题一般搜索框只会展示 10 个搜索词但以用户输入字符串为前缀的字符串可能远超 10 次到底该展示哪 10 个呢最简单的规则是展示搜索次数最多的 10 个字符串于是问题就转化为了 TopK 问题维护一个有 10 个元素的小顶堆步骤如下先根据用户输入的前缀在树中找出含有此前缀的所有字符串我们知道在节点中保存了字符串的被搜索次数所以利用小顶堆即可算出被搜索次数最多的 10 个字符串即可得最终展示给用户的提示词。注意这里的求 TopK 要用是小顶堆不是大顶堆哦在之前一篇文章中有读者提出了疑问不要搞混了小顶堆是求最大的 Top K 值大顶堆是求最小的 TopK 值由于我们要求最多的前 10 个搜索词所以应该是用小顶堆)。这样就解决了考虑以下现象我们在输入搜索词的时候搜索引擎给出的提示词可能并不是以用户输入的字符串为前缀的。如图示搜索引擎给出的搜索关键字并不包含有「brekfa」 前缀。这种又是怎么实现的呢它实际上用到了字符串编辑距离的思想所谓字符串编辑距离是说一个字符串可以通过增删改查字符来变成另外一个字符串。如图示: brekfa 添加 a 之后变成了 breakfa显然所作的增删改查次数越少效率越高经过最少的字符中编辑变成另一个合法的字符串后就以此字符串为前缀去 Trie 树中查找提示词。当然了像 Google 这样的搜索引擎要实时显示这些结果背后肯定经过了很多改造。不过原理都大同小异。再谈 Trie 树从前面的介绍中我们可以看到使用 Trie 树确实在能在快速查找字符串与词频统计上发挥重要作用但天下没有免费的午餐如果字符集比较大的话用 Trie 树可能会造成空间的浪费以上文中构建的 Trie 树为例每个结点维护一个 26 个元素大小的数组共有 4 个数组也就是分配了 26 x 4 104 个元素的空间但实际上只有三个元素空间(and)被分配了浪费了 101 个空间空间利率率很低所以一般更适用于字符串前缀重复比较多的情况当然也可以考虑对 Trie 树进行如下缩点优化能节省一些空间当然这么优化后也增加了代码的编码难度所以要视情况而定。另外如果用 Trie 树的话一般需要我们自己编码对工程师的编码能力要求较高所以是否用 Trie 树我们一般建议如下如果是字符串的精确匹配查找我们一般建议使用散列表或红黑树来解决毕竟很多语言的类库都有现成的不需要自己实现拿来即用如果需要进行前缀匹配查找则用 Trie 树更合适一些总结本文通过搜索引擎字符串提示简要地概述了其实现原理相信大家应该理解了需要注意的是其使用场景更推荐在需要前缀匹配查找的时候用 Trie 树否则像一般的精确匹配查找等更推荐用散列表和红黑树这些很成熟的数据结构毕竟这两数据结构实现一般在类库中都是实现了的不需要自己实现尽量不要重复造轮子。推荐阅读手把手教你配置VS Code 远程开发工具工作效率提升N倍用大白话彻底搞懂HBase RowKey详细设计后端程序员必备书写高质量SQL的30条建议Go 远超 Python机器学习人才极度稀缺全球 16,655 位程序员告诉你这些真相任正非谈“狼文化”华为没有 996更没有 007区块链必读“上链”哲学“胖链下”与“瘦链上”在商业中如何与人工智能建立共生关系真香朕在看了
