倒排索引的结构

数据样例:

ID 文本
ID1 I like search engines
ID2 I search keywords in Google

正排索引

ID I like search engine keyword in Google
ID1 1 1 1 1 0 0 0
ID2 1 0 1 0 1 1 1

倒排索引

翻转

单词 ID1 ID2
I 1 1
like 1 0
search 1 1
engine 1 0
keyword 0 1
in 0 1
Google 0 1

合并

单词 ID
I ID1, ID2
like ID1
search ID1, ID2
engine ID1
keyword ID2
in ID2
Google ID2

倒排索引中的术语

文档(Document)

将构建索引的单位统称为“文档”

文档编号(Document ID)

将文档的标识信息称为“文档编号”。

倒排项(Posting)

在倒排索引中,将表示单词和文档编号对应关系的信息称为倒排项

倒排列表(PostingsList)

将各个单词的倒排项的集合称为倒排列表。

词典(Dictionary)

单词的集合

倒排文件(Inverted File)

倒排列表的集合

倒排索引的实现

文档级别的倒排文件(Document-level Inverted File)

倒排文件都只带有“各单词都出现在了哪个文档中”这一种信息。

单词级别的倒排文件(Word-level Inverted File)

倒排文件中不仅带有有关单词出现在了哪个文档中的信息,还带有单词出现在了文档中的什么位置(从开头数是第几个单词)这一信息。具体实现时,还有更多的维度。如:单词的开始位置、出现次数。

倒排项表示法:

  1. DocID; offset1, offset2, ...
单词 ID
I ID1;1, ID2;1
like ID1:2
search ID1:3, ID2:2
engine ID1:4
keyword ID2:3
in ID2:4
Google ID2:5

从倒排索引中查找短语

样例:

  • I search for a gas station because my car’s engine doesn’t start.
  • I like search engines

查找短语 search engine。

  1. 先从词典中找出单词search和engine
  2. 分别获取它们的倒排列表
  3. 算出这两个倒排列表中文档编号的交集。
  4. 确认search和engine是否是相邻出现
文档更新时间: 2020-03-11 03:15   作者:admin