Trie Tree 原理分析

什么是 Trie Tree?

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

Trie 的读音？

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

应用场景

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

特点

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

优势

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

双数组 Trie 树？

参考资料

2. Trie Tree 字典树
3. Trie 树-北京大学张铭 Course 视频

---

茶歇驿站

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