在非精准 Top K 检索中,一个降低打分计算复杂度的重要思路是:尽可能地将计算放到离线环节,而不是在线环节。这样,在线环节我们就只需要进行简单的计算,然后快速截断就可以了。一个极端的方案就是根据检索结果的静态质量得分进行打分和截断。具体该怎么做呢?我们一起来看。
- 根据静态质量得分排序截断
所谓静态质量得分,指的是不考虑检索结果和实时检索词的相关性,打分计算仅和结果自身的质量有关。这样,所有的打分计算就都可以在离线环节完成了。也就是说,我们只需要根据离线算好的静态质量得分直接截断,就可以加速检索的过程了。这么说可能比较抽象,我们通过一个例子来解释一下。
以搜索引擎为例,我们可以不考虑搜索词和网页之间复杂的相关性计算,只根据网站自身的质量打分排序。比如说,使用 Page Rank 算法(Google 的核心算法,通过分析网页链接的引用关系来判断网页的质量)离线计算好每个网站的质量分,当一个搜索词要返回多个网站时,我们只需要根据网站质量分排序,将质量最好的 Top K 个网站返回即可。
不过,为了能快速返回 Top K 个结果,我们需要改造一下倒排索引中的 posting list 的组织方式。我们讲过,倒排索引的 posting list 都是按文档 ID 进行排序的。如果希望根据静态质量得分快速截断的话,那我们就应该将 posting list 按照静态质量得分,由高到低排序。对于分数相同的文档,再以文档 ID 二次排序。
这样一来,在检索的时候,如果只有一个关键词,那我们只需要查出该关键词对应的 posting list,截取前 k 个结果即可。但是如果我们要同时查询两个关键词,截断的过程就会复杂一些。尽管比较复杂,我们可以总结为两步:
● 第一步,我们取出这两个关键词的 posting list,但不直接截断;
● 第二步,我们对这两个 posting list 归并排序。留下分数和文档 ID 都相同的条目作为结果集合,当结果集合中的条目达到 k 个时,我们就直接结束归并。
如果是查询多个关键词,步骤也一样。那在这个过程中,我们为什么可以对这两个 posting list 进行归并排序呢?这是因为文档是严格按照静态质量得分排列的。如果文档 1 的分数大于文档 2,那在这两个 posting list 中文档 1 都会排在文档 2 前面。而且,对于分数相同的文档,它们也会按照 ID 进行二次排序。所以,任意的两个文档在不同的 posting list 中,是会具有相同的排序次序的。也因此,我们可以使用归并的方式来处理这两个 posting list。
总结来说,在使用静态质量得分选取非精准 Top K 个结果的过程中,因为没有实时的复杂运算,仅有简单的截断操作,所以它和复杂的精准检索打分相比,开销几乎可以忽略不计。因此,在对相关性要求不高的场景下,如果使用静态质量得分可以满足系统需求,这会是一个非常合适的方案。但如果应用场景对相关性的要求比较高,那我们还得采用其他考虑相关性的非精准检索方案。