压缩 Trie（也称为 Radix Tree、Patricia Trie 或 Compact Prefix Tree）是一种通过合并单子节点路径来减少节点数量和内存占用的 Trie 变体。它在搜索引擎、路由表、自动补全等系统中广泛应用。

以下是 压缩 Trie 的常见技巧与实现策略，兼顾效率、正确性和实用性：

✅ 一、核心思想：路径压缩（Path Compression）

原始 Trie 的问题：
root
└─ a
└─ p
└─ p
└─ l
└─ e → “apple”

每个字符一个节点，深度 = 单词长度
内存浪费（尤其长单词、稀疏前缀）

压缩后（Radix Tree）：
root
└─ “apple” → “apple”

单链路径合并为一个字符串边
节点数大幅减少

🔑 压缩条件：从某节点开始，每个节点只有一个子节点，直到分叉或叶子

✅ 二、常见压缩技巧

按最大公共前缀合并（Insert 时分裂）

当插入新单词时，若与现有路径有公共前缀但后续不同，则分裂节点。

示例：
已有 “apple”
插入 “applet”

步骤：
公共前缀 = “apple”
原节点 “apple” 分裂为：
父节点：“apple”
子节点1：“” → 标记为单词（“apple”）
子节点2：“t” → “applet”

root
└─ “apple”
├─ “” → (isWord=true) // 表示 “apple”
└─ “t” → “applet”

💡 实现关键：找到最长公共前缀（LCP），然后分裂

懒压缩（Lazy Compression）

不在插入时立即压缩，而是在查询或批量构建后统一压缩
优点：简化插入逻辑，适合动态场景
缺点：中间状态非最优

适用于频繁更新的 Trie（如实时关键词过滤）

使用字符串边代替字符边

每个边存储一个 字符串片段（label），而非单个字符。

class RadixNode {
Map children = new HashMap();
boolean isWord = false;
String word = null; // 可选：存储完整单词
}

插入 “apply” 到已有 “apple”：
LCP = “appl”
分裂：
原 “apple” → 边 “e”
新 “apply” → 边 “y”
公共父节点边为 “appl”

root
└─ “appl”
├─ “e” → “apple”
└─ “y” → “apply”

✅ 查询时逐段匹配字符串，而非逐字符

后缀共享（Suffix Sharing）→ DAFSA

更进一步：不仅压缩前缀，还共享后缀（有向无环词图，DAFSA）。

“apple” 和 “people” 可共享 “ple”
需要更复杂的构建算法（如 algorithm from Jan Daciuk）

⚠️ 实现复杂，但内存节省可达 70%+
应用于拼写检查器（如 Hunspell）

✅ 三、高效实现技巧

避免字符串拷贝（使用索引/视图）

在 Java/Python 中，频繁创建子串（substring）会复制内存。

优化方案：
存储 (originalString, start, end) 三元组
或使用 CharSequence / StringView（C++）

// 避免
String label = word.substring(i, j); // O(k) copy

// 推荐（伪代码）
class Edge {
char[] chars;
int start, len;
}

在大规模词典中，可节省 GB 级内存

预排序 + 批量构建

对单词列表按字典序排序后线性构建 Radix Tree：

相邻单词共享最长前缀
可用栈维护当前路径，高效分裂

words = sorted(words)
stack = [root]
for word in words:
lcp = longest_common_prefix(word, prev_word)
# 弹出栈直到 lcp 层级
# 压入新节点

时间复杂度接近 O(N)（N = 总字符数）

限制最小压缩长度

不压缩长度 < 2 的路径（如 “a” → “b”）
避免过度分裂导致节点数反而增加

经验值：min_compression_length = 2 or 3

✅ 四、查询优化（配合压缩）

逐段匹配（Segment Matching）

boolean search(String word) {
RadixNode node = root;
int i = 0;
while (i < word.length()) {
boolean found = false;
for (String label : node.children.keySet()) {
if (word.startsWith(label, i)) {
i += label.length();
node = node.children.get(label);
found = true;
break;
}
}
if (!found) return false;
}
return node.isWord;
}

⚠️ 注意：children 应用 Trie 或排序 Map 加速匹配（否则 O(k) 遍历所有边）

边使用 Trie 存储（Hybrid Structure）

每个节点的 children 本身是一个小 Trie（按首字符索引）
避免遍历所有边

class RadixNode {
TrieNode edgeTrie; // 存储所有出边的首字符
}

适用于出度高的节点

✅ 五、工业级应用案例
系统 使用方式 优势
Redis Stream Radix Tree 存储消息 ID 内存高效，范围查询快

Linux 内核 路由表（fib_trie） 快速 IP 前缀匹配

Lucene FST（有限状态 transducer） 比 Radix 更紧凑

Git 对象名前缀查找 快速定位 SHA1

✅ 六、何时不 使用压缩 Trie？
场景 原因
需要逐字符处理（如输入法实时提示） 压缩后无法中途截断

单词极短且无公共前缀（如随机 ID） 压缩收益低，反而增加复杂度

频繁动态增删且要求强一致性 分裂/合并逻辑复杂，易出错

✅ 总结：压缩 Trie 最佳实践
技巧 适用场景
路径压缩 + 字符串边 通用静态词典 ✅

LCP 分裂 + 批量构建 构建一次，多次查询 ✅

避免字符串拷贝 大词典、内存敏感 ✅

结合 DAFSA 极致内存优化（如嵌入式）✅

保留原始 Trie 需要字符级控制（如 LeetCode）⚠️

💡 一句话口诀：
“单链合并，分叉分裂，批量构建，避免拷贝”

通过合理应用这些技巧，压缩 Trie 可在保持 O(L) 查询时间的同时，减少 50%~90% 的内存占用，是高性能文本系统的基石之一。