字典树(Trie)是以共享前缀组织字符串集合的多叉树,它把「比较」的单位从整个字符串分解为单个字符,因而支持前缀查询、字典序枚举与最长前缀匹配这类散列表无法提供的操作。字符串作为键的不可分解性、字符集对分支因子的影响,其背景见 数组与链表 与 抽象数据类型(ADT);与散列表在精确查找上的分工见 散列表;树形结构的基本术语、递归到迭代的转换与退化问题的讨论见 二叉树与二叉搜索树 与 平衡树:AVL 与红黑树;字典树与磁盘索引的分工见 B 树与 B+ 树;复杂度记号的口径与实测的必要性见 复杂度与算法分析 与 JMH 微基准测试。

一、起源:字符串集合的查找需求

1.1 从精确匹配到前缀匹配

以字符串为键的集合有三类常见查询,难度依次上升。

查询 形式 语义
精确匹配 判断某个字符串是否在集合中 成员判断
前缀查询 返回集合中以某字符串开头的全部元素 范围查询在字符串上的对应物
最相近查询 返回与给定串共享最长前缀的元素,或返回编辑距离最近者 最长前缀匹配、模糊匹配

这三类查询在文本处理中同等常见:判断一个词是否收录属于第一类,输入法联想与搜索框提示属于第二类,IP 路由表与词根替换属于第三类。因此字符串集合这一抽象数据类型的能力要求,并不止于「是否存在」。

1.2 散列表能判等,不能做前缀匹配

散列表把整个键映射为一个地址,见 散列表:

address = H(key)

H("app")  与  H("apple")  之间没有任何可推导的关系

散列函数的构造要求之一是「键的微小变化引起散列值的大幅变化」,即雪崩效应。这条要求对精确匹配是有利的——它保证相似但不相同的键落入不同的桶;但对前缀查询恰好是障碍——前缀查询需要的正是「相似键落在相近位置」这一性质。

在散列表上实现前缀查询,只有两条路:

  1. 枚举前缀。对查询串的每个前缀分别做一次精确查找,代价为 O(m) 次散列计算(m 为串长),但得到的信息只有「该前缀是否恰为一个完整的键」,无法回答「有多少个键以它为前缀」,也无法枚举这些键。
  2. 全表扫描。遍历全部 n 个键,逐一判断前缀,代价 O(nm)。

数据库索引中的对应现象是同一个原因:B+ 树上的 LIKE '前缀%' 可以利用有序性定位扫描区间,而 LIKE '%关键字%' 因为通配符出现在最左侧、前缀不确定而退化为全扫描,具体的对照与替代方案见 mysql: 索引与执行计划 的模糊匹配一节。

1.3 共享前缀:改变比较的单位

观察一批字符串:

app, apple, application, apply, banana, band

共享前缀的分布:
    app  ├─ le
         ├─ lication
         └─ ly
    ban  ├─ ana
         └─ d

逐字符看,app、apple、application、apply 四个串在前 3 个字符上完全重复。把这些重复字符只保存一份,就得到一个前缀的公共结构:

        root
         │ a
         │ p
         │ p
        (n)
        / | \
       l  l  l
       e  i  y
          │
          c a t i o n

由此得到两条收益,它们分别对应空间与时间:

  • 空间的收益:公共前缀只存一份,存储量与「不同前缀的个数」相关,而不是「字符串个数 × 平均长度」。若 10 万个词共享少数几个长前缀(如按 ISBN 前缀、手机号段、行政区划编码组织的词表),节省的量级很显著。
  • 时间的收益:一次查询沿字符逐层下降,每一步把候选集合缩小到「具有该前缀」的那一部分,前缀越长,剩余分支越少。查询的代价与串长相关,与集合规模无关,并且「查询一个前缀」与「查询恰好等于该前缀的键」共享同一段下降路径。

需要注意确切的口径:字典树改善的是前缀信息的可获取性,而不是把单次精确查找降到比散列表更快。精确查找时两者都要扫描整个键(散列函数同样要读完整个字符串),复杂度都是 O(m) 量级;区别在于字典树的最坏代价是确定的 O(m),不依赖散列函数的分布,也不存在冲突处理,而散列表的期望 O(1) 是以「散列均匀」为前提的。

1.4 字符串索引与键值索引的差异

把字符串作为键,与把整数或其他定长值作为键,有四处结构性差异,它们决定了字典树的形态。

维度 键值索引(整数、UUID 等) 字符串索引
键的可分解性 键是原子,比较是一次操作 键是字符序列,可分解为前缀,比较可提前结束
比较代价 一条指令 可能与键长成正比的内存扫描
天然次序 数值大小 字典序(由字符集编码决定)
分支依据 整个键的比较结果(三分支) 单个字符的取值(字符集大小个分支)

第三点与第四点合起来给出了字典树的基本形态:以字符为分支依据、以字典序为输出次序的多叉树。分支数等于字符集大小,这一点直接决定了节点中子节点容器的选择(见第二节第 3 小节),也决定了「小字符集(小写字母 26)上的字典树」与「大字符集(Unicode)上的字典树」在内存上的巨大差别。

关于字符串的编码方式(字符与字节的对应、变长编码对「字符」这一单位的干扰)见 Java 时间与字符编码。

二、原理

1. 结构定义

1.1 节点、边与字符

字典树的定义可以精确表述为:

  • 每个节点对应一个前缀:从根到该节点的路径上所有边上的字符依次相连,构成该节点所代表的前缀;
  • 每条边上标记一个字符,从父节点到子节点的边表示「在该前缀后追加一个字符」;
  • 根节点对应空字符串,它不代表任何具体的词,只作为所有字符串的公共起点;
  • 每个节点的所有子节点的边标记互不相同,这是树形结构本身的要求(同一个前缀后追加同一个字符,只会得到一个前缀)。
插入 app, apple, apply, banana 后的结构(isEnd 标记以 * 表示)

            (root)
           /      \
          a        b
          │        │
          p        a
          │        │
          p        n
        (n)*       │
        /   \      a
       l     l     │
       e*    y*    n
                  /
                 a*

由定义直接得到三条性质:

1. 深度为 k 的节点代表长度为 k 的前缀,第 k 层的所有节点互不相同
2. 树的高度 = 集合中最长字符串的长度(以边数计)
3. 对树做先序遍历,按字符升序访问子节点,得到的词序列即为字典序

第 3 条是字典树区别于散列表的关键能力之一:字典序不需要额外的排序操作,它由结构本身给出,与二叉搜索树的中序遍历给出递增序列是同一原理。

1.2 根节点与终止标记

仅靠「路径上的字符」无法区分「词」与「词的前缀」。在上图中,app 与 apple 共用路径 root→a→p→p,若只保存字符,节点 (n) 既表示词 app,也表示词 apple 与 apply 的中间前缀。

解决办法是在节点上增加终止标记(常命名为 isEnd、end、terminal),表示「从根到该节点的路径构成集合中的一个完整字符串」:

isEnd(node) = true   →  该节点对应的前缀是一个完整的键
isEnd(node) = false  →  该节点只是某些键的中间前缀

三类操作对终止标记的处理因此不同:

操作 走完路径后是否检查 isEnd 语义
精确查找 必须检查 路径存在但不带标记,说明该串只是别的键的前缀,不算命中
前缀查询 不检查 只要路径存在,就存在以它为前缀的键
枚举某前缀下的全部键 不检查路径存在性,但对收集到的节点检查 只有带标记的节点才是词

允许重复键时,把布尔标记换成计数(count 或 pass),既能判重,又能承载词频统计(见第三节第 4.3 小节)。

另有一类常见的统计需求:查询「有多少个键以某前缀开头」。这需要在每个节点上维护经过该节点的键数(记作 pass),插入时沿途每个节点加一,删除时减一,查询时读前缀末端节点的计数即可,不需要遍历子树。

1.3 与其他树形结构的定位差异

字典树在多叉树谱系中的位置,可以由「分支依据」与「节点的语义」两项确定。

结构 分支依据 节点语义 主要用途
二叉树 / 二叉搜索树 键与节点键的比较(三分支) 一个键 有序映射、范围查询
B 树 / B+ 树 页内多个分隔键的比较 一页多个键 磁盘索引,降低树高
字典树 键的下一个字符 一个前缀 前缀查询、字典序、多模式匹配
堆 父子的大小关系 一个元素 取最值

两点值得强调。其一,B+ 树与字典树在「前缀匹配」上的能力是同源的:两者都利用「有序 + 逐段比较」把范围收缩到一段连续区间,区别是 B+ 树按整个键排序、字典树按字符分层,因此 B+ 树需要「最左前缀」,而字典树天然只在前缀方向上有效。其二,字典树的节点不分层存储、节点大小不固定,这与 B+ 树为磁盘按页组织的方式相反,因此字典树是内存结构,落地到磁盘需要专门的组织方式(见第三节第 4.6 小节)。

