知识卡片
用公共前缀换查询时间
Trie(单词查找树、键树)用空间换时间:根节点不含字符,其余每个节点只含一个字符,从根到某节点的路径拼起来就是该节点对应的字符串,同一节点的子节点字符互不相同。因此检索从根走到叶,时间复杂度只与查询词长度 m 有关,为 O(m),与词典规模无关。
省时的机制有两层:公共前缀的词共享同一条「串」,查词范围被前缀一路收窄;逐字符下跳靠映射直接定位子节点,不必遍历该节点的所有分支。它天然适合前缀召回场景,比如查询建议里按前缀匹配候选 Query。
代价有三条:实现比普通字典复杂;建词典时必须对每个词、每个字逐一处理,构建慢;虽然共享前缀省了部分空间,但要额外表达字与字、词与词之间的关系,实际占用反而更大。判断是否该用:查询以「前缀匹配、逐字推进」为主且词典可离线构建时收益明显;若只需精确整词查找,哈希表更简单也更省内存。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第4章 搜索系统框架及原理 · 查看原书依据
Trie树主要利用词的公共前缀缩小查词范围,通过状态间的映射关系避免所有字符的遍历,从而达到高效检索的目的。
参考来源
- 位置:《智能搜索和推荐系统:原理、算法与应用(零基础掌握搜索和推荐系统的原理、架构、算法) (智能系统与技术丛书)》第4章 搜索系统框架及原理(源文件:extracted/智能搜索和推荐系统:原理、算法与应用(零基础掌握搜索和推荐系统的原理、架构、算法) (智能系统与技术丛书)/_epub-src/text/part0061.html)
- 结论依据:原文把 Trie 的高效归因于「前缀收窄范围」与「映射避免遍历」两条机制,这是其 O(m) 复杂度的来源。
- 原始内容:Trie树主要利用词的公共前缀缩小查词范围,通过状态间的映射关系避免所有字符的遍历,从而达到高效检索的目的。