第 15 章 Trie 字典树¶

原作：Josh Hug，UC Berkeley CS61B Spring 2021 配套读本。
中文翻译版，仅供非商业学习；采用 CC BY-NC-SA 4.0 许可。
原始网站：https://joshhug.gitbooks.io/hug61b/content/

15.1 Trie 入门¶

Trie（字典树、前缀树）是 Set 和 Map 的一种特殊实现。它针对能够拆分为“字符”、且不同键之间经常共享前缀的数据，提供了额外能力。

回顾已有实现¶

此前，Set 和 Map 主要使用平衡搜索树或拉链哈希表：

平衡搜索树：
contains(x)：\(\Theta(\log N)\)
add(x)：\(\Theta(\log N)\)
可扩容拉链哈希表：
contains(x)：在分布均匀的假设下为 \(\Theta(1)\)
add(x)：在分布均匀且按摊还分析时为 \(\Theta(1)\)

这些复杂度已经非常优秀。但如果我们知道键具有特殊结构，还能使用更专门的方法。

例如，若所有键都是 ASCII 字符，可直接用字符编码作为数组索引：

public class DataIndexedCharMap<V> {
    private V[] items;

    public DataIndexedCharMap(int R) {
        items = (V[]) new Object[R];
    }

    public void put(char c, V val) {
        items[c] = val;
    }

    public V get(char c) {
        return items[c];
    }
}

R 是可能字符的数量，例如 ASCII 可取 128。知道键的范围后，这个实现非常简单高效。

练习 15.1.1：实现一个只允许键为 0 到 100 的整数 Map，并让它比通用 HashMap 更直接。

发明 Trie¶

Trie 适用于键可以拆成字符、且多个键共享前缀的场景，例如字符串。

假设集合中有：sam、sad、sap、same、a、awls。

Trie 的关键思想：

每个结点只代表一个字符。
多个键可以共享结点。
相同前缀只存储一次。

例如 sam、sad、sap 和 same 都共享前缀 sa。

查找一个键时，从根开始按照字符串的字符逐层向下走。

仅仅存在一条字符路径还不够，因为某个键可能只是另一个键的前缀。每个结点因此还需要记录“到这里是否构成完整键”，图中用蓝色表示终止结点。

contains("sam")：true，终点是已标记结点。
contains("sa")：false，路径存在但终点未标记。
contains("a")：true。
contains("saq")：false，中途没有对应孩子。

练习 15.1.2：向图中的 Trie 加入 ants、zebra、potato 和 sadness。

练习 15.1.3：Trie 用作 Map 与用作 Set 时有什么差别？提示：Map 的终止结点还需要保存 value。

可查看 Trie Map 动画。

总结¶

给通用问题增加合理约束，常常可以设计出更高效或功能更强的结构。
ADT 与实现不同：并查集是 ADT，Quick Find、Quick Union、WQU 和 WQUPC 是不同实现。
Trie 是专门针对字符串键的 Set/Map 实现。
每个结点对应字符，共同前缀由多个键共享。
搜索失败有两种原因：路径中断，或终点没有被标记为完整键。
Trie 来自 “retrieval tree”。通常读作 “try”。

15.2 实现与性能¶

基本实现¶

第一次实现中，每个结点保存：

一个字符；
是否为完整键的终点；
指向孩子的映射。

由于键字符已知，可以用 DataIndexedCharMap 表示孩子：

public class TrieSet {
    private static final int R = 128; // ASCII
    private Node root;

    private static class Node {
        private char ch;
        private boolean isKey;
        private DataIndexedCharMap<Node> next;

        private Node(char c, boolean isKey, int R) {
            ch = c;
            this.isKey = isKey;
            next = new DataIndexedCharMap<>(R);
        }
    }
}

问题是空间浪费严重。若某个结点只有一个孩子，它仍然拥有 128 个引用位置，其中 127 个都是 null。

还可以删掉结点自己的 ch 字段。字符已经由它在父结点 next 映射中的键决定：

public class TrieSet {
    private static final int R = 128;
    private Node root;

    private static class Node {
        private boolean isKey;
        private DataIndexedCharMap<Node> next;

        private Node(boolean isKey, int R) {
            this.isKey = isKey;
            next = new DataIndexedCharMap<>(R);
        }
    }
}

练习 15.2.1：设计一种更节省孩子引用空间的方案。

性能¶

若 Trie 中有 \(N\) 个键，只以 \(N\) 为参数看：

add：\(\Theta(1)\)
contains：\(\Theta(1)\)

原因是操作时间不依赖键的总数量，只依赖当前键本身的长度。更准确地，令键长度为 \(L\)：

add：\(\Theta(L)\)
contains：\(O(L)\)

与哈希表不同，这种性能不依赖“分布均匀”假设，也没有扩容带来的摊还条件。不过数组孩子映射会消耗大量空间。