2. 基本操作

2.1 插入

插入的过程是「沿字符下降,缺则建」:

insert(word):
    node = root
    for c in word:                       // 逐个字符
        if node.children[c] == null:
            node.children[c] = new Node()
        node = node.children[c]
    node.isEnd = true                    // 末尾打终止标记

复杂度为 O(m)(m 为串长),与集合中已有的字符串个数无关。这一性质在批量导入场景中很重要:把 n 个平均长度为 m 的字符串插入字典树的代价是 O(nm),即与输入总字符数成正比,不存在排序或重平衡的开销。

插入只增加节点,不修改已有节点的相对关系。这一性质使字典树的构建过程易于并行化,也使「插入顺序无关」成立——给定的字符串集合对应的字典树形状唯一(子节点的存储顺序除外,它只影响遍历时的输出次序)。

2.2 查找与前缀匹配

两种操作共享同一段下降逻辑,只在终点判断上不同:

search(word):                            // 精确匹配
    node = root
    for c in word:
        node = node.children[c]
        if node == null: return false     // 路径中断,键不存在
    return node.isEnd                     // 路径存在还须是词

startsWith(prefix):                      // 前缀查询
    node = root
    for c in prefix:
        node = node.children[c]
        if node == null: return false
    return true                           // 只要求路径存在

两个失败的时机需要区分:下降过程中 children[c] 为空,说明连前缀都不存在;下降走完但 isEnd 为假,说明该串是别的键的前缀而非一个独立的键。把后者误判为命中,是字典树实现中最常见的语义缺陷(见第三节第 5.2 小节)。

复杂度口径需要写明「与什么有关」:

插入、精确查找、前缀查询     O(m)          m 为查询串长度,与集合规模 n 无关
枚举某前缀下的全部键         O(m + k)      k 为结果个数(含遍历子树的开销)
查询「以某前缀开头的键数」   O(m)          由节点上的计数直接给出
全量字典序输出               O(N)          N 为全部键的字符总数

与二叉搜索树的 O(log n)、散列表的期望 O(1) 相比,字典树的复杂度不随集合规模变化,而是随键长变化。键长通常是对数级的(n 个随机字符串的区分长度约为 log_σ n),因此字典树的实际性能与散列表同量级,但没有冲突处理的成本,也没有最坏 O(n) 的风险。

2.3 通配符匹配与模糊匹配

前缀查询之所以是 O(m),原因是每一步的下一步都是唯一的。一旦引入通配符,下降路径不再唯一,必须转为递归或回溯。

支持 . 匹配任意单字符、* 匹配任意长度(含空)的匹配:

match(node, pattern, i):
    if i == len(pattern):
        return node.isEnd                 // 模式耗尽,必须落在词节点上
    c = pattern[i]
    if c == '.':
        for each child of node:           // 枚举全部分支
            if match(child, pattern, i + 1): return true
        return false
    if c == '*':
        for each child of node:           // * 消耗 0 个或多个字符
            if match(child, pattern, i) or match(child, pattern, i + 1): return true
        return true                       // 也可在此处终止
    child = node.children[c]
    return child != null && match(child, pattern, i + 1)

复杂度不再是 O(m):每个下划线或星号都可能引入分支,最坏情况需要访问整棵子树,代价与节点数同阶。因此通配符查询的代价由「通配符的个数与位置」决定,而不是由模式长度单一决定。

工程上更常用的是把模糊匹配控制在小范围内:

模糊形式 处理方式 代价
单字符通配(.、_) 在对应位置枚举子节点 分支数 = 字符集大小
后缀通配(* 在末尾) 枚举子树并收集词 O(子树规模)
编辑距离容错(允许 k 次增删改) 递归时同时携带编辑距离预算,超过即剪枝 O(m × 分支数^k) 量级,k 小时可用
拼音或前缀归一化 预处理后再查字典树 需要维护归一化后的键

编辑距离容错的一处实用剪枝:当剩余可编辑距离不足以覆盖「当前节点之后还需匹配的字符数与模式剩余长度之差」时立即返回,这条下界剪枝把可用范围从「k 极小」放宽到「k 取 1 至 2」。

3. 空间分析

3.1 节点数与字符串数量的关系

字典树的节点数由互不相同的前缀个数决定,与字符串个数不是同一个量:

节点总数上界:Σ|s_i| + 1        (所有串无公共前缀时,每个字符一个新节点,另加根)
节点总数下界:max|s_i| + 1      (所有串构成一条链,即集合中每个串都是最长串的前缀)
非根节点数 = 边数 = 节点总数 − 1

上界与下界之间的差距,就是共享前缀带来的节省。以手机号段或行政区划编码这类「长公共前缀」的集合为例,共享率可以非常高;而随机字符串(哈希值、UUID)几乎没有公共前缀,节点数接近总字符数。

字节点数的实测意义在于:它决定了内存的下界,任何子节点表示方式都至少要容纳这么多节点。

3.2 定长指针数组表示的空间浪费

最直观的子节点容器是按字符集大小开一个定长指针数组:

// 假设字符集为 26 个小写字母
class Node {
    Node[] children = new Node[26];      // 26 个引用
    boolean isEnd;
}

// 或者用整数下标记账,同一写法
int[] children = new int[26];            // 26 个 int,0 表示无子节点

访问是 O(1) 的下标运算,缓存局部性最好,实现也最短。代价是每个节点都要为字符集的全部取值预留槽位,与它实际有几个子节点无关。

节点数 E,字符集大小 σ,每槽位 P 字节:
    子节点表空间 = E × σ × P

σ = 26,P = 4(int 下标):每节点 104 字节
σ = 128(ASCII)         :每节点 512 字节
σ = 65536(Unicode BMP) :每节点 256 KB —— 完全不可用

这解释了字典树的字符集敏感性:同一份算法,在小写字母表上可用,在 Unicode 上不可用。实际工程中的三条处理方式:

  1. 按实际字符集收窄。若能确定键只含小写字母、数字或 ASCII,直接按该字符集定长开表,是最快的方案;需要在预处理阶段做归一化(大小写转换、全半角转换)。
  2. 改用映射或有序数组。以实际分支数为空间单位,代价是每次访问多一次散列或二分。
  3. 改用压缩表示或双数组。见第 4 小节。

3.3 子节点表示的多种方式

表示 定位代价 空间(E 个节点、每个平均 b 个分支) 插入代价 适用场景
定长指针数组 O(1) 下标 E × σ × P O(1) 字符集小且固定(小写字母、数字、ASCII);节点访问最频繁
哈希表(HashMap) 期望 O(1) E × (节点开销 + 表开销) 期望 O(1),可能扩容 字符集大或实际分支稀疏;实现简单,指针追逐与装箱带来常数开销
有序数组 / 跳表 O(log b) 与 b 成正比 有序数组 O(b) 搬移 静态或分支少;需要按字符有序遍历时天然支持
兄弟链表(左孩子右兄弟) O(b) 每节点固定 2 个指针 O(1) 内存极度受限、分支很少;定位退化为线性
双数组(base + check) O(1) 两次数组访问 与状态数同阶的整型数组 构造期需要寻找空闲基址 静态词典、需要紧凑内存与高缓存命中

选择依据可以归纳为三条:

  • 访问频度与分支稀疏度。分支稀疏(b 远小于 σ)时定长数组浪费严重,映射或有序数组更合适;分支稠密时定长数组的空间浪费被摊薄,O(1) 定位的收益占优。
  • 是否需要在遍历时按字符有序。补全、字典序输出要求子节点可按字符升序枚举,有序数组与定长数组天然满足,哈希表需要额外排序。
  • 是否允许在构造期付出额外代价。双数组把构造复杂度换成运行期的紧凑与缓存友好,适合「构建一次、查询很多次」的静态词典;频繁增删的场景不适合。

4. 压缩与优化

4.1 压缩字典树与基树

观察原始字典树的空间浪费来源:只有单个子节点的节点会形成长链。application 一词在 app 之后会依次创建 l→i→c→a→t→i→o→n 八个只有唯一子节点的节点,其中间状态都不是词,只是为了记录字符。

压缩字典树(compressed trie) 的做法是:把单分支路径合并为一条边,边上的标记不再是单个字符,而是一个字符串片段。

未压缩:                         压缩后:
    (p)*                             (p)*
     │l                               │
     │i                             "lication"
     │c                               │
     │a                               │
     │t                               │
     │i                               │
     │o                               │
     │n                               │
    (n)*                             (n)*

两条结构性结论:

压缩字典树的内部节点数 ≤ 词数 n(每个节点至少是两个词的分叉点,或是一个词的终点)
未压缩字典树的节点数 ≤ 总字符数

