字典树之旅01：开篇

Trie¹ 通常被称为字典树（或前缀树、单词搜索树），是一种用于存储和检索字符串的树型数据结构。

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

图1：关键词推荐列表

典型的应用场景是搜索引擎的输入框：譬如当输入 “trie” 时，会列出以 “trie” 为前缀的关键词推荐列表。

此外，还有诸如拼写检查、词典分词、词频统计、数据压缩、倒排索引、字符串排序、关键词过滤……等等众多应用场景。

技术演化

由于字典树相关算法的应用广泛，所以演化出大量的数据结构和优化技术，其进化史就是一个脑洞大开的过程。

我之前画过一张复杂的演进图，现在看来并无必要，事实上只要了解关键脉络即可。删繁就简，最终留下了这张比较简单的图。

图2：技术演化

未完待续……