Double Array Trie：高效字典树的压缩与检索实现
Trie 树（前缀树、字典树）是字符串检索领域最经典的数据结构之一，广泛应用于中文分词、输入法联想、DNA 序列匹配等场景。然而，朴素 Trie 的空间开销极大——每个节点通常需要维护一个大小等于字符集的指针数组，在 Unicode 字符集下这一问题尤为突出。Double Array Trie（DAT）通过两个整型数组 BASE 和 CHECK 对 Trie 进行紧凑编码，在保留 O(m) 查询复杂度（m 为查询串长度）的前提下，将空间占用压缩到接近理论下限。本文从有限自动机的视角出发，系统剖析 DAT 的数据结构设计、构建算法、查询流程、动态更新策略及其工程应用。
朴素 Trie 的空间困境
Trie 树的核心思想是利用字符串的公共前缀来减少存储冗余。给定一组字符串集合，Trie 将每个字符串拆解为字符序列，从根节点出发，沿着字符边依次向下延伸，共享相同前缀的路径。这种结构天然支持前缀匹配和最长前缀查找，查询时间复杂度仅与查询串长度 m 相关，与字典规模 n 无关。
然而朴素实现存在严重的空间浪费问题。最常见的做法是为每个节点分配一个大小为 |Σ| 的数组（Σ 为字符集），数组的第 i 个位置存储字符 i 对应的子节点指针。对于 ASCII 字符集，|Σ| = 128；对于中文场景，常用汉字约 6700 个，若考虑 Unicode 全集则更大。一棵包含数万个词条的中文词典 Trie，节点数可能达到数十万，每个节点都分配一个 6700 大小的指针数组，空间开销将高达 GB 级别，而这些数组中绝大多数位置是空的——一个典型的中文 Trie 节点平均只有 2~5 个子节点。
另一种做法是使用 HashMap 或链表来存储子节点映射，虽然能节省空间，但引入了哈希计算或链表遍历的额外开销，在高频查询场景下性能不够理想。
这就是 Double Array Trie 要解决的核心问题：如何在保持 Trie 的查询效率的同时，将空间占用降低到可接受的水平。
从 Trie 到 DFA：有限自动机视角
理解 Double Array Trie 的关键在于将 Trie 树重新建模为一个确定有限自动机（Deterministic Finite Automaton，DFA）。
状态与变量的定义
在 DFA 的视角下，Trie 的每一个节点对应一个状态（State），每一条边对应一个输入变量（Input Symbol）。具体地：
- 状态集合 Q：Trie 中所有节点的集合。根节点为初始状态
s₀，所有标记为词尾的节点构成接受状态集F。 - 输入字母表 Σ：所有可能出现的字符构成的集合。每个字符被编码为一个正整数（变量编号），例如"啊"编为 1，"阿"编为 2，"胶"编为 5 等。
- 状态转移函数 δ：
δ(s, c) = t表示在状态 s 下，接收输入字符 c 后转移到状态 t。
状态转移的核心语义
以一个简单的中文词典为例，包含词条：啊、阿胶、阿根廷、阿拉伯、阿拉伯人、埃及。
从根节点出发，输入"阿"后进入"阿"节点，再输入"胶"进入"阿胶"节点。整个过程就是一系列状态转移的链式执行。DFA 的判定规则是：如果输入串消耗完毕后当前状态属于接受状态集 F，则该串被"接受"（即是词典中的合法词条）；否则拒绝。
这种建模方式的意义在于：DFA 是一个纯数学对象，其状态转移函数可以用任何满足语义约束的数据结构来实现。朴素 Trie 用指针数组实现 δ，而 Double Array Trie 用两个整型数组实现 δ——这正是 DAT 压缩空间的理论基础。
Double Array Trie 的数据结构
DAT 的核心数据结构极其简洁：仅由两个等长的整型数组 base[] 和 check[] 构成，整个 Trie 的拓扑结构和状态转移信息都被编码在这两个数组之中。
BASE 数组与 CHECK 数组的语义
设 Trie 中存在一条从状态 s 经字符 c 到达状态 t 的转移边（即 δ(s, c) = t），则 DAT 中的编码规则为：
base[s] + c = t
check[t] = s
其中：
s和t是状态在数组中的下标位置c是字符的编号（正整数）base[s]称为状态 s 的基地址（base value），它决定了 s 的所有子状态在数组中的分布起点check[t]记录状态 t 的父状态，用于验证状态转移的合法性
这组公式的含义可以直观理解为：状态 s 的所有子节点在数组中以 base[s] 为偏移量排列，子节点 t 的位置由 base[s] + c 确定，同时 check[t] 反向指回父节点 s 以确保不冲突。
词结尾标记
除了拓扑结构，DAT 还需要记录哪些状态是"接受状态"（即对应一个完整词条的结尾）。标记方式如下：
- 如果状态 i 是某个词的结尾节点：
- 若
base[i] == 0（该节点无子节点），则将base[i]设为-i - 若
base[i] != 0（该节点有子节点，即某个词是另一个词的前缀），则将base[i]设为-base[i]（取负值）
- 若
这样，通过检查 base[i] 是否为负数即可判定状态 i 是否为词的结尾。在查询时，使用 |base[i]| 取绝对值来恢复真正的基地址以继续转移。
结构示意
以词典 {啊, 阿胶, 阿根廷, 阿拉伯, 阿拉伯人, 埃及} 为例，假设变量编号如下：
| 字符 | 啊 | 阿 | 埃 | 根 | 胶 | 拉 | 及 | 廷 | 伯 | 人 |
|---|---|---|---|---|---|---|---|---|---|---|
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
构建完成后的双数组（简化示意）大致如下：
| 下标 i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| base[i] | 0 | -1 | 1 | 1 | 4 | -5 | -6 | 2 | -8 | -9 | 8 | -11 | 0 | 0 | 0 | 0 | 0 |
| check[i] | 0 | 0 | 0 | 0 | 2 | 2 | 2 | 3 | 4 | 6 | 9 | 10 | 0 | 0 | 0 | 0 | 0 |
在该表中，base[1] = -1 表示下标 1 对应的状态"啊"是一个完整词条且无子节点。base[6] = -6 表示"阿胶"既是完整词条，同时 |base[6]| = 6 还可以作为基地址继续向下转移（虽然在本例中"阿胶"无后续词）。
构建算法
DAT 的构建过程本质上是将 Trie 的树形结构"铺平"到一维数组中，核心挑战在于为每个父节点找到一个合适的 base 值，使得其所有子节点都能无冲突地映射到数组的空闲位置上。
层次遍历构建过程
构建过程采用层次遍历（BFS）策略，逐层处理 Trie 中的每一层节点。
Step 1：处理第一层（根节点的子节点）。
根节点的 base 值通常初始化为 0 或 1。将根的所有子节点按其变量编号直接放入数组。例如根有三个子节点"啊"(编号 1)、"阿"(编号 2)、"埃"(编号 3)，若 base[root] = 0，则它们分别放入位置 1、2、3，并设置对应的 check 值指向根节点。
Step 2：为有子节点的状态分配 base 值。
对于当前层中每一个拥有子节点的状态 s，需要找到一个正整数 k 作为 base[s] 的值，使得对于 s 的所有子节点变量编号 c₁, c₂, ..., cₙ，位置 k + c₁, k + c₂, ..., k + cₙ 在数组中全部为空（即 check[k + cᵢ] == 0）。
具体做法是从 k = 1 开始递增搜索，直到找到满足条件的 k 值。找到后：
- 设置
base[s] = k - 对每个子节点变量 cᵢ，设置
check[k + cᵢ] = s
Step 3：逐层重复。
将当前层所有已分配位置的子节点加入下一层待处理队列，重复 Step 2 直至所有层处理完毕。
Step 4：标记词结尾。
遍历数组，对所有属于词尾的状态 i，按前述规则将 base[i] 取负。
冲突解决：寻找可用偏移量
Step 2 中寻找 k 的过程是构建算法的性能瓶颈。最朴素的做法是线性扫描，从 1 开始逐一尝试。这种方式的时间复杂度在最坏情况下可达 O(n * |Σ|)，其中 n 为数组长度。
实际工程实现中有若干优化手段：
- 空位链表：维护一个空闲位置的链表，跳过已占用的位置，减少无效扫描
- 起始搜索位置优化：记录上一次成功分配的 k 值，下一次从该值附近开始搜索，利用局部性原理减少搜索范围
- 字符编号排序：将子节点按编号从小到大排序，利用最小编号快速排除不可能的 k 值
完整构建示例
以词典 {啊, 阿胶, 阿根廷, 阿拉伯, 阿拉伯人, 埃及} 为例，逐步演示构建过程。
初始化：base[root] = 0，root 位于下标 0。
第一层：根的子节点为"啊"(c=1)、"阿"(c=2)、"埃"(c=3)。
- k = 0（base[root] = 0）
- "啊" → 位置 0+1 = 1，check[1] = 0
- "阿" → 位置 0+2 = 2，check[2] = 0
- "埃" → 位置 0+3 = 3，check[3] = 0
第二层：处理"啊"、"阿"、"埃"的子节点。
"啊"无子节点，标记为词尾：base[1] = -1。
"阿"有子节点"根"(c=4)、"胶"(c=5)、"拉"(c=6)。需要找 k 使得位置 k+4、k+5、k+6 均为空。k=1 时，位置 5、6、7 均空闲，满足条件。
- base[2] = 1
- "阿根" → 位置 1+4 = 5，check[5] = 2（状态"阿"的下标）
- "阿胶" → 位置 1+5 = 6，check[6] = 2
- "阿拉" → 位置 1+6 = 7，check[7] = 2（注意此处是"阿拉"对应变量"拉"编号 6）
"埃"有子节点"及"(c=7)。需要找 k 使得位置 k+7 为空。k=1 时，位置 8 空闲。
- base[3] = 1
- "埃及" → 位置 1+7 = 8，check[8] = 3
第三层及后续：继续处理"阿根"、"阿胶"、"阿拉"、"埃及"等节点的子节点，按同样的规则分配 base 值和 check 值。
"阿胶"无子节点，标记词尾：base[6] = -6（若原本 base[6] 非零则取负）。
"阿根"有子节点"廷"(c=8)。找 k 使得 k+8 为空闲位置。
"阿拉"有子节点"伯"(c=9)。找 k 使得 k+9 为空闲位置。
以此类推，直到所有叶节点处理完毕，并对"阿根廷""阿拉伯""阿拉伯人""埃及"等词尾状态做标记。
查询算法
DAT 的查询过程与 DFA 的运行语义完全一致：从初始状态出发，逐字符消耗输入串，通过状态转移函数判断路径是否合法。
前缀匹配流程
给定查询串 w = c₁c₂...cₘ，查询过程如下：
- 初始化当前状态
s = root（下标 0） - 对于每个字符
cᵢ（i 从 1 到 m）：- 计算目标位置
t = |base[s]| + code(cᵢ) - 检查
check[t]是否等于 s - 若相等，则转移成功，令
s = t，继续处理下一个字符 - 若不等，则转移失败，查询串不存在于词典中
- 计算目标位置
- 所有字符处理完毕后，检查
base[s]是否为负数：- 若为负，则 s 是词尾状态，查询串是词典中的完整词条
- 若为正，则 s 不是词尾状态，查询串仅为某个词的前缀
查询示例
以查询"阿胶及"为例：
第一步：当前状态 s = 0（根），输入字符"阿"，编号 2。
- 计算 t = |base[0]| + 2 = 0 + 2 = 2
- check[2] == 0（根的下标）？是 → 转移到状态 2
第二步：当前状态 s = 2，输入字符"胶"，编号 5。
- 计算 t = |base[2]| + 5 = 1 + 5 = 6
- check[6] == 2？是 → 转移到状态 6
- 此时 base[6] 为负数，说明"阿胶"是一个完整词条
第三步：当前状态 s = 6，输入字符"及"，编号 7。
- 计算 t = |base[6]| + 7 = 6 + 7 = 13
- check[13] == 6？否（check[13] 不等于 6）→ 转移失败
- 结论："阿胶及"不是词典中的合法词条
查询失败的快速检测
DAT 的查询具有"fast-fail"特性。在任意一步中，只要 check[t] != s，即可立即终止查询并返回"不存在"。这意味着：
- 对于不存在的词条，查询通常在消耗少量字符后就能快速拒绝
- 查询时间复杂度严格为 O(m)，其中 m 为查询串长度
- 每一步仅涉及一次加法运算、一次数组访问和一次整数比较，Cache 友好且无分支预测负担
这种效率是 HashMap 实现难以比拟的——HashMap 在最坏情况下可能退化为 O(m * n) 的逐一比对，而且哈希计算本身也有开销。
动态更新
DAT 的一个显著弱点在于动态更新的复杂性。与 HashMap 或链表 Trie 的 O(1) 插入不同，DAT 的插入操作可能触发级联的位置重分配。
插入新词的冲突处理
当向已构建好的 DAT 中插入一个新词时，可能出现以下情况：新词的某个前缀已存在于 DAT 中，但在需要分叉的节点处，新子节点的目标位置已被其他状态占用。
例如，假设词典中已有"阿拉伯"和"阿拉伯人"。现在要插入"阿拉根"。在处理到"阿拉"节点时，需要添加子节点"根"(c=4)。计算目标位置 base[阿拉] + 4，若该位置已被占用，则发生冲突。
子树迁移策略
冲突解决的基本思路是子树迁移：将冲突节点的整个子树迁移到一个新的基地址位置。具体步骤为：
确定需要迁移的节点：比较冲突双方（当前节点的子节点集合 vs. 占用位置的节点的子节点集合），选择子节点较少的一方进行迁移，以减少迁移开销。
寻找新的 base 值：为待迁移的节点找到一个新的 k 值，使得其所有子节点（包括新增的）都能映射到空闲位置。
执行迁移：
- 将旧位置的子节点逐一复制到新位置
- 更新每个子节点的 check 值指向新的父节点位置
- 递归更新所有孙子节点的 check 值（因为它们的 check 指向的是父节点的旧位置）
- 清空旧位置
完成插入：冲突解除后，在正确位置插入新节点。
动态更新的性能开销
子树迁移的时间复杂度取决于被迁移子树的规模。在最坏情况下，一次插入可能触发一个大型子树的完整迁移，导致 O(n) 的时间开销。但在实际应用中，以下策略可以降低平均开销：
- 静态构建优先：如果词典是已知的，优先采用离线批量构建，避免逐词插入带来的冲突
- 预留空间：构建时适当增大数组长度，降低冲突概率
- 增量更新缓冲：将增量更新暂存于辅助数据结构（如 HashMap），达到阈值后与主 DAT 合并重建
在绝大多数工程场景中，DAT 被用作静态词典的存储结构，动态更新需求较少。因此，动态更新的高开销在实践中并不构成主要瓶颈。
空间效率分析
与朴素 Trie 的空间对比
空间效率是 DAT 最核心的优势。以下对比基于一个包含 30 万中文词条的词典：
| 结构 | 空间占用 | 查询复杂度 | 说明 |
|---|---|---|---|
| 朴素 Trie（数组实现） | ~10 GB | O(m) | 每节点分配 6700 大小的指针数组 |
| 朴素 Trie（HashMap 实现） | ~150 MB | O(m)（平均） | HashMap 有额外对象头、装载因子等开销 |
| Double Array Trie | ~8 MB | O(m) | 仅两个 int 数组，无指针、无对象头 |
DAT 的空间效率来源于两个方面：
共享寻址空间：不同父节点的子节点可以交错分布在同一段数组区域中，只要它们不发生冲突。这种"紧凑排列"使得数组的利用率远高于朴素 Trie 的稀疏数组。
零指针开销：DAT 仅使用整数运算定位子节点，不需要存储任何指针或引用。在 64 位系统上，一个指针占 8 字节，而 DAT 中定位一个子节点仅需一个 int 加法。
与 HashMap 的权衡
DAT 并非在所有场景下都优于 HashMap。两者的适用边界大致如下：
| 维度 | Double Array Trie | HashMap |
|---|---|---|
| 空间 | 极为紧凑 | 有对象头、链表/红黑树额外开销 |
| 查询速度 | O(m)，常数极小 | O(m)（平均），哈希计算有固定开销 |
| 前缀查询 | 天然支持 | 不支持，需额外结构 |
| 动态更新 | 代价高 | O(1) 均摊 |
| 构建成本 | 离线构建较慢 | 逐条插入即可 |
| 序列化/反序列化 | 极快（直接读写数组） | 需要逐条重建 |
结论是：当词典相对稳定、需要前缀匹配能力、对空间和查询延迟有严格要求时，DAT 是更优选择；当词典频繁变动或无前缀查询需求时，HashMap 更为实用。
工程应用
中文分词系统
DAT 在中文分词领域有着广泛而深入的应用。中文分词的核心任务之一是快速判断一个字符序列是否为词典中的合法词条，以及找到所有可能的分词方案。DAT 的前缀匹配能力使其天然适合这一任务。
HanLP 是目前主流的中文 NLP 工具包之一，其核心词典采用 DAT 作为底层存储结构。HanLP 在启动时将词典文件加载为 DAT，后续的分词、词性标注等操作均基于 DAT 进行高速检索。由于 DAT 可以直接序列化为字节数组写入文件，HanLP 的词典加载速度极快——30 万词条的词典加载通常在毫秒级完成。
Jieba 分词（Java 版本）在其词典查询模块中同样使用了 DAT。Jieba 的前缀词典在 DAG（有向无环图）构建阶段需要高频执行前缀查询，DAT 的 O(m) 查询保证了这一阶段的性能。
AC 自动机的底层存储
AC 自动机（Aho-Corasick Automaton）是多模式字符串匹配的经典算法，被广泛应用于敏感词过滤、入侵检测等场景。AC 自动机的第一步就是构建一棵 Trie 树，然后在其上添加失败指针（failure link）。
在高性能实现中，AC 自动机底层的 Trie 通常替换为 DAT，以获得更优的空间效率和缓存命中率。例如，在一个包含数十万敏感词的过滤系统中，使用 DAT 替代朴素 Trie 可以将内存占用从数百 MB 降至数十 MB，同时查询性能因更好的 cache locality 而提升 20%~50%。
输入法词库
输入法引擎需要根据用户的按键序列实时检索候选词，这一过程对延迟和空间都有极严格的要求——用户每敲一个键，引擎需要在毫秒内返回候选列表，而词库规模通常在百万级。DAT 的常数级别查询延迟和极低的内存占用使其成为输入法词库的理想存储结构。多数主流中文输入法引擎（如 Google 日文输入法开源实现 Mozc）在其词典模块中采用了 DAT 或其变体。
Darts-java 实现
Darts-java 是 DAT 的一个经典 Java 实现，也是 HanLP 等工具的底层依赖之一。其核心代码结构清晰，值得参考：
public class DoubleArrayTrie {
private int[] base; // BASE 数组
private int[] check; // CHECK 数组
/**
* 精确匹配查询
* @param key 查询字符串
* @return 匹配结果（词条编号），-1 表示未找到
*/
public int exactMatchSearch(String key) {
int result = -1;
int b = base[0]; // 从根节点出发
int p;
for (int i = 0; i < key.length(); i++) {
p = b + (int)(key.charAt(i)) + 1;
if (b == check[p]) {
b = base[p];
} else {
return result; // 转移失败，快速返回
}
}
p = b; // 检查是否为完整词条
int n = base[p];
if (b == check[p] && n < 0) {
result = -n - 1;
}
return result;
}
}
此外，Darts-java 还提供了 commonPrefixSearch 方法，用于查找查询串的所有前缀匹配结果，这是中文分词中构建词图（word lattice）的关键操作。
在实际工程中，DAT 通常与其他技术组合使用：与 AC 自动机结合实现多模式匹配，与维特比算法结合实现最优分词路径选择，与概率语言模型结合实现统计分词。DAT 扮演的角色始终是最底层的高效词典检索引擎——不起眼但不可或缺。