知识卡片

普通读书笔记卡 · 2338.f.1

正排与倒排索引互补

理解等级:未标注

正排结构按文档标识找到文档内容或分词列表,倒排结构按词找到包含它的文档标识列表。查询多词时,先分词,再查各词的倒排列表并求交集;需要展示内容时可回到正排结构取文档。两种查找方向服务不同步骤。原文用 Map 示意,实际分词、查找和交集成本不能一概写成 O(1)。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《架构师之路》第54章《深入浅出搜索架构引擎、方案与细节(上)》(源文件:_epub-src/OEBPS/Text/54.html) - 结论依据:原文分别用 Map<url, list<item>> 和 Map<item, list<url>> 定义正排与倒排方向,并给出多词查询取交集的流程;复杂度断言只适用于局部示意。 - 原始内容:正排索引可以理解为Map<url, list<item>>,能够由网页快速(时间复杂度O(1))找到内容的一个数据结构 。 提问:什么是倒排索引(inverted index)? 回答 : 由item查询key的过程,是倒排索引。