双数组 Trie(Double-Array Trie)

双数组 Trie(Double-Array Trie,简称 DAT)是一种对字典树进行紧凑存储的数据结构,由日本学者青江順一(Jun-ichi Aoe)于 1989 年提出。它用 base 和 check 两个整型数组来编码整棵 Trie 的状态转移,在保持 O(串长) 检索速度的同时,大幅压缩了传统 Trie 的空间。

概述

传统 Trie 每个节点都要为字符集里的每个字符预留子节点指针,空间浪费严重;而链式或哈希实现虽省空间却牺牲了访问速度。双数组 Trie 通过精巧的下标运算,把树的父子关系编码进两个平行数组,既紧凑又能保持常数级的单步跳转。

核心原理

结构维护两个数组:base 数组记录每个状态的基址,check 数组用于校验父子关系是否合法。从状态 s 沿字符 c 转移到子状态 t 时,下标 t 由 base[s] 加上 c 的编码算出,并要求 check[t] 恰好等于 s,才认为该转移有效。

• 状态转移:通过下标算术在 O(1) 时间内完成,匹配一个长度为 m 的串仅需 O(m) 时间。
• 空间紧凑:所有状态共享两个数组,避免了每节点存指针的开销。
• 构建代价:插入新词可能引发状态冲突,需要为兄弟状态寻找新的 base 值并搬迁,因此动态更新较慢,通常适合一次构建、多次查询。

应用场景

双数组 Trie 是中文分词、输入法、敏感词过滤等词典匹配任务的常用底层结构。许多知名的中文分词工具和 AC 自动机实现都采用它作为词典存储,以在内存受限的环境下实现高速多模式匹配。

常见问题

问:双数组 Trie 为什么比普通 Trie 省空间?答:普通 Trie 每个节点要为整个字符集预留槽位,大量空指针浪费空间;双数组 Trie 让不同状态共享底层数组并通过 check 校验,消除了这种冗余。

问:它适合频繁增删词典吗?答:不太适合。插入可能触发状态搬迁,动态更新代价较高,因此它更适用于词典相对静态、构建一次后大量查询的场景。