- 浏览: 412651 次
- 性别:
- 来自: 北京
最新评论
-
springdata_spring:
apache lucene开源框架demo使用实例教程源代码下 ...
有关Lucene的问题(6):Lucene的事务性 -
jaychang:
必须要感谢作者的分享,对理解Lucene的工作原理帮助很大
Lucene学习总结之一:全文检索的基本原理 -
yin_kaihua:
...
Lucene学习总结之三:Lucene的索引文件格式 (1) -
djh122:
...
Lucene 原理与代码分析完整版 -
wayne0830:
多谢楼主分享!
Lucene 原理与代码分析完整版
2.4、搜索查询对象
2.4.4、收集文档结果集合及计算打分
在函数IndexSearcher.search(Weight, Filter, int) 中,有如下代码:
TopScoreDocCollector collector = TopScoreDocCollector.create(nDocs, !weight.scoresDocsOutOfOrder());
search(weight, filter, collector);
return collector.topDocs();
2.4.4.1、创建结果文档收集器
TopScoreDocCollector collector = TopScoreDocCollector.create(nDocs, !weight.scoresDocsOutOfOrder());
public static TopScoreDocCollector create(int numHits, boolean docsScoredInOrder) { if (docsScoredInOrder) { return new InOrderTopScoreDocCollector(numHits); } else { return new OutOfOrderTopScoreDocCollector(numHits); } } |
其根据是否按照文档号从小到大返回文档而创建InOrderTopScoreDocCollector或者OutOfOrderTopScoreDocCollector,两者的不同在于收集文档的方式不同。
2.4.4.2、收集文档号
当创建完毕Scorer对象树和SumScorer对象树后,IndexSearcher.search(Weight, Filter, Collector) 有以下调用:
scorer.score(collector) ,如下代码所示,其不断的得到合并的倒排表后的文档号,并收集它们。
public void score(Collector collector) throws IOException { collector.setScorer(this); while ((doc = countingSumScorer.nextDoc()) != NO_MORE_DOCS) { collector.collect(doc); } } |
InOrderTopScoreDocCollector的collect函数如下:
public void collect(int doc) throws IOException { float score = scorer.score(); totalHits++; if (score <= pqTop.score) { return; } pqTop.doc = doc + docBase; pqTop.score = score; pqTop = pq.updateTop(); } |
OutOfOrderTopScoreDocCollector的collect函数如下:
public void collect(int doc) throws IOException { float score = scorer.score(); totalHits++; doc += docBase; if (score < pqTop.score || (score == pqTop.score && doc > pqTop.doc)) { return; } pqTop.doc = doc; pqTop.score = score; pqTop = pq.updateTop(); } |
从上面的代码可以看出,collector的作用就是首先计算文档的打分,然后根据打分,将文档放入优先级队列(最小堆)中,最后在优先级队列中取前N篇文档。
然而存在一个问题,如果要取10篇文档,而第8,9,10,11,12篇文档的打分都相同,则抛弃那些呢?Lucene的策略是,在文档打分相同的情况下,文档号小的优先。
也即8,9,10被保留,11,12被抛弃。
由上面的叙述可知,创建collector的时候,根据文档是否将按照文档号从小到大的顺序返回而创建InOrderTopScoreDocCollector或者OutOfOrderTopScoreDocCollector。
对于InOrderTopScoreDocCollector,由于文档是按照顺序返回的,后来的文档号肯定大于前面的文档号,因而当score <= pqTop.score的时候,直接抛弃。
对于OutOfOrderTopScoreDocCollector,由于文档不是按顺序返回的,因而当score<pqTop.score,自然直接抛弃,当score==pqTop.score的时候,则要比较后来的文档和前面的文档的大小,如果大于,则抛弃,如果小于则入队列。
2.4.4.3、打分计算
BooleanScorer2的打分函数如下:
- 将子语句的打分乘以coord
public float score() throws IOException { coordinator.nrMatchers = 0; float sum = countingSumScorer.score(); return sum * coordinator.coordFactors[coordinator.nrMatchers]; } |
ConjunctionScorer的打分函数如下:
- 将取交集的子语句的打分相加,然后乘以coord
public float score() throws IOException { float sum = 0.0f; for (int i = 0; i < scorers.length; i++) { sum += scorers[i].score(); } return sum * coord; } |
DisjunctionSumScorer的打分函数如下:
public float score() throws IOException { return currentScore; } currentScore计算如下: currentScore += scorerDocQueue.topScore(); 以上计算是在DisjunctionSumScorer的倒排表合并算法中进行的,其是取堆顶的打分函数。 public final float topScore() throws IOException { return topHSD.scorer.score(); } |
ReqExclScorer的打分函数如下:
- 仅仅取required语句的打分
public float score() throws IOException { return reqScorer.score(); } |
ReqOptSumScorer的打分函数如下:
- 上面曾经指出,ReqOptSumScorer的nextDoc()函数仅仅返回required语句的文档号。
- 而optional的部分仅仅在打分的时候有所体现,从下面的实现可以看出optional的语句的分数加到required语句的分数上,也即文档还是required语句包含的文档,只不过是当此文档能够满足optional的语句的时候,打分得到增加。
public float score() throws IOException { int curDoc = reqScorer.docID(); float reqScore = reqScorer.score(); if (optScorer == null) { return reqScore; } int optScorerDoc = optScorer.docID(); if (optScorerDoc < curDoc && (optScorerDoc = optScorer.advance(curDoc)) == NO_MORE_DOCS) { optScorer = null; return reqScore; } return optScorerDoc == curDoc ? reqScore + optScorer.score() : reqScore; } |
TermScorer的打分函数如下:
- 整个Scorer及SumScorer对象树的打分计算,最终都会源自叶子节点TermScorer上。
- 从TermScorer的计算可以看出,它计算出tf * norm * weightValue = tf * norm * queryNorm * idf^2 * t.getBoost()
public float score() { int f = freqs[pointer]; float raw = f < SCORE_CACHE_SIZE ? scoreCache[f] : getSimilarity().tf(f)*weightValue; return norms == null ? raw : raw * SIM_NORM_DECODER[norms[doc] & 0xFF]; } |
Lucene的打分公式整体如下,2.4.1计算了图中的红色的部分,此步计算了蓝色的部分:
打分计算到此结束。
2.4.4.4、返回打分最高的N篇文档
IndexSearcher.search(Weight, Filter, int)中,在收集完文档后,调用collector.topDocs()返回打分最高的N篇文档:
public final TopDocs topDocs() { return topDocs(0, totalHits < pq.size() ? totalHits : pq.size()); } |
public final TopDocs topDocs(int start, int howMany) { int size = totalHits < pq.size() ? totalHits : pq.size(); howMany = Math.min(size - start, howMany); ScoreDoc[] results = new ScoreDoc[howMany]; //由于pq是最小堆,因而要首先弹出最小的文档。比如qp中总共有50篇文档,想取第5到10篇文档,则应该先弹出打分最小的40篇文档。 for (int i = pq.size() - start - howMany; i > 0; i--) { pq.pop(); } populateResults(results, howMany); return newTopDocs(results, start); } |
protected void populateResults(ScoreDoc[] results, int howMany) { //然后再从pq弹出第5到10篇文档,并按照打分从大到小的顺序放入results中。 for (int i = howMany - 1; i >= 0; i--) { results[i] = pq.pop(); } } |
protected TopDocs newTopDocs(ScoreDoc[] results, int start) { return results == null ? EMPTY_TOPDOCS : new TopDocs(totalHits, results); } |
2.4.5、Lucene如何在搜索阶段读取索引信息
以上叙述的是搜索过程中如何进行倒排表合并以及计算打分。然而索引信息是从索引文件中读出来的,下面分析如何读取这些信息。
其实读取的信息无非是两种信息,一个是词典信息,一个是倒排表信息。
词典信息的读取是在Scorer对象树生成的时候进行的,真正读取这些信息的是叶子节点TermScorer。
倒排表信息的读取时在合并倒排表的时候进行的,真正读取这些信息的也是叶子节点TermScorer.nextDoc()。
2.4.5.1、读取词典信息
此步是在TermWeight.scorer(IndexReader, boolean, boolean) 中进行的,其代码如下:
public Scorer scorer(IndexReader reader, boolean scoreDocsInOrder, boolean topScorer) { TermDocs termDocs = reader.termDocs(term); if (termDocs == null) return null; return new TermScorer(this, termDocs, similarity, reader.norms(term.field())); } |
ReadOnlySegmentReader.termDocs(Term)是找到Term并生成用来读倒排表的TermDocs对象:
public TermDocs termDocs(Term term) throws IOException { ensureOpen(); TermDocs termDocs = termDocs(); termDocs.seek(term); return termDocs; } |
termDocs()函数首先生成SegmentTermDocs对象,用于读取倒排表:
protected SegmentTermDocs(SegmentReader parent) { this.parent = parent; this.freqStream = (IndexInput) parent.core.freqStream.clone();//用于读取freq synchronized (parent) { this.deletedDocs = parent.deletedDocs; } this.skipInterval = parent.core.getTermsReader().getSkipInterval(); this.maxSkipLevels = parent.core.getTermsReader().getMaxSkipLevels(); } |
SegmentTermDocs.seek(Term)是读取词典中的Term,并将freqStream指向此Term对应的倒排表:
public void seek(Term term) throws IOException { TermInfo ti = parent.core.getTermsReader().get(term); seek(ti, term); } |
TermInfosReader.get(Term, boolean)主要是读取词典中的Term得到TermInfo,代码如下: private TermInfo get(Term term, boolean useCache) { if (size == 0) return null; ensureIndexIsRead(); TermInfo ti; ThreadResources resources = getThreadResources(); SegmentTermEnum enumerator = resources.termEnum; seekEnum(enumerator, getIndexOffset(term)); enumerator.scanTo(term); if (enumerator.term() != null && term.compareTo(enumerator.term()) == 0) { ti = enumerator.termInfo(); } else { ti = null; } return ti; } |
在IndexReader打开一个索引文件夹的时候,会从tii文件中读出的Term index到indexPointers数组中,TermInfosReader.seekEnum(SegmentTermEnum enumerator, int indexOffset)负责在indexPointers数组中找Term对应的tis文件中所在的跳表区域的位置。
private final void seekEnum(SegmentTermEnum enumerator, int indexOffset) throws IOException { enumerator.seek(indexPointers[indexOffset], (indexOffset * totalIndexInterval) - 1, indexTerms[indexOffset], indexInfos[indexOffset]); } |
final void SegmentTermEnum.seek(long pointer, int p, Term t, TermInfo ti) { input.seek(pointer); position = p; termBuffer.set(t); prevBuffer.reset(); termInfo.set(ti); } |
SegmentTermEnum.scanTo(Term)在跳表区域中,一个一个往下找,直到找到Term:
final int scanTo(Term term) throws IOException { scanBuffer.set(term); int count = 0; //不断取得下一个term到termBuffer中,目标term放入scanBuffer中,当两者相等的时候,目标Term找到。 while (scanBuffer.compareTo(termBuffer) > 0 && next()) { count++; } return count; } |
public final boolean next() throws IOException { if (position++ >= size - 1) { prevBuffer.set(termBuffer); termBuffer.reset(); return false; } prevBuffer.set(termBuffer); //读取Term的字符串 termBuffer.read(input, fieldInfos); //读取docFreq,也即多少文档包含此Term termInfo.docFreq = input.readVInt(); //读取偏移量 termInfo.freqPointer += input.readVLong(); termInfo.proxPointer += input.readVLong(); if (termInfo.docFreq >= skipInterval) termInfo.skipOffset = input.readVInt(); indexPointer += input.readVLong(); return true; } |
TermBuffer.read(IndexInput, FieldInfos) 代码如下: public final void read(IndexInput input, FieldInfos fieldInfos) { this.term = null; int start = input.readVInt(); int length = input.readVInt(); int totalLength = start + length; text.setLength(totalLength); input.readChars(text.result, start, length); this.field = fieldInfos.fieldName(input.readVInt()); } |
SegmentTermDocs.seek(TermInfo ti, Term term)根据TermInfo,将freqStream指向此Term对应的倒排表位置:
void seek(TermInfo ti, Term term) { count = 0; FieldInfo fi = parent.core.fieldInfos.fieldInfo(term.field); df = ti.docFreq; doc = 0; freqBasePointer = ti.freqPointer; proxBasePointer = ti.proxPointer; skipPointer = freqBasePointer + ti.skipOffset; freqStream.seek(freqBasePointer); haveSkipped = false; } |
2.4.5.2、读取倒排表信息
当读出Term的信息得到TermInfo后,并且freqStream指向此Term的倒排表位置的时候,下面就是在TermScorer.nextDoc()函数中读取倒排表信息:
public int nextDoc() throws IOException { pointer++; if (pointer >= pointerMax) { pointerMax = termDocs.read(docs, freqs); if (pointerMax != 0) { pointer = 0; } else { termDocs.close(); return doc = NO_MORE_DOCS; } } doc = docs[pointer]; return doc; } |
SegmentTermDocs.read(int[], int[]) 代码如下:
public int read(final int[] docs, final int[] freqs) { final int length = docs.length; int i = 0; while (i < length && count < df) { //读取docid final int docCode = freqStream.readVInt(); doc += docCode >>> 1; if ((docCode & 1) != 0) freq = 1; else freq = freqStream.readVInt(); //读取freq count++; if (deletedDocs == null || !deletedDocs.get(doc)) { docs[i] = doc; freqs[i] = freq; ++i; } return i; } } |
评论
认真学习您的研究成果,我现在基本上对lucene的来龙去脉,有了几分了解,当然这个问题也迎刃而解。
在我的学习过程中,认为 深入理解 全文搜索的原理和索引文件的格式 非常重要,这是算法和数据结构所在,其余的都是对这个实现,因而当前两块知识弄清楚了,相当多的问题,都解决了。
另外,我想在lucene 搜索引擎领域里有所建树,希望得到您的指点。
认真学习您的研究成果,我现在基本上对lucene的来龙去脉,有了几分了解,当然这个问题也迎刃而解。
在我的学习过程中,认为 深入理解 全文搜索的原理和索引文件的格式 非常重要,这是算法和数据结构所在,其余的都是对这个实现,因而当前两块知识弄清楚了,相当多的问题,都解决了。
另外,我想成为一个lucene 搜索引擎领域里有所建树,希望得到您的指点。
谢谢的lz深入钻研,我看后受益匪浅,通过楼主的讲解,我得到了一个单词在文章出现的频
率,现在我想得到一个单词在文章出现的位置,有何思路?
盼复。
3q
发表评论
-
Lucene应用开发揭秘
2011-09-25 22:13 5352Lucene应用开发揭秘 ... -
Lucene应用开发揭秘上线了
2011-09-09 23:54 114Lucene应用开发揭秘 华章培训网地址:http:/ ... -
LinkedIn公司实现的实时搜索引擎Zoie
2010-11-29 21:19 8488一、总体架构 Zoie是linkedin公司基于Luce ... -
Lucene 原理与代码分析完整版
2010-06-13 01:30 34951Lucene 原理与代码分析系列文章已经基本告一段落, ... -
Lucene学习总结之十:Lucene的分词器Analyzer
2010-06-06 22:13 71401、抽象类Analyzer 其主要包含两个接口,用于生 ... -
Lucene学习总结之九:Lucene的查询对象
2010-05-19 02:39 2799Lucene学习总结之九:Lucene的查询对象(1) ... -
Lucene学习总结之九:Lucene的查询对象(3)
2010-05-19 02:37 29636、FilteredQuery FilteredQu ... -
Lucene学习总结之九:Lucene的查询对象(2)
2010-05-19 02:36 26035、SpanQuery 所谓SpanQ ... -
Lucene学习总结之九:Lucene的查询对象(1)
2010-05-19 02:34 6325Lucene除了支持查询语法以外,还可以自己构造查询对象 ... -
Lucene学习总结之八:Lucene的查询语法,JavaCC及QueryParser
2010-05-08 13:41 2388Lucene学习总结之八:Lucene的查询语法,Java ... -
Lucene学习总结之八:Lucene的查询语法,JavaCC及QueryParser(2)
2010-05-08 00:25 5538三、解析QueryParser.jj 3.1、声明Qu ... -
Lucene学习总结之八:Lucene的查询语法,JavaCC及QueryParser(1)
2010-05-08 00:20 8377一、Lucene的查询语法 Lucene所支持的查询语 ... -
Lucene学习总结之七:Lucene搜索过程解析
2010-04-05 14:52 2950本系列文章将详细描述几乎最新版本的Lucene的基本原理 ... -
Lucene学习总结之七:Lucene搜索过程解析
2010-04-04 22:54 2642本系列文章将详细描述几乎最新版本的Lucene的基本原理 ... -
Lucene学习总结之七:Lucene搜索过程解析(7)
2010-04-04 22:39 43612.4、搜索查询对象 2.4.3.2、并集Di ... -
Lucene学习总结之七:Lucene搜索过程解析(6)
2010-04-04 22:20 36172.4、搜索查询对象 2.4.3、进行倒排表合并 在 ... -
Lucene学习总结之七:Lucene搜索过程解析(5)
2010-04-04 21:26 43252.4、搜索查询对象 2.4.2、创建Score ... -
Lucene学习总结之七:Lucene搜索过程解析(4)
2010-04-04 20:46 44492.4、搜索查询对象 2.4.1.2、创建Weight ... -
Lucene学习总结之七:Lucene搜索过程解析(3)
2010-04-04 20:19 42982.3、QueryParser解析查询语句生成查询对象 代码 ... -
Lucene学习总结之七:Lucene搜索过程解析(2)
2010-04-04 20:10 4863二、Lucene搜索详细过程 为了解析Lucene对索引文件 ...
相关推荐
目 录 1. Lucene 学习总结 1.1 Lucene学习总结之一:全文检索的基本原理 ....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实例与解析。