知识卡片
倒排索引与前向索引的差别
前向索引是「文档 → 它含哪些词」,本质仍要按文档顺序扫描:同一文档内多次出现的字符串可以不重复扫、用二分查找加速,但面对海量文档依旧慢。倒排索引把方向反过来,变成「词 → 含它的文档集合」,于是单个查询词的检索退化为一次字典查找,不需要碰任何一篇原文。
构建过程是「先扫后排」:扫描每篇文档,产出(文档号, 单词号, 出现位置)三元组;再按单词号排序,单词号相同按文档号排,两者都相同按出现位置排。排完就得到以词为键的倒排表。
保留「出现位置」不是冗余:有了位置才能判断两个词是否相邻(短语查询),也才能算命中密度、首现位置这类排序特征。这就是为什么存储组件回给计算组件的不只是文档列表,还有命中位置与频次——排序阶段的特征几乎全靠这张表。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第4章 搜索系统框架及原理 · 查看原书依据
还需要一个倒排索引的数据结构,让查询面向词和文档集,使搜索任务更快捷和简单。对于单个查询词,搜索就是字典查找的过程,不需要扫描所有文档。
参考来源
- 位置:《智能搜索和推荐系统:原理、算法与应用(零基础掌握搜索和推荐系统的原理、架构、算法) (智能系统与技术丛书)》第4章 搜索系统框架及原理(源文件:extracted/智能搜索和推荐系统:原理、算法与应用(零基础掌握搜索和推荐系统的原理、架构、算法) (智能系统与技术丛书)/_epub-src/text/part0061.html)
- 结论依据:原文对比前向索引的逐文档扫描与倒排索引的字典查找,直接支撑「查询方向反转带来复杂度下降」的结论。
- 原始内容:还需要一个倒排索引的数据结构,让查询面向词和文档集,使搜索任务更快捷和简单。对于单个查询词,搜索就是字典查找的过程,不需要扫描所有文档。