节点数从 O(总字符数) 降到 O(词数),这是数量级的改善。代价出现在操作上:

  • 边的比较跨越多个字符,一次转移可能需要在边上比对若干字符(可以用哈希或首字符索引加速);
  • 插入可能触发边分裂:新词在某条边的中间位置分叉时,需要把该边拆成两条并新增一个分叉节点;
  • 删除可能触发边合并:删除后若某节点只剩一个子节点,需要把它的边与子节点的边拼接回去;
  • 实现复杂度明显高于原始字典树,这是「以实现换空间」的典型取舍。

压缩字典树在 IP 路由中被称为基数树(radix tree),在文本处理中也被称为 Patricia trie(当「压缩到每个内部节点都至少有两个分支」时)。Linux 内核的路由表、多数 Web 框架的路由前缀匹配都使用这一结构(见第三节第 4.4 与 4.5 小节)。

4.2 三叉字典树

三叉字典树(ternary search trie,TST)换一个思路解决字符集问题:把「按字符取值分叉」改为「按字符比较分叉」,每个节点只保存一个字符与三个指针(小于、等于、大于),于是字典树的每个节点退化为一个二叉搜索树的节点。

节点结构:char c; TST left, mid, right; boolean isEnd;
         left  : 本位置字符小于 c 的分支
         mid   : 本位置字符等于 c,进入下一位置(相当于普通字典树的一步下降)
         right : 本位置字符大于 c 的分支

查找 "bay":
    根节点字符 b:相等 → 走 mid,进入位置 2
    节点字符 a:相等 → 走 mid,进入位置 3
    节点字符 y:相等 → 走 mid,进入位置 4(终止位置),检查 isEnd

三点性质:

  1. 空间与字符集大小无关,每个节点固定三个指针,因而不存在 Unicode 上的爆炸问题;
  2. 查找代价为 O(log σ + m),其中 O(log σ) 是每一层在兄弟间按字符比较的代价(期望情形;树退化时更差);
  3. 有序性天然保持,中序遍历给出字典序,因为它本身是搜索树。

三叉字典树在字符集大而分支稀疏的场合(如混合编码的词表)比定长数组省内存,比哈希表省指针分配,代价是每层多出的比较与更深的树高。

4.3 双数组字典树

双数组字典树(Double-Array Trie,DAT) 用两个整型数组表示整棵树,把指针运算换成数组下标运算:

base[]  基址数组
check[] 校验数组

转移关系:从状态 s 读入字符 c 后,若
        t = base[s] + c
        check[t] == s
    则转移到状态 t,否则转移失败

终止标记与状态本身一同记录(如另用一个数组或状态偏移表示)

要点与取舍:

  • 空间紧凑。整棵树占用两个整型数组,没有对象头、没有引用字段;状态与转移的对应关系由算术给出。
  • 缓存友好。一次转移是两次数组访问,且数组连续分配,命中率远高于遍历节点对象。
  • 构造代价高。为每个状态寻找一个「其所有子字符对应的槽位都空闲」的基址是一个装箱问题,需要遍历空闲槽位,构造时间可能显著高于原树;常用策略是按分支数从多到少地分配状态,减少冲突。
  • 静态性强。数组一旦构造完成,插入或删除会引起基址调整(可能牵动大量状态),因此适合「词典固定、查询频繁」的场景,如分词词典、敏感词库。

双数组字典树的本质是「用数组下标替代指针」,与二叉堆用下标算术替代左右引用是同一种思路;关于数组表示与链式表示在空间与缓存上的通盘比较,见 数组与链表 与 二叉树与二叉搜索树 的存储表示一节。

4.4 后缀树与后缀数组的定位

上面几类结构都在「多个字符串集合」上做索引。若问题变成「在单个长文本中反复查询任意子串」,索引的对象就从字符串集合变为该文本的全部后缀:

  • 后缀树(suffix tree) 是把文本全部后缀构成的压缩字典树,配合唯一的终止符保证每个后缀对应一个叶子。它支持 O(m) 的子串查询与最长重复子串、最长公共子串等经典问题,但构造算法复杂、节点与边的开销大。
  • 后缀数组(suffix array) 记录全部后缀按字典序排序后的起始位置,配合 LCP(最长公共前缀)数组以更小的空间提供与后缀树等价的大部分能力,是现代实现的主流选择。

此处只做定位说明:后缀结构解决的是「一个文本内部的子串索引」问题,与字典树解决的「一个字符串集合的前缀索引」问题不同。两者共享「用树形结构表示公共前缀」这一思想,但索引对象、构造代价与适用规模都不同。工程中若只需要子串存在性判断,全文索引组件(如数据库的全文索引)已经封装了这一层。

5. 与散列表的对比

5.1 逐项对比

维度 字典树 散列表
精确查找 确定 O(m),m 为键长 期望 O(1)(严格说含 O(m) 的散列计算),最坏 O(n)
前缀查询 支持,O(m) 不支持,需枚举前缀或全表扫描
对前缀词计数 支持,O(m)(节点计数) 不支持
字典序枚举 支持,先序遍历天然有序 不支持,需要额外排序
最长前缀匹配 支持,沿路径记录最后一个词节点 不支持
空间开销 与「不同前缀数 × 每节点开销」相关,通常大于散列表 与元素数及负载因子相关,存储紧凑
冲突处理 不需要,路径唯一 必需(链地址、开放寻址),见 散列表
最坏情况 确定 O(m),无退化风险 最坏 O(n),可被恶意键构造触发
对键分布敏感 不敏感(只依赖字符集与键长) 敏感(依赖散列函数的均匀性)
追加字段的成本 每个节点都要加(如计数、top-k) 每个条目加,粒度更小
删除的清理 可能需要自底向上回收节点 需要处理墓碑或链,见 散列表

5.2 选型判据

只需要精确匹配,且键分布可信       → 散列表(空间更小,实现更简单)
需要前缀查询、补全、字典序、最长前缀匹配 → 字典树
键很长、公共前缀多、查询以「分组前缀」为主 → 字典树优势最大(共享前缀节省显著)
键是随机串(哈希、UUID)、无公共前缀     → 散列表更省空间,字典树只带来指针开销
只需要「可能存在」的近似判断           → 布隆过滤器(../hash/bitmap_and_bloom_filter.html)
需要按键排序的范围查询(任意区间,不限于前缀) → 平衡树、跳表或有序数组
需要按键的子串或词包含检索           → 倒排索引、全文索引,见数据库检索一节

两条容易混淆的判断需要明确:

  1. 「前缀查询」与「范围查询」不是同一件事。字典树能高效回答「以 X 开头」,但不能回答「字典序在 X 与 Y 之间」(除非先定位 X 再逐节点后继推进,代价与结果规模相关)。反过来,平衡树与 B+ 树能回答任意区间,但对前缀查询要依赖最左前缀式的键设计。
  2. 「公共前缀多」既是字典树的收益来源,也是它的成本来源。共享前缀节省空间,但共享也意味着更多节点同时位于高频路径上——若某个前缀的子树极大(如以 http 开头的百万级 URL),该节点的子节点容器与遍历代价都会集中在这里,成为热点。此时需要在该节点上做额外处理(分片、把子节点换为更紧凑的结构、或对子树延迟构建)。

6. 扩展方向:从单模式匹配到多模式匹配

6.1 多模式匹配的问题

单模式匹配(在一个文本中找一个模式串)有 KMP、Boyer-Moore 这类线性算法。多模式匹配(在一段文本中同时找出若干个模式串的全部出现位置)若逐个模式串跑一遍单模式算法,代价为 O(kn)(k 为模式数,n 为文本长)。

字典树给出了一个自然的改进方向:用模式集合构建一棵字典树,然后让文本在这棵树上「走」一遍。

朴素做法:从文本的每个位置出发,沿字典树走,走到不能走为止
     代价 O(n × Lmax),Lmax 为最长模式长度
问题:每次失败都要回到字典树的根重新开始,前缀信息被丢弃

失败时「回到根」丢弃的正是最有价值的信息——已经匹配的一段后缀可能仍是一个有效的前缀。

6.2 AC 自动机:字典树加 fail 指针

AC 自动机(Aho-Corasick automaton)在字典树的每个节点上增加一个 fail 指针,把上述「失败后退回」的过程从「回到根」改为「退到最长的、仍是某模式前缀的真后缀位置」:

fail 指针的定义:
    对节点 u(代表前缀 P),fail(u) 指向节点 v,使得
    v 代表的前缀是 P 的最长真后缀,且 v 代表的前缀是某个模式串的前缀

