Double Array Trie：高效字典树的压缩与检索实现

目录

词典查询常需要两种能力：判断一个词是否存在，以及找到查询文本的所有词典前缀。Trie 很适合这类任务，但如果每个节点都按完整字符集分配子指针，就会浪费大量空间。

Double Array Trie（DAT）用数组位置编码状态转移，减少指针和小对象的开销。它的价值在于保留按字符推进的查询方式；实际空间取决于字符编码、空槽比例和附加数据，不能仅凭“双数组”就断言达到理论下限。

从 Trie 到状态转移

以词典 啊、阿胶、阿根廷、阿拉伯、阿拉伯人、埃及 为例，每个前缀对应一个状态，字符对应转移边，完整词条的末尾状态具有终止标记。

查询“阿拉伯人”时，依次经过“阿”“阿拉”“阿拉伯”“阿拉伯人”。其中“阿拉伯”已经是完整词条，但仍可继续转移，因此“是否词尾”与“是否有子节点”必须分开表达。

本文统一采用以下约定：

  • 根状态下标为 0
  • 字符编码为正整数
  • base[s] 表示状态 s 的转移偏移
  • check[t] 存储目标状态 t 的父状态下标；空槽为 -1
  • 词尾使用独立的 terminal[] 标记

拓扑由 base/check 两个数组表达，terminal 是额外的词尾元数据。这种教学表示便于核对；实际实现也可以使用终止字符、位标记或其他编码，但不能混用不同约定。

一次合法转移满足：

t = base[s] + code(c)
0 <= t < check.length
check[t] == s

空槽不能也用 0 表示，否则查询根节点时，未使用的位置会被误认为根的孩子。

用一张可核对的表表示整棵树

先为例子中的字符编号：

字符 啊 阿 埃 根 胶 拉 及 廷 伯 人
编号 1 2 3 4 5 6 7 8 9 10

以下是一种合法布局，并不是唯一布局：

下标 状态 base check terminal
0 根 0 -1 false
1 啊 0 0 true
2 阿 1 0 false
3 埃 1 0 false
4 空槽 0 -1 false
5 阿根 1 2 false
6 阿胶 0 2 true
7 阿拉 1 2 false
8 埃及 0 3 true
9 阿根廷 0 5 true
10 阿拉伯 1 7 true
11 阿拉伯人 0 10 true

例如，从“阿”到“胶”：base[2] + 5 = 6，且 check[6] == 2，所以转移成立。从“阿拉伯”到“人”：base[10] + 10 = 11，且 check[11] == 10，同样成立。

“阿胶及”会失败：到达下标 6 后，候选位置为 base[6] + 7 = 7，但 check[7] == 2，不是当前状态 6。位置存在，不等于这条边存在。

构建时寻找无冲突偏移

可以先建立普通 Trie，再按广度或深度遍历分配数组位置。处理状态 s 时，收集它的所有孩子字符编码，寻找一个偏移 k，使每个 k + code(c) 都是未占用槽位，并保证不会占用根槽。

找到后，设置 base[s] = k，再填入各孩子的 check 和词尾标记。数组不足时扩容，并将新增 check 槽初始化为 -1。

在例子中：

  1. 根使用偏移 0，将“啊”“阿”“埃”放在 1、2、3
  2. “阿”使用偏移 1，将“根”“胶”“拉”放在 5、6、7
  3. “埃”使用偏移 1，将“及”放在 8
  4. “阿根”“阿拉”“阿拉伯”分别使用偏移 1，将后继放在 9、10、11

不同父状态可以共享相同 base 值，只要所需的目标槽位不冲突。check 负责区分这些交错分布的孩子。

构建开销主要来自偏移搜索与扩容，不能只根据字符集大小给出统一的最坏复杂度。空闲槽索引、孩子排序、紧凑字符编码和搜索起点策略，可以减少无效尝试；是否有效应使用目标词典测量。

查询实现与词尾语义

