用 Rust 从零实现前缀树:从普通 Trie 到双数组 Trie
搜索框里输入"rust",下拉出"rust 异步""rust 所有权""rust 宏"——这个功能看起来简单,但用哈希表根本做不了。
原因很简单:哈希表能回答"这个 key 存在吗",但回答不了"哪些 key 以这个前缀开头"。前者是点查,后者是范围查。
而 Trie(前缀树)天生就是为前缀查设计的。这篇从最朴素的实现开始,一路优化到工业级的双数组 Trie。
朴素 Trie:每个节点一个子节点映射
Trie 的结构很直观:从根出发,每个字符走一条边。字符串共享前缀,就共享路径。
(root)
/ | \
r c z
| | |
u a i
| | |
s r g
/ \ |
t t p
| | |
(1)(2) p插入 rust、rusk、carp、zig,路径会自动共享 rus 这一段。
use std::collections::HashMap;
#[derive(Default)]
pub struct Node {
children: HashMap<char, Node>,
/// 这个节点是不是某个词的结尾
is_terminal: bool,
/// 存附加值(比如词频、文档 id)
value: Option<u64>,
}
#[derive(Default)]
pub struct Trie {
root: Node,
size: usize,
}插入:
impl Trie {
pub fn insert(&mut self, word: &str, value: u64) {
let mut node = &mut self.root;
for c in word.chars() {
node = node.children.entry(c).or_default();
}
if !node.is_terminal {
self.size += 1;
}
node.is_terminal = true;
node.value = Some(value);
}
}查找和前缀匹配:
/// 精确查找
pub fn get(&self, word: &str) -> Option<u64> {
let mut node = &self.root;
for c in word.chars() {
node = node.children.get(&c)?;
}
if node.is_terminal { node.value } else { None }
}
/// 前缀匹配:这个前缀存在吗
pub fn has_prefix(&self, prefix: &str) -> bool {
let mut node = &self.root;
for c in prefix.chars() {
match node.children.get(&c) {
Some(n) => node = n,
None => return false,
}
}
true
}自动补全还需要"找出所有以某前缀开头的词":
pub fn complete(&self, prefix: &str, limit: usize) -> Vec<(String, u64)> {
// 1. 先走到前缀对应的节点
let mut node = &self.root;
for c in prefix.chars() {
match node.children.get(&c) {
Some(n) => node = n,
None => return Vec::new(),
}
}
// 2. 从这个节点开始收集所有词
let mut out = Vec::new();
let mut buf = prefix.to_string();
Self::collect(node, &mut buf, &mut out, limit);
out
}
fn collect(node: &Node, buf: &mut String, out: &mut Vec<(String, u64)>, limit: usize) {
if out.len() >= limit {
return;
}
if node.is_terminal {
out.push((buf.clone(), node.value.unwrap_or(0)));
}
// 字典序输出,结果稳定
let mut keys: Vec<&char> = node.children.keys().collect();
keys.sort_unstable();
for c in keys {
buf.push(*c);
Self::collect(&node.children[c], buf, out, limit);
buf.pop();
}
}limit 参数不是可选的,是必需的。 输入一个 "a",可能匹配上十万个词。必须能提前终止。
朴素 Trie 的三个问题
上面的实现能跑,但有三个硬伤:
1. 每个节点一个 HashMap,内存开销巨大。 一个 HashMap 的空实例就有几十字节,而绝大多数节点只有一个子节点。
2. 指针追逐严重。 沿着字符串走,每一步都要解引用一次指针,缓存命中率极低。
3. 无法持久化 / 序列化。 一堆堆分配的 HashMap 很难高效写进文件再读出来。
改进方向很明确:把树拍扁成数组。
改进一:用固定数组换掉 HashMap(但只对 ASCII 可行)
如果字符集很小(比如只有 26 个小写字母),可以用定长数组:
pub struct AsciiNode {
children: [u32; 26], // 子节点下标,0 表示空
is_terminal: bool,
value: u64,
}查找变成一次数组索引:
fn index(c: char) -> Option<usize> {
let c = c.to_ascii_lowercase();
if c.is_ascii_lowercase() {
Some((c as u8 - b'a') as usize)
} else {
None
}
}性能提升是数量级的:数组索引是 O(1) 且缓存友好,HashMap 要做哈希再探测。
但代价是空间:每个节点 26 × 4 = 104 字节的指针数组,即使它只用一个子节点。对于有百万词条的词典,这意味着几十 MB 的纯浪费。
这就是 Trie 的核心矛盾:查找要快就得用数组(空间浪费),要省空间就得用哈希或链表(查找变慢)。
双数组 Trie 的价值,正是同时解决这两点:用数组实现 O(1) 查找,同时把空间浪费压到可接受。
双数组 Trie 的核心思想
双数组 Trie(Double-Array Trie,DAT)用两个平行数组表示整棵树:
base[i] : 转移的基准值
check[i]: 校验值,记录"谁是我的父节点"转移规则:
从节点 s 输入字符 c 后到达的节点是:
t = base[s] + c
这个转移合法的条件是:
check[t] == s展开看这个机制的精妙之处:
base[s] + c 让"同一节点的所有子节点"在数组里占据一段连续区间(因为 c 是连续的字符编码)。于是查找一次加法就够。
check[t] == s 用来确认"这个位置真的属于 s 的子节点",而不是别的节点碰巧也映射到这里。
pub struct DoubleArrayTrie {
base: Vec<i32>,
check: Vec<i32>,
/// 每个节点的附加值(只在终止节点上有意义)
value: Vec<u64>,
/// 是否终止节点
terminal: Vec<bool>,
/// 下一个可用位置
next_free: usize,
}为什么 check 是必需的
假设 base[1] = 10,那么节点 1 的子节点位于 10 + c 处。如果字符 c = 3(比如 'c'),子节点就在位置 13。
现在另一个节点 2 恰好也有 base[2] = 10。那么从节点 1 输入 'c' 和从节点 2 输入 'c' 都会到达位置 13——冲突了。
check[13] 记录了"位置 13 到底属于谁"。如果 check[13] == 1,从节点 2 出发的转移就是非法的。冲突被检测出来,而不是被错误地接受。
插入:为一个节点找"空闲的连续槽位"
这是 DAT 构建里最麻烦的部分。给某个节点的字符集找一段连续的空闲位置:
impl DoubleArrayTrie {
/// 为一组字符找一个 base,使得 base + c 全部空闲
fn find_base(&mut self, chars: &[u8]) -> usize {
let mut base = self.next_free;
loop {
base += 1;
if self.slot_available(base, chars) {
return base;
}
}
}
fn slot_available(&self, base: usize, chars: &[u8]) -> bool {
for &c in chars {
let pos = base + c as usize;
if pos >= self.check.len() {
continue; // 超出当前数组,可以扩容
}
// 已被占用
if self.check[pos] != -1 {
return false;
}
}
true
}
}"从 next_free 之后开始找,每次 +1"这个朴素策略是 DAT 性能瓶颈的来源。 它最坏会退化成 O(字符集大小 × 节点数)。
工业实现(比如 cedar、darts-clone)用各种技巧加速:
- 按字符集大小排序,先安排"子节点多"的(更可能找到连续区间)
- 用位图记录空闲位置,快速判断
- 记录"每个空闲段的长度",直接跳到足够长的段
双数组 Trie 的构建复杂度,是整个结构里最容易被低估的部分。 查询是 O(字符长度),但构建可能是 O(n²)。
插入的完整流程
pub fn insert(&mut self, word: &str, value: u64) {
let mut s = 0usize; // 从根开始(根固定在下标 0)
let chars: Vec<u8> = word.bytes().collect();
for (i, &c) in chars.iter().enumerate() {
let t = self.base[s] as usize + c as usize;
self.ensure_capacity(t + 1);
// 转移已存在
if self.check[t] == s as i32 {
s = t;
continue;
}
// 转移不存在:新节点
if self.check[t] == -1 {
// 位置 t 空闲,直接占用
self.check[t] = s as i32;
// 新节点的 base 先置 0,后面按需分配
self.base[t] = 0;
s = t;
} else {
// 位置 t 被别的节点占用(冲突),需要重新分配 s 的 base
let remaining = &chars[i..];
self.rebase(s, remaining);
let t = self.base[s] as usize + c as usize;
self.check[t] = s as i32;
s = t;
}
let _ = self.next_free;
}
self.terminal[s] = true;
self.value[s] = value;
}
/// 重新安排节点 s 的 base,让它所有子节点都落在空闲区
fn rebase(&mut self, s: usize, remaining: &[u8]) {
// 收集 s 现有子节点的字符集
let mut chars: Vec<u8> = Vec::new();
// ... 遍历 check 数组找出所有 check[t] == s 的 t,反推字符 ...
chars.extend_from_slice(remaining);
chars.sort_unstable();
chars.dedup();
let new_base = self.find_base(&chars);
// 把原有子节点搬到新位置(要递归处理整棵子树!)
for &c in &chars {
let old_pos = self.base[s] as usize + c as usize;
let new_pos = new_base + c as usize;
if old_pos < self.check.len() && self.check[old_pos] == s as i32 {
// 搬运子树:这里需要递归更新所有子孙
self.move_subtree(old_pos, new_pos);
}
}
self.base[s] = new_base as i32;
}注意 rebase 里的那个注释——搬运一个节点,需要递归搬运它的整棵子树,因为子节点的位置也依赖父节点的 base。这是 DAT 实现里最容易写错的地方。
查询:极致简单
相比之下,DAT 的查询只有几行:
pub fn get(&self, word: &str) -> Option<u64> {
let mut s = 0usize;
for c in word.bytes() {
// 越界 = 不存在
if self.base[s] < 0 {
return None;
}
let t = self.base[s] as usize + c as usize;
if t >= self.check.len() || self.check[t] != s as i32 {
return None; // check 不匹配 = 这条路不存在
}
s = t;
}
if self.terminal[s] {
Some(self.value[s])
} else {
None
}
}
pub fn has_prefix(&self, prefix: &str) -> bool {
let mut s = 0usize;
for c in prefix.bytes() {
let t = self.base[s] as usize + c as usize;
if t >= self.check.len() || self.check[t] != s as i32 {
return false;
}
s = t;
}
true
}没有哈希、没有指针、没有任何分支判断——只有两次数组访问和一次整数比较,全部在连续内存里。
这就是 DAT 相对链式 Trie 的性能优势来源:它把树结构完全线性化了,缓存友好度拉满。
自动补全:DAT 上的遍历
前缀匹配之后要列举所有词。DAT 上的遍历和一个关键优化:
pub fn complete(&self, prefix: &str, limit: usize) -> Vec<String> {
let Some(s) = self.walk(prefix) else {
return Vec::new();
};
let mut out = Vec::new();
let mut buf = prefix.as_bytes().to_vec();
// 记录子树里的最大值,用于"优先给出更重要的词"
self.collect(s, &mut buf, &mut out, limit);
out.into_iter().map(|b| String::from_utf8_lossy(&b).into_owned()).collect()
}
fn walk(&self, prefix: &str) -> Option<usize> {
let mut s = 0usize;
for c in prefix.bytes() {
let t = self.base[s] as usize + c as usize;
if t >= self.check.len() || self.check[t] != s as i32 {
return None;
}
s = t;
}
Some(s)
}
fn collect(&self, s: usize, buf: &mut Vec<u8>, out: &mut Vec<Vec<u8>>, limit: usize) {
if out.len() >= limit {
return;
}
if self.terminal[s] {
out.push(buf.clone());
}
for c in 0u8..=255 {
let t = self.base[s] as usize + c as usize;
if t >= self.check.len() {
break;
}
if self.check[t] == s as i32 {
buf.push(c);
self.collect(t, buf, out, limit);
buf.pop();
}
}
}按热度排序:给每个节点加一个"子树最大值"
上面的实现按字符序输出,但自动补全应该把更热门的词排在前面。
技巧是:在每个节点上缓存"整棵子树里最大的 value"。
/// 带优先级的补全:总是先展开"子树里有热门词"的分支
fn collect_top(&self, s: usize, buf: &mut Vec<u8>, out: &mut Vec<Vec<u8>>, limit: usize) {
if out.len() >= limit {
return;
}
if self.terminal[s] {
out.push(buf.clone());
}
// 收集所有子节点,按子树最大值降序
let mut children: Vec<(u8, usize, u64)> = (0u8..=255)
.filter_map(|c| {
let t = self.base[s] as usize + c as usize;
if t < self.check.len() && self.check[t] == s as i32 {
Some((c, t, self.subtree_max[t]))
} else {
None
}
})
.collect();
children.sort_unstable_by(|a, b| b.2.cmp(&a.2));
for (c, t, _) in children {
buf.push(c);
self.collect_top(t, buf, out, limit);
buf.pop();
}
}subtree_max 在构建结束后做一次后序遍历就能算出来。 有了它,补全就能"先给最热的分支",而不是按字典序从 'a' 开始扫。
这是自动补全里非常实用的一个优化:不需要收集全部候选再排序,而是在遍历时就按优先级展开。
给 Trie 节点加"子树聚合信息",是让它从"能查"变成"能排序"的关键一步。 同样的做法可以聚合"子树节点数""子树总词频"等。
什么时候该用 DAT,什么时候不该
| 场景 | 推荐 |
|---|---|
| 静态词典 + 大量前缀查询(自动补全、拼写检查) | DAT |
| 频繁动态插入删除 | 普通 Trie 或哈希 |
| 中文等大字符集 | DAT + 编码映射(先转成紧凑编码空间) |
| 需要持久化 / 内存映射 | DAT(天然就是数组!) |
DAT 最大的战略优势是:它就是两个整数数组。 这意味着可以
- 直接
mmap到内存,零解析成本启动 - 直接写进文件,不需要序列化
- 在只读场景下被多个进程共享
对于"词典固定、查询量巨大"的场景(输入法、拼写检查、自动补全),DAT 几乎是唯一正确的选择。
中文怎么办:编码压缩
DAT 的 base + c 依赖字符编码连续。Unicode 码点跨度很大(汉字在 0x4E00 起),直接用会导致数组稀疏、内存爆炸。
解法是把用到的字符重新编码成连续的 0..N:
pub struct CharCodec {
encode: std::collections::HashMap<char, u32>,
decode: Vec<char>,
}
impl CharCodec {
pub fn build(words: &[&str]) -> Self {
let mut chars: Vec<char> = words
.iter()
.flat_map(|w| w.chars())
.collect();
chars.sort_unstable();
chars.dedup();
let encode = chars.iter().enumerate().map(|(i, &c)| (c, i as u32)).collect();
Self { encode, decode: chars }
}
}这样字符空间就从"Unicode 全集"压缩到"实际用到的字符数"(一个中文字典大概几千到几万个字符),数组大小立刻可控。
结论
从链式 Trie 到双数组 Trie,优化的主线是同一条:
普通 Trie 用哈希表存子节点,直观但内存分散、查找慢;DAT 用 base/check 两个数组把树"拍平",查找变成两次数组访问,且天然可持久化。
代价是构建复杂度:DAT 的插入需要为每个节点的子节点找连续空闲槽位,冲突时还要搬运整棵子树。 所以它适合"一次性构建、长期只读"的场景。
理解了 base[s] + c 和 check[t] == s 这两条规则,你就掌握了 DAT 的全部核心——剩下的都是关于"怎么更快地找到空闲槽位"的工程技巧。