返回文章列表

用 Rust 从零实现前缀树:从普通 Trie 到双数组 Trie

664 字·6 分钟阅读
Rust从零造轮子数据结构

搜索框里输入"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 的全部核心——剩下的都是关于"怎么更快地找到空闲槽位"的工程技巧。