查询原理(四)

  本文承接查询原理(三),继续介绍查询原理。

查询原理流程图

图1:

点击查看大图

  图2、图3是BooleanQuery的查询实例,在查询原理(三)中我们根据这个例子介绍了生成BulkScorer的流程点,本篇文章根据这个例子,继续介绍图1中剩余的流程点。

图2:

图3:

Collector处理查询结果

  查询原理(三)文章中的生成BulkScorer流程点,我们获得了每一个子查询对应的文档号跟词频,见图4,结合查询原理(二)文章中的生成Weight流程点,我们就可以在当前流程点获得满足查询条件(图3)的文档集合及对应的文档打分值。

图4:

Collector处理查询结果的流程图

图5:

是否还有遍历区间?

图6:

  图4中的子查询4,该查询对应的文档号集合不是用户期望返回的,那么可以根据这些文档号划分出多个左闭右开的遍历区间。

  满足子查询4条件的文档号集合为3、8,故可以划分出3个遍历区间:

  随后从每个遍历区间中找到满足子查询1、子查询2、子查询3且minShouldMatch为2的文档号,minShouldMatch通过图3中的builder.setMinimumNumberShouldMatch方法设置,描述的是用户期望的文档必须至少满足子查询1、子查询2、子查询3中的任意两个(minShouldMatch)的查询条件。

  为什么要使用遍历区间

处理子查询的所有文档号

图7:

  该流程处理子查询的所有文档号,先看下Bucket数组,该数组的数组下标用来描述文档号,数组元素是Bucket对象,它用来记录该文档的打分值跟满足子查询条件的查询个数,Bucket类如下所示:

freq

  我们先说下freq,freq描述的是满足子查询条件的查询个数,例如图2中的文档8(文档号为8),因为文档号8中包含了"h"、"f"、"a",所以它满足子查询1、子查询2、子查询3的三个查询条件,故文档号8对应的Bucket对象的freq值为3。

score

  图8为BM25模型的理论打分公式:

图8:

  图17源自于<<这就是搜索引擎>>,作者:张俊林。

  图9为在Lucene7.5.0版本中BM25模型的具体实现BM25Similarity的公式:

图9:

  从图9的公式可以看出,一篇文档的打分值是一个累加值,累加的过程即更新Bucket数组的流程,如果一篇文档满足多个子查询的条件,那么该文档的打分值是每个子查询对这篇文档打分的和值。

  例如图2中的文档0,该文档包含了两种term,分别是 "a","h",故文档0满足图3中的两个子查询的条件,分别是子查询1、子查询3,所以文档0的打分值是两个查询对这篇文档打分的和值,最后将这个和值添加到Bucket数组的数组下标为0(因为文档0的文档号是0)的数组元素Bucket对象中,该对象的freq的值同理会被赋值为2。

BM25Similarity打分公式

图10:

图11:

  图11中,横坐标为文档长度值,纵坐标为dl,由于数据跨度太大,无法看出文档长度值较小的区间的趋势图,故图12给出的是文档长度值在[0,100]区间的映射图

图12:

  图13中,文档长度值在[0,50]区间的映射图,能进一步看出文档长度值小于等于40时,dl正比于文档长度值

图13:

  图10中的normValue根据文档号从索引文件.nvd中获得,图14中用红框标识了一篇文档的文档号及其对应的normValue。

  读取索引文件的过程不展开介绍,本人不想介绍的原因是,只要了解索引文件的数据结构(见索引文件数据结构 )是如何生成的,自然就明白如何读取索引文件~~

图14:

处理Bucket数组

图15:

  处理Buck数组的过程就是找出所有满足图3中minShouldMatch的文档,然后分别将文档号交给Collector收集器处理

  某个遍历区间内的生成Bucket数组的过程在文档号合并(SHOULD)的文章中已经介绍,不过注意的是,在那篇文档中,没有考虑文档的打分值,故Bucket数组只介绍了freq。由于那篇中没有类似图3中的子查询4,所以遍历区间为[0,2147483647]。

  对于本篇文章中图2、图3的例子,在遍历区间为[0,3)对应生成的Bucket数组如下所示,相比较文档号合并(SHOULD)中的内容,我们增加每篇文档的打分值,列出遍历区间为[0,3)的Bucket数组:

遍历区间[0,3)

图16:

  在图16中,文档0跟文档2的freq 大于等于minShouldMatch(2),故这两篇文档满足图3中的查询要求。

结语

  至此,我们介绍了单线程下的查询原理的所有流程点,但还有一个很重要的逻辑没有介绍,那就是在图5的是否还有未处理的子查询流程点,我们并没有介绍在还有未处理的子查询的情况下,如何选择哪个子查询进行处理,这个逻辑实际是个优化的过程,可能可以减少遍历区间的处理,以图2、图3为例,尽管根据子查询4,我们得出3个遍历区间,实际上我们只要处理[0,3)、[4,8)这两个逻辑区间,至于原因会在下一篇文档中展开。

  图2.、图3的demo点击这里:https://github.com/LuXugang/Lucene-7.5.0/blob/master/LuceneDemo/src/main/java/lucene/query/BooleanQuerySHOULDNOTTEST.java

  另外对于多线程的情况,图1中的合并查询结果流程也留到下一篇文章中介绍。

点击下载附件