fail 指针的构建(按 BFS 逐层处理):
    根的 fail 指向自身(或空),根的第一层孩子 fail 指向根
    对节点 u 的字符 c 分支 v:
        设 f = fail(u)
        若 f 有字符 c 分支,则 fail(v) = f.children[c]
        否则沿 fail 链继续上溯,直到找到有 c 分支的节点或到达根
        若 v 本身是某个模式的终点(或 fail(v) 是),则 v 也是输出节点

匹配过程因此变成 O(n) 的线性扫描:

在当前节点读入文本字符 c:
    若当前节点有 c 分支 → 转移到该孩子,检查输出
    否则沿 fail 链上溯,直到找到有 c 分支的节点或回到根
    上溯的总代价是均摊 O(1)(每次转移最多使「当前深度」加一,上溯减少的深度总量有界)

复杂度:

构建:O(Σ|p_i|)(BFS 加均摊 O(1) 的 fail 链上溯)
      若为每个节点补齐字符集大小的转移表(完整 goto 函数),构建代价为 O(|Σ| · Σ|p_i|),换来匹配时无上溯
匹配:O(n + 匹配出现数)
空间:O(Σ|p_i|),fail 指针每节点一个

三点工程含义:

  1. AC 自动机是「预处理换扫描效率」的结构。模式集合固定时,构建一次,可以长期用于流式文本扫描;模式集合频繁变化时,构建开销会变成主要成本(见第三节第 5.5 小节的热更新)。
  2. fail 指针把「模式之间的后缀关系」显式记录了下来。若模式集合中存在一个是另一个后缀的模式(如 he、she、hers),fail 链会自动把它们串起来,无需为每个模式单独扫描。
  3. 输出可以沿 fail 链累积。需要找出全部匹配时,一个节点上的输出集合应包含其 fail 祖先的输出(构建时合并,或匹配时沿 fail 链上报),否则会漏掉被更长模式覆盖的短模式。

6.3 有限状态自动机的位置

从自动机的视角看,本节的结构属于同一族:

结构 状态 转移 失败处理
KMP 的 next 数组 已匹配的字符数 读入字符后的字符数 回退到最长真前缀
字典树 一个前缀 读入字符后的新前缀 无转移即失败(终止匹配)
AC 自动机 一个前缀 读入字符后的新前缀 沿 fail 链找最长可用后缀
正则表达式引擎的 DFA/NFA 正则的匹配位置 读入字符后的位置 状态集合的转移(NFA)或预计算(DFA)

共同点是:把「匹配进度」保存为状态,把字符的读入表示为状态转移。KMP 的失败函数与 AC 的 fail 指针是同一思想在不同结构上的推广——前缀在树上推广为节点的祖先链,失败退避在链上推广为 fail 链上溯。词法分析器的关键字识别、词典的重复匹配检测、正则引擎的自动机构造,都是这一族结构的具体应用。KMP、Rabin-Karp、Z 函数与 Manacher 等单模式匹配算法的原理、复杂度与实现要点见 字符串算法。

三、实现

1. 节点与操作实现要点

1.1 节点定义

两种常见写法对应第 3.3 小节讨论的两种表示。

// 写法一:定长数组,适用于已知字符集
class TrieNode {
    TrieNode[] children = new TrieNode[26];   // 下标 = 字符 - 'a'
    boolean isEnd;                            // 是否为某个键的终点
    int pass;                                 // 经过该节点的键数(用于前缀计数)

    // 词频统计场景下用 count 取代 isEnd,允许重复键
    int count;
}
// 写法二:映射,适用于字符集大或分支稀疏
class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd;
}

两处工程要点:

  • 字符到下标的转换必须集中在一处。把 c - 'a' 这类算术散落在各处,一旦需要支持大写字母、数字或 Unicode,修改面会覆盖全部操作。建议提供 index(char c) 与反向的 charAt(int i) 两个函数,并在入口处做字符归一化(大小写、全半角、繁简)。
  • 统计字段只在需要时添加。pass 与 count 每增加一个,就要求在插入、删除、以及可能的结构清理中同步维护;不需要时不要预留,理由与二叉搜索树中「辅助字段必须同步」的讨论相同,见 二叉树与二叉搜索树。

1.2 插入与查找

class Trie {
    private final TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();      // 缺则建,已有则复用(共享前缀)
            }
            node = node.children[idx];
            node.pass++;                                  // 经过计数:插入路径上每个节点加一
        }
        node.isEnd = true;
        node.count++;
    }

    boolean search(String word) {
        TrieNode node = find(word);
        return node != null && node.isEnd;                // 路径存在且是词
    }

    boolean startsWith(String prefix) {
        return find(prefix) != null;                      // 只要求路径存在
    }

    int countPrefix(String prefix) {
        TrieNode node = find(prefix);
        return node == null ? 0 : node.pass;              // O(m) 得到前缀词数
    }

    private TrieNode find(String s) {
        TrieNode node = root;
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if (idx < 0 || idx >= 26) return null;         // 归一化未覆盖的字符,直接判定不存在
            node = node.children[idx];
            if (node == null) return null;
        }
        return node;
    }
}

find 抽成私有方法是这段实现的关键:精确查找、前缀查询、前缀计数三者的下降逻辑完全相同,差别只在终点的判断。合并之后,三者对字符归一化与边界处理的规则自然一致。

1.3 前缀统计与补全

「统计以某前缀开头的词数」由 pass 直接给出(第 1.2 小节)。「列出以某前缀开头的全部词」需要收集子树:

// 收集以 prefix 开头的全部词,最多 limit 个(用于补全场景的截断)
List<String> complete(String prefix, int limit) {
    List<String> res = new ArrayList<>();
    TrieNode node = find(prefix);
    if (node == null) return res;
    dfs(node, new StringBuilder(prefix), res, limit);
    return res;
}

private void dfs(TrieNode node, StringBuilder path, List<String> res, int limit) {
    if (res.size() >= limit) return;                      // 结果截断,避免遍历整棵子树
    if (node.isEnd) res.add(path.toString());
    for (int i = 0; i < 26; i++) {
        if (node.children[i] == null) continue;           // 按下标升序访问即字典序
        path.append((char) ('a' + i));
        dfs(node.children[i], path, res, limit);
        path.deleteCharAt(path.length() - 1);             // 回溯,撤销本次选择
    }
}

三点值得注意:

  • 按下标升序遍历天然得到字典序输出,不需要排序,这是第 1.1 小节性质 3 的直接应用。
  • 截断必须在进入子树前生效。补全场景只关心前若干个候选,若先收集全部再截断,代价会退化为子树规模。
  • 回溯的路径容器是共享的,因此必须在返回前撤销修改;若需要保存路径,保存的是副本而非引用。这与树上回溯枚举路径的注意事项一致,见 二叉树与二叉搜索树 的回溯与剪枝一节。

1.4 删除与清理

删除有两种策略,取舍在内存与实现复杂度之间。

策略一:只清标记(惰性删除)。

void delete(String word) {
    TrieNode node = find(word);
    if (node == null || !node.isEnd) return;              // 键不存在
    node.isEnd = false;
    node.count = 0;                                       // 计数清零
    // 结构保留:pass 计数通常也需要沿路径递减,但节点不回收
}

实现极简,前缀查询的行为仍然正确(残留节点只会让「以某串开头」判断偏多)。代价是内存不随删除释放,在「长生命周期进程中反复增删词表」的场景会持续膨胀(见第 5.1 小节)。

策略二:自底向上回收无用节点。

delete(word):
    沿路径下降时记录经过的节点(显式栈或递归返回)
    清掉终点节点的 isEnd 与 count
    自底向上回溯:
        若某节点的所有子槽位为空,且 isEnd 为假、count 为 0
        → 断开它与父节点的连接,节点可回收
        否则停止回溯(该节点仍被其他键使用,其祖先同样不能回收)

要点是回溯必须在遇到第一个「仍有用」的节点时停止,而不是继续向上遍历整条路径——继续向上只会重复判断不可能回收的节点。

// 递归写法:返回「该子树是否已空」,空则断开连接
private boolean clean(TrieNode node, String word, int depth) {
    if (node == null) return false;
    if (depth == word.length()) {                          // 到达终点,先清标记
        node.isEnd = false;
        node.count = 0;
    } else {
        int idx = word.charAt(depth) - 'a';
        if (clean(node.children[idx], word, depth + 1)) {
            node.children[idx] = null;                     // 子树已空,断开
        }
    }
    if (node.isEnd || node.count > 0) return false;        // 仍是词节点,不可回收
    for (TrieNode child : node.children) {
        if (child != null) return false;                   // 仍有子节点,不可回收
    }
    return true;                                           // 可回收
}

第三点关于计数的处理:若实现中维护了 pass,删除成功后必须沿路径递减,否则前缀计数会给出偏大的结果;这一维护与插入时的递增必须严格配对。

