什么是 Trie Tree?

在计算机科学中,trie,又称前缀树或字典樹,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定,它主要用途就是将字符串整合成树形。

Trie 的读音?

trie 的发明者 Edward Fredkin 把它读作英语发音:”tree”。但是,其他作者把它读作英语发音:”try”。

应用场景

  • 在 NLP 中一般会用其存储大量的字典字符以用于文本的快速分词
  • 词频统计
  • 字符串查询
  • 模糊匹配(比如关键词的模糊匹配)
  • 字符串排序

特点

  • 根节点不包含字符,除根节点外的每一个子节点都包含一个字符
  • 从根节点到某一节点,路径上经过的字符连接起来,就是该节点对应的字符串
  • 每个单词的公共前缀作为一个字符节点保存,每个节点的所有子节点包含的字符都不相同。

优势

Trie 大幅降低了无谓的字符串比较,因此在执行上述任务时,其效率非常的高

双数组 Trie 树?

参考资料

  1. [](https://segmentfault.com/a/1190000008877595)
  2. Trie Tree 字典树
  3. Trie 树-北京大学张铭 Course 视频

茶歇驿站

一个可以让你停下来看一看,在茶歇之余给你帮助的小站,这里的内容主要是后端技术,个人管理,团队管理,以及其他个人杂想。

茶歇驿站二维码