本文承接查询原理(三),继续介绍查询原理。
图1:
点击查看大图
图2、图3是BooleanQuery的查询实例,在查询原理(三)中我们根据这个例子介绍了生成BulkScorer
的流程点,本篇文章根据这个例子,继续介绍图1中剩余的流程点。
图2:
图3:
在查询原理(三)文章中的生成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类如下所示:
1static class Bucket {
2 double score;
3 int freq;
4}
我们先说下freq,freq描述的是满足子查询条件的查询个数,例如图2中的文档8(文档号为8),因为文档号8中包含了"h"、"f"、"a",所以它满足子查询1、子查询2、子查询3的三个查询条件,故文档号8对应的Bucket对象的freq值为3。
图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。
图10:
Idf、boost、avgdl、docCount、docFreq:这些值在查询原理(二)中计算SimWeight时获得,不赘述
freq:子查询条件中的域值在文档(正在计算打分的文档)中的词频,即图4中的freqBuffer数组的数组元素
、b:BM25模型的两个调节因子,这两个值都是经验参数,默认值为 = 1.2、b = 0.75。值用来控制非线性的词频标准化(non-linear term frequency normalization)对打分的影响,b值用来控制文档长度对打分的影响
norm:该值描述的是文档长度对打分的影响,满足同一种查询的多篇文档, 会因为norm值的不同而影响打分值
cache数组:在查询原理(二)文章中,我们简单的提了一下cache生成的时机是在生成Weight
的流程中,下面详细介绍该数组。
图11:
图11中,横坐标为文档长度值,纵坐标为dl,由于数据跨度太大,无法看出文档长度值较小的区间的趋势图,故图12给出的是文档长度值在[1,100]区间的映射图
图12:
图13中,文档长度值在[1,50]区间的映射图,能进一步看出文档长度值小于等于40时,dl正比于文档长度值
图13:
图10中的normValue根据文档号从索引文件.nvd中获得,图14中用红框标识了一篇文档的文档号及其对应的normValue。
读取索引文件的过程不展开介绍,本人不想介绍的原因是,只要了解索引文件的数据结构(见索引文件数据结构 )是如何生成的,自然就明白如何读取索引文件~~
图14:
图15:
处理Buck数组的过程就是找出所有满足图3中minShouldMatch的文档,然后分别将文档号交给Collector收集器处理
某个遍历区间内的生成Bucket数组的过程在文档号合并(SHOULD)的文章中已经介绍,不过注意的是,在那篇文档中,没有考虑文档的打分值,故Bucket数组只介绍了freq。由于那篇中没有类似图3中的子查询4,所以遍历区间为[0,2147483647]。
对于本篇文章中图2、图3的例子,在遍历区间为[0,3)对应生成的Bucket数组如下所示,相比较文档号合并(SHOULD)中的内容,我们增加每篇文档的打分值,列出遍历区间为[0,3)的Bucket数组:
图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中的合并查询结果
流程也留到下一篇文章中介绍。
点击下载附件