前端知识库Trie 关键词匹配与高亮
将百万级关键词高亮从重复遍历优化为前缀树扫描，并处理重叠匹配、HTML 安全和前端性能边界。
Trie 关键词匹配与高亮
这是一个典型的“项目问题转算法模型”场景：词典规模很大，页面文本需要找出所有关键词。先说明匹配语义，再选择数据结构；不能只说“用 Trie 就更快”。
一、先明确匹配规则
需要先和产品确认四件事：
- 匹配是否区分大小写、全角半角和 Unicode 规范化；
- 关键词是否必须按完整词边界匹配，还是任意子串都算；
- 关键词互相包含时选择最长词、最短词还是全部标记；
- 同一段文本中的重叠匹配如何展示。
例如词典包含 前端 和 前端工程，文本为“前端工程师”。最长匹配策略会优先得到“前端工程”；如果业务要求两个词都可见，就需要保存所有终止节点，而不是只保留一个结果。
二、构建 Trie
下面的实现使用 Map 保存稀疏子节点，并在终止节点保存词本身：
class TrieNode {
constructor() {
this.children = new Map()
this.words = []
}
}
class Trie {
constructor() {
this.root = new TrieNode()
}
insert(word) {
let node = this.root
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode())
}
node = node.children.get(char)
}
if (!node.words.includes(word)) node.words.push(word)
}
matchLongest(text, start) {
const chars = Array.from(text)
let node = this.root
let longest = []
for (let index = start; index < chars.length; index += 1) {
node = node.children.get(chars[index])
if (!node) break
if (node.words.length > 0) longest = node.words
}
return longest
}
}
for...of 按 Unicode 码点迭代，比直接按 UTF-16 code unit 遍历更适合包含代理对的文本。若业务需要按用户感知字符（字素簇）匹配，还要引入 Intl.Segmenter 或明确的分词规则；不要假设“一个 JavaScript 字符就是一个汉字/字母”。
三、扫描文本并处理重叠
对每个起点沿 Trie 向后走，最简单的最长匹配扫描复杂度约为 O(N * K)，其中 N 是文本长度，K 是从任一起点能走的最大词长。它共享了关键词的公共前缀，通常能减少对每个关键词重复调用 includes/正则的工作；但实际收益仍取决于词典分布、文本长度和输出数量，不能只凭数据结构名称保证更快。
function findLongestMatches(text, trie) {
const chars = Array.from(text)
const matches = []
for (let start = 0; start < chars.length; start += 1) {
let node = trie.root
let best = null
for (let end = start; end < chars.length; end += 1) {
node = node.children.get(chars[end])
if (!node) break
if (node.words.length > 0) {
best = { start, end: end + 1, words: node.words }
}
}
if (best) matches.push(best)
}
return matches
}
上例会返回相邻起点的结果，适合“所有起点都独立判断”的语义。若展示层不允许重叠，应在结果排序后做一次区间选择：优先更长区间，再按起点和业务优先级稳定排序；不要在扫描过程中随意丢结果，否则词典更新后可能出现顺序抖动。
四、生成安全的高亮结果
不要把原文和关键词直接拼到 innerHTML。关键词来自用户配置时，词本身可能包含 <、& 或恶意属性；即使匹配算法正确，也可能造成 XSS。更稳妥的做法是生成文本节点和元素节点：
function renderHighlights(container, text, matches) {
const chars = Array.from(text)
const fragment = document.createDocumentFragment()
let cursor = 0
for (const match of matches) {
if (match.start < cursor) continue // 已被前一个区间覆盖
fragment.append(document.createTextNode(chars.slice(cursor, match.start).join('')))
const mark = document.createElement('mark')
mark.textContent = chars.slice(match.start, match.end).join('')
fragment.append(mark)
cursor = match.end
}
fragment.append(document.createTextNode(chars.slice(cursor).join('')))
container.replaceChildren(fragment)
}
如果原内容本身包含 HTML，先把它当作 DOM/纯文本解析，再只对文本节点做匹配；不要用正则跨标签改写 HTML。高亮颜色也不能是唯一信息，应保持键盘焦点、读屏语义和足够的对比度。
五、百万级词典的工程取舍
PDF 中“百万关键词高亮”真正的难点不只是把双重循环换成 Trie：
- 构建成本：词典更新时不要在输入每个字符时同步重建整棵树，可在 Worker 中批量构建并用版本号切换。
- 内存：每个 JavaScript
Map和节点对象都有较大开销。超大词典可考虑压缩边、整数节点数组、分块加载或服务端检索；先用快照和真实词典测量。 - 主线程：文本很长时，把扫描拆成时间片或放入 Worker；Worker 只返回区间，不返回重复的大段文本。
- 结果数量：匹配结果本身可能是百万级，必须分页、窗口化或限制展示数量，不能把全部
<mark>节点一次性挂到 DOM。 - 版本一致性：词典和文本应带同一版本号，用户修改词典时取消旧扫描，避免旧结果覆盖新结果。
Trie 对前缀匹配很合适，但多模式匹配且要求一次线性扫描时，Aho-Corasick 可以在 Trie 上增加失败指针，把扫描复杂度降到 O(N + Z)（Z 为输出匹配数）。面试时说出这个边界，比笼统声称“Trie 一定是 O(n)”更准确。
六、面试回答模板
可以按以下顺序回答：