返回主题:存储常用数据结构

知识卡片

结构图卡 · 2774.g

倒排索引反向查找

理解等级:未标注

全文检索要解决的问题是在大量非结构化文档里,根据任意一段文字内容快速定位包含它的文档。最原始的办法是顺序扫描:逐个打开每个文件、从头看到尾判断是否包含目标字符串,对小数据量可行,但面对大量文件会慢到不可用。顺序扫描慢的根本原因在于:非结构化数据天然保存的是”文件→字符串”的映射(已知文件求它包含哪些字符串很容易),而要搜索的信息恰恰相反,是”字符串→文件”的映射(已知字符串求哪些文件包含它)。全文检索的核心突破就是提前构建一份反向的索引——对每个词记录一份包含它的文档链表(倒排表),这样搜索时直接查倒排表就能拿到结果,不再需要逐个扫描原文档。这个索引构建过程只需做一次,之后可以反复搜索复用,这正是”一次索引、多次使用”相对于”每次都要重新顺序扫描”的核心优势,代价是索引本身的构建也需要时间和存储空间。

结构图:

flowchart LR
  A["非结构化数据天然存储:文件→字符串映射<br/>(已知文件求含哪些词,容易)"]
  A --> B["但检索需求相反:字符串→文件映射<br/>(已知词求含它的文件,难)"]
  B --> C["解法:提前构建倒排索引<br/>词典→每个词对应的文档链表(倒排表)"]
  C --> D["检索时直接查倒排表<br/>一次索引,多次使用,免去逐文件顺序扫描"]
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《企业大数据系统构建实战:技术、架构、实施与应用》第5章《大数据技术介绍》"5.1.4 全文检索"之"Lucene"(源文件:_epub-src/OEBPS/text00071.html) - 结论依据:原文说明"非结构化数据中所存储的信息是每个文件包含哪些字符串……而我们想搜索的信息是哪些文件包含此字符串……两者恰恰相反。于是如果索引总能够保存从字符串到文件的映射,则会大大提高搜索速度……于是将保存这种信息的索引称为倒排索引",并说明"顺序扫描是每次都要扫描,而创建索引的过程仅仅需要一次……这也是Lucene或者说全文检索技术相对于顺序扫描的优势之一:一次索引,多次使用",直接支撑本卡结构图。 - 原始内容:非结构化数据中所存储的信息是每个文件包含哪些字符串,即已知文件,欲求字符串相对容易……而我们想搜索的信息是哪些文件包含此字符串,即已知字符串,欲求文件……于是将保存这种信息的索引称为倒排索引(也称为反向索引)