摘要：倒排索引是基于詞的搜索。關于倒排索引要學習搜索引擎，就需要了解倒排索引，要更加深刻地理解倒排索引，就要先了解什么是正排索引表。由于不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引。

Lucene是apache軟件基金會4 jakarta項目組的一個子項目，是一個開放源代碼的全文檢索引擎工具包，但它不是一個完整的全文檢索引擎，而是一個全文檢索引擎的架構，提供了完整的查詢引擎和索引引擎，部分文本分析引擎（英文與德文兩種西方語言）。Lucene的目的是為軟件開發人員提供一個簡單易用的工具包，以方便的在目標系統中實現全文檢索的功能，或者是以此為基礎建立起完整的全文檢索引擎。Lucene是一套用于全文檢索和搜尋的開源程式庫，由Apache軟件基金會支持和提供。Lucene提供了一個簡單卻強大的應用程式接口，能夠做全文索引和搜尋。在Java開發環境里Lucene是一個成熟的免費開源工具。就其本身而言，Lucene是當前以及最近幾年最受歡迎的免費Java信息檢索程序庫。人們經常提到信息檢索程序庫，雖然與搜索引擎有關，但不應該將信息檢索程序庫與搜索引擎相混淆。

簡單來說，Lucene提供了一套完整的工具來幫助開發者構建自己的搜索引擎，開發者只需要import Lucene對應的package即可快速地開發構建自己的業務搜索引擎。

索引(Index)：文檔的集合組成索引。和一般的數據庫不一樣，Lucene不支持定義主鍵，但Solr支持。

為了方便索引大量的文檔，Lucene中的一個索引分成若干個子索引，叫做段(segment)。段中包含了一些可搜索的文檔。

文檔(Document)：代表索引庫中的一條記錄。一個文檔可以包含多個列(Field)。和一般的數據庫不一樣，一個文檔的一個列可以有多個值。例如一篇文檔既可以屬于互聯網類，又可以屬于科技類。

列(Field)：命名的詞的集合。

詞(Term) ：由兩個值定義——詞語和這個詞語所出現的列。

倒排索引是基于詞(Term)的搜索。

要學習搜索引擎，就需要了解倒排索引，要更加深刻地理解倒排索引，就要先了解什么是正排索引(表)。

正排表是以文檔的ID為關鍵字，表中記錄文檔中每個字的位置信息，查找時掃描表中每個文檔中字的信息直到找出所有包含查詢關鍵字的文檔。
正排表結構如圖1所示，這種組織方法在建立索引的時候結構比較簡單，建立比較方便且易于維護;因為索引是基于文檔建立的，若是有新的文檔加入，直接為該文檔建立一個新的索引塊，掛接在原來索引文件的后面。若是有文檔刪除，則直接找到該文檔號文檔對應的索引信息，將其直接刪除。但是在查詢的時候需對所有的文檔進行掃描以確保沒有遺漏，這樣就使得檢索時間大大延長，檢索效率低下。
盡管正排表的工作原理非常的簡單，但是由于其檢索效率太低，除非在特定情況下，否則實用性價值不大。

倒排表以字或詞為關鍵字進行索引，表中關鍵字所對應的記錄表項記錄了出現這個字或詞的所有文檔，一個表項就是一個字表段，它記錄該文檔的ID和字符在該文檔中出現的位置情況。
由于每個字或詞對應的文檔數量在動態變化，所以倒排表的建立和維護都較為復雜，但是在查詢的時候由于可以一次得到查詢關鍵字所對應的所有文檔，所以效率高于正排表。在全文檢索中，檢索的快速響應是一個最為關鍵的性能，而索引建立由于在后臺進行，盡管效率相對低一些，但不會影響整個搜索引擎的效率。

搜索引擎通常檢索的場景是：給定幾個關鍵詞，找出包含關鍵詞的文檔。怎么快速找到包含某個關鍵詞的文檔就成為搜索的關鍵。這里我們借助單詞——文檔矩陣模型，通過這個模型我們可以很方便知道某篇文檔包含哪些關鍵詞，某個關鍵詞被哪些文檔所包含。單詞-文檔矩陣的具體數據結構可以是倒排索引、簽名文件、后綴樹等。

倒排索引源于實際應用中需要根據屬性的值來查找記錄，lucene是基于倒排索引實現的。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。由于不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引(inverted index)。帶有倒排索引的文件我們稱為倒排索引文件，簡稱倒排文件(inverted file)。

倒排索引一般表示為一個關鍵詞，然后是它的頻度（出現的次數），位置（出現在哪一篇文章或網頁中，及有關的日期，作者等信息），它相當于為互聯網上幾千億頁網頁做了一個索引，好比一本書的目錄、標簽一般。讀者想看哪一個主題相關的章節，直接根據目錄即可找到相關的頁面。不必再從書的第一頁到最后一頁，一頁一頁的查找。

依據上面的原理，假設有這么兩篇文檔：

文檔1: When in Rome, do as the Romans do.

文檔2: When do you come back from Rome?

停用詞: in, as, the, from。（在信息檢索中，為節省存儲空間和提高搜索效率，在處理自然語言數據（或文本）之前或之后會自動過濾掉某些字或詞，這些字或詞即被稱為Stop Words(停用詞)。）

