Patricia 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 字段，该字段用于存储节点合并之后的字符串，其它无变化。 ...