Lucene
全文检索的心,天才的想法。
- 一个高效的,可扩展的,全文检索库。
- 全部用 Java 实现,无须配置。
- 仅支持纯文本文件的索引(Indexing)和搜索(Search)。
- 不负责由其他格式的文件抽取纯文本文件,或从网络中抓取文件的过程。
基于《Lucene 原理与代码分析 觉先 (forfuture1978)》
核心就是将进来的数据,创建进行倒排索引。以及将搜索的内容根据倒排索引来搜索,避免了遍历搜索的速度消耗。
一种牺牲空间,换取时间的手段。
image索引的创建
将简单的文本数据,处理成易于根据单词查询的格式。便于全文检索。
image数据查询
对于搜索的条件也会进行同样的分词手法,
- 把数据进行分割,去除is are那种无意义的词。
- 动名词变词根之类的操作。
- 然后去查询存储了这些词的文档链表,进行搜索条件中的与或非操作。
- 最后得到的文档进行权重分析,排序。
- 最后得到数据。
权重计算
计算权重(Termweight)的过程。 影响一个词(Term)在一篇文档中的重要性主要有两个因素:
- Term Frequency (tf):即此 Term 在此文档中出现了多少次。tf 越大说明越重要。
- Document Frequency (df):即有多少文档包次 Term。df 越大说明越不重要。
这只是权重计算的一部分,完整的要复杂得多。考虑到不同单词的重要性,和搜索内容的在不同场景下会有特殊意义,权重自然都不相同。
向量空间模型的算法(VSM)
大致思路就是,将每一个文档通过计算每个词的权重,然后组成一个向量。然后用户搜索的条件也变成一个搜索的向量(因为搜索条件可能会有must,也可能有must not这种,所以会分布在坐标系的各个象限),最后对比哪个向量的夹角较小,就符合搜索条件。
image相关计算过程:
image参考 http://www.lucene.com.cn/about.htm 中文章《开放源代码的全文检索引擎 Lucene》
Lucene架构
save: Document->IndexWriter->index
search: Query->IndexSearch->index->TopDocsController
- 被索引的文档用Document对象表示。
- IndexWriter通过函数addDocument将文档添加到索引中,实现创建索引的过程。
- Lucene的索引是应用反向索引。
- 当用户有请求时,Query代表用户的查询语句。
- IndexSearcher通过函数search搜索LuceneIndex。
- IndexSearcher计算termweight和score并且将结果返回给用户。
- 返回给用户的文档集合用TopDocsCollector表示。
Create
imageFlie f = ?
//需要写入的文档
Document doc = new Document();
doc.add(new Field("path",f.getPath(),
Field.Store.Yes,
Field.Index.NOT_ANALYZED);
//数据字段写入doc
doc.add(new Field("contents", new FlieReader(f)):
//创建writer写 一个INDEX_DIR存储文件的位置
IndexWriter writer = new IndexWrte(
//源文件地址
FSDirectory.open(INDEX_DIR),
//分词器
new StandardAnalyzer(Version.LOCENE_CURRENT),
true,
IndexWriter,
MaxFeildLenth.LIMITED);
writer addDocument(doc);
writer optimize();
writer.close();
Search
image//根据索引创建一个search
Searcher searcher = new IndexSearcher(reader);
//分词器
Analyzer analyzer = new StanardAnalyzer(xxx);
//分词器分词 查询语句分析
QueryParser parser = new QueryParser(field,analyzer) ;
Query query = parser.parse(queryString)
//查询
searcher.search(query,collecor)
代码结构
- Lucene的analysis模块主要负责词法分析及语言处理而形成Term。 ! Lucene的index模块主要负责索引的创建,里面有IndexWriter。
- Lucene的store模块主要负责索引的读写。
- Lucene的QueryParser主要负责语法分析。
- Lucene的search模块主要负责对索引的搜索。
- Lucene的similarity模块主要负责对相关性打分的实现。
索引文件结构
Lucene 的索引过程,就是按照全文检索的基本过程,将倒排表写成此文件格式的过程。
Lucene 的搜索过程,就是按照此文件格式将索引进去的信息读出来,然后计算每篇文档打分(score)的过程。
具体文件保存逻辑,更新太频繁,推荐官网阅读。
参考:
Home - Apache Lucene (Java) - Apache Software Foundation
http://lucene.apache.org/java/2_9_0/fileformats.html
image image- Lucene
一个lucene索引放在一个文件夹里面。
-
Segment
- Segment分段是包裹某一堆数据的集合。一个索引将会有多个段,新增一个文档就会放到个新的段里面,段之间会合并。
- 图中—1—2就是两个不同的段,lucene中留有两个segments.gen和segments—5来防止元数据。
-
Doc
- doc中就保存的是每一个完整的文件数据。比如是新闻就包括他的标题,内容,创建时间,点击量等等
- 新增一个文档就会放到个新的段里面,段之间会合并。
-
Field
- field则是精确到字段,每个字段都在不同的field里面
- 不同类型的字段,建立倒排索引的方式不同,比如long,text,date等
-
Term
- 经过分词器分词出来得到的词,一句话中提取出核心的单词用来建立倒排的根本。
- Xxx.tis存储的是term dictionary,即此段包含的所有词按字典顺序的排序("book",2)(词找分段)
- xxx.frq保存了倒排表,即每个词包含的文档id(词找文档)
- xxx.prx保存了每个词在文档的位置。(词在文档的位置(高亮功能))
底层保存规则
- 前缀后缀优化
- 数值改为差值优化
-
跳表操作
很多数据库都使用了类似的跳表,原理与B+树类似。
索引过程分析
Lucene 的索引过程,很多的博客,文章都有介绍,推荐大家上网搜一篇文章:《Annotated Lucene》,好像中文名称叫《Lucene 源码剖析》是很不错的。
段合并过程分析
概述
由IndexWriter的代码中与段合并有关的成员变量有:
//保存正在合并 的段,以防止合并期间再次选中被合并。
HashSet<Segmentlnfo:>mergingSegments=new HashSet<Segmentlnfo>();
//合并策略,也即选取哪些段 来进行合并。
MergePolicy mergePolicy=new LogByteSizeMergePolicy(this);
//段合并器,背后有 一个线程负责合并。
MergeScheduler mergeScheduler=new ConcurrentMergeScheduler();
//等待被合并的任务
LinkedList<MergePolicy.OneMerge> =LinkedList<MergePolicy.OneMerge:();
//正在被合并的任务
Set<MergePolicy.OneMerge>runningMerges new HashSet<MergePolicy.OneMerge>():
我们可以得出:
一个是选择哪些段应该参与合并,这一步由MergePolicy来决定。
一个是将选择出的段合并成新段的过程,这一步由MergeScheduler来执行。
段的合并也主要 包括:
1. 对正向信息的合并,如存储域,词向量,标准化因子等。
1. 对反向信息的合并,如词典,倒排表。
段合并代码分析
-
将缓存写入新的段
//DocumentsWriter添加文档,最 后返回是否进行向硬盘写入 doFlush=docWriter.addDocument(doc,analyzer); //这取决于当使用的内存大于 ramBufferSize 的时候,则由内存向硬盘写入。 return state.doFlushAfter || timeToFlushDeletes(); //当缓存写入硬盘,形成了新的段后,就有可能触发一次段合并,所以调用 maybeMerge() IndexWriter.maybeMerge() //主要负责 找到可以合并的段,并生产段合并任务对象,并向段合并器注册这个任务。 IndexWriter.updatePendingMerges(int maxNumSegmentsOptimize, boolean optimize) //主要负责进行段的合并。 ConcurrentMergeScheduler.merge(IndexWriter)
-
选择合并段,生成合并任务
//生成合并任务 IndexWriter.updatePendingMerges(int maxNumSegmentsOptimize, boolean optimize) //两部分: //选择能够合并段: MergePolicy.MergeSpecificationspec= mergePolicy.findMerges(segmentInfos); //向段合并器注册合并任务,将任务加到pendingMerges中: " for(int i=0;i<spec.merges.size();i++) registerMerge(spec.merges.get(i)); //选择合并逻辑
段合并逻辑
在LogMergePolicy中,选择可以合并的段的基本逻辑是这样的:
-
选择的可以合并的段都是在硬盘上的,不再存在内存中的段,也不是像早期的版本一样 每添加一个Document就生成一个段,然后进行内存中的段合并,然后再合并到硬盘中。
-
由于从内存中flush到硬盘上是按照设置的内存大小来DocumentsWriter.ramBufferSize 触发的,所以每个刚flush到硬盘上的段大小差不多,当然不排除中途改变内存设置, 接下来的算法可以解决这个问题。
(通过1,2解决了早起磁盘上段大小差距大的问题) -
合并的过程是尽量按照合并几乎相同大小的段这一原则,只有大小相当的mergeFacetor 个段出现的时候,才合并成一个新的段。 在硬盘上的段基本应该是大段在前,小段在后,因为大段总是由小段合并而成的,当小 段凑够mergeFactor个的时候,就合并成一个大段,小段就被删除了,然后新来的一定 是新的小段。
(可以理解为一个自动整理文件的手法,毕竟写入的时候是多线程,写入多个小段速度最快,然后在一个同步程序来把写入的文件好好整理成册) -
比如mergeFactor:3,开始来的段大小为10M,当凑够3个10M的时候,0.cfs,1.cfs,2.cfs 则合并成一个新的段3.cfs,大小为30M,然后再来4.cfs,5.cfs,6.cfs,合并成7.cfs,大 小为30M,然后再来8.cfs,9.cfs,a.cfs合并成b.cfs,大小为30M,这时候又凑够了3个 30M的,合并成90M的c.cfs,然后又来d.cfs,e.cfs,f.cfs合并成10.cfs,大小为30M,然 后11.cfs大小为10M,这时候硬盘上的段为:c.cfs(90M)10.cfs(30M),11.cfs(10M)。
-
在段合并的时候,会将所有的段按照生成的顺序,将段的大小以 merge Factor为底取对数,放入数组中,作 为选择的标准。然后再对段进行判定然后执行段的合并逻辑。
![](https://myalipapa-for-live.oss-cn-chengdu.aliyuncs.com/pic-mac/image-20220105141839569.png" alt="image-20220105141839569" style="zoom: 50%;" />
-
段合并器执行段合并
// 得到下一个合并任务: MergePolicy.OneMergemerge=writer.getNextMerge(); // 初始化合并任务: writer.mergeInit(merge); // 将删除文档写入硬盘: applyDeletes(); //是否合并存储域: mergeDocStores=false //按照Lucene的索引文件格式(2)中段的元数据信息(segments_N)中提到的,IndexWriter.flush(boolean triggerMerge, boolean flushDocStores, boolean flushDeletes)中第二个参数 flushDocStores 会影 响到是否单独或是共享存储。其实最终影响的是 DocumentsWriter.closeDocStore()。 每当 flushDocStores 为 false 时,closeDocStore 不被调用,说明下次添加到索引文件 中的域和词向量信息是同此次共享一个段的。直到 flushDocStores 为 true 的时候, closeDocStore 被调用,从而下次添加到索引文件中的域和词向量信息将被保存在一个新 的段中,不同此次共享一个段。如 2.1 节中说的那样,在 addDocument 中,如果内存中 缓存满了,则写入硬盘,调用的是 flush(true, false, false),也即所有的存储域都存储在 共享的域中(_0.fdt),因而不需要合并存储域。 //生成新的段: merge.info=newSegmentInfo(newSegmentName(),...) for(int i=0;i<count;i++) mergingSegments.add(merge.segments.info(i)); //将新的段加入mergingSegments //如果已经有足够多的段合并线程,则等待while(mergeThreadCount()>= maxThreadCount) wait(); //生成新的段合并线程: merger = getMergeThread(writer, merge); mergeThreads.add(merger); //启动段合并线程: merger.start(); //循环执行合并 while(true){ // 合并当前的任务: doMerge(merge); // 得到下一个段合并任务: merge = writer.getNextMerge(); }
- 合并存储域/元数据
for (IndexReader reader : readers) {
SegmentReader segmentReader = (SegmentReader) reader; FieldInfos readerFieldInfos = segmentReader.fieldInfos(); int numReaderFieldInfos = readerFieldInfos.size();
for (int j = 0; j < numReaderFieldInfos; j++) {
FieldInfo fi = readerFieldInfos.fieldInfo(j);
//这里有两种情况,如果两个doc的元数据相同,也就是字段都一样,那么就是快速的合并add
//如果是有数据字段的变化,那么就需要一个个doc挨个更新元数据,会导致速度变慢
//所以在使用lucene时,最好一个索引定死那些字段,那样能得到最优的速度
fieldInfos.add(fi.name,
fi.isIndexed,
fi.storeTermVector,
fi.storePositionWithTermVector,
fi.storeOffsetWithTermVector,
!reader.hasNorms(fi.name),
fi.storePayloads,
fi.omitTermFreqAndPositions);
}
}
-
合并标准化因子(标准化因子:用于影响文档打分)
合并标准化因子的过程比较简单,基本就是对每一个域,用指向合并段的 reader 读出标准 化因子,然后再写入新生成的段。(重新打分)
-
合并词向量(词向量:表示词出现的多少,位置,和数量的向量)
与存储域差不多
-
合并词典和倒排表
倒排索引合并
-
对词典的合并需要找出两个段中相同的词,Lucene是通过一个称为match的 SegmentMergelnfo类型的数组以及称为queue的SegmentMergeQueue(图画起来更像一个栈)实现的。
-
SegmentMergeQueue是继承于PriorityQueue<SegmentMergelnfo>,是一个优先级队列,是按照字典顺序排序的。SegmentMergelnfo保存要合并的段的词典及倒排表信息,在 SegmentMergeQueue中用来排序的key是它代表的段中的第一个Term。 我们来举一个例子来说明合并词典的过程,以便后面解析代码的时候能够很好的理解:
-
对字典的合并,词典中的Term是按照字典顺序排序的,需要对词典中的Term进行重新排序对于相同的Term,对包含此Term的文档号列表进行合并,需要对文档号重新编号。
-
假设要合并五个段,每个段包含的em也是按照字典顺序排序的,如下图所示。 首先把五个段全部放入优先级队列中,段在其中也是按照第一个em的字典顺序排序 的,如下图。
-
打分公式的数学推导
整体打分思路:
image核心参数标准化因子:
image所以我们可以在改动权重,来改变搜索和写入词的比重,以搜索到更有价值的信息。
搜索过程解析
<img src="https://myalipapa-for-live.oss-cn-chengdu.aliyuncs.com/pic-mac/image-20220105170125590.png" alt="image-20220105170125590" style="zoom:67%;" />
总共包括以下几个过程:
- IndexReader 打开索引文件,读取并打开指向索引文件的流。
- 用户输入查询语句
- 将查询语句转换为查询对象 Query 对象树
- 构造 Weight 对象树,用于计算词的权重 Term Weight,也即计算打分公式中与仅与搜索
语句相关与文档无关的部分(红色部分)。 - 构造 Scorer 对象树,用于计算打分(TermScorer.score())。
- 在构造 Scorer 对象树的过程中,其叶子节点的 TermScorer 会将词典和倒排表从索引中读出来。
(同时读取词典和倒排表,此时只有doc id) - 构造 SumScorer 对象树,其是为了方便合并倒排表对 Scorer 对象树的从新组织,它的叶子节点仍为 TermScorer,包词典和倒排表。此步将倒排表合并后得到结果文档集,并 对结果文档计算打分公式中的蓝色部分。打分公式中的求和符合,并非简单的相加,而 是根据子查询倒排表的合并方式(与或非)来对子查询的打分求和,计算出父查询的打分。
(打分同时拿到文档) - 将收集的结果集合及打分返回给用户。
查询语法,JavaCC 及 QueryParser
场景lucene语法
SIP-9 Advanced Query Parser - SOLR
查询语法
-
语法关键字
+- && || ! ( ) { } [ ] ^ " ~ * ? : \ 如果所要查询的查询词中本身包含关键字,则需要用\进行转义
-
查询词(Term)
Lucene 支持两种查询词,一种是单一查询词,如"hello",一种是词组(phrase),如"hello world"。
-
查询域(Field)
在查询语句中,可以指定从哪个域中寻找查询词,如果不指定,则从默认域中查找。 查询域和查询词之间用:分隔,如 title:"Do it right"。 :仅对紧跟其后的查询词起作用,如果 title:Do it right,则仅表示在 title 中查询 Do,而 it right 要在默认域中查询。
-
通配符查询(Wildcard)
支持两种通配符:?表示一个字符,*表示多个字符。 通配符可以出现在查询词的中间或者末尾,如 te?t,test*,te*t,但决不能出现在开始, 如*test,?test。 -
模糊查询(Fuzzy)
模糊查询的算法是基于 Levenshtein Distance,也即当两个词的差小于某个比例的时 候,就算匹配,如 roam~0.8,即表示差距小于 0.2,相似度大于 0.8 才算匹配。 -
临近查询(Proximity)
在词组后面跟随~10,表示词组中的多个词之间的距离之和不超过 10,则满足查询。所谓词之间的距离,即查询词组中词为满足和目标词组相同的最小移动次数。 如索引中有词组"apple boy cat"。
如果查询词为"apple boy cat"~0,则匹配。
如果查询词为"boy apple cat"~2,距离设为 2 方能匹配,设为 1 则不能匹配。 -
区间查询(Range)
区间查询包括两种,一种是包含边界,用[A TO B]指定,一种是不包含边界,用{A TO B} 指定。
如 date:[20020101 TO 20030101],当然区间查询不仅仅用于时间,如 title:{Aida TO Carmen} -
增加一个查询词的权重(Boost)
可以在查询词后面加^N 来设定此查询词的权重,默认是 1,如果 N 大于 1,则说明此查询 词更重要,如果 N 小于 1,则说明此查询词更不重要。
如 jakarta^4 apache,"jakarta apache"^4 "Apache Lucene" -
布尔操作符
布尔操作符包括连接符,如 AND,OR,和修饰符,如 NOT,+,-。 默认状态下,空格被认为是 OR 的关系, QueryParser.setDefaultOperator(Operator.AND)设置为空格为 AND。 +表示一个查询语句是必须满足的(required),NOT 和-表示一个查询语句是不能满足的 (prohibited)。 -
组合
可以用括号,将查询语句进行组合,从而设定优先级。
如(jakarta OR apache) AND website
JavaCC
JavaCC 本身既不是一个词法分析器,也不是一个语法分析器,而是根据指定的规则生成两者的生成器。
Lucene 的查询语法是由 QueryParser 来进行解析,从而生成查询对象的。 通过编译原理我们知道,解析一个语法表达式,需要经过词法分析和语法分析的过程,也即 需要词法分析器和语法分析器。
QueryParser 是通过 JavaCC 来生成词法分析器和语法分析器的。
//词法分析器编写
SKIP : { " " }
SKIP : { "\n" | "\r" | "\r\n" }
TOKEN : { < PLUS : "+" > }
TOKEN : { < NUMBER : (["0"-"9"])+ > }
//语法分析器编写
void Start() :
{} {
<NUMBER> (
<PLUS>
<NUMBER> )*
<EOF> }
//编译后就可以变成一个能够解析器 输入正确 就能输出结果
QueryParser
用javacc实现,能够把易懂的lucene语法变为java语法。
查询对象
和es的查询差不了太多,但是也提供了一些很有趣的。
常用的就不写了,写一些有趣的。
BoostingQuery
/*** match 必须满足* context 不影响结果,可选,会将打分 X boost* boost 权重分*/public BoostingQuery(Query match, Query context, float boost)
CustomScoreQuery
//自定义打分规则//子查询和其他的信息源来共同决定最后的打分public float customScore(int doc, float subQueryScore, float valSrcScores[])
MoreLikeThisQuery
在分析 MoreLikeThisQuery 之前,首先介绍一下 MoreLikeThis。
在实现搜索应用的时候,时常会遇到"更多相似文章","更多相关问题"之类的需求,也即根 据当前文档的文本内容,在索引库中查询相类似的文章。我们可以使用 MoreLikeThis 实现此功能:
IndexReader reader = IndexReader.open(......);IndexSearcher searcher = new IndexSearcher(reader);MoreLikeThis mlt = new MoreLikeThis(reader);Reader target = ... //此是一个 io reader,指向当前文档的文本内容。Query query = mlt.like( target); //根据当前的文本内容,生成查询对象。 Hits hits = searcher.search(query); //查询得到相似文档的结果。
SpanQuery
//所谓 SpanQuery 也即在查询过程中需要考虑进 Term 的位置信息的查询对象。//SpanQuery 中最基本的是 SpanTermQuery,其只包一个 Term,与 TermQuery 所不同的是, 其提供一个函数来得到位置信息:public Spans getSpans(final IndexReader reader) throws IOException { return new TermSpans(reader.termPositions(term), term);}//Spans 有以下方法://next() 得到下一篇文档号,不同的 SpanQuery 此方法实现不同 ! skipTo(int) 跳到指定的文档//doc() 得到当前的文档号//start() 得到起始位置,不同的 SpanQuery 此方法实现不同//end() 得到结束位置,不同的 SpanQuery 此方法实现不同//isPayloadAvailable() 是否有 payload//getPayload() 得到 payload
在这个基础上,我们可以开发出搜索词高亮的功能。
SpanFirstQuery
搜索以xx开头的文档。
SpanNearQuery
搜索词必须满足x间隔。
FieldCacheRangeFilter<T>及 FieldCacheTermsFilter
FieldCacheRangeFilter 同 NumericRangeFilter 或者 TermRangeFilter 功能类似,只不过后两者 取得 docid 的 bitset 都是从索引中取出,而前者是缓存了的,加快了速度。
同样 FieldCacheTermsFilter 同 TermFilter 功能类似,也是前者进行了缓存,加快了速度。
分词器 Analyzer
Analyzer
public final class SimpleAnalyzer extends Analyzer { @Overridepublic TokenStream tokenStream(String fieldName, Reader reader) {//返回的是将字符串最小化,并且按照空格分隔的 Tokenreturn new LowerCaseTokenizer(reader); } @Overridepublic TokenStream reusableTokenStream(String fieldName, Reader reader) throws IOException {// 得 到 上 一 次 使 用 的 TokenStream , 如 果 没 有 则 生 成 新 的 , 并 且 用 setPreviousTokenStream 放入成员变量,使得下一个可用。Tokenizer tokenizer = (Tokenizer) getPreviousTokenStream(); if (tokenizer == null) {tokenizer = new LowerCaseTokenizer(reader);setPreviousTokenStream(tokenizer); } else//如果上一次生成过 TokenStream,则 reset。tokenizer.reset(reader); return tokenizer;} }
TokenStream
TokenStream是一个由分词后的 Token 结果组成的流,能够不断的 得到下一个分成的 Token。
TokenStream 主要以下几个方法://用于得到下一个 Tokenboolean incrementToken()//使得此 TokenStrean 可以重新开始返回各个分词。public void reset()
例:NumericTokenStream.class
public static int intToPrefixCoded(final int val, final int shift, final char[] buffer) { if (shift>31 || shift<0)throw new IllegalArgumentException("Illegal shift value, must be 0..31"); int nChars = (31-shift)/7 + 1, len = nChars+1;buffer[0] = (char)(SHIFT_START_INT + shift);int sortableBits = val ^ 0x80000000;sortableBits >>>= shift; while (nChars>=1) {//int 按照每七位组成一个 utf-8 的编码,并且字符串大小比较的顺序同 int 大小比较 的顺序完全相同。buffer[nChars--] = (char)(sortableBits & 0x7f);sortableBits >>>= 7; }return len; }
存储方面使用了各种优化方式,做到最高效的存储。
具体存储优化方式使用<索引文件结构.底层保存规则>小节中的部分方式。
网友评论