把這兩篇文檔拆解轉化為倒排索引如下：

現在檢索的時候就可以利用倒排索引的優勢大大提高效率：假如查詢back這個單詞，通過上面的倒排索引，可以直接定位到它出現在文檔2中，且出現了1次（頻率），出現的位置是文檔的第5個單詞，一目了然，相較于正排索引，也即是以文檔為基本查詢單位的結構，倒排索引能夠更快地定位到keyword的所在，極大提高檢索響應速度。

首先把信息建立索引庫(原始信息一般由網絡爬蟲獲得)，通過Lucene的IndexWriter寫入倒排索引建立索引庫，當有query請求時，通過IndexSearcher解析、匹配，從索引庫獲得結果返回并排序。

一個Document代表索引庫中的一條記錄。一個Document可以包含多個列。例如一篇文章可以包含“標題”、“正文”、“修改時間”等field，創建這些列對象以后，可以通過Document的add方法增加這些列到Document實例。

一段有意義的文字通過Analyzer分割成一個個的詞語后寫入到索引庫。

//創建新的索引庫
IndexWriter index = new IndexWriter(indexDirectory,//索引庫存放的路徑
              new StandardAnalyzer(Version.LUCENE_CURRENT),
              true,//新建索引庫
              IndexWriter.MaxFieldLength.UNLIMITED);//不限制列的長度

File dir = new File(sourceDir);
indexDir(dir); //索引sourceDir路徑下的文件
index.optimize();//索引優化
index.close();//關閉索引庫

一個索引和一個數據庫表類似，但是數據庫中是先定義表結構后使用。但Lucene在放數據的時候定義字段結構。

Document doc = new Document();
//創建網址列
Field f = new Field(“url”, news.URL , //news.URL 存放url地址的值
                Field.Store.YES, Field.Index. NOT_ANALYZED,//不分詞
                Field.TermVector.NO);
doc.add(f);
//創建標題列
f = new Field(“title”, news.title , //news.title 存放標題的值
                Field.Store.YES, Field.Index.ANALYZED,//分詞
                Field.TermVector.WITH_POSITIONS_OFFSETS);//存Token位置信息
doc.add(f);
//創建內容列
f = new Field(“body”, news.body , //news.body 存放內容列的值
                Field.Store.YES, Field.Index. ANALYZED, //分詞
                Field.TermVector.WITH_POSITIONS_OFFSETS); //存Token位置信息
doc.add(f);
index.addDocument(doc); //把一個文檔加入索引

加權: "dog^4 cat"，^表示加權

修飾符: + - NOT, 例如, "+dog cat"

布爾操作符: OR AND, 例如, "(dog OR cat) AND mankind"

按域查詢: title:apple, 一個字段名后跟冒號，再加上要搜索的詞語或者短句，就可以把搜索條件限制在該字段。

QueryParser將輸入查詢字串解析為Lucene Query對象。

QueryParser是使用JavaCC(Java Compiler Compiler )工具生成的詞法解析器。

QueryParser.jj中定義了查詢語法。

全文索引是按詞組織的，所以在一長串keyword輸入之后需要對其進行切分，Lucene中把索引中的詞稱為token，Analyzer會通過內部的Tokenizer把keyword解析成詞序列，也就是token流，以供檢索使用，可以使用Filter來過濾最后的查詢結果。Lucene在兩個地方使用到Analyzer：索引文檔的時候和按keyword檢索文檔的時候。索引文檔的時候Analyzer解析出的token(詞)即為倒排表中的詞。

// 分析公司名的流程
Analyzer analyzer = new CompanyAnalyzer(); 
TokenStream ts = analyzer.tokenStream("title", new StringReader("北京xxx科技發展有限公司"));
while (ts.incrementToken()) {
    System.out.println("token: "+ts));
}

IndexSearcher isearcher = new IndexSearcher(directory,//索引路徑
true); //只讀
//搜索標題列
QueryParser parser = new QueryParser(Version.LUCENE_CURRENT,"title", analyzer);
Query query = parser.parse(“NBA”); //搜索NBA這個詞
//返回前1000條搜索結果
ScoreDoc[] hits = isearcher.search(query, 1000).scoreDocs;
//遍歷結果
for (int i = 0; i < hits.length; i++) {
  Document hitDoc = isearcher.doc(hits[i].doc);
  System.out.println(hitDoc.get("title"));
}
isearcher.close();
directory.close();

常用的查詢類型：

1. 最基本的詞條查詢-TermQuery： 一般用于查詢不切分的字段或者基本詞，即全匹配。

IndexSearcher isearcher = new IndexSearcher(directory, true);
//查詢url地址列
Termterm = new Term("url","http://www.lietu.com");
TermQuery query = new TermQuery(term);
//返回前1000條結果
ScoreDoc[] hits = isearcher.search(query, 1000).scoreDocs;

2. 布爾邏輯查詢-BooleanQuery： 同時查詢標題列和內容列。

