至此为止,我们就讲解完了倒排索引的概要。下面,就让我们再来略微详细地了解一下倒排索引吧。 倒排索引= 词典+ 倒排文件 倒排索引是由单词的集合“词典”和倒排列表的集合“倒排文件”构成的。词典和倒排文件以及作为这二者构成要素的单词和倒排列表的关系如图1-2 所示。 图 1-2 倒排索引的结构 词典中的每个单词都持有一段引用信息,指明了对应着该单词的倒排列表。利用这段引用信息,我们就可以从词典中的各个单词那里获取到相应的倒排列表了。 从倒排索引中查找单词 若要从倒排索引中查找出包含了某个单词的文档,只需要先从词典中找到该单词,然后获取与之对应的倒排列表,最后从倒排列表中获取文档编号即可。这里只是改用检索的术语将之前讲解过的方法描述了一遍,所以若有疑问的话,请再重新读读前面的内容。 那么,我们又该如何查找同时包含了多个单词的文档呢?查找时只需要先从词典中找出各个单词,然后分别获取这些单词的倒排列表并加在一起,由此计算出包含在各个倒排列表中的文档编号的交集。举例来说,假设我们使用的是上一节生成的那个倒排索引,并要从中查找出既包含search 又包含engine 的文档。那么根据上述方法,一旦获取到了search 和engine 分别对应的倒排列表,就可以知道search 包含在页面1(P1)和页面2(P2)中,engine 包含在页面1(P1)中。而接下来,只要再计算出这两个倒排列表的交集,就又可以知道同时包含这两个单词的文档是文档1(P1)。 将单词的位置信息加入倒排文件中 到目前为止,我们见到的倒排文件都只带有“各单词都出现在了哪个文档中”这一种信息。这样的倒排文件称为“文档级别的倒排文件”(Document-level Inverted File)。 除此以外,还有另一种倒排文件,称作“单词级别的倒排文件”(Word-level Inverted File)。这种倒排文件中不仅带有有关单词出现在了哪个文档中的信息,还带有单词出现在了文档中的什么位置(从开头数是第几个单词)这一信息。 在单词级别的倒排文件中,各个倒排项的表示方法如下所示。 DocID;offset1, offset2... 还是以刚刚使用过的两个文档为例,从头数的话,单词search 是文档1(P1)中的第3 个单词,是文档2(P2)中的第2 个单词,因此其倒排列表是 search: D1;3, D2;2 如果把各个单词在文档中的出现位置都如此考察一遍,就可以得到如下所示的单词级别的倒排文件了。 engine: D1;4 Google: D2;5 I: D1;1,D2;1 in: D2;4 keyword: D2;3 like: D1;2 search: D1;3, D2;2 随后我们要介绍的从倒排索引中查找短语,或是计算检索结果中文档的得分等场景中都会用到这种单词的位置信息。 从倒排索引中查找短语 我们刚刚讲解的是如何利用文档级别的倒排文件查找同时包含search 和engine 的文档。但是利用这种方法得到的检索结果,未必都是关于搜索引擎(search engine)的文档。例如,虽然下面的文档也同样包含了search 和engine,但却与搜索引擎无关。 I search for a gas station because my car’s engine doesn’t start. (因为汽车的引擎发动不起来了,所以我要找加油站。) 因此,要想查找关于搜索引擎的文档,就需要从倒排索引中找出含有短语search engine 的文档。而要想从倒排索引中查找短语,就需要使用刚刚介绍过的单词级别的倒排文件①。 ----———— ① 也可以使用文档级别的倒排文件找出含有短语search engine 的文档,方法是在 检索完各个单词之后,用全扫描的方式在原文档中检索该短语。但是,这样做的效率通常较低。 ———————— 在使用单词级别的倒排文件查找短语时,前几步与使用文档级别的倒排列表相同,即也是先从词典中找出单词search 和engine,然后分别获取它们的倒排列表,最后算出这两个倒排列表中文档编号的交集。但是到这里还没有结束,查找短语时还需要确认search 和engine 是否是相邻出现的。在上面的例子中,由于search 和engine 都出现在了文档1中,并且search 是文档1 中的第3 个单词,engine 是第4 个单词,这说明这两个单词是相邻出现的,所以可以得出结论,短语search engine 出现在了文档1 中。