【轉(zhuǎn)】Lucene工作原理——反向索引

原文鏈接：  http://www.cnblogs.com/lyhero11/p/5192732.html

倒排索引

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

用途

原理

　　Lucene倒排索引原理

　　Lucene是一個高性能的java全文檢索工具包，它使用的是 倒排文件索引結(jié)構(gòu)。該結(jié)構(gòu)及相應(yīng)的生成算法如下：

　　0）設(shè)有兩篇文章1和2

　　文章1的內(nèi)容為：Tom lives in Guangzhou,I live in Guangzhou too.

　　文章2的內(nèi)容為：He once lived in Shanghai.

取得關(guān)鍵詞

　　1)由于lucene是基于關(guān)鍵詞索引和查詢的，首先我們要取得這兩篇文章的關(guān)鍵詞，通常我們需要如下處理措施

　　a.我們現(xiàn)在有的是文章內(nèi)容，即一個字符串，我們先要找出字符串中的所有單詞，即分詞。英文單詞由于用空格分隔，比較好處理。中文單詞間是連在一起的需要特殊的分詞處理。

　　b.文章中的”in”, “once” “too”等詞沒有什么實(shí)際意義，中文中的“的”“是”等字通常也無具體含義，這些不代表概念的詞可以過濾掉

　　c.用戶通常希望查“He”時能把含“he”，“HE”的文章也找出來，所以所有單詞需要統(tǒng)一大小寫。

　　d.用戶通常希望查“l(fā)ive”時能把含“l(fā)ives”，“l(fā)ived”的文章也找出來，所以需要把“l(fā)ives”，“l(fā)ived”還原成“l(fā)ive”

　　e.文章中的標(biāo)點(diǎn)符號通常不表示某種概念，也可以過濾掉

　　在lucene中以上措施由Analyzer類完成

　　經(jīng)過上面處理后

　　文章1的所有關(guān)鍵詞為：[tom] [live] [guangzhou] [i] [live] [guangzhou]

　　文章2的所有關(guān)鍵詞為：[he] [live] [shanghai]

建立倒排索引

　　2) 有了關(guān)鍵詞后，我們就可以建立倒排索引了。上面的對應(yīng)關(guān)系是：“文章號”對“文章中所有關(guān)鍵詞”。倒排索引把這個關(guān)系倒過來，變成：“關(guān)鍵詞”對“擁有該關(guān)鍵詞的所有文章號”。文章1，2經(jīng)過倒排后變成

　　關(guān)鍵詞 文章號

　　guangzhou 1

　　he 2

　　i 1

　　live 1,2

　　shanghai 2

　　tom 1

　　通常僅知道關(guān)鍵詞在哪些文章中出現(xiàn)還不夠，我們還需要知道關(guān)鍵詞在文章中出現(xiàn)次數(shù)和出現(xiàn)的位置，通常有兩種位置：a)字符位置，即記錄該詞是文章中第幾個字符（優(yōu)點(diǎn)是關(guān)鍵詞亮顯時定位快）；b)關(guān)鍵詞位置，即記錄該詞是文章中第幾個關(guān)鍵詞（優(yōu)點(diǎn)是節(jié)約索引空間、詞組（phase）查詢快），lucene中記錄的就是這種位置。

　　加上“出現(xiàn)頻率”和“出現(xiàn)位置”信息后，我們的索引結(jié)構(gòu)變?yōu)椋?/p> 

　　關(guān)鍵詞 文章號[出現(xiàn)頻率] 出現(xiàn)位置

　　guangzhou 1[2] 3，6

　　he 2[1] 1

　　i 1[1] 4

　　live 1[2] 2，5, 2[1]，2

　　shanghai 2[1] 3

　　tom 1[1] 1

　　以live 這行為例我們說明一下該結(jié)構(gòu)：live在文章1中出現(xiàn)了2次，文章2中出現(xiàn)了一次，它的出現(xiàn)位置為“2,5,2”這表示什么呢？我們需要結(jié)合文章號和出現(xiàn)頻率來分析，文章1中出現(xiàn)了2次，那么“2,5”就表示live在文章1中出現(xiàn)的兩個位置，文章2中出現(xiàn)了一次，剩下的“2”就表示live是文章2中第 2個關(guān)鍵字。

　　以上就是lucene索引結(jié)構(gòu)中最核心的部分。我們注意到關(guān)鍵字是按字符順序排列的（lucene沒有使用B樹結(jié)構(gòu)），因此lucene可以用二元搜索算法快速定位關(guān)鍵詞。

實(shí)現(xiàn)

　　實(shí)現(xiàn)時 lucene將上面三列分別作為詞典文件（Term Dictionary）、頻率文件(frequencies)、位置文件 (positions)保存。其中詞典文件不僅保存有每個關(guān)鍵詞，還保留了指向頻率文件和位置文件的指針，通過指針可以找到該關(guān)鍵字的頻率信息和位置信息。

　　Lucene中使用了field的概念，用于表達(dá)信息所在位置（如標(biāo)題中，文章中，url中），在建索引中，該field信息也記錄在詞典文件中，每個關(guān)鍵詞都有一個field信息(因?yàn)槊總€關(guān)鍵字一定屬于一個或多個field)。

壓縮算法

　　為了減小索引文件的大小，Lucene對索引還使用了壓縮技術(shù)。首先，對詞典文件中的關(guān)鍵詞進(jìn)行了壓縮，關(guān)鍵詞壓縮為<前綴長度，后綴>，例如：當(dāng)前詞為“ 阿拉伯語”，上一個詞為“阿拉伯”，那么“阿拉伯語”壓縮為<3，語>。其次大量用到的是對數(shù)字的壓縮，數(shù)字只保存與上一個值的差值（這樣可以減小數(shù)字的長度，進(jìn)而減少保存該數(shù)字需要的字節(jié)數(shù)）。例如當(dāng)前文章號是16389（不壓縮要用3個字節(jié)保存），上一文章號是16382，壓縮后保存7（只用一個字節(jié)）。

應(yīng)用原因

　　下面我們可以通過對該索引的查詢來解釋一下為什么要建立索引。

　　假設(shè)要查詢單詞 “l(fā)ive”，lucene先對詞典二元查找、找到該詞，通過指向頻率文件的指針讀出所有文章號，然后返回結(jié)果。詞典通常非常小，因而，整個過程的時間是毫秒級的。

　　而用普通的順序匹配算法，不建索引，而是對所有文章的內(nèi)容進(jìn)行字符串匹配，這個過程將會相當(dāng)緩慢，當(dāng)文章數(shù)目很大時，時間往往是無法忍受的。