数据结构——倒排索引

分类:数据结构
作者:ZhouJianGuo
发布时间:2020年02月25日 12:11:22

一、简介:图一是一个文档的结构,文档由许多的单词组成。

图一:文档结构

  假设我们有3个文档,为了方便管理,我们需要对其建立如图二所示的文档集合。

图二:示例文档集合

  当我们需要查询所有包含关键词word2的文档时,我们需要把三个文档都查一遍如图三所示,并把包含有word2关键此词的文档file1和file2作为检索结果返回。这样的检索方式就叫做正排索引

图三:word2关键词的检索结果

  很明显,这样的检索方式有着很大的问题,所期望的是获取所有含有word2的文档,但是却要对每个文档进行完全检索,于是将文档与单词的关系逆转过来,如图四所示,这样就可以直接通过检索关键词的方式直接获取哪些文档包含该关键词,节省了大量的检索时间。

图四:调整后的索引结构

二、概念介绍:

  1.文档:以文本形式存储的文件(一个网页,一封邮件等等),里面包含多个关键词信息。

  2.文档集合:由多个文档组成的集合称之为文档集合。

  3.文档编号(id):管理者会对文档集合进行编号,类似于数据表的主键,方便管理。

  4.单词词典:根据文档集合整理出来的单词集合,一般都会在单词字符串后添加文档的文件地址从而实现关键词对文档的映射,即:(单词,文件地址)

  5.倒排列表:倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息,每条记录称为一个倒排项。根据倒排列表,即可获知哪些文档包含某个单词。

  6.倒排文件:倒排列表存储的物理形式,即倒排列表存储形式。

 

版权声明:本站所有文章除特别声明外,转载请注明出处!
本文最后修改于:2020-03-01 21:42:55
许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

发表评论
请先登录后再发表评论~
评论 共1条
{{articleCommentItem.username}}
评论于 {{articleCommentItem.createBy}}
{{articleCommentItem.content}}
{{replyItem.username}}
回复于 {{replyItem.createBy}}
@{{replyItem.targetUsername}} {{replyItem.content}}

@CopyRight 2019 ZhouJianGuo版权所有
苏ICP备19061991号