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

精选留言(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