2. 复杂度与空间实测

2.1 时间与空间复杂度

以 n 为键数、m 为单个键的长度、N 为全部键的字符总数(N = Σ|s_i|)、σ 为字符集大小、Lmax 为最长键长度:

操作 时间 空间(结构存储) 说明
构建(逐个插入) O(N × 定位代价) O(节点数) ≤ O(N) 定长数组表示下定位代价为 O(1),映射为期望 O(1)
精确查找 O(m) O(1) 额外 与 n 无关
前缀查询 O(m) O(1) 额外 同上
前缀词数统计 O(m) O(1) 额外 由节点计数给出
枚举前缀下的键 O(m + k) O(Lmax) 递归栈 k 为结果数
字典序全量输出 O(节点数) O(Lmax) 递归栈 无需排序
删除 O(m) 惰性 / O(m) 并回收 — 回收版需要路径记录
通配符匹配 最坏 O(节点数) O(Lmax) 取决于通配符的个数与位置
AC 自动机构建 O(Σ|p_i|) O(Σ|p_i|) 含 fail 指针
AC 自动机匹配 O(n + 匹配数) O(Σ|p_i|) n 为文本长度

空间一栏需要单独强调:字典树的空间由「不同前缀的个数 × 每节点开销」决定,其中每节点开销与子节点表示方式强相关,跨度可达两个数量级(定长数组表示 Unicode 时完全不可用,双数组表示则接近理论下界)。因此「字典树占多少内存」这个问题必须与表示方式一起回答。

2.2 子节点表示的实测取舍

第 3.3 小节给出的是定性排序,具体数值必须实测。基准设计需要覆盖以下几项,方法层面的完整说明见 JMH 微基准测试 的场景设计与结果表述两节。

维度 设计要点
词表规模参数化 至少覆盖 10⁴、10⁵、10⁶ 三个量级,观察耗时与内存随规模的变化曲线,而不是比较单点
字符集参数化 小写字母(σ = 26)、ASCII(σ ≈ 128)、含中文字符(σ 很大)分别测量,这是表示方式差异最大的变量
前缀共享度参数化 随机字符串(几乎无共享)与真实词表(共享前缀多)分别测量;前者测空间开销,后者测共享收益
查询模式分离 精确查找、前缀查询、前缀计数、子树枚举分别测量;它们的瓶颈不同(分别是定位、定位、定位、遍历)
操作混合 只读(构建后查询)、读写混合(含插入删除)分别测量;回收式删除会显著改变读写混合的曲线
内存测量方式 固定堆参数(-Xms 与 -Xmx 相等)后统计结构与实际占用,或统计构建前后的分配量;必须关闭不变量校验与调试输出
对照实现 同一任务下与 HashMap、有序数组、前缀索引(B+ 树或数据库)对照,避免把实现质量差异误读为结构差异

可以给出的、不依赖具体数值的结论有三条:

  1. 定长数组表示的查找常数最小,因为定位是一次数组下标运算且数据连续;其空间代价随字符集线性增长,在 Unicode 上不可接受。
  2. 映射表示的空间与实际分支数成正比,稀疏时最省;但每次转移包含散列与指针追逐,查找常数明显更大,且遍历时子节点无序,字典序输出需要额外排序。
  3. 双数组表示的查找常数接近定长数组,空间接近理论下界,代价集中在构造期;对「构建一次、查询海量」的静态词典,它是内存与速度的较优折中。

2.3 十万级词表的空间估算方法

估算过程分三步,第一步与表示方式无关,后两步与表示方式绑定。

第一步:估算节点数
    上界 = Σ|s_i| + 1
    实际值 = 上界 − 共享前缀节省的节点数
    实测手段:按字符逐层统计「不同前缀的个数」,或直接构建后统计节点数

    例:10 万词,平均长度 8(含分隔符),则 Σ|s_i| ≈ 80 万,上界节点数 ≈ 80 万
        真实词表共享前缀较多时通常落在上界的 40% 至 70%,即约 32 万至 56 万节点
        若词表是随机字符串,则接近上界

第二步:确定每节点开销(以 Java 为例,数值为量级估算,随 JVM 与字段布局变化)
    定长数组表示(26 项引用数组):
        节点对象头 + 数组对象头 + 26 个引用 ≈ 数百字节量级
        总空间 ≈ 节点数 × 每节点开销
    映射表示:
        节点对象 + 映射对象 + 每个子边一个条目对象
        总空间 ≈ 节点数 × 节点开销 + 边数 × 条目开销 + 桶数组开销
        (边数 = 节点数 − 1)
    双数组表示:
        两个 int 数组,长度由状态数决定(约等于节点数的常数倍)
        总空间 ≈ 状态数组长度 × 4 字节 × 2

第三步:加上运行期辅助结构
    补全场景的 top-k 缓存、词频排序数组、fail 指针数组等

量级上的结论:同样的词表,定长数组表示与双数组表示的内存占用可能相差数倍到数十倍,差异主要来自「每节点固定槽位数」与「对象头与引用字段」两项。因此当词表达到百万级、或需要在有限堆内存中并存多份词表(如多语言、多版本)时,表示方式的选择比算法层面的优化更有效。

内存占用的精确测量与 GC 压力的关系见 JVM 内存结构与垃圾回收:字典树的节点数量大、单个对象小、生命周期长,属于对 GC 不友好的形态——节点对象多会加重标记阶段的工作量,而节点一旦构建就长期存活,容易被晋升到老年代,因此在大词表场景中,减少对象数量本身(改用双数组等紧凑表示)同时改善内存占用与 GC 表现。

3. 典型题型

3.1 实现前缀搜索与自动补全

思路:构建字典树,前缀查询定位到前缀末端节点,再对该子树做有序 DFS,收集到 limit 个结果即截断。

复杂度:定位 O(m) + 遍历 O(输出规模 + 剪枝后访问的节点数)
空间:O(Lmax) 递归栈
要点:
    1. 结果按字典序输出由「按字符升序访问子节点」保证,不需要排序
    2. 截断在使用处生效,避免遍历过大的子树
    3. 若需要按热度排序而非字典序,在节点上维护 top-k 列表或跳表,
       或先按字典序取较多候选再按热度重排(两种做法的取舍见 4.1 小节)

3.2 单词搜索与单词替换

单词搜索(在二维字符网格中找词表中的词) 与逐个模式做 DFS 相比,字典树的收益在于剪枝:网格 DFS 的每一步沿字典树下降,一旦字典树中无对应分支,整条分支立即放弃,不需要继续搜索。

思路:
    1. 全部单词建字典树
    2. 从网格的每个格子出发 DFS,同时沿字典树转移
    3. 转移失败即回溯;到达词节点时记录结果并(可选)标记已找到以去重
    4. 剪枝依据:字典树的分支存在性,等价于「当前前缀不是任何词的前缀」
复杂度:O(格子数 × 4 × Lmax),实际远低于此,因为剪枝在浅层就大量生效
易错点:结果去重(同一个词可能匹配多个位置)、访问标记的恢复(回溯时撤销)

单词替换(用最短词根替换词) 是字符串集合上「最短前缀匹配」的直接应用:

思路:
    1. 用词根集合建字典树
    2. 对句子中每个词沿字典树下降,遇到的第一个 isEnd 节点即为最短词根
    3. 若在词结束前没有遇到 isEnd,则该词不变
复杂度:O(句中总字符数)
要点:必须在「第一个词根」处停止,而不是走完整条路径——这就利用了 isEnd 区分词与前缀的能力

3.3 前缀词数统计与最长公共前缀

统计以某前缀开头的词数:节点上维护 pass,插入时沿途加一,查询 O(m)。

最长公共前缀的两种问法:

问法一:给定一批字符串,求它们的最长公共前缀
    做法:以第一个串为基准逐个比较,或用字典树——从根开始沿唯一子节点下降,
          遇到的第一个「有多于一个子节点」或「isEnd 为真」的节点处停止
    复杂度:字典树做法 O(所有串的总字符数)(构建)+ O(结果长度)

问法二:给定目标串与一批字符串,找与目标串共享最长前缀的那个字符串
    做法:沿字典树下降,记录路径上最后一个 isEnd 节点;下降失败时返回记录值
    复杂度:O(m + 结果长度)

问法二的「记录路径上最后一个词节点」是最长前缀匹配的标准写法,IP 路由中的查找使用同一逻辑(见第 4.5 小节)。

3.4 字符串排序与字典序输出

字典树的先序遍历即字典序输出,代价为 O(节点数),不需要比较操作:

比较两种排序方式:
    通用排序:O(n log n) 次字符串比较,每次比较扫描到首个不同字符
    字典树排序:O(N) 一次先序遍历,N 为总字符数
