Trie

前文实现了 Patricia Trie，但用的是字符比较，而原论文则采用的是二进制位比较。 然后，我们心里可能会有疑问：二进制位比较是如何推广到字符比较的呢？二进制位比较相比于字符比较，又有哪些优点或缺点呢？ 相关代码：https://github.com/patricklaux/perfect-code 1. 基数 让我们先从基数说起吧。 1.1. 基数(radix) 基数(radix)，在定位数系(positional numeral system) 中表示不重复编码(digit) 的数量。 譬如在10进制中，有 {0, 1, 2, … ,8, 9} 共 10 个编码，那么基数就是 10； 譬如在16进制中，有 {0, 1, 2, … ,e, f} 共 16 个编码，那么基数就是 16； ………… 如果我们用 EASCII 字符编码来作为集合，那么其基数就是 256； 如果我们用 UTF-16 字符编码来作为集合，那么其基数就是 65536； ………… 如果我们用小写英文字母 {a, b, c, … , y, z} 来作为集合，那么其基数就是26。 也就是说，我们可以根据需要定义一套编码集，而基数就是这套编码集的元素数量。 注：基数(radix) 也可以看作是集合论中的基数(cardinal)，而编码集是有限良序集。 1.2. 基数树(radix tree) 基数概念推广到树中，那么这个基数就是 R 的大小。 我们在前两篇文章的节点定义就有一个 R，用来指定数组容量。类似于如下定义： class RadixNode{ // 值 V val; // 子节点数组 RadixNode<V>[] table; // R为数组容量 public RadixNode(int R) { this.table = new RadixNode[R]; } } 这棵树会有 R 个分支，又因为编码集是有限良序集，所以可将数组索引映射为唯一编码。 ...

这篇文章我将介绍 StandardTrie 的简单变体： PatriciaTrie1。 PatriciaTrie 或 PatriciaTree， 在一些论文中又被称为 CompactTrie（紧凑 trie）或 CompressedTrie（压缩 trie）。 相关代码：https://github.com/patricklaux/perfect-code 1. 导引 PatriciaTrie 的显著优化是合并单路分支：如果一个非根无值节点有且仅有一个子节点，则将其子节点与该节点合并。 文字描述稍有点抽象，还是看图： 节点合并 图1：节点合并 节点分裂 如果需要添加键 “da”，该如何来处理哪？我们需要将 “dad” 分裂成两个节点，效果见下图： 图2：节点分裂 相信，这两张图已足以说明一切😀 同时，我们也可以看到合并后节点数变少，因此减少了可能的内存消耗。 2. 代码实现 依照惯例，还是写代码来实现它。 2.1. 节点定义 package com.igeeksky.perfect.nlp.trie; private static class PatriciaNode<V> { // key 的子串 String subKey; // 值（支持泛型，可以是非字符串） V val; // 子节点 PatriciaNode<V>[] table; public PatriciaNode(int R) { this.table = new PatriciaNode[R]; } public PatriciaNode(int R, String subKey) { this.subKey = subKey; this.table = new PatriciaNode[R]; } public PatriciaNode(String subKey, V value) { this.subKey = subKey; this.val = value; } public PatriciaNode(int R, String subKey, V value) { this.subKey = subKey; this.val = value; this.table = new PatriciaNode[R]; } } 对比前文的 StandardNode，多了一个 String 类型的 subKey 字段，该字段用于存储节点合并之后的字符串，其它无变化。 ...

这篇文章将介绍最简单的 Trie 结构，即 StandardTrie，常被称为 标准 Trie，或朴素 Trie。 相关代码：https://github.com/patricklaux/perfect-code 1. 导引 假设有一个关键词集，其中有 6 个单词：bad, bade, bed, ca, cad, dad。 当输入 “b” 时，输出以 “b” 为前缀的所有单词； 输入一段文本，输出文本中存在这六个单词的哪几个，以及单词出现的起止位置…… 我们可以建立如下图所示的树形结构。 图1：字典树示例 每个字符一个节点，节点之间用边相连； 有特殊标记（有值）则代表一个完整的关键词。 2. 基本性质与操作 通过观察 ”图1：字典树示例“，我们可以发现一些性质和规律。 基本性质 根节点无字符； 兄弟节点的字符互异； 非根节点有且仅有一个字符； 非根节点有且仅有一个父节点； 根节点到其它节点的每条路径代表一个唯一的字符串。 根据以上性质，我们又可以得到一个有意思的推论：6. 兄弟节点都具有同一前缀； 键查找 从根节点沿着序列路径递归查找子节点，最后一个字符对应节点如果有特殊标记，则命中。 譬如要查找 bad，root → b → a → d，命中，返回 bad；譬如查找 cup，root → c → NULL，未命中，返回空。 前缀匹配 先找到前缀节点，然后遍历其子节点。 譬如查找以 b 为前缀的关键词：1. 先找到 b 对应的节点，root → b，找到 b 节点；2. 遍历 b 节点的所有子节点。 ...

Trie1 通常被称为字典树（或前缀树、单词搜索树），是一种用于存储和检索字符串的树型数据结构。 Trie 是英文单词 retrieval 的一部分，名称最早由 E. Fredkin2 提出，发音同 “try”。 图1：关键词推荐列表 典型的应用场景是搜索引擎的输入框：譬如当输入 “trie” 时，会列出以 “trie” 为前缀的关键词推荐列表。 此外，还有诸如拼写检查、词典分词、词频统计、数据压缩、倒排索引、字符串排序、关键词过滤……等等众多应用场景。 技术演化 由于字典树相关算法的应用广泛，所以演化出大量的数据结构和优化技术，其进化史就是一个脑洞大开的过程。 我之前画过一张复杂的演进图，现在看来并无必要，事实上只要了解关键脉络即可。删繁就简，最终留下了这张比较简单的图。 图2：技术演化 文章目录 字典树之旅01：开篇（本文） 字典树之旅02：Trie 的标准实现 字典树之旅03：Patricia Trie(一) 字典树之旅04：Patricia Trie(二) 未完待续…… 参考资料 https://en.wikipedia.org/wiki/Trie ↩︎ Fredkin, E. . “Trie memory.” Communications of the Acm 3(1960). ↩︎