前端知识库字典树 高频追问 Q&A
用短答复习 Trie 的终止标记、复杂度、重叠关键词和 Aho-Corasick 边界。
约 2 分钟算法 · 字典树 · Trie · 面试
字典树 高频追问 Q&A
1. Q: Trie 为什么适合前缀查询？
A: 每条根到节点的路径就是一个前缀，查询只需沿字符边走 L 步，不必扫描所有词。节点上的终止标记用来区分“完整词”和“只是某个词的前缀”。（深入阅读：字典树基础知识速览）
2. Q: Trie 的空间复杂度是多少？
A: 最坏与词典总字符数 S 同阶，但每个节点的 Map、数组或对象都有常数开销。共享前缀越多越省空间；稀疏大词典要评估节点表示和压缩方案。（深入阅读：字典树基础知识速览、关键词匹配与高亮）
3. Q: 词典有一百万个关键词，Trie 一定够吗？
A: 不一定。还要看总字符数、更新频率、结果数量和内存预算。多模式匹配可比较 Aho-Corasick；词典更新频繁或只查完整词时，哈希表可能更合适。（深入阅读：关键词匹配与高亮）
4. Q: 关键词互相包含时怎么高亮？
A: 先定义策略。最长匹配适合避免短词抢占长词；若要保留所有结果，就记录多个终止节点，再用区间选择算法处理重叠，不能在扫描中无规则覆盖。（深入阅读：关键词匹配与高亮）
5. Q: 为什么不直接用正则或 includes？
A: 词典很小、规则简单时可以用；关键词规模大时，重复遍历词典会让每个文本位置承担与词数相关的成本。Trie 共享公共前缀，Aho-Corasick 还能一次线性扫描多模式。（深入阅读：关键词匹配与高亮）
6. Q: 高亮结果如何避免 XSS？
A: 不把关键词和原文拼入 innerHTML。把文本作为 textContent/文本节点插入 <mark>，或在可信 sanitizer 后再渲染；原始 HTML 应先按文本节点处理。（深入阅读：关键词匹配与高亮）