字典树之旅 01. 开篇

简介

字典树（Trie），又称为前缀树（prefix tree），用于从集合中定位特定键的树数据结构。

Trie 是“检索”的英文单词 retrieval 的一部分，名称最早由 E. Fredkin [1] 提出，其发音同“try”。

注：名词解释原文见参考资料 [^2]

想象一下我们用字典查找单词的过程：

譬如，我们要找 “abandon” 这个单词（键），首先找第一个字符 a，定位到 a 所在页码，然后是通过第二个字符 b，定位到 ab 所在的页或行……最后定位完成，找到完整的单词 “abandon”，然后我们就可以查看单词对应的解释（值）了。

Trie 指的就是类似这样的一种检索行为，至于是用数组、二叉查找树或又是其它一些数据结构去模拟，只是不同的实现策略而已。

图1：搜索推荐列表

常见的应用场景如搜索引擎的输入框：输入“trie”，会列出以“trie”为前缀的搜索推荐信息。

此外，还有诸如词典分词、词频统计、拼写检查、数据压缩、倒排索引、字符串排序、关键字过滤……等等应用场景，由于其应用广泛，所以涌现出大量相关的优化算法和数据结构，各种优化，各种变体。

因此，这是一种非常有意思的数据结构，其进化史就是一个脑洞大开的过程。

家族

我在学习过程中有两大困扰：

1. 谁提出了这种数据结构或算法？是对哪种数据结构或算法的改进？为什么要提出新的数据结构和优化算法？其解决了什么问题？其付出的代价是什么？

2. 为什么定义这个名词？该名词代表的含义和主要思想是什么？该名词从诞生到现在含义是否已经有变化？为什么多个名词指代的都是同一种数据结构？

作为一个喜欢穷根究底的人，当然希望能够了解其演变思想和改进过程，将知识片段转化成知识体系，因此边查资料边思考，整理了如下字典树演化图：

图2：字典树家族

注：红色部分是我计划实现的数据结构。

提纲

图 2 只是基本脉络，我计划从字典树的标准实现开始，一步步去探索优化策略和实现各种变体，行文过程中再进一步详述各个数据结构或算法之间的联系和演变。大致提纲如下，这貌似是一个浩大的工程，希望我能完成😀

1. Trie 的标准实现
   

2. Patricia Trie

3. Ternary search trie

4. Trie 的综合优化

5. Suffix tree

6. 单模式匹配之 KMP

7. AC 自动机

8. Double array trie

9. DAC

10. 单模式匹配之 BM

11. Wu-Manber

12. B-trie

最后，希望我的文章能对读者有一些帮助，也希望朋友们能给我建议和反馈。总之，相互学习！共同进步！

代码仓库

文章相关代码在这两个仓库：

实验性代码：https://github.com/patricklaux/perfect-code

生产级代码：https://github.com/patricklaux/xtool

参考资料

[1]: Fredkin, E. . "Trie memory." Communications of the Acm 3(1960).

[2]: Donald E. Knuth. "The Art of Computer Programming. Volume III: Sorting and Searching." Addison-Wesley(1973):492-512