- 浏览: 412901 次
- 性别:
- 来自: 北京
-
最新评论
-
springdata_spring：
apache lucene开源框架demo使用实例教程源代码下 ...
有关Lucene的问题(6)：Lucene的事务性 -
jaychang：
必须要感谢作者的分享，对理解Lucene的工作原理帮助很大
Lucene学习总结之一：全文检索的基本原理 -
yin_kaihua：
...
Lucene学习总结之三：Lucene的索引文件格式 (1) -
djh122：
...
Lucene 原理与代码分析完整版 -
wayne0830：
多谢楼主分享！
Lucene 原理与代码分析完整版
2.4、搜索查询对象
2.4.3.2、并集DisjunctionSumScorer(A OR B)
DisjunctionSumScorer中有成员变量List<Scorer> subScorers，是一个Scorer的链表，每一项代表一个倒排表，DisjunctionSumScorer就是对这些倒排表取并集，然后将并集中的文档号在nextDoc()函数中依次返回。
DisjunctionSumScorer还有一个成员变量minimumNrMatchers，表示最少需满足的子条件的个数，也即subScorer中，必须有至少minimumNrMatchers个Scorer都包含某个文档号，此文档号才能够返回。
为了描述清楚此过程，下面举一个具体的例子来解释倒排表合并的过程：
(1) 假设minimumNrMatchers = 4，倒排表最初如下：
(2) 在DisjunctionSumScorer的构造函数中，将倒排表放入一个优先级队列scorerDocQueue中(scorerDocQueue的实现是一个最小堆)，队列中的Scorer按照第一篇文档的大小排序。
|
private void initScorerDocQueue() throws IOException { scorerDocQueue = new ScorerDocQueue(nrScorers); for (Scorer se : subScorers) { if (se.nextDoc() != NO_MORE_DOCS) { //此处的nextDoc使得每个Scorer得到第一篇文档号。 scorerDocQueue.insert(se); } } } |
(3) 当BooleanScorer2.score(Collector)中第一次调用nextDoc()的时候，advanceAfterCurrent被调用。
|
public int nextDoc() throws IOException { if (scorerDocQueue.size() < minimumNrMatchers || !advanceAfterCurrent()) { currentDoc = NO_MORE_DOCS; } return currentDoc; } |
|
protected boolean advanceAfterCurrent() throws IOException { do { currentDoc = scorerDocQueue.topDoc(); //当前的文档号为最顶层 currentScore = scorerDocQueue.topScore(); //当前文档的打分 nrMatchers = 1; //当前文档满足的子条件的个数，也即包含当前文档号的Scorer的个数 do { //所谓topNextAndAdjustElsePop是指，最顶层(top)的Scorer取下一篇文档(Next)，如果能够取到，则最小堆的堆顶可能不再是最小值了，需要调整(Adjust，其实是downHeap())，如果不能够取到，则最顶层的Scorer已经为空，则弹出队列(Pop)。 if (!scorerDocQueue.topNextAndAdjustElsePop()) { if (scorerDocQueue.size() == 0) { break; // nothing more to advance, check for last match. } } //当最顶层的Scorer取到下一篇文档，并且调整完毕后，再取出此时最上层的Scorer的第一篇文档，如果不是currentDoc，说明currentDoc此文档号已经统计完毕nrMatchers，则退出内层循环。 if (scorerDocQueue.topDoc() != currentDoc) { break; // All remaining subscorers are after currentDoc. } //否则nrMatchers加一，也即又多了一个Scorer也包含此文档号。 currentScore += scorerDocQueue.topScore(); nrMatchers++; } while (true); //如果统计出的nrMatchers大于最少需满足的子条件的个数，则此currentDoc就是满足条件的文档，则返回true，在收集文档的过程中，DisjunctionSumScorer.docID()会被调用，返回currentDoc。 if (nrMatchers >= minimumNrMatchers) { return true; } else if (scorerDocQueue.size() < minimumNrMatchers) { return false; } } while (true); } |
advanceAfterCurrent具体过程如下：
- 最初，currentDoc=2，文档2的nrMatchers=1
- 最顶层的Scorer 0取得下一篇文档，为文档3，重新调整最小堆后如下图。此时currentDoc等于最顶层Scorer 1的第一篇文档号，都为2，文档2的nrMatchers为2。
- 最顶层的Scorer 1取得下一篇文档，为文档8，重新调整最小堆后如下图。此时currentDoc等于最顶层Scorer 3的第一篇文档号，都为2，文档2的nrMatchers为3。
- 最顶层的Scorer 3取得下一篇文档，为文档7，重新调整最小堆后如下图。此时currentDoc还为2，不等于最顶层Scorer 2的第一篇文档3，于是退出内循环。此时检查，发现文档2的nrMatchers为3，小于minimumNrMatchers，不满足条件。于是currentDoc设为最顶层Scorer 2的第一篇文档3，nrMatchers设为1，重新进入下一轮循环。
- 最顶层的Scorer 2取得下一篇文档，为文档5，重新调整最小堆后如下图。此时currentDoc等于最顶层Scorer 4的第一篇文档号，都为3，文档3的nrMatchers为2。
- 最顶层的Scorer 4取得下一篇文档，为文档7，重新调整最小堆后如下图。此时currentDoc等于最顶层Scorer 0的第一篇文档号，都为3，文档3的nrMatchers为3。
- 最顶层的Scorer 0取得下一篇文档，为文档5，重新调整最小堆后如下图。此时currentDoc还为3，不等于最顶层Scorer 0的第一篇文档5，于是退出内循环。此时检查，发现文档3的nrMatchers为3，小于minimumNrMatchers，不满足条件。于是currentDoc设为最顶层Scorer 0的第一篇文档5，nrMatchers设为1，重新进入下一轮循环。
- 最顶层的Scorer 0取得下一篇文档，为文档7，重新调整最小堆后如下图。此时currentDoc等于最顶层Scorer 2的第一篇文档号，都为5，文档5的nrMatchers为2。
- 最顶层的Scorer 2取得下一篇文档，为文档7，重新调整最小堆后如下图。此时currentDoc还为5，不等于最顶层Scorer 2的第一篇文档7，于是退出内循环。此时检查，发现文档5的nrMatchers为2，小于minimumNrMatchers，不满足条件。于是currentDoc设为最顶层Scorer 2的第一篇文档7，nrMatchers设为1，重新进入下一轮循环。
- 最顶层的Scorer 2取得下一篇文档，为文档8，重新调整最小堆后如下图。此时currentDoc等于最顶层Scorer 3的第一篇文档号，都为7，文档7的nrMatchers为2。
- 最顶层的Scorer 3取得下一篇文档，为文档9，重新调整最小堆后如下图。此时currentDoc等于最顶层Scorer 4的第一篇文档号，都为7，文档7的nrMatchers为3。
- 最顶层的Scorer 4取得下一篇文档，结果为空，Scorer 4所有的文档遍历完毕，弹出队列，重新调整最小堆后如下图。此时currentDoc等于最顶层Scorer 0的第一篇文档号，都为7，文档7的nrMatchers为4。
- 最顶层的Scorer 0取得下一篇文档，为文档9，重新调整最小堆后如下图。此时currentDoc还为7，不等于最顶层Scorer 1的第一篇文档8，于是退出内循环。此时检查，发现文档7的nrMatchers为4，大于等于minimumNrMatchers，满足条件，返回true，退出外循环。
(4) currentDoc设为7，在收集文档的过程中，DisjunctionSumScorer.docID()会被调用，返回currentDoc，也即当前的文档号为7。
(5) 当再次调用nextDoc()的时候，文档8, 9, 11都不满足要求，最后返回NO_MORE_DOCS，倒排表合并结束。
2.4.3.3、差集ReqExclScorer(+A -B)
ReqExclScorer有成员变量Scorer reqScorer表示必须满足的部分(required)，成员变量DocIdSetIterator exclDisi表示必须不能满足的部分，ReqExclScorer就是返回reqScorer和exclDisi的倒排表的差集，也即在reqScorer的倒排表中排除exclDisi中的文档号。
当nextDoc()调用的时候，首先取得reqScorer的第一个文档号，然后toNonExcluded()函数则判断此文档号是否被exclDisi排除掉，如果没有，则返回此文档号，如果排除掉，则取下一个文档号，看是否被排除掉，依次类推，直到找到一个文档号，或者返回NO_MORE_DOCS。
|
public int nextDoc() throws IOException { if (reqScorer == null) { return doc; } doc = reqScorer.nextDoc(); if (doc == NO_MORE_DOCS) { reqScorer = null; return doc; } if (exclDisi == null) { return doc; } return doc = toNonExcluded(); } |
|
private int toNonExcluded() throws IOException { //取得被排除的文档号 int exclDoc = exclDisi.docID(); //取得当前required文档号 int reqDoc = reqScorer.docID(); do { //如果required文档号小于被排除的文档号，由于倒排表是按照从小到大的顺序排列的，因而此required文档号不会被排除，返回。 if (reqDoc < exclDoc) { return reqDoc; } else if (reqDoc > exclDoc) { //如果required文档号大于被排除的文档号，则此required文档号有可能被排除。于是exclDisi移动到大于或者等于required文档号的文档。 exclDoc = exclDisi.advance(reqDoc); //如果被排除的倒排表遍历结束，则required文档号不会被排除，返回。 if (exclDoc == NO_MORE_DOCS) { exclDisi = null; return reqDoc; } //如果exclDisi移动后，大于required文档号，则required文档号不会被排除，返回。 if (exclDoc > reqDoc) { return reqDoc; // not excluded } } //如果required文档号等于被排除的文档号，则被排除，取下一个required文档号。 } while ((reqDoc = reqScorer.nextDoc()) != NO_MORE_DOCS); reqScorer = null; return NO_MORE_DOCS; } |
2.4.3.4、ReqOptSumScorer(+A B)
ReqOptSumScorer包含两个成员变量，Scorer reqScorer代表必须(required)满足的文档倒排表，Scorer optScorer代表可以(optional)满足的文档倒排表。
如代码显示，在nextDoc()中，返回的就是required的文档倒排表，只不过在计算score的时候打分更高。
|
public int nextDoc() throws IOException { return reqScorer.nextDoc(); } |
2.4.3.5、有关BooleanScorer及scoresDocsOutOfOrder
在BooleanWeight.scorer生成Scorer树的时候，除了生成上述的BooleanScorer2外， 还会生成BooleanScorer，是在以下的条件下：
- !scoreDocsInOrder：根据2.4.2节的步骤(c)，scoreDocsInOrder = !collector.acceptsDocsOutOfOrder()，此值是在search中调用TopScoreDocCollector.create(nDocs, !weight.scoresDocsOutOfOrder())的时候设定的，scoreDocsInOrder = !weight.scoresDocsOutOfOrder()，其代码如下：
|
public boolean scoresDocsOutOfOrder() { int numProhibited = 0; for (BooleanClause c : clauses) { if (c.isRequired()) { return false; } else if (c.isProhibited()) { ++numProhibited; } } if (numProhibited > 32) { return false; } return true; } |
- topScorer：根据2.4.2节的步骤(c)，此值为true。
- required.size() == 0，没有必须满足的子语句。
- prohibited.size() < 32，不需不能满足的子语句小于32。
从上面可以看出，最后两个条件和scoresDocsOutOfOrder函数中的逻辑是一致的。
下面我们看看BooleanScorer如何合并倒排表的：
|
public int nextDoc() throws IOException { boolean more; do { //bucketTable等于是存放合并后的倒排表的文档队列 while (bucketTable.first != null) { //从队列中取出第一篇文档，返回 current = bucketTable.first; bucketTable.first = current.next; if ((current.bits & prohibitedMask) == 0 && (current.bits & requiredMask) == requiredMask && current.coord >= minNrShouldMatch) { return doc = current.doc; } } //如果队列为空，则填充队列。 more = false; end += BucketTable.SIZE; //按照Scorer的顺序，依次用Scorer中的倒排表填充队列，填满为止。 for (SubScorer sub = scorers; sub != null; sub = sub.next) { Scorer scorer = sub.scorer; sub.collector.setScorer(scorer); int doc = scorer.docID(); while (doc < end) { sub.collector.collect(doc); doc = scorer.nextDoc(); } more |= (doc != NO_MORE_DOCS); } } while (bucketTable.first != null || more); return doc = NO_MORE_DOCS; } |
|
public final void collect(final int doc) throws IOException { final BucketTable table = bucketTable; final int i = doc & BucketTable.MASK; Bucket bucket = table.buckets[i]; if (bucket == null) table.buckets[i] = bucket = new Bucket(); if (bucket.doc != doc) { bucket.doc = doc; bucket.score = scorer.score(); bucket.bits = mask; bucket.coord = 1; bucket.next = table.first; table.first = bucket; } else { bucket.score += scorer.score(); bucket.bits |= mask; bucket.coord++; } } |
从上面的实现我们可以看出，BooleanScorer合并倒排表的时候，并不是按照文档号从小到大的顺序排列的。
从原理上我们可以理解，在AND的查询条件下，倒排表的合并按照算法需要按照文档号从小到大的顺序排列。然而在没有AND的查询条件下，如果都是OR，则文档号是否按照顺序返回就不重要了，因而scoreDocsInOrder就是false。
因而上面的DisjunctionSumScorer，其实"apple boy dog"是不能产生DisjunctionSumScorer的，而仅有在有AND的查询条件下，才产生DisjunctionSumScorer。
我们做实验如下：
对于查询语句"apple boy dog"，生成的Scorer如下：
|
scorer BooleanScorer (id=34) |
对于查询语句"+hello (apple boy dog)"，生成的Scorer对象如下：
|
scorer BooleanScorer2 (id=40) //weight(contents:apple) //weight(contents:boy) //weight(contents:cat) |
- 大小: 17.1 KB
- 大小: 13.5 KB
- 大小: 17.2 KB
- 大小: 16.1 KB
- 大小: 16.4 KB
- 大小: 16.1 KB
- 大小: 15.3 KB
- 大小: 15.2 KB
- 大小: 14.4 KB
- 大小: 14.1 KB
- 大小: 15.2 KB
- 大小: 10.5 KB
- 大小: 14.2 KB
- 大小: 15.4 KB
- 大小: 15.8 KB
发表评论
-
Lucene应用开发揭秘
2011-09-25 22:13 5357Lucene应用开发揭秘 ... -
Lucene应用开发揭秘上线了
2011-09-09 23:54 114Lucene应用开发揭秘 华章培训网地址：http:/ ... -
LinkedIn公司实现的实时搜索引擎Zoie
2010-11-29 21:19 8490一、总体架构 Zoie是linkedin公司基于Luce ... -
Lucene 原理与代码分析完整版
2010-06-13 01:30 34962Lucene 原理与代码分析系列文章已经基本告一段落， ... -
Lucene学习总结之十：Lucene的分词器Analyzer
2010-06-06 22:13 71461、抽象类Analyzer 其主要包含两个接口，用于生 ... -
Lucene学习总结之九：Lucene的查询对象
2010-05-19 02:39 2801Lucene学习总结之九：Lucene的查询对象(1) ... -
Lucene学习总结之九：Lucene的查询对象(3)
2010-05-19 02:37 29666、FilteredQuery FilteredQu ... -
Lucene学习总结之九：Lucene的查询对象(2)
2010-05-19 02:36 26055、SpanQuery 所谓SpanQ ... -
Lucene学习总结之九：Lucene的查询对象(1)
2010-05-19 02:34 6328Lucene除了支持查询语法以外，还可以自己构造查询对象 ... -
Lucene学习总结之八：Lucene的查询语法，JavaCC及QueryParser
2010-05-08 13:41 2390Lucene学习总结之八：Lucene的查询语法，Java ... -
Lucene学习总结之八：Lucene的查询语法，JavaCC及QueryParser(2)
2010-05-08 00:25 5543三、解析QueryParser.jj 3.1、声明Qu ... -
Lucene学习总结之八：Lucene的查询语法，JavaCC及QueryParser(1)
2010-05-08 00:20 8384一、Lucene的查询语法 Lucene所支持的查询语 ... -
Lucene学习总结之七：Lucene搜索过程解析
2010-04-05 14:52 2954本系列文章将详细描述几乎最新版本的Lucene的基本原理 ... -
Lucene学习总结之七：Lucene搜索过程解析
2010-04-04 22:54 2644本系列文章将详细描述几乎最新版本的Lucene的基本原理 ... -
Lucene学习总结之七：Lucene搜索过程解析(8)
2010-04-04 22:43 76582.4、搜索查询对象 2.4.4、收集文档结果集 ... -
Lucene学习总结之七：Lucene搜索过程解析(6)
2010-04-04 22:20 36192.4、搜索查询对象 2.4.3、进行倒排表合并 在 ... -
Lucene学习总结之七：Lucene搜索过程解析(5)
2010-04-04 21:26 43292.4、搜索查询对象 2.4.2、创建Score ... -
Lucene学习总结之七：Lucene搜索过程解析(4)
2010-04-04 20:46 44502.4、搜索查询对象 2.4.1.2、创建Weight ... -
Lucene学习总结之七：Lucene搜索过程解析(3)
2010-04-04 20:19 43022.3、QueryParser解析查询语句生成查询对象 代码 ... -
Lucene学习总结之七：Lucene搜索过程解析(2)
2010-04-04 20:10 4865二、Lucene搜索详细过程 为了解析Lucene对索引文件 ...
相关推荐
1.18 Lucene学习总结之七：Lucene搜索过程解析(7) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .286 1.19 Lucene学习总结之七：Lucene搜索过程解析(8) . . . . . . . . . . . . ....
官网的lucene全文检索引擎工具包，下载后直接解压缩即可使用
由于林良益先生在2012之后未对IKAnalyzer进行更新，后续lucene分词接口发生变化，导致不可使用，所以此jar包支持lucene6.0以上版本
Lucene查询解析器 Lucene查询字符串解析器，用作Web api查询或过滤器字符串。 基本代码来自 使用这种语言的示例查询： name: apple price: > 100 price: > 100 AND active: = 1 product.price: > 100 AND ...
lucene-搜索过程源码解析-Score树
lucene搜索端uml时序图，lucene源码解析 图比较大，看不清，可以下载【sd-search.svg】后再用浏览器打开 使用starUML画图，可以下载【lucene.mdj】后打开，编辑 前提 只考虑最简单的查询，比如只对一个字段，用一个...
本文并给出一个经典的lucene全文收索例子代码。该例子功能是从磁盘文档建立索引，搜索该文档中的哪个TXT文件包含所搜索内容。最后再大致介绍Lucene的结构模块，应用流程希望对网友能有帮助。
----使用iText解析PDF 文档代码 PDFBoxHello.java ----------- --PDFBox测试代码 PDFBoxLuceneIndex.java ------ --PDFBox创建PDF文件的Lucene索引 PDFBoxPathIndex.java ------- --PDFBox创建指定目录PDF文档...
Lucene搜索过程的核心类 IndexSearcher：用于搜索IndexWriter创建的索引 Term：用于搜索的一个基本单元包括了一对字符串元素，与Field相对应 Query ：抽象的查询类 TermQuery：最基本的查询类型，用来匹配特定Field...
Lucene搜索引擎开发权威经典 光盘 于天恩 著 中国铁道出版社出版 2008-10 这本书基于Lucene的当前最新版本（2.1）精解了Lucene搜索引擎的相关知识，从基础知识到应用开发，精练简洁，恰到好处。 本书共包括16章，...
lucene-搜索过程源码解析-1-Weight生成.txt
详细分析lucene搜索的实现过程，通过代码解析，会对lucene的搜索实现过程有一个更加深刻的认识
Eclipse工程/ch7：原书第七章和第九章的Eclipse工程文件 使用PDFBox解析PDF文件 使用xpdf解析中文PDF文件 使用POI解析WORD和Excel文件 使用Jacob解析WORD文件 Google的Search API的使用 安装：直接在Eclipse中...
描述了Lucene中如何使用FST算法构建term的内存索引，使用了很多图，直观的展现了FST图的构建流程，能够对想了解lucene内部实现机制原理的同学有帮助。
Eclipse工程/ch7：原书第七章和第九章的Eclipse工程文件 使用PDFBox解析PDF文件 使用xpdf解析中文PDF文件 使用POI解析WORD和Excel文件 使用Jacob解析WORD文件 Google的Search API的使用 安装：直接在Eclipse中...
Lucene 是一个开源、高度可扩展的搜索引擎库，可以从 Apache Software Foundation 获取。您可以将 Lucene 用于商业和开源应用程序。Lucene 强大的 API 主要关注文本索引和搜索。它可以用于为各种应用程序构建搜索...
开源全文搜索工具包Lucene2.9.1的使用。 1. 搭建Lucene的开发环境：在classpath中添加lucene-core-2.9.1.jar包 2. 全文搜索的两个工作: 建立索引文件,搜索索引. 3. Lucene的索引文件逻辑结构 1) 索引(Index)由...
这是一篇公司的内部培训教材，其中中的内容涵盖LUCENE的方方面面，从源代码角度深入剖析LUCENE，如果要对LUCENE有更加深入的了解（专家级别），这篇技术文档必不可少。 前提：对LUCENE有一定程度的了解,否则会让你云...
FileReaderAll函数用来从文件中读取字符串，默认编码为“GBK”。在创建完最重要的IndexWriter之后，就开始遍历需要索引的文件，构造对应的Document和Filed类，最终通过IndexWriter的addDocument函数开始索引。...
Lucene的功能请打，方法众多。主要介绍了Lucene的功能模块及其调用代码，实际使用中可以具体修改。最后还有一个常见的Lucene实例与解析。