外观
15 - Trie 前缀树:搜索提示、路由匹配与敏感词过滤
前置阅读:04 - Hash 表原理与工程应用、13 - 二叉树遍历与层级结构。
单模式字符串扫描见24 - 字符串匹配与 KMP。
摘要
搜索框输入 spring 后,要找的是所有以它开头的词,而不只是判断 spring 本身是否存在。HashMap 擅长按完整键精确查询;若没有额外索引,找出某个前缀的全部结果通常需要扫描键集合。Trie 把相同的开头共享为一条路径,先沿前缀定位,再只查看这条路径下面的词。
本文先解释路径与完整词的区别,再阅读查询、删除和补全代码,最后讨论内存、Unicode 和业务匹配规则。前缀定位快不代表补全的全部结果也能以同样成本返回。
1. 结构
**Trie(Prefix Tree,前缀树)**把字符串逐步拆成路径。这里先按字符理解:根节点表示空前缀,一条边表示读入一个字符,从根走到某个节点时,沿途字符连起来就是该节点代表的前缀。节点不需要各自保存整个前缀。
例如插入 app 和 apple,两者共用 a → p → p,apple 再从第二个 p 向下延伸 l → e。查询 ap 时能走到节点,说明存在这条前缀路径,但不能据此认定 ap 是已插入的词。因此节点还要有终止标记:word = true 表示路径到这里恰好构成一个完整词。单词结尾也可以继续有孩子,app 就是这种情况。
下面的基础类只实现插入、精确查询和前缀路径查询,没有运行入口。children 是“边上的字符到子节点”的映射;插入时,computeIfAbsent 复用已有孩子,只在对应字符没有孩子时创建节点。contains 必须同时检查路径存在和终止标记,startsWith 只检查路径。
java
import java.util.HashMap;
import java.util.Map;
class Trie {
static class Node {
Map<Character, Node> children = new HashMap<>();
boolean word;
}
private final Node root = new Node();
void insert(String text) {
Node node = root;
for (char ch : text.toCharArray()) {
node = node.children.computeIfAbsent(ch, (key) -> new Node());
}
node.word = true;
}
boolean contains(String text) {
Node node = find(text);
return node != null && node.word;
}
boolean startsWith(String prefix) {
return find(prefix) != null;
}
private Node find(String text) {
Node node = root;
for (char ch : text.toCharArray()) {
node = node.children.get(ch);
if (node == null) return null;
}
return node;
}
}设输入长度为 L,以 Java char 的数量计算。每次操作最多沿 L 条边前进;在 HashMap 单次查找或更新平均为常数成本的条件下,插入、精确查询和前缀路径查询通常为 O(L)。这是增长量级,不是延迟实测,也不是无条件的最坏情况保证。
两份示例都把词当作集合元素:重复插入只会再次设置终止标记,不记录出现次数。空串对应根节点,插入空串会将根标记为完整词;基础类的 startsWith("") 即使在空树中也返回 true,因为根始终存在。字符串参数应非 null,代码没有提供空引用处理,也没有并发访问保护。
2. 应用场景
- 搜索提示:定位前缀节点后遍历其子树,遇到终止标记就收集一个词;结果排序和数量上限还需单独处理。
- 路由匹配:可以把
/分隔的路径段作为边,而不是逐字符建树;参数和通配规则见第 6 节。 - 敏感词过滤:从文本中的候选起点沿 Trie 扩展,遇到终止标记就找到一个词;扫描整段文本还需要安排起点与重叠匹配策略。
- IP 路由:二进制 Trie 的边表示 0 或 1。最长前缀匹配是在沿地址位向下走时,记住最后一个带有效路由记录的节点,以选择匹配位数最多的前缀。
3. 内存问题
每个不同的非空前缀都需要一个节点;前缀共享越少,节点数量越接近所有词的长度之和。除了节点,还要存储分支映射和引用,因此不能仅按原始字符串大小估算内存。
字符集是允许出现在边上的字符范围。若每个节点都分配覆盖整个字符集的固定大小数组,而实际孩子很少,就会保留大量空槽,这叫分支稀疏。HashMap 可以避免为每个可能字符预留位置,但它自己的对象、桶和条目也有开销。可选方案包括压缩 Trie、Radix Tree 和紧凑数组编码;紧凑编码用数组等布局组织节点与边,以减少分散对象和引用。
**Radix Tree(基数树)**是一类压缩前缀树:把可合并的单分支连续路径压缩成带字符串标签的边,减少节点和指针数量。压缩时仍须保留词结束的位置;例如 app 已是完整词,就不能丢失它的终止信息。新词可能只与标签的一部分相同,插入时便需要拆分边;删除后则可能合并边。选择普通 Trie 还是压缩结构,应以公共前缀比例、字符集和更新频率为依据。
4. 完整可运行示例:查询、删除与补全
下面的完整类对应文件名 TrieDemo.java。N、next 对应前例的 Node、children,add、has 对应插入和精确查询。这里改用 TreeMap 存储孩子,让遍历按 Character 的自然顺序输出;这不是按热度排名,也不等于按特定语言的排序规则补全。
示例使用 List.of 和局部变量类型推断 var,需要支持这些语法与 API 的 Java 环境(Java 10 或更高版本)。
java
import java.util.*;
/**
* 可运行示例:Trie 前缀树:搜索提示、路由匹配与敏感词过滤。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class TrieDemo {
static class N {
Map<Character, N> next = new TreeMap<>();
boolean word;
}
final N root = new N();
void add(String s) {
N n = root;
// 每个字符沿一条边前进;已有公共前缀会复用节点。
for (char c : s.toCharArray())
n = n.next.computeIfAbsent(c, (k) -> new N());
// 终止标记区分“完整单词”与“只是其他单词的前缀”。
n.word = true;
}
N find(String s) {
N n = root;
for (char c : s.toCharArray()) {
n = n.next.get(c);
if (n == null) return null;
}
return n;
}
boolean has(String s) {
N n = find(s);
return n != null && n.word;
}
boolean remove(String s) {
return remove(root, s, 0)[0];
}
boolean[] remove(N n, String s, int i) {
if (i == s.length()) {
if (!n.word) return new boolean[] { false, false };
n.word = false; // 删除单词只需先清除终止标记。
return new boolean[] { true, n.next.isEmpty() };
}
char c = s.charAt(i);
N child = n.next.get(c);
if (child == null) return new boolean[] { false, false };
boolean[] r = remove(child, s, i + 1);
// 子节点不再代表单词且没有孩子时,当前边才可安全剪掉。
if (r[1]) n.next.remove(c);
return new boolean[] { r[0], !n.word && n.next.isEmpty() };
}
List<String> complete(String p, int limit) {
List<String> out = new ArrayList<>();
N n = find(p);
if (n != null) collect(n, new StringBuilder(p), out, limit);
return out;
}
void collect(N n, StringBuilder p, List<String> out, int limit) {
if (out.size() >= limit) return;
if (n.word) out.add(p.toString());
// TreeMap 让补全结果按字符顺序稳定输出。
for (var e : n.next.entrySet()) {
p.append(e.getKey());
collect(e.getValue(), p, out, limit);
p.setLength(p.length() - 1);
}
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
TrieDemo t = new TrieDemo();
for (String s : List.of("app", "apple", "apply")) t.add(s);
System.out.println(t.complete("app", 10));
t.remove("app");
System.out.println(t.has("app") + " " + t.has("apple"));
}
}删除 app 为什么不能删除整条路径
按 main 手工推演,两行预期输出依次为 [app, apple, apply] 和 false true,并非实测记录。补全先定位 app 节点,把它本身加入结果,再向下找 apple 与 apply。
删除 app 时,第二个 p 仍是 apple、apply 的共享前缀,因此只能先清除 word。剪枝是移除已无用途的分支:只有节点既不是单词结尾、又没有孩子时,父节点才可以移除指向它的边,然后继续向上判断。
递归删除返回的 boolean[] 有两个含义:下标 0 表示是否确实删除了一个词,下标 1 表示当前节点是否可以被父节点剪掉。remove(String) 只返回删除是否成功;根节点本身始终保留。若词不存在,则返回 false,不应删除已有词的共享路径。
补全中的 StringBuilder 保存当前路径。进入孩子前追加一个字符,返回后移除这个字符,恢复父节点路径,再访问下一个孩子;这种“深入后恢复状态”的过程称为回溯。limit <= 0 时结果为空,正数上限限制收集的词数。不过当前代码在达到上限后仍会进入已展开节点的后续循环,再由递归入口立即返回;结果上限不等于严格的扫描工作量上限。
复杂度还取决于分支容器。基础 HashMap 版本通常按 O(L) 分析;完整示例使用 TreeMap,若路径上节点的最大分支数为 b,按有序映射操作的对数成本分析,插入、精确查询和删除可写为 O(L log(b + 1))。字符集固定且将分支成本视为常数时,才可简写为 O(L)。补全还需计算分支遍历和复制结果字符串的成本,不能只算定位前缀的长度。删除和补全使用递归,路径很深时也要关注调用栈。
5. Unicode 边界
示例按 Java char 遍历,一个 char 是一个 UTF-16 码元(Code Unit),即这种编码的基本单位。一个 Unicode **码点(Code Point)**是字符编码空间中的一个编号,可能需要一个或两个 UTF-16 码元表示;部分 Emoji 因而会占两个 char。若业务要求每条边对应一个码点,应改用 text.codePoints(),并把边的键改为整数,插入、查询、删除和补全也都要采用相同单位。
码点仍不等于用户看到的一个字符。一个字母与组合附加符号可能由多个码点构成,但显示为一个整体;这种用户感知的字符单位涉及字素簇(Grapheme Cluster)。大小写折叠用于按约定消除大小写差异,**Unicode 规范化(Normalization)**用于将等价的编码序列转换到约定形式。它们都会影响“相同前缀”的定义。索引构建与查询必须使用完全一致的处理规则,否则视觉上相同的输入可能沿不同路径查找。本文代码未实现这些处理。
6. 路由匹配不是字符补全
HTTP 路由通常按路径段组织匹配规则:静态段要求字面值相等,如 me;参数段捕获某个位置的值,如 {id};通配段按路由系统约定匹配更宽的范围。例如请求 /users/me 可能同时符合 /users/me 和 /users/{id},必须预先规定优先级。字符 Trie 只知道字符路径,不会自动处理这些规则;若候选按插入顺序搜索并返回第一个匹配项,结果就可能依赖插入顺序。具体树结构和优先级以路由实现为准。
敏感词过滤中的模式就是要查找的词或字符串。多个模式共用 Trie 后,若仍从文本的每个起点重新扫描,就可能反复比较相同区段。大规模多模式匹配通常会考虑 **Aho-Corasick(AC 自动机)**等结构:它在 Trie 上增加失败指针,让当前匹配无法继续时,转到可承接已匹配后缀的状态,复用部分扫描信息。本文 Trie 只提供前缀索引基础,没有实现失败指针和完整的多模式输出逻辑。
7. 验证与排障
- 按顺序插入、查询、删除和再次查询,将结果与参考词集合对照;覆盖空串、重复插入、不存在的词及删除前缀词,检查共享节点是否保留。
- 补全时检查前缀本身是否被收集、无匹配时是否为空,以及上限为 0、负数和小于结果数量时的行为。
- 对大小写、规范化结果、Emoji 和组合字符建立兼容样例,先明确业务按码元、码点还是字素簇匹配。
- 延迟异常时记录节点数、平均分支数、最大深度和补全扫描节点数,区分前缀定位成本与结果收集成本。
- 内存异常时分别统计输入字符串、节点对象、分支 Map 和结果集合的成本,避免把所有占用都归因于键本身。
现有 main 只演示一组补全和删除前缀词,不能作为完整边界测试,也不包含性能或内存实测。
8. 容易踩的坑
- 没有终止标记,无法区分
app与apple的前缀。 - 删除单词时误删仍被其他词共享的节点。
- 搜索提示遍历整个巨大子树,没有结果上限。
- 忽略大小写、Unicode 规范化和语言规则。
- 用 Trie 做纯精确查询,却承担不必要内存成本。
- 路由参数与静态路径没有明确优先级,按插入顺序返回候选时可能产生意外结果。
9. 总结
Trie 把字符串公共前缀共享为路径,适合前缀查询,但代价是节点与分支结构的内存开销。
- 精确词与前缀必须通过终止标记区分。
- 字符集大小和分支稀疏度决定节点存储方式。
- 搜索提示、路由和文本匹配还需处理结果上限与 Unicode 语义。
图关系主线继续阅读:图的 DFS 与 BFS。字符串匹配可继续阅读KMP。