字典树(Trie)是以共享前缀组织字符串集合的多叉树,它把「比较」的单位从整个字符串分解为单个字符,因而支持前缀查询、字典序枚举与最长前缀匹配这类散列表无法提供的操作。字符串作为键的不可分解性、字符集对分支因子的影响,其背景见 数组与链表 与 抽象数据类型(ADT);与散列表在精确查找上的分工见 散列表;树形结构的基本术语、递归到迭代的转换与退化问题的讨论见 二叉树与二叉搜索树 与 平衡树:AVL 与红黑树;字典树与磁盘索引的分工见 B 树与 B+ 树;复杂度记号的口径与实测的必要性见 复杂度与算法分析 与 JMH 微基准测试。
一、起源:字符串集合的查找需求
1.1 从精确匹配到前缀匹配
以字符串为键的集合有三类常见查询,难度依次上升。
| 查询 | 形式 | 语义 |
|---|---|---|
| 精确匹配 | 判断某个字符串是否在集合中 | 成员判断 |
| 前缀查询 | 返回集合中以某字符串开头的全部元素 | 范围查询在字符串上的对应物 |
| 最相近查询 | 返回与给定串共享最长前缀的元素,或返回编辑距离最近者 | 最长前缀匹配、模糊匹配 |
这三类查询在文本处理中同等常见:判断一个词是否收录属于第一类,输入法联想与搜索框提示属于第二类,IP 路由表与词根替换属于第三类。因此字符串集合这一抽象数据类型的能力要求,并不止于「是否存在」。
1.2 散列表能判等,不能做前缀匹配
散列表把整个键映射为一个地址,见 散列表:
address = H(key)
H("app") 与 H("apple") 之间没有任何可推导的关系
散列函数的构造要求之一是「键的微小变化引起散列值的大幅变化」,即雪崩效应。这条要求对精确匹配是有利的——它保证相似但不相同的键落入不同的桶;但对前缀查询恰好是障碍——前缀查询需要的正是「相似键落在相近位置」这一性质。
在散列表上实现前缀查询,只有两条路:
- 枚举前缀。对查询串的每个前缀分别做一次精确查找,代价为 O(m) 次散列计算(m 为串长),但得到的信息只有「该前缀是否恰为一个完整的键」,无法回答「有多少个键以它为前缀」,也无法枚举这些键。
- 全表扫描。遍历全部 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 上不可用。实际工程中的三条处理方式:
- 按实际字符集收窄。若能确定键只含小写字母、数字或 ASCII,直接按该字符集定长开表,是最快的方案;需要在预处理阶段做归一化(大小写转换、全半角转换)。
- 改用映射或有序数组。以实际分支数为空间单位,代价是每次访问多一次散列或二分。
- 改用压缩表示或双数组。见第 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
三点性质:
- 空间与字符集大小无关,每个节点固定三个指针,因而不存在 Unicode 上的爆炸问题;
- 查找代价为 O(log σ + m),其中 O(log σ) 是每一层在兄弟间按字符比较的代价(期望情形;树退化时更差);
- 有序性天然保持,中序遍历给出字典序,因为它本身是搜索树。
三叉字典树在字符集大而分支稀疏的场合(如混合编码的词表)比定长数组省内存,比哈希表省指针分配,代价是每层多出的比较与更深的树高。
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)
需要按键排序的范围查询(任意区间,不限于前缀) → 平衡树、跳表或有序数组
需要按键的子串或词包含检索 → 倒排索引、全文索引,见数据库检索一节
两条容易混淆的判断需要明确:
- 「前缀查询」与「范围查询」不是同一件事。字典树能高效回答「以 X 开头」,但不能回答「字典序在 X 与 Y 之间」(除非先定位 X 再逐节点后继推进,代价与结果规模相关)。反过来,平衡树与 B+ 树能回答任意区间,但对前缀查询要依赖最左前缀式的键设计。
- 「公共前缀多」既是字典树的收益来源,也是它的成本来源。共享前缀节省空间,但共享也意味着更多节点同时位于高频路径上——若某个前缀的子树极大(如以
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 指针每节点一个
三点工程含义:
- AC 自动机是「预处理换扫描效率」的结构。模式集合固定时,构建一次,可以长期用于流式文本扫描;模式集合频繁变化时,构建开销会变成主要成本(见第三节第 5.5 小节的热更新)。
- fail 指针把「模式之间的后缀关系」显式记录了下来。若模式集合中存在一个是另一个后缀的模式(如
he、she、hers),fail 链会自动把它们串起来,无需为每个模式单独扫描。 - 输出可以沿 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+ 树或数据库)对照,避免把实现质量差异误读为结构差异 |
可以给出的、不依赖具体数值的结论有三条:
- 定长数组表示的查找常数最小,因为定位是一次数组下标运算且数据连续;其空间代价随字符集线性增长,在 Unicode 上不可接受。
- 映射表示的空间与实际分支数成正比,稀疏时最省;但每次转移包含散列与指针追逐,查找常数明显更大,且遍历时子节点无序,字典序输出需要额外排序。
- 双数组表示的查找常数接近定长数组,空间接近理论下界,代价集中在构造期;对「构建一次、查询海量」的静态词典,它是内存与速度的较优折中。
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 列表,按热度排序 | 更新灵活;每个前缀都存列表,空间与更新代价高 |
三点工程要点:
- top-k 合并的写法决定构建成本。节点上的 top-k 是「自身词(若 isEnd)与其全部子节点的 top-k 的并集中取前 k 个」,合并时需要去重并保持有序;词表更新时受影响的只有该词路径上的节点,可以只重算这条路径。
- 结果截断与缓存。热门前缀(如单字符、双字符前缀)应当有独立缓存,因为它们的查询占比高而候选集大;冷门前缀的子树小,直接遍历更划算。
- 输入归一化在入口处完成。大小写、全半角、前后空白、简繁体的处理若分散在查询与构建两处,会出现「构建时用小写、查询时未转换」导致的命中率下降——这类缺陷表现为「部分词查不到」,且与查询串的形态相关,排查时容易误判为字典树结构问题。
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,更具体)
最终返回最后记录的一次命中 → 最长前缀匹配
三点要点:
- 最长匹配优先由「记录路径上最后一个命中」实现,与第 3.3 小节的问法二完全同构;
- 参数段(
{id})需要在分叉处单独处理,因为它匹配任意字符串,等价于通配符; - 路径段的分隔符使压缩字典树特别合适,因为路径天然有「段」这一粒度,压缩后的边通常是一整段而非单字符。
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: 索引与执行计划 的联合索引与最左前缀、模糊匹配场景的替代方案两节。这里只提炼两条与结构选择直接相关的结论:
- 前缀匹配的能力来自「有序 + 逐段比较」,不是来自某种特定树的形状。B+ 树与字典树都能支持它,差别是 B+ 树按整串排序(于是只能利用最左前缀)、字典树按字符分层(于是天然只支持前缀方向)。若要支持任意位置的匹配,两者都需要额外的结构(全文索引、倒排索引、后缀结构)。
- 磁盘上的词典与内存中的词典是不同的结构。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)把增量折入基线,
否则层数会持续增长
三点判断依据:
- 更新频率与词典规模。词典大而更新少(词典按天发布)时,重建加切换最合适,因为重建的开销被摊薄,而读路径无锁;词典小而更新频繁(运行时添加屏蔽词)时,原地增删或分层更合适。
- 查询的延迟要求。版本切换的切换点是瞬时引用赋值,读路径没有额外开销;分层方式则给每次查询增加一层未命中的代价,需要评估。
- 内存余量。双缓冲需要接近两倍的内存,在受限环境中可能不可行;此时代价更小的是「原地增删 + 读写锁」,或「分层 + 定期合并」。
无论采用哪种方式,都建议把词典的构建与生效分离:构建是一次批处理(可以校验完整性、统计规模、做归一化),生效是一次原子操作。这样可以把「词典内容错误」与「切换机制错误」两类问题分开排查。
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+ 树与字典树都能支持前缀方向,而任意位置的匹配两者都需要额外的结构(倒排索引、全文索引或后缀结构)。
实现与排查。 实现的三个关键点是:终止标记的语义、子节点容器与字符集的匹配、删除时的结构回收与计数维护。常见的五类缺陷是:内存膨胀(表示方式与字符集不匹配、惰性删除的累积)、词与前缀的误判(终止标记缺失或被误用)、递归深度受键长限制(遍历与清理的递归实现)、并发更新的一致性(单容器线程安全不等于查询路径一致)、热更新期间的可用性与内存峰值(双缓冲的代价与切换语义)。是否使用字典树,判据只有一条——查询是否包含前缀维度;若包含,再按字符集、共享前缀比例与词典动态性选择具体的表示方式,并用实测确认空间与时间的取舍。