主流搜索引擎算法【查询】

主要有下面三种查询处理机制。

一次一文档(Doc at a Time)

以倒排列表中包含的文档为单位,每次将其中某个文档与查询的最终相似性得分计算完毕,然后开始计算另外一个文档的最终得分,直到所有文档的得分计算完毕为止。然后根据文档得分进行大小排序,输出得分最高的K个文档作为搜索结果输出,即完成了一次用户查询的响应。实际实现中,只需在内存中维护一个大小为K的优先级队列。输出 top K 个文档。

虚线箭头标出查询处理计算的前进方向。查询时,对于文档1而言,因为两个单词的倒排列表中都包含这个文档,所以可以根据各自的TF和IDF等参数计算文档和查询单词的相似性,之后将两个分数相加得到文档1和用户查询的相似性得分Score1。其他的也是类似计算。最后根据文档得分进行大小排序,输出得分最高的K隔文档作为搜索结果输出。

一次一单词(Term at a Time)

首先将某个单词对应的倒排列表中的每个文档ID都计算一个部分相似性得分

接着计算下一个单词倒排列表中包含的文档ID,即进行纵向计算,如果发现某个文档ID已经有了得分,则在原先得分基础上累加。当所有单词都处理完毕后,每个文档最终的相似性得分计算结束,之后按照大小排序,输出得分最高的K个文档作为搜索结果。 

跳跃指针(Skip Pointers)

基本思想:

1. 将一个倒排列表数据化整为零,切分为若干个固定大小的数据块,一个数据块作为一组,

2. 对于每个数据块,增加元信息来记录关于这个块的一些信息。

这样即使是面对压缩后的倒排列表,在进行倒排列表合并的时候也能有两个好处:

1、无须解压所有倒排列表项,只解压部分数据即可

2、无须比较任意两个文档ID。

从上面的查找过程可知,在查找数据时,只需要对其中一个数据块进行解压缩和文档编号查找即可获得结果,而不必解压所有数据,很明显加快查找速度,并节省内存空间。

缺点:增加指针比较操作的次数。

实践表明:假设倒排列表的长度为L(即包含L个文档ID),使用根号L作为块大小,则效果较好。

多字段索引

即对文档的多个字段进行索引。

多字段索引的方式:多索引方式、倒排列表方式和扩展列表方式。

1、多索引方式

针对每个不同的字段【标题、摘要、正文等】,分别建立一个索引,当用户指定某个字段作为搜索范围时,可以从相应的索引里提取结果。当用户没有指定特定字段时,搜索引擎会对所有字段都进行查找并合并多个字段的相关性得分,这样效率较低。

2、倒排列表方式

将字段信息存储在某个关键词对应的倒排列表内,在倒排列表中每个文档索引项信息的末尾追加字段信息,这样在读出用户查询关键词的倒排列表的同时,就可以根据字段信息,判断关键词是否在某个字段出现,以此来进行过滤。倒排列表方式示意图如下:

3、扩展列表方式

为每个字段建立一个列表,该列表记录了每个文档这个字段对应的出现位置信息。比如第一项<1,(1,4)>,代表对于文档1而言,其标题的位置为从第一个单词到第4个单词这个范围,其他项含义类似。

如下图:


对于查询而言,假设用户在标题字段搜索”搜索引擎“,通过倒排列表可以知道文档1、3、4包含这个查询词,接下来需要判断这些文档是否在标题字段中出现过查询词

短语查询

短语查询的本质是如何在索引中维护单词之间的顺序关系或者位置信息。

较常见的支持短语查询技术包括:位置信息索引、双词索引和短语索引。也可将三者结合使用。

1.位置信息索引(Position Index)

在索引中记录单词位置信息,可以很方便地支持短语查询。但是其付出的存储和计算代价很高。

分别按照词进行查询;再比较查询结果之间是不是同文档、是不是相邻

2. 双词索引(Nextword Index):首词+下词

统计数据表明,二词短语在短语中所占比例最大,因此针对二词短语提供快速查询,能解决短语查询的问题。但是这样做的话倒排列表个数会发生爆炸性增长。

    2个词典:首词、下词 词典

    查询方法:短语查询,“我的父亲” =>我_的 + 的_父亲 

     缺点:双词索引会使得索引急剧增大,一般实现并非对所有单词都建立双词索引,而是只对计算代价高的短语建立双词索引。

3.短语索引(Phrase Index)

    词典中加入多次短语并维护短语的倒排列表。

    查询方法:先短语查找,再词典查找

    缺点:就是不可能事先将所有短语都建好索引。通用做法就是挖掘出热门短语。下图是加入短语索引后的整体索引结构:

4、混合方法

首先在短语索引中查找,如果找到则返回结果,否则在双词索引中查找,如果找到则返回结果,否则从常规索引中对短语进行处理,充分发挥各自的优势。

短语查询用来对热门短语和高频短语进行索引,双词索引对包含停用词等高代价短语进行索引。

对于查询,系统首先在短语索引中查找,如果找到则返回结果,否则在双词索引中查找,如果找到则返回结果,否则从常规索引中对短语进行处理,这样就充分发挥各自的优势。

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容