知识卡片

普通读书笔记卡 · 9812.i · 生成模型:DeepSeek-V4.1-Flash

用公共前缀换查询时间

理解等级:高级

Trie(单词查找树、键树)用空间换时间:根节点不含字符,其余每个节点只含一个字符,从根到某节点的路径拼起来就是该节点对应的字符串,同一节点的子节点字符互不相同。因此检索从根走到叶,时间复杂度只与查询词长度 m 有关,为 O(m),与词典规模无关。

省时的机制有两层:公共前缀的词共享同一条「串」,查词范围被前缀一路收窄;逐字符下跳靠映射直接定位子节点,不必遍历该节点的所有分支。它天然适合前缀召回场景,比如查询建议里按前缀匹配候选 Query。

代价有三条:实现比普通字典复杂;建词典时必须对每个词、每个字逐一处理,构建慢;虽然共享前缀省了部分空间,但要额外表达字与字、词与词之间的关系,实际占用反而更大。判断是否该用:查询以「前缀匹配、逐字推进」为主且词典可离线构建时收益明显;若只需精确整词查找,哈希表更简单也更省内存。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能搜索和推荐系统:原理、算法与应用(零基础掌握搜索和推荐系统的原理、架构、算法) (智能系统与技术丛书)》第4章 搜索系统框架及原理(源文件:extracted/智能搜索和推荐系统:原理、算法与应用(零基础掌握搜索和推荐系统的原理、架构、算法) (智能系统与技术丛书)/_epub-src/text/part0061.html) - 结论依据:原文把 Trie 的高效归因于「前缀收窄范围」与「映射避免遍历」两条机制,这是其 O(m) 复杂度的来源。 - 原始内容:Trie树主要利用词的公共前缀缩小查词范围,通过状态间的映射关系避免所有字符的遍历,从而达到高效检索的目的。