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

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

簡單來說，Lucene提供了一套完整的工具來幫助開發(fā)者構(gòu)建自己的搜索引擎，開發(fā)者只需要import Lucene對應(yīng)的package即可快速地開發(fā)構(gòu)建自己的業(yè)務(wù)搜索引擎。

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

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

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

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

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

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

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

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

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

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

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

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

依據(jù)上面的原理，假設(shè)有這么兩篇文檔：

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

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

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

把這兩篇文檔拆解轉(zhuǎn)化為倒排索引如下：

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

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

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

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

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

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

一個索引和一個數(shù)據(jù)庫表類似，但是數(shù)據(jù)庫中是先定義表結(jié)構(gòu)后使用。但Lucene在放數(shù)據(jù)的時候定義字段結(jié)構(gòu)。

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

加權(quán): "dog^4 cat"，^表示加權(quán)

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

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

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

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

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

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

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

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

IndexSearcher isearcher = new IndexSearcher(directory,//索引路徑
true); //只讀
//搜索標(biāo)題列
QueryParser parser = new QueryParser(Version.LUCENE_CURRENT,"title", analyzer);
Query query = parser.parse(“NBA”); //搜索NBA這個詞
//返回前1000條搜索結(jié)果
ScoreDoc[] hits = isearcher.search(query, 1000).scoreDocs;
//遍歷結(jié)果
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條結(jié)果
ScoreDoc[] hits = isearcher.search(query, 1000).scoreDocs;

2. 布爾邏輯查詢-BooleanQuery： 同時查詢標(biāo)題列和內(nèi)容列。

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

布爾查詢的實(shí)現(xiàn)過程如下：

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

后臺實(shí)現(xiàn)代碼：

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

RangeQuery采用擴(kuò)展成TermQuery來實(shí)現(xiàn)，如果查詢區(qū)間范圍太大，RangeQuery會導(dǎo)致TooManyClausesException ConstantScoreRangeQuery 內(nèi)部采用Filter來實(shí)現(xiàn)，當(dāng)索引很大的時候，查詢速度會很慢

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

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

索引時，增加一個浮點(diǎn)數(shù)列到索引：

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

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

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

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

因?yàn)榇嬖谌哂?，所以可以壓縮。壓縮的原理：使用預(yù)測編碼，對前后相似的內(nèi)容壓縮。 壓縮的對象

字符串?dāng)?shù)組(Term List)

整數(shù)數(shù)組(DocId)

字符串?dāng)?shù)組排序后使用前綴壓縮，整數(shù)數(shù)組排序后使用差分編碼壓縮 。壓縮算法的兩個過程：編碼(壓縮)過程和解碼(解壓縮)過程。編碼過程可以時間稍長，解碼過程需要速度快。類似ADSL上網(wǎng)機(jī)制：下載速度快，而上傳速度慢。因?yàn)樵谒饕龜?shù)據(jù)階段執(zhí)行編碼過程，而在搜索階段執(zhí)行解碼過程。索引數(shù)據(jù)速度可以稍慢，但是搜索速度不能慢。

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

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

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

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

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

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

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

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

這是Lucene的用法和原理，構(gòu)建自己的搜索引擎可以使用Lucene這個強(qiáng)大的工具包，將大大縮減開發(fā)周期，實(shí)現(xiàn)一個高性能的業(yè)務(wù)搜索引擎。

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

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

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