Lucene
全文檢索的心,天才的想法。
- 一個高效的,可擴展的,全文檢索庫。
- 全部用 Java 實現,無須配置。
- 僅支持純文本文件的索引(Indexing)和搜索(Search)。
- 不負責由其他格式的文件抽取純文本文件,或從網絡中抓取文件的過程。
基于《Lucene 原理與代碼分析 覺先 (forfuture1978)》
核心就是將進來的數據,創建進行倒排索引。以及將搜索的內容根據倒排索引來搜索,避免了遍歷搜索的速度消耗。
一種犧牲空間,換取時間的手段。

索引的創建
將簡單的文本數據,處理成易于根據單詞查詢的格式。便于全文檢索。

數據查詢
對于搜索的條件也會進行同樣的分詞手法,
- 把數據進行分割,去除is are那種無意義的詞。
- 動名詞變詞根之類的操作。
- 然后去查詢存儲了這些詞的文檔鏈表,進行搜索條件中的與或非操作。
- 最后得到的文檔進行權重分析,排序。
- 最后得到數據。

權重計算
計算權重(Termweight)的過程。 影響一個詞(Term)在一篇文檔中的重要性主要有兩個因素:
- Term Frequency (tf):即此 Term 在此文檔中出現了多少次。tf 越大說明越重要。
- Document Frequency (df):即有多少文檔包次 Term。df 越大說明越不重要。

這只是權重計算的一部分,完整的要復雜得多。考慮到不同單詞的重要性,和搜索內容的在不同場景下會有特殊意義,權重自然都不相同。
向量空間模型的算法(VSM)
大致思路就是,將每一個文檔通過計算每個詞的權重,然后組成一個向量。然后用戶搜索的條件也變成一個搜索的向量(因為搜索條件可能會有must,也可能有must not這種,所以會分布在坐標系的各個象限),最后對比哪個向量的夾角較小,就符合搜索條件。

相關計算過程:

參考 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

Flie 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

//根據索引創建一個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


- 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為底取對數,放入數組中,作 為選擇的標準。然后再對段進行判定然后執行段的合并邏輯。
; // 初始化合并任務: 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
打分公式的數學推導
整體打分思路:

核心參數標準化因子:

所以我們可以在改動權重,來改變搜索和寫入詞的比重,以搜索到更有價值的信息。
搜索過程解析
<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語法
Luecene 3.0.1
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 本身既不是一個詞法分析器,也不是一個語法分析器,而是根據指定的規則生成兩者的生成器。
javacc.com
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; }
存儲方面使用了各種優化方式,做到最高效的存儲。
具體存儲優化方式使用<索引文件結構.底層保存規則>小節中的部分方式。

喜歡的朋友記得點贊、收藏、關注哦!!!