字典树之旅 04.Patricia Trie(二)

字典树之旅系列文章：

1. 开篇
   

2. Trie 的标准实现
   

3. Patricia Trie(一)
   

4. Patricia Trie(二)【本文】

5. 小结【待续】

1. 概述

上一篇文章中，我们用字符比较的方式编写代码实现了 Patricia Trie，但原论文采用的是二进制位比较的方式。那么，心里可能会有一些疑问：

1. 原论文涉及到好多其它概念，两者为什么都是 Patricia Trie？

2. 二进制位比较是如何推广到字符比较方式的？

3. 二进制位比较与字符比较，两者分别有哪些优点和缺点？

那么，就带着这些疑问，继续我们的字典树之旅。相信看完这篇文章，您会找到自己的答案。

2. 由基数说起

2.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

…………

当然，我们也可以设计出一个 26 进制，譬如用小写英文字母 {a, b, c, ... , y, z} 来作为不重复编码的集合，那么其基数就是 26；

也就是说，我们可以根据需要定义一套编码集，而这个基数就是这套编码集的数量。

注：其实这里的基数(radix)，也可以看作是集合论中的基数(cardinal)，两者都有元素数量的含义，而编码集也可以看作是集合论中的有限有序集。

2.2. 基数树(radix tree)

基数概念推广到树中，那么这个基数就是 R 的大小。譬如，我们在前两篇文章中的节点定义中都有一个 R，用来表示数组大小。类似于如下定义：