当字符串存在大量公共前缀时,字典树排序的比较次数明显更少,
因为公共前缀只被走一次,而不是被参与比较的每个元素各走一次

需要注意的是,字典树排序的空间代价高于原地排序:需要用 O(N) 的节点空间换取时间上的收益。

3.5 题型汇总

题型 关键做法 时间 额外空间 易错点
实现前缀树 节点容器 + isEnd 各操作 O(m) O(N) 精确查找漏判 isEnd
前缀搜索与补全 定位 + 有序 DFS + 截断 O(m + k) O(Lmax) 截断位置过晚、结果未按序
单词搜索(网格) 字典树剪枝 + 回溯 O(格子数 × Lmax) O(Lmax) 结果去重、访问标记未恢复
单词替换(词根) 首个 isEnd 处停止 O(总字符数) O(N) 走完整条路径导致取到最长词根
前缀词数统计 节点 pass 计数 O(m) O(1) 删除时未同步递减
最长公共前缀 单链下降至分叉点 O(N) O(N) 忽略 isEnd 判断(词是另一个词的前缀)
找最长前缀匹配 记录路径上最后一个词节点 O(m) O(1) 未记录中间命中点
字典序输出 先序遍历 O(节点数) O(Lmax) 子节点容器无序(映射表示)
词频统计 节点 count 计数 O(总字符数) O(N) 与归一化规则不一致导致计数分散
多模式匹配 AC 自动机(fail 指针) O(文本长 + 匹配数) O(Σ|p_i|) fail 构建的上溯逻辑、输出未沿 fail 链累积

4. 工程应用

4.1 搜索框自动补全与提示

补全是最典型的字典树场景,但直接使用「前缀查询 + 遍历子树」会遇到两个问题:结果需要按热度排序(而不是字典序),以及热门前缀的子树极大。

常见的三种处理:

方案 做法 取舍
只按字典序取前 k 个 子树有序 DFS,取到 k 个即停 最简单;候选质量依赖字典序,与热度无关
节点缓存 top-k 每个节点保存「以该前缀开头的热度前 k 个词」 查询 O(m + k);构建与更新时需自底向上合并子节点的 top-k,内存放大
倒排 + 排序 前缀节点保存候选词 id 列表,按热度排序 更新灵活;每个前缀都存列表,空间与更新代价高

三点工程要点:

  1. top-k 合并的写法决定构建成本。节点上的 top-k 是「自身词(若 isEnd)与其全部子节点的 top-k 的并集中取前 k 个」,合并时需要去重并保持有序;词表更新时受影响的只有该词路径上的节点,可以只重算这条路径。
  2. 结果截断与缓存。热门前缀(如单字符、双字符前缀)应当有独立缓存,因为它们的查询占比高而候选集大;冷门前缀的子树小,直接遍历更划算。
  3. 输入归一化在入口处完成。大小写、全半角、前后空白、简繁体的处理若分散在查询与构建两处,会出现「构建时用小写、查询时未转换」导致的命中率下降——这类缺陷表现为「部分词查不到」,且与查询串的形态相关,排查时容易误判为字典树结构问题。

4.2 敏感词过滤

敏感词过滤的两种实现对应第 6 节的两种结构:

方案一:字典树逐位置扫描
    对文本的每个起始位置,沿字典树尽量匹配,命中则替换
    代价 O(n × Lmax),实现最简单
    适合:文本短、词库小、或对吞吐要求不高的场景

方案二:AC 自动机单遍扫描
    构建一次自动机,扫描文本一遍即可得到全部匹配位置
    代价 O(n + 匹配数),实现较复杂(需要 fail 指针与输出集合)
    适合:文本长、词库大、吞吐要求高的场景

命中的替换策略:
    最长匹配优先:沿路径记录最后一个词节点,用于确定替换的边界
    最短匹配优先:遇到的第一个词节点即命中(如 4.3 节的词根替换)
    两种策略都要在需求阶段明确,否则会出现「替换后仍含敏感词」的漏网
       (例如词库有 "ab" 与 "abcd",文本为 "abcd":
         最短优先替换 "ab" 后剩余 "cd",结果可能仍构成另一个敏感词)

工程上还需要处理三类输入变体,它们与结构无关,但决定了召回率:

  • 字符变体:全角与半角、大小写、繁体与简体、以及插入分隔符(敏*感*词)等规避手段;处理方式是在扫描前归一化,或为变体额外建索引;
  • 插入符号跳过:在转移时允许跳过特定字符(如空白、标点),代价是转移不再是一对一,需要引入状态集合或对文本预处理;
  • 命中后的处理粒度:替换、打码、拦截或仅记录,需要与业务语义一致(例如某些词只在特定语境下敏感)。

4.3 词频统计与文本处理

字典树在文本处理中的另一类用途是统计:

构建:把分词结果逐个插入字典树,节点上的 count 累加
查询:某个词的词频、某个前缀下的词数、按词频排序的词表

需要明确一点:若只需要「词到频次」的映射,散列表已经足够,且空间更小。字典树在此的价值只在于同时需要前缀维度(前缀词数、按前缀分组统计、前缀聚合)时。若两者的需求都存在,常见做法是两者并存——散列表负责精确统计,字典树负责前缀维度,或直接用字典树同时承载(节点上的 count 承担精确统计、pass 承担前缀统计)。

4.4 路由匹配(前缀路由表)

Web 框架的路由表是「路径前缀 → 处理器」的映射,天然适合用压缩字典树组织:

路由表:
    /api/v1/users        → handlerA
    /api/v1/users/{id}   → handlerB
    /api/v1/orders       → handlerC
    /static              → handlerD

结构(压缩字典树,路径段作为边的一部分):

    /
    ├─ api/v1/
    │   ├─ users        [handlerA]
    │   │   └─ /{id}    [handlerB]
    │   └─ orders       [handlerC]
    └─ static           [handlerD]

匹配 /api/v1/users/42:
    沿路径下降,到 users 时记录命中(handlerA)
    继续到 /{id} 时再次命中(handlerB,更具体)
    最终返回最后记录的一次命中 → 最长前缀匹配

三点要点:

  1. 最长匹配优先由「记录路径上最后一个命中」实现,与第 3.3 小节的问法二完全同构;
  2. 参数段({id})需要在分叉处单独处理,因为它匹配任意字符串,等价于通配符;
  3. 路径段的分隔符使压缩字典树特别合适,因为路径天然有「段」这一粒度,压缩后的边通常是一整段而非单字符。

4.5 IP 路由的基数树

IP 路由表是「前缀 → 下一跳」的映射,其索引结构是压缩字典树在位上的应用:

路由表(CIDR 前缀 → 下一跳):
    10.0.0.0/8        → nexthop1
    10.1.0.0/16       → nexthop2
    10.1.2.0/24       → nexthop3
    0.0.0.0/0         → default

结构:以地址的二进制位为分支依据,压缩掉单分支路径
查找 10.1.2.5:沿位逐位下降,记录路径上最后一个命中前缀,返回最具体的那个

与字符串字典树的差别:
    1. 分支依据是位(字符集大小 2),而不是字符
    2. 压缩程度更高:单分支路径必然被合并,因此节点数远小于地址位数 × 前缀数
    3. 前缀长度的语义是掩码长度,查找即最长前缀匹配

这正是「基数树(radix tree)」这一名称的常见来源。其三处工程性质:查找代价与地址位数相关(IPv4 为 32 位、IPv6 为 128 位)而与路由条数无关;节点数量由前缀的分叉结构决定;最长前缀匹配不需要额外的比较,只依赖「沿路径记录最后一个命中」这一规则。

4.6 数据库与检索系统中的词典结构

场景 使用的结构 与字典树的关系
等值查询(WHERE name = '...') B+ 树或散列索引 字典树不参与;散列在等值上更快
前缀匹配(LIKE 'abc%') B+ 树,利用最左前缀定位扫描区间 与字典树的能力同源,但按整串排序而非按字符分层
包含匹配(LIKE '%abc%') 无法用 B+ 树定位,需全文索引或外部检索组件 字典树在内存中可以承担,但库表场景由检索组件承担
词级别的检索与相关性排序 倒排索引(词 → 文档列表) 倒排索引的词典常用紧凑的自动机或压缩字典树组织,以节省内存(词典层与倒排表的分工、增量编码与块索引见 工程中的数据结构)
输入法、分词、拼写纠正的词典 双数组字典树、三叉字典树等内存结构 静态词典、查询密集,正对应双数组的适用场景