QueryParser parser = new QueryParser(Version.LUCENE_CURRENT, "body", analyzer);
QuerybodyQuery =  parser.parse("NBA");//查詢內容列
parser = new QueryParser(Version.LUCENE_CURRENT, "title", analyzer);
QuerytitleQuery = parser.parse("NBA");//查詢標題列
BooleanQuery bodyOrTitleQuery = new BooleanQuery();
//用OR條件合并兩個查詢
bodyOrTitleQuery.add(bodyQuery, BooleanClause.Occur.SHOULD);
bodyOrTitleQuery.add(titleQuery, BooleanClause.Occur.SHOULD);
//返回前1000條結果
ScoreDoc[] hits = isearcher.search(bodyOrTitleQuery, 1000).scoreDocs;

布爾查詢的實現過程如下：

3. RangeQuery-區間查找： 例如日期列time按區間查詢的語法， time:[2007-08-13T00:00:00Z TO 2008-08-13T00:00:00Z]

后臺實現代碼：

ConstantScoreRangeQuery dateQuery = new ConstantScoreRangeQuery("time", t1, t2, true,
true);

RangeQuery采用擴展成TermQuery來實現，如果查詢區間范圍太大，RangeQuery會導致TooManyClausesException ConstantScoreRangeQuery 內部采用Filter來實現，當索引很大的時候，查詢速度會很慢

在Lucene2.9以后的版本中，用Trie結構索引日期和數字等類型。例如：把521這個整數索引成為：百位是5、十位是52、個位是521。這樣重復索引的好處是可以用最低的精度搜索匹配區域的中心地帶，用較高的精度匹配邊界。這樣減少了要搜索的Term數量。

?例如：TrieRange:[423 TO 642] 分解為5個子條件來執行： handreds:5 OR tens:[43 TO 49] OR ones:[423 TO 429] OR tens:[60 TO 63] OR ones:[640 TO 642]?

索引時，增加一個浮點數列到索引：

document.add(new NumericField("weight").setFloatValue(value));

搜索時，使用NumericRangeQuery來查詢這樣的數字列。例如：

Query q = NumericRangeQuery.newFloatRange(“weight”, new Float(0.3f), new Float(0.10f), true, true);

weight：列名稱，new Float(0.3f)：最小值從它開始，new Float(0.10f)：最大值到它結束，true：是否包含最小/大值。

因為存在冗余，所以可以壓縮。壓縮的原理：使用預測編碼，對前后相似的內容壓縮。 壓縮的對象

字符串數組(Term List)

整數數組(DocId)

字符串數組排序后使用前綴壓縮，整數數組排序后使用差分編碼壓縮 。壓縮算法的兩個過程：編碼(壓縮)過程和解碼(解壓縮)過程。編碼過程可以時間稍長，解碼過程需要速度快。類似ADSL上網機制：下載速度快，而上傳速度慢。因為在索引數據階段執行編碼過程，而在搜索階段執行解碼過程。索引數據速度可以稍慢，但是搜索速度不能慢。

因為索引詞是排序后寫入索引的，所以前后兩個索引詞詞形差別往往不大。前綴壓縮算法省略存儲相鄰兩個單詞的共同前綴。每個詞的存儲格式是： <相同前綴的字符長度,不同的字符長度,不同的字符>。

例如：順序存儲如下三個詞：term、termagancy、termagant。不用壓縮算法的存儲方式是<詞長,詞>，例如： <4,term> <10,termagancy> <9,termagant>；應用前綴壓縮算法后，實際存儲的內容如下： <4,term> <4,6, agancy> <8,1,t>。

變長壓縮算法對于較小的數字有較好的壓縮比。差分編碼可以把數組中較大的數值用較小的數來表示，所以可以和變長壓縮算法聯合使用來實現數組的壓縮。

例如，排好序的DocId序列：
編碼前：345, 777, 11437, …
編碼后：345, 432, 10660, …

VInt是一個變長的正整數表示格式，是一種整數的壓縮格式表示方法。每字節分成兩部分：最高位和低7位。最高位表明是否有更多的字節在后面，0表示這個字節是尾字節，1表示還有后續字節，低7位表示數值。按如下的規則編碼正整數x：

if (x < 128)，則使用一個字節(最高位置0，低7位表示數值)；

if (x< 128*128)，則使用2個字節(第一個字節最高位置1，低7位表示低位數值，第二個字節最高位置0 ，低7位表示高位數值)；

if (x<128^3)，則使用3個字節，以此類推，把VInt看成是128進制的表示方法，低位優先，隨著數值的增大，向后面的字節進位。

這是Lucene的用法和原理，構建自己的搜索引擎可以使用Lucene這個強大的工具包，將大大縮減開發周期，實現一個高性能的業務搜索引擎。

[1] Michael McCandless, Erik Hatcher, Otis Gospodnetic 著；Lucene in Action(Second Edition)；電子工業出版社，2011

[2] (美)W Bruce Croft 著，劉挺 秦兵 譯；搜索引擎:信息檢索實踐 暢銷書籍 科技 正版搜索引擎 信息檢索實踐；機械工業出版社，2010

[3] (日)山田浩之 (日)末永匡 著，胡屹 譯；自制搜索引擎；人民郵電出版社，2016