下面是与表格完全一致的 Java 查询示例。数组是固定词典的演示数据，不包含通用构建器；字符映射也仅覆盖本文词典。

public final class ExampleDat {
    private static final int[] BASE =
        {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0};
    private static final int[] CHECK =
        {-1, 0, 0, 0, -1, 2, 2, 2, 3, 5, 7, 10};
    private static final boolean[] TERMINAL =
        {false, true, false, false, false, false,
         true, false, true, true, true, true};

    private static int code(char c) {
        int index = "啊阿埃根胶拉及廷伯人".indexOf(c);
        return index < 0 ? -1 : index + 1;
    }

    public static boolean contains(String word) {
        int state = 0;
        for (int i = 0; i < word.length(); i++) {
            int symbol = code(word.charAt(i));
            if (symbol < 0) return false;
            long next = (long) BASE[state] + symbol;
            if (next < 0 || next >= CHECK.length) return false;
            int target = (int) next;
            if (CHECK[target] != state) return false;
            state = target;
        }
        return TERMINAL[state];
    }
}

精确匹配需要在全部字符消耗后检查 terminal。查找查询串的所有词典前缀时，则在每次转移后检查 terminal，并记录对应的结束位置。“阿拉伯人”因此可以产生“阿拉伯”和“阿拉伯人”两个匹配。

查询最多进行 m 次转移，时间为 O(m)，m 是编码后的输入长度。真实 Unicode 实现需要明确按 UTF-16 代码单元、Unicode 码点还是字节编码；不能把教学示例的 char 映射直接当作完整 Unicode 方案。

每步是少量数组访问和条件判断，布局也较紧凑，但仍有缓存失效与分支预测开销。DAT 的优势需要与具体的稀疏 Trie、哈希表或压缩 Trie 实现比较。

动态更新为什么更复杂

向某个状态增加孩子时，新目标位置可能已被另一条边占用。这时可以为一组孩子重新选择偏移，移动这些孩子，并修正它们的孩子记录中指向旧父位置的 check。

这通常不要求无条件复制整棵后代子树：如果被移动节点的 base 保留，它的孩子可以仍在原位置，只更新父状态引用。具体实现还要处理词尾数据、空槽管理，以及迁移和并发读取之间的协调。

因此，插入成本不仅包含查找长度，还可能包含偏移搜索与节点迁移。普通 Trie 插入一个长度为 m 的词也不是整体 O(1)，通常需要按字符推进；只有找到前驱后的某次局部链接修改才可能是常数时间。

对于读多写少的词典，可以离线构建新数组，再原子替换读取版本。更新较频繁时，也可以保留增量结构，按查询语义合并结果，并定期重建。

空间与工程选型

设 base/check 都使用 32 位整数，分配容量为 C，这两个数组的数据区约为 8C 字节；另计数组对象、词尾位图、词条值与字符映射。C 与实际状态数的比值，反映了空槽开销。

需求 DAT 的特点 需要比较的对象
稳定词典、频繁前缀查询 按字符转移，布局紧凑 压缩 Trie、其他静态词典结构
频繁局部更新 可能触发迁移或重建 稀疏 Trie、增量结构
只做完整键查找 可以使用，但前缀能力未必有价值 哈希表
多模式文本匹配 可作为自动机转移的存储方式 转移表示、失败链接和输出结构的总成本

DAT 可以服务于词典分词、输入候选和模式匹配，但整个系统的表现还取决于上层算法与数据。不能将某个词库的内存或加载时间写成所有实现都能达到的结果。

Darts-java 是可参考的开源实现。阅读其代码时，应先核对状态、check 与终止状态的编码约定；本文的父下标和独立 terminal 表示用于解释机制，并非该项目源码的逐行复刻。

DAT 最值得借鉴的设计，是将树的转移关系编码进共享数组空间。理解寻址公式、空槽与词尾三个约定，再讨论布局和性能，才能把“看起来紧凑”变成可核对、可使用的结构。

评论