数据库侧的具体限制与替代方案(最左前缀原则、前缀索引、全文索引、反转列等)见 mysql: 索引与执行计划 的联合索引与最左前缀、模糊匹配场景的替代方案两节。这里只提炼两条与结构选择直接相关的结论:

  1. 前缀匹配的能力来自「有序 + 逐段比较」,不是来自某种特定树的形状。B+ 树与字典树都能支持它,差别是 B+ 树按整串排序(于是只能利用最左前缀)、字典树按字符分层(于是天然只支持前缀方向)。若要支持任意位置的匹配,两者都需要额外的结构(全文索引、倒排索引、后缀结构)。
  2. 磁盘上的词典与内存中的词典是不同的结构。B+ 树为磁盘按页组织,牺牲了「按字符分层」这一特性换取更低的树高,代价是前缀匹配只能利用最左前缀;内存中的字典树没有页访问的约束,因此可以按字符分层,代价是节点数量的膨胀。这一对照与二叉搜索树与 B+ 树在内存与磁盘上的分工是同一个原因,见 B 树与 B+ 树。

5. 常见问题与排查

5.1 节点过多导致内存膨胀

现象:词典规模不大(几万词),但内存占用远超预期;频繁 GC 或出现 OutOfMemoryError;堆转储中某类节点对象数量巨大。

原因:

  • 子节点容器按字符集定长开表,而实际分支稀疏(Unicode 场景最严重,第 3.2 小节);
  • 每个节点一个对象、每条边一次引用,对象头与引用字段的开销占主导;
  • 删除只清标记不回收结构,长生命周期进程中反复增删导致残留节点累积(第 1.4 小节);
  • 未做字符归一化,同一逻辑词以多种形态各占一条路径(如大小写、全半角各建一份)。

排查:

  • 统计节点数与边数,与「总字符数 + 1」这一上界比较:若接近上界,说明共享前缀少,字典树的空间收益本就不成立;
  • 检查字符串的平均长度与字符集:字符集大而词长短(如短 ID)时,定长数组表示的成本最高;
  • 用堆转储检查节点对象与容器对象的数量比例,确认开销来自节点还是容器(映射表示下容器的条目可能比节点更多)。

修复方向:

  • 改用按实际分支分配的容器(映射或有序数组),或改用双数组表示;
  • 改用压缩字典树,把节点数从 O(总字符数) 降到 O(词数);
  • 删除时按第 1.4 小节的策略二回收节点,或对长期不更新的词表采用「重建代替增删」;
  • 统一归一化规则,消除同一逻辑词的多种形态。

5.2 未区分词与前缀导致误判

现象:集合中只有 apple,但查询 app 返回「存在」;前缀查询与精确查询的返回值混用;startsWith 被误当作 contains 使用。

原因:节点只记录了路径字符,没有区分「该前缀是否是一个完整的键」。这是第 1.2 小节讨论的终止标记缺失。

排查:

  • 单独构造一组用例:集合为 {app, apple} 时,search("app")、search("apple")、startsWith("ap") 三个结果是否都符合预期;
  • 检查删除操作是否清除了 isEnd(若只清理子节点而保留标记,会出现「删掉的词仍能查到」);
  • 检查允许重复键的实现是否用计数取代了布尔标记,且计数递减到 0 时行为正确。

防护:把「精确查询」与「前缀查询」实现为两个显式的接口,共享同一个私有下降函数但在终点判断处分开;命名上避免使用 contains 这类含义模糊的方法名。

5.3 递归深度受字符串长度限制

现象:处理超长字符串或深树时抛出 StackOverflowError;遍历大词表时崩溃。

原因:字典树的递归深度等于当前字符串的长度(遍历时等于最长词的长度),而不是元素个数。键盘输入、日志行、Base64 编码数据这类超长字符串(数千至数万字符)会使递归深度线性增长;在 Java 中线程栈默认容量为数 MB 量级,深度通常在数千到数万时耗尽。

排查与修复:

  • 确认异常堆栈中是否出现同一方法重复成百上千层,这是递归过深的直接特征;
  • 遍历改为显式栈(深度由堆容量而非线程栈决定);插入与查找本身是迭代的,风险主要在遍历与清理阶段;
  • 若词汇表中存在超长键,考虑对其分段或改用其他结构;
  • 递归与迭代的取舍、栈深度与栈溢出的机制见 栈与队列,树上的同类问题见 二叉树与二叉搜索树 的常见问题一节。

5.4 并发更新字典树的一致性问题

现象:并发读写时偶发空指针异常;查询返回不存在的词或漏掉已插入的词;结构出现环或重复节点。

原因:字典树的插入会创建新节点并修改父节点的容器,删除会断开连接,这些都不是原子操作。并发场景下的三类具体问题:

1. 读到半构建状态
   插入先创建节点再挂接到父容器,中间存在「节点已存在但尚未与树连通」的窗口,
   或父容器的结构(哈希表)正在扩容,读线程可能看不到已写入的条目
2. 容器本身不是线程安全的
   HashMap 的并发写入可能导致结构损坏;即使换成并发容器,
   「先检查后创建」这一复合操作仍需要原子性,否则会产生重复节点
3. 删除与读取竞争
   回收节点的实现会在读取线程持有引用时断开连接,导致读取到悬空结构

处理方式:

方案 做法 取舍
读写锁 查询持读锁、修改持写锁 实现简单;查询之间可并行,但写操作会阻塞全部读
局部锁 只对分支节点(或分片)加锁 并发度更高;分片策略与锁粒度设计复杂
不可变结构 + 路径复制 修改时复制从根到修改点的整条路径,原子替换根引用 读完全无锁且无阻塞,读到的是某个一致快照;写入代价为 O(m) 的复制,内存回收依赖引用计数或 GC
双缓冲 + 版本切换 在旁路上构建新结构,构建完成后原子切换引用 读无锁、写入不阻塞读;内存峰值翻倍,切换点需要处理正在进行的查询

要点:ConcurrentHashMap 之类的并发容器只保证单个操作的线程安全,不保证「沿路径的一系列操作」整体一致。若查询需要「定位到前缀节点后遍历其子树」这样跨越多个操作的过程,仅在容器级别加并发保护是不够的——遍历期间的结构修改仍会破坏结果的一致性。因此高并发场景下,持久化(不可变)结构与版本切换是更可靠的选择,而基于锁的方案需要把「整条查询路径」纳入同一临界区。并发的可见性、锁与 CAS 的完整讨论见 Java 并发编程,集合框架中并发容器的定位见 Java 集合框架实现原理。

5.5 构建与热更新字典树的方式

词典需要在线更新(新增敏感词、调整补全候选)时,「原地增删」与「整体重建后切换」的取舍如下。

方式一:原地增删
    直接对现有结构执行插入与删除
    优点:单次更新的代价小(O(m)),内存增量小
    缺点:更新过程与查询并发,需要 5.4 小节的并发控制;
         连续增删后残留节点与新节点使内存难以估计;
         某些紧凑表示(双数组)不支持增量更新

方式二:双缓冲与版本切换
    1. 保留当前生效的结构(读版本)与正在构建的结构(写版本)两个引用
    2. 全量或增量地把新词典构建到写版本
    3. 构建完成后原子地交换两个引用
    4. 旧版本等待「仍在进行的查询」结束后回收

    优点:查询始终读到一个完整一致的结构,无需加锁;
         构建的开销与查询解耦,可以放到后台线程
    缺点:内存峰值接近两倍;构建期间的新增词典要合并到写版本,
         或等下一轮构建(需要明确可接受的数据延迟);
         旧版本的回收时机需要引用计数或宽限期机制

方式三:分层与合并
    读路径上先查「增量小结构」,未命中再查「基线大结构」
    优点:避免全量重建,内存增量与更新量成正比
    缺点:查询代价随层数增加;需要定期的合并(compaction)把增量折入基线,
         否则层数会持续增长

三点判断依据:

  1. 更新频率与词典规模。词典大而更新少(词典按天发布)时,重建加切换最合适,因为重建的开销被摊薄,而读路径无锁;词典小而更新频繁(运行时添加屏蔽词)时,原地增删或分层更合适。
  2. 查询的延迟要求。版本切换的切换点是瞬时引用赋值,读路径没有额外开销;分层方式则给每次查询增加一层未命中的代价,需要评估。
  3. 内存余量。双缓冲需要接近两倍的内存,在受限环境中可能不可行;此时代价更小的是「原地增删 + 读写锁」,或「分层 + 定期合并」。

无论采用哪种方式,都建议把词典的构建与生效分离:构建是一次批处理(可以校验完整性、统计规模、做归一化),生效是一次原子操作。这样可以把「词典内容错误」与「切换机制错误」两类问题分开排查。

5.6 其他常见问题