class RadixNode{
    // 值    V val;
    // 子节点数组    RadixNode<V>[] table;
    // R为数组容量    public RadixNode(int R) {        this.table = new RadixNode[r];    }}

这棵树会有基数 R 个分支，且因为编码集是一个有序集，因此数组中的每一个位置都可以对应为一个唯一编码。

2.3. 基数与二进制

二进制的基数是 2，其编码集合为 {0, 1}；

而数据在计算机中都是用二进制来表示的，

那么，4 进制也可以用二进制编码的方式来表示，其编码集合为 {00, 01, 10, 11}；

然后，8 进制也可以用二进制编码的方式来表示，其编码集合为 {000, 001, ... ,110, 111}；

然后，16 进制也可以用二进制编码的方式来表示，其编码集合为 {0000, 0001, ... ,1110, 1111}，当然也可以转换成 {0, 1, 2, ... ,e , f}来表示。

…………

我们可以得到一个公式：$R=2^r(r>=1)$ ；R 为基数, r 为位数。

当使用 4 bit 来表示一个编码时 ，$R=2^4=16$，那么此时基数就是 16。

5 bit，R 就是 32；

…………

8 bit，R 就是 256，正好对应 ASCII 码；

9 bit，R 就是 512；

…………

16 bit，R 就是 65536，正好是 UTF-16 字符集。

…………

于是，如果我们把 R 设为 256 或 65536，我们就又回到了字符编码的世界，位与字符的转换由编程语言帮我们处理了。

再进一步，直接将字符看作是编码的基本单元，那么我们还可以选择部分字符来作为编码集，根据需要设计 26 进制，36 进制，37 进制……等等，正如 16 进制可以用 16 个字符来表示。

既然计算机中数据都是用二进制来表示的，我们当然就可以基于位操作来实现 Radix Tree。

2.4. 基数树与二进制

2.4.1. R 为 2

我们先来看看 R 为 2 的情形，此时只有两个编码 {0,1}。我们可以初始化节点：

// 数组大小为 2RadixNode<V> node = new RadixNode<>(2);

也就是说其构造函数会初始化数组容量为 2：

RadixNode<V>[] table = new RadixNode[2];

我们发现有且仅有两个链接，那么干脆直接将节点定义成二叉搜索树形式：

class BinaryNode{
    // 值    V val;
    // 左孩子(空 或 0)    BinaryNode<V> left;        // 右孩子(空 或 1)    BinaryNode<V> right;
    public BinaryNode() {    }}

现在，我们根据这个节点定义来构建一棵树，例如有三个键："ab", "ac" 和 "hi"。

首先，将字符串转换成二进制形式（为了避免树太高，这里按 ASCII 编码转换）；

然后，每个 bit 为一个节点，将其保存到树中。如下图所示：

图1：基数树(R=2)

最后，我们得到了一棵高度为 16 的树。

注：图中标出 0 和 1，仅为帮助理解，节点中无此字段，是隐式定义；节点中也无需保存键。

2.4.2. R 为 16

可想而知，仅仅是两个字符的字符串，就需要 16 次节点查找，效率是非常低的。

那么，我们还可以一个节点保存 4bit(nibble) ，还是这三个字符串，再画个图：

图2：基数树(R=16)

注 1：图中标出 0110 等，仅为帮助理解，节点中无此字段，是隐式定义；节点中也无需保存键。

注 2：以太坊的 MPT（Merkle Patricia Tree）就是上图这个结构的复合运用，根节点保存了树的 Hash 值。

这样，树的高度变为 4，但不能再用二叉树了，又需要定义一个数组来保存子节点， $R=2^4=16$ 。

// 数组大小为 16RadixNode<V> node = new RadixNode<>(16);

那么，能不能继续用二叉搜索树，但又让树变矮呢？下面来看几个变体。

2.5. 变体一

我们先来定义节点：

class BinaryNode<V>{
    // 键（节点中需保存完整的键）    // 因为是二进制，键其实可以不局限于字符串，这里为了方便依然设为字符串    String key;
    // 值    V val;
    // 左孩子    BinaryNode<K,V> left;
    // 右孩子    BinaryNode<K,V> right;}

具体还是先看张图：

图3：二进制树(变体一)

新增键：

假设键值相同，依次在树中插入 "ab", "ac" 和 "hi"，过程如下：

1. 插入“ab”：判断 "ab" 的第 0 个 bit，为 0，将其添加为根节点的左孩子；

2. 插入"ac"：判断 "ac" 的第 0 个 bit，为 0，根节点左孩子已存在节点 "ab" 且 "ab" != "ac"；判断第 1 个 bit，为 1，将其添加为 "ab" 的右孩子；

3. 插入 "hi"：判断 "hi" 的第 0 个 bit，为 0，根节点左孩子已存在节点 "ab" 且 "ab" != "hi"；判断第 1 个 bit，为 1，"ab" 节点已存在右孩子"ac" 且 "ac" != "hi"；判断第 2 个 bit， 为 1，将其添加为 "ac" 节点的右孩子。

查找键类似，略。

即是说，树的第 n 层就判断第 n 个 bit：如果为 0，查找左子树；如果为 1，查找右子树。但是，每一层都要判断输入键是否与当前节点的键是否相同。

这个数据结构有点莫名其妙的地方在于：既然每一层都要判断查找键与节点的键是否相同，从计算机硬件层面来说，其实是每一层都要判断两个键的全部 bit 是否完全相同，那这个数据结构按 bit 比较的意义何在？

注：我是在《Algorithms in C. 3ed[^2]》的 15.1 节看到这个介绍的，当时非常非常困惑。然后找了些相关论文来读，结果也没发现哪篇论文有类似结构（如果哪位朋友看到了介绍这个的论文，烦请告知）。

或许，作者只是为了展现有这样一种可能性，然后引出其它变体？

2.6. 变体二

图4：二进制树(变体二)

新增键：

1. 插入“ab”：判断 "ab" 的第 0 个 bit，为 0，将其添加为根节点的左孩子；

2. 插入"ac"："ab" 和 "ac" 的第 15 个 bit 不同，按 bit 依次添加空节点，最后将第 15 层空节点的左孩子设为 "ab"，右孩子设为 "ac"。

3. 插入 "hi"："hi" 的第 4 个 bit 与已存在的节点不同，将 "hi" 设为第 4 层空节点的右孩子。

查找键（以查找"ab"为例）：

1. 判断 "ab" 的第 0 个 bit，为 0，查找左子树；

2. 判断左子树是否为叶子节点，不是叶子节点，判断第 1 个 bit，第 2 个 bit……第 15 个 bit，到达第 16 层节点；

3. 判断第 16 层节点是否为叶子节点：是，全键比较。

4. 判断键是否相同：是，返回键值对；否，返回空。

注：

变体二与变体一的不同：变体二仅在叶子节点保存键，因此只需在叶子节点进行全键比较。

变体二与 2.4.1 的不同：变体二消除了单一分支的空节点，叶子节点增加了键字段。

2.7. PATRICIA

变体二有一个问题：树中有大量的空节点。而 PATRICIA，正是要解决这个问题。

2.7.1. 节点定义

惯例，我们先定义节点：

private static class PatriciaBinaryNode<V> {    // 差异位的下标位置    final int diffIndex;    // 完整的键    final String key;    // 值    V val;    // 左孩子    PatriciaBinaryNode<V> left;    // 右孩子    PatriciaBinaryNode<V> right;        // root 的构造方法    PatriciaBinaryNode() {        this.diffIndex = 0;        this.key = String.valueOf('\0');        this.left = this.right = this;    }  // 普通节点构造方法    PatriciaBinaryNode(int diffIndex, String key, V value) {        this.diffIndex = diffIndex;        this.key = key;        this.val = value;    }}

2.7.2. 查找与新增

图5：Patricia(二进制)

1. 图中的虚线为上指链接，即该链接指向自身或祖先节点；

2. root 节点的字符串为 '\0'，差异位的下标 diffIndex 为 0；

3. 为跟代码一致，这里采用 UTF-16 字符集编码进行转换。

2.7.2.1. 查找键

基本思路：先找到上指链接，然后再判断键是否相同。

从根节点依次向下查找，每次都根据当前所在节点的 diffIndex 获取键的 bit：如果该 bit 为 0，向左；如果该 bit 为 1，向右。一旦孩子节点的链接为上指链接，则停止查找 (child.diffIndex <= current.diffIndex)。

这里以查找"hi"为例【图 5 的 (4)】：

1. root 节点作为起点，root 节点的 diffIndex 为 0，键"hi" 的第 0 个 bit 为 0，查找左孩子；

2. 左孩子为 "ab" 节点，"ab" 节点的 diffIndex 为 9，键"hi" 的第 9 个 bit 为 1，查找右孩子；

3. 右孩子为 "hi" 节点，"hi" 节点的 diffIndex 为 12，键"hi" 的第 12 个 bit 为 1，查找右孩子；

4. "hi" 节点的右孩子为上指链接，该链接指向自身，停止查找。

5. 判断 “hi” 节点的键是否与输入键"hi"相同：是，返回值；否，返回空。

2.7.2.2. 新增键值对

基本思路：先查找，后新增。

这里以新增 "hi" 为例【图 5 的 (2)—>(3)】

1. 首先调用查找方法，找到 "ac" 节点【图 5 的 (2)】；

2. 比较 "ac" 与 "hi"，找到两者 的差异位下标为 12 （用于确定新增节点的位置）；

3. 再次从根节点开始向下查找，当遇到 "ac" 节点的 diffIndex 大于 12，结束查找；

4. "hi" 的第 9 个 bit 为 1，将其添加为 "ab" 节点的右孩子；

5. "hi" 的第 12 个 bit 为 1，"hi" 节点的右孩子指向自身，左孩子指向 "ac"节点；

最后，将 "hi" 节点新增到 "ab" 节点和 "ac" 节点之间【图 5 的 (3)】。

2.7.2.3. 代码实现

具体的代码实现如下，关键步骤已加注释，这里不再详述。

public class PatriciaBinaryTrie<V> implements Trie<V> {
    private final IntegerValue size = new IntegerValue();    private final PatriciaBinaryNode<V> root = new PatriciaBinaryNode<>();
    /**     * 添加键值对     *     * @param key   键     * @param value 值     */    @Override    public void put(String key, V value) {        Assert.notNull(value);        // 1.查找最接近的节点        PatriciaBinaryNode<V> near = find(key);        String nearKey = near.key;        // 2.判断键是否相同，相同则设置并返回，不同则跳到过程3        if (Objects.equals(key, nearKey)) {            if (near.val == null) {                size.increment();            }            near.val = value;            return;        }        // 3.找到两个键的差异位        int diffAt = KeyBits.diffAt(key, nearKey);        // 4.新增节点        insert(key, value, diffAt);    }
    /**     * 新增节点     *     * @param key    键     * @param value  值     * @param diffAt 差异位下标     */    private void insert(String key, V value, int diffAt) {        PatriciaBinaryNode<V> path = root, current = (KeyBits.bitAt(key, path.diffIndex) > 0) ? path.right : path.left;        while (true) {            /*              * 如果 current.diffIndex 大于等于已经比较得到的差异位 diffAt（插入键的范围下界），             * 或者 current.diffIndex 小于等于 path.diffIndex（遇到上指链接，插入键的范围上界）：             * 结束查找并新增节点             */            if (current.diffIndex >= diffAt || current.diffIndex <= path.diffIndex) {                PatriciaBinaryNode<V> node = new PatriciaBinaryNode<>(diffAt, key, value);                // 新增节点的链接指向当前节点                int bit = KeyBits.bitAt(key, node.diffIndex);                node.left = bit > 0 ? current : node;                node.right = bit > 0 ? node : current;                // 父节点的链接指向新增节点                bit = KeyBits.bitAt(key, path.diffIndex);                if (bit > 0) {                    path.right = node;                } else {                    path.left = node;                }                size.increment();                return;            }            path = current;            current = (KeyBits.bitAt(key, current.diffIndex) > 0) ? current.right : current.left;        }    }        /**     * 查找键关联的值     *     * @param key 键     * @return 值     */    @Override    public V get(String key) {        PatriciaBinaryNode<V> near = find(key);        return (Objects.equals(key, near.key)) ? near.val : null;    }
    /**     * 找到最接近的节点     *     * @param key 键     * @return 与输入的 key 最接近的节点     */    private PatriciaBinaryNode<V> find(String key) {        Assert.hasLength(key);        PatriciaBinaryNode<V> path = root;        while (true) {            PatriciaBinaryNode<V> current = (KeyBits.bitAt(key, path.diffIndex) > 0) ? path.right : path.left;            if (current.diffIndex <= path.diffIndex) {                return current;            }            path = current;        }    }}

为避免篇幅过长，其它代码不再贴出，有兴趣可以访问：

Github：https://github.com/patricklaux/perfect-code

Gitee：https://gitee.com/igeeksky/perfect-code

2.7.3. 分析

无序：观察图 5，我们会发现这棵树并不像常见的二叉树一样，左小右大，因此是无序的。但如预排序再依次插入键到树中，则是有序的，有兴趣的话可以试画图推演。另，由于其无序性，类似于前缀匹配、包含匹配之类的方法的实现会有问题，需要前驱节点和后继节点之类的方式来补充，这里并没有进行实现。

树高：最坏的情况下，树的高度等于最长的键所有位的长度。即如果一个键有 10 个字符，一个字符按 16bit 计算，最坏的情况下，查找该键需要经过 16 * 10 = 160 个节点。

前缀：仔细推演，我们会发现一个键不能是另外一个键的前缀。譬如，在这棵树中 "a" 和 "ab" 不能同时存在。 “a” 和 "ab" 的前 16 位相同，其差异位是 17，而 "a" 没有 17 位，因此无法比较。这个可以采用 C 语言中字符串的做法，在后面补一个空字符 '\0' 来解决。原代码逻辑无需改变，只是比较的时候发现不够长就补一个 '\0'，如有兴趣可以看 com.igeeksky.perfect.nlp.string.KeyBits 这个类。

3. 小结

回到文章开头的问题：

1. 原论文涉及到许多其它概念，两者为什么都是 Patricia Trie？

2. 原论文描述的几乎是一个完整的检索系统，因此包含了许多术语和概念，但其算法的核心思想是合并单路分支。因此，无论字符比较方式还是二进制比较方式，只要是合并单路分支，都可以认为是 Patricia trie（原论文见参考资料 3）。

3. 二进制位比较是如何推广到字符比较方式的？

4. 如果看作是基数树，位比较推广到字符比较，只是基数大小变化而已。

5. 二进制位比较与字符比较，两者分别有哪些优点和缺点？

6. 二进制位比较，减少了空链接，但增加了树的高度，查找的时间性能会变差。同时，虽然空链接少了，但一个 bit 一个节点的方式依然会耗费大量内存。在上面介绍的这么多结构中，<2.4.2. R 为 16> 是相对合理的，在时间和空间上找到了一个比较完美的平衡点。

最后，感谢您的阅读！不要忘了点赞收藏哦！

参考资料

[1]  R. Sedgewick and K. Wayne. "Algorithms, fourth edition." Addison-Wesley(2011):730-753

[2]  R. Sedgewick. "Algorithms in C, third edition." Addison-Wesley(1998):614-648

[3]  Morrison, Donald R.. “PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric.” Journal of the ACM (JACM) 15 (1968): 514 - 534.

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