孩子映射的选择¶

方案一：直接字符数组 `DataIndexedCharMap`¶

每个结点固定拥有 \(R\) 个引用。
查找孩子为 \(\Theta(1)\)。
字母表较大、分支较少时非常浪费空间。

方案二：BST¶

只为实际存在的 \(C\) 个孩子创建结点：

空间约为 \(C\) 条孩子链接。
查找孩子为 \(O(\log R)\)。

方案三：哈希表¶

同样只保存实际孩子：

空间约为 \(C\) 条孩子链接。
在合理哈希假设下，查询近似常数时间。

源材料表中的复杂度可以概括为：

孩子映射实现	每结点空间	查询孩子
`DataIndexedCharMap`	\(R\) 个引用	\(\Theta(1)\)
BST	\(C\) 个引用及结点开销	\(O(\log R)\)
哈希表	\(C\) 个引用及桶开销	平均 \(O(1)\)

这里 \(R\) 是固定字母表大小，因此即使 \(O(\log R)\) 也可以视作与键数量无关的常数。不过 BST 和哈希表的每条链接有更高对象开销。

这一选择再次体现了抽象屏障：Trie 的结点需要的是一个 Map ADT，而孩子 Map 的具体实现可以根据空间与速度需求替换。

15.3 字符串操作¶

Trie 的插入和查询复杂度看起来非常好，但它在普通操作上未必一定比 BST 或哈希表更快。Trie 必须逐字符走完整个字符串，而 BST 或哈希表在程序层面可以直接处理整个字符串对象。

Trie 真正突出的地方，是能高效支持特殊字符串操作。

前缀匹配¶

`longestPrefixOf`¶

给定一个查询字符串，从根开始逐字符向下走，并记录最近一次遇到的完整键终点。无法继续时，返回最后记录的最长键前缀。

收集所有键¶

可以用深度优先搜索收集 Trie 中的所有键：

collect():
    创建空结果列表 x
    对 root.next.keys() 中的每个字符 c：
        调用 colHelp(String.valueOf(c), x, root.next.get(c))
    返回 x

colHelp(String s, List<String> x, Node n):
    如果 n.isKey：
        x.add(s)
    对 n.next.keys() 中的每个字符 c：
        调用 colHelp(s + c, x, n.next.get(c))

递归参数 s 表示从根到当前结点形成的字符串。只有当前结点标记为完整键时才加入结果，然后继续遍历所有孩子。

`keysWithPrefix(prefix)`¶

先沿 prefix 找到对应终点结点 alpha。
若路径不存在，返回空列表。
从 alpha 出发调用与 collect 相同的递归辅助方法，并把已有前缀带入。

keysWithPrefix(prefix):
    找到 prefix 的终点结点 alpha
    若 alpha 不存在，返回空列表
    创建空列表 x
    若 alpha.isKey，把 prefix 加入 x
    对 alpha.next.keys() 中每个字符 c：
        colHelp(prefix + c, x, alpha.next.get(c))
    返回 x

练习 15.3.1：为 longestPrefixOf 写出完整伪代码。

自动补全¶

搜索框输入文字时出现的建议，可以用 Trie 实现。建立一个从字符串到分数的 Map：

value 表示查询的重要性，例如使用频率。
大量字符串共享前缀结点，减少重复存储。
用户输入前缀 x 后，调用 keysWithPrefix(x)，再返回分数最高的 10 个字符串。

直接收集所有匹配键在短前缀下可能非常昂贵，因为结果可能有数百万条，而我们只需要 10 条。

一种优化是：在每个 Trie 结点中额外记录其子树内的最大分数。搜索时优先探索潜在最高分的孩子，并结合优先队列逐步取出最有希望的候选分支。

另一种优化是合并只有单一孩子的冗余路径，让一个结点保存一段字符串而不是单个字符。这会得到基数 Trie（radix trie）。

练习 15.3.2：思考为每个结点保存子树最佳分数会增加哪些维护成本，以及如何用优先队列设计 Top-K 自动补全算法。

总结¶

如果所有键都是字符串，就可以使用 Trie 实现 Map 或 Set：

理论操作复杂度按键长 \(L\) 计为 \(\Theta(L)\)，与键数量 \(N\) 无关。
孩子可以由字符数组、BST 或哈希表保存。
实际速度不一定总胜过哈希表，但 Trie 天然支持：
longestPrefixOf
keysWithPrefix
自动补全

结构	键要求	`get/contains`	`add`
平衡 BST	可比较	\(\Theta(\log N)\)	\(\Theta(\log N)\)
可扩容拉链哈希表	可哈希	平均 \(\Theta(1)\)，依赖均匀分布	摊还平均 \(\Theta(1)\)
直接索引数组	有限字符范围	\(\Theta(1)\)	\(\Theta(1)\)
Trie	字符串	\(\Theta(L)\)	\(\Theta(L)\)