现象 可能原因 排查方向
部分词查不到,且与输入形态相关 构建与查询的归一化规则不一致(大小写、全半角、空白) 统一入口归一化;用同一批词分别走构建与查询路径比对
前缀计数与实际不符 删除时 pass 未递减,或插入时重复累加 断言「根节点的 pass 等于键总数」这一不变量
遍历输出的顺序不是字典序 子节点容器无序(映射实现的哈希顺序) 遍历时对子节点按字符排序;或改用有序数组与定长数组表示
通配符查询极慢 通配符位置靠前导致大量分支 记录通配符的位置与个数;对「前缀部分」先做定位,缩小搜索范围
补全结果重复或缺失 回溯时路径未撤销,或结果集合未去重 检查 DFS 的进入与撤销是否严格配对;结果是否按词去重
删除后内存不释放 惰性删除保留结构 与 5.1 小节的处理方式相同

6. 选型与检查清单

6.1 选型判据

需要判断的核心问题是:查询模式中是否包含「前缀」这一维度。若答案是肯定的,字典树或其压缩变体有不可替代的价值;若只包含精确匹配,字典树带来的只是内存开销。

条件 建议
只需精确匹配,键分布可信 散列表:空间更小、实现更简单
需要前缀查询、补全、字典序输出、最长前缀匹配 字典树族
键共享前缀多(编码、路径、词) 压缩字典树或双数组字典树,共享收益最大
键几乎无公共前缀(随机 ID、哈希值) 散列表优先;字典树只带来指针开销
字符集小且固定(小写字母、数字、ASCII) 定长数组表示的字典树,速度优先
字符集大或包含中文、emoji 映射、三叉字典树或双数组;避免定长数组表示
词典静态、查询密集 双数组字典树(构造期付代价,运行期紧凑且快)
词典频繁增删 原始字典树 + 可回收删除;双数组不适用
需要在长文本中同时匹配大量模式 AC 自动机(字典树 + fail 指针)
需要按键排序的任意区间查询 平衡树、跳表、有序数组;字典树不支持任意区间
需要按键的子串或词包含检索 倒排索引、全文索引;数据库侧的对照见 mysql: 索引与执行计划
只需判断「可能存在」 布隆过滤器,见 位图与布隆过滤器
数据量大到无法全量驻留内存 磁盘索引(B+ 树);字典树不适用,需借助磁盘上的检索组件

6.2 实现评审检查清单

结构与语义:

  • 是否用终止标记区分「词」与「词的前缀」;精确查询是否检查了它,前缀查询是否刻意未检查?
  • 允许重复键时的计数语义是否明确(isEnd 与 count 的关系,计数为 0 时 isEnd 是否仍为真);
  • 根节点的语义是否明确:它代表空串,是否可能被判为一个词(插入空串时的行为是否已定义)?
  • 字符归一化是否集中在入口一处完成,且构建与查询使用同一套规则?

表示与空间:

  • 子节点容器的选择是否与字符集大小、实际分支密度匹配;
  • 是否评估过节点数与「总字符数 + 1」这一上界的差距,从而判断共享前缀的收益是否成立;
  • 是否为节点上的统计字段(pass、count、top-k 缓存)做了内存估算;
  • 删除是否会释放结构,或已明确接受惰性删除的内存增长。

操作与边界:

  • 空串、单字符、最长键的插入、查询与删除是否都已覆盖;
  • 删除不存在的键是否安全(不应抛出异常或破坏结构);
  • 前缀计数与插入、删除的计数维护是否严格配对,根节点的计数是否等于键总数;
  • 遍历的截断(补全场景)是否在使用处生效;
  • 递归实现(遍历、清理)的深度是否与键长绑定,超长键是否需要改为显式栈。

性能与并发:

  • 是否按第 2.2 小节的维度做过实测,且结论带有词表规模、字符集、共享度、堆参数等条件;
  • 查询路径是否跨越多个操作(定位后遍历),若是,并发方案是否覆盖了整条路径而不只是单个容器操作;
  • 词典更新采用原地增删还是重建切换,其选择依据(更新频率、内存余量、延迟要求)是否已记录;
  • 若使用双缓冲切换,旧版本的回收时机与切换期间的查询是否已明确处理。

排查与验证:

  • 是否有一组固定用例覆盖「词与前缀」「删除后残留」「归一化变体」三类易错场景;
  • 是否有可独立验证的不变量(如前缀计数之和、根节点计数等于键总数、字典序输出有序)用于交叉校验;
  • 通配符或编辑距离查询是否有分支数与耗时的上限保护,避免单次查询拖垮服务。

四、总结

问题与解法。 字符串作为键时,除了等值判断还存在前缀维度的查询需求,而散列表的雪崩性把「相似键」有意打散,因此无法支持前缀查询与字典序输出。字典树的解法是改变比较的单位:把整个字符串的比较分解为逐个字符的分支选择,节点代表前缀,边标记字符,根代表空串,终止标记区分词与其前缀。由此得到三项散列表不具备的能力——前缀存在性判断、前缀词数统计、字典序枚举,以及一项散列表不具备的性质:查找代价与集合规模无关,且最坏情况与平均情况同为 O(m)。

结构的关键性质。 节点总数介于「最长键长度 + 1」与「总字符数 + 1」之间,两者的差距即共享前缀带来的节省;根到任一节点的路径唯一确定一个前缀;节点上的计数可以承载前缀维度与词频维度两类统计;先序遍历天然给出字典序,不需要比较操作。这些性质共同解释了字典树在前缀类问题上不可替代的原因,也解释了它空间代价的来源——节点数由「不同前缀的个数」决定,而每节点开销由子节点表示方式决定,后者的跨度可达两个数量级。

空间与表示。 定长指针数组表示定位最快,但每节点为字符集的全部取值预留槽位,在 Unicode 上不可用;映射与有序数组按实际分支分配,稀疏时最省,代价是定位常数与遍历顺序;双数组表示用两个整型数组表示转移,兼顾紧凑与缓存友好,代价是构造期的复杂度,因而适合静态词典。压缩字典树合并单分支路径,把节点数从 O(总字符数) 降到 O(词数),代价是边比较与分裂合并的实现复杂度;三叉字典树把按字符取值分叉改为按字符比较分叉,使空间与字符集大小解耦;后缀树与后缀数组解决的是「单个文本内部的子串索引」,与字典树的索引对象不同,只在「用树形表示公共前缀」这一点上同源。

与散列表的分工。 两者在精确查找上是同一量级(都要扫描整个键),差别在功能、最坏保证与空间:字典树支持前缀与有序,代价不需要处理冲突、最坏代价确定,但空间通常更大;散列表在只需等值判断、键无公共前缀时更省空间也更快。选型的核心判据是「查询模式中是否包含前缀维度」,其次才是键的字符集、共享前缀的比例与词典的动态性。

从单模式到多模式。 多模式匹配若逐个模式扫描,代价随模式数线性增长;用模式集合构建字典树后,文本只需扫描一遍,问题转化为「失配时如何保留已匹配的后缀信息」。AC 自动机用 fail 指针回答这个问题——它指向「当前前缀的最长真后缀,且该后缀仍是某模式的前缀」,从而把失配后的回退从「回到根」缩短为链上的一步。fail 指针通过 BFS 构建,上溯代价均摊 O(1),因此构建为 O(Σ|p_i|)、匹配为 O(n + 匹配数)。从自动机的视角看,KMP 的失败函数、字典树的分支、AC 的 fail 链与正则引擎的状态转移属于同一族思想:把匹配进度保存为状态,把字符读入表示为状态转移,把失配处理表示为状态的重新定位。

工程落点。 前缀搜索与自动补全、敏感词过滤、词频与前缀统计、路由前缀匹配、IP 路由的基数树、数据库与检索系统的词典组织,都是字典树族的具体形态。其中三处结论值得强调:自动补全需要解决的问题不是「找到候选」而是「按什么顺序给出候选」,因此节点上的 top-k 合并与结果截断比查找本身更影响体验;敏感词过滤的吞吐取决于是否使用 AC 自动机,而召回率取决于是否处理字符变体,两者属于不同层面的工作;数据库的前缀匹配能力来自「有序 + 逐段比较」,而不是某种特定树的形状,因此 B+ 树与字典树都能支持前缀方向,而任意位置的匹配两者都需要额外的结构(倒排索引、全文索引或后缀结构)。

实现与排查。 实现的三个关键点是:终止标记的语义、子节点容器与字符集的匹配、删除时的结构回收与计数维护。常见的五类缺陷是:内存膨胀(表示方式与字符集不匹配、惰性删除的累积)、词与前缀的误判(终止标记缺失或被误用)、递归深度受键长限制(遍历与清理的递归实现)、并发更新的一致性(单容器线程安全不等于查询路径一致)、热更新期间的可用性与内存峰值(双缓冲的代价与切换语义)。是否使用字典树,判据只有一条——查询是否包含前缀维度;若包含,再按字符集、共享前缀比例与词典动态性选择具体的表示方式,并用实测确认空间与时间的取舍。