Lucene(發(fā)音為 ['lusen] )是一個(gè)非常優(yōu)秀的開(kāi)源的全文搜索引擎,我們可以在它的上面開(kāi)發(fā)出各種全文搜索的應(yīng)用來(lái)。Lucene在國(guó)外有很高的知名度，現(xiàn)在已經(jīng)是Apache的頂級(jí)項(xiàng)目，在國(guó)內(nèi)，Lucene的應(yīng)用也越來(lái)越多。

Lucene的算法原理：

　　Lucene是一個(gè)高性能的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.

　1)全文分析：由于lucene是基于關(guān)鍵詞索引和查詢的，首先我們要取得這兩篇文章的關(guān)鍵詞，通常我們需要如下處理措施
　　a.我們現(xiàn)在有的是文章內(nèi)容，即一個(gè)字符串，我們先要找出字符串中的所有單詞，即分詞。英文單詞由于用空格分隔，比較好處理。中文單詞間是連在一起的需要特殊的分詞處理。
　　b.文章中的”in”, “once” “too”等詞沒(méi)有什么實(shí)際意義，中文中的“的”“是”等字通常也無(wú)具體含義，這些不代表概念的詞可以過(guò)濾掉
　　c.用戶通常希望查“He”時(shí)能把含“he”，“HE”的文章也找出來(lái)，所以所有單詞需要統(tǒng)一大小寫。
　　d.用戶通常希望查“live”時(shí)能把含“lives”，“lived”的文章也找出來(lái)，所以需要把“lives”，“lived”還原成“live”
　　e.文章中的標(biāo)點(diǎn)符號(hào)通常不表示某種概念，也可以過(guò)濾掉
　在lucene中以上措施由Analyzer類完成

　經(jīng)過(guò)上面處理后
　　文章1的所有關(guān)鍵詞為：[tom] [live] [guangzhou] [i] [live] [guangzhou]
　　文章2的所有關(guān)鍵詞為：[he] [live] [shanghai]

　2) 倒排索引：有了關(guān)鍵詞后，我們就可以建立倒排索引了。上面的對(duì)應(yīng)關(guān)系是：“文章號(hào)”對(duì)“文章中所有關(guān)鍵詞”。倒排索引把這個(gè)關(guān)系倒過(guò)來(lái)，變成：“關(guān)鍵詞”對(duì)“擁有該關(guān)鍵詞的所有文章號(hào)”。文章1，2經(jīng)過(guò)倒排后變成
關(guān)鍵詞 文章號(hào)
　　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)字符位置，即記錄該詞是文章中第幾個(gè)字符（優(yōu)點(diǎn)是關(guān)鍵詞亮顯時(shí)定位快）；b)關(guān)鍵詞位置，即記錄該詞是文章中第幾個(gè)關(guān)鍵詞（優(yōu)點(diǎn)是節(jié)約索引空間、詞組（phase）查詢快），lucene中記錄的就是這種位置。

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

　　以live 這行為例我們說(shuō)明一下該結(jié)構(gòu)：live在文章1中出現(xiàn)了2次，文章2中出現(xiàn)了一次，它的出現(xiàn)位置為“2,5,2”這表示什么呢？我們需要結(jié)合文章號(hào)和出現(xiàn)頻率來(lái)分析，文章1中出現(xiàn)了2次，那么“2,5”就表示live在文章1中出現(xiàn)的兩個(gè)位置，文章2中出現(xiàn)了一次，剩下的“2”就表示live是文章2中第 2個(gè)關(guān)鍵字。
　　以上就是lucene索引結(jié)構(gòu)中最核心的部分。我們注意到關(guān)鍵字是按字符順序排列的（lucene沒(méi)有使用B樹(shù)結(jié)構(gòu)），因此lucene可以用二元搜索算法快速定位關(guān)鍵詞。
　　實(shí)現(xiàn)時(shí) lucene將上面三列分別作為詞典文件（Term Dictionary）、頻率文件(frequencies)、位置文件 (positions)保存。其中詞典文件不僅保存有每個(gè)關(guān)鍵詞，還保留了指向頻率文件和位置文件的指針，通過(guò)指針可以找到該關(guān)鍵字的頻率信息和位置信息。

　　Lucene中使用了field的概念，用于表達(dá)信息所在位置（如標(biāo)題中，文章中，url中），在建索引中，該field信息也記錄在詞典文件中，每個(gè)關(guān)鍵詞都有一個(gè)field信息(因?yàn)槊總€(gè)關(guān)鍵字一定屬于一個(gè)或多個(gè)field)。
　　為了減小索引文件的大小，Lucene對(duì)索引還使用了壓縮技術(shù)。首先，對(duì)詞典文件中的關(guān)鍵詞進(jìn)行了壓縮，關(guān)鍵詞壓縮為<前綴長(zhǎng)度，后綴>，例如：當(dāng)前詞為“阿拉伯語(yǔ)”，上一個(gè)詞為“阿拉伯”，那么“阿拉伯語(yǔ)”壓縮為<3，語(yǔ)>。其次大量用到的是對(duì)數(shù)字的壓縮，數(shù)字只保存與上一個(gè)值的差值（這樣可以減小數(shù)字的長(zhǎng)度，進(jìn)而減少保存該數(shù)字需要的字節(jié)數(shù)）。例如當(dāng)前文章號(hào)是16389（不壓縮要用3個(gè)字節(jié)保存），上一文章號(hào)是16382，壓縮后保存7（只用一個(gè)字節(jié)）。 注意是“上一個(gè)詞”。由于詞典是按順序排列的，這種壓縮方法的效果會(huì)非常顯著。

　　下面我們可以通過(guò)對(duì)該索引的查詢來(lái)解釋一下為什么要建立索引。
假設(shè)要查詢單詞 “live”，lucene先對(duì)詞典二元查找、找到該詞，通過(guò)指向頻率文件的指針讀出所有文章號(hào)，然后返回結(jié)果。詞典通常非常小，因而，整個(gè)過(guò)程的時(shí)間是毫秒級(jí)的。
而用普通的順序匹配算法，不建索引，而是對(duì)所有文章的內(nèi)容進(jìn)行字符串匹配，這個(gè)過(guò)程將會(huì)相當(dāng)緩慢，當(dāng)文章數(shù)目很大時(shí)，時(shí)間往往是無(wú)法忍受的。

全文檢索框架的實(shí)現(xiàn)機(jī)制：

　　Lucene的API接口設(shè)計(jì)的比較通用，輸入輸出結(jié)構(gòu)都很像數(shù)據(jù)庫(kù)的表==>記錄==>字段，所以很多傳統(tǒng)的應(yīng)用的文件、數(shù)據(jù)庫(kù)等都可以比較方便的映射到Lucene的存儲(chǔ)結(jié)構(gòu)/接口中。總體上看：可以先把Lucene當(dāng)成一個(gè)支持全文索引的數(shù)據(jù)庫(kù)系統(tǒng)。

比較一下Lucene和數(shù)據(jù)庫(kù)：

全文檢索 ≠ like "%keyword%"

　　由于數(shù)據(jù)庫(kù)索引不是為全文索引設(shè)計(jì)的，因此，使用like "%keyword%"時(shí)，數(shù)據(jù)庫(kù)索引是不起作用的，在使用like查詢時(shí)，搜索過(guò)程又變成類似于一頁(yè)頁(yè)翻書的遍歷過(guò)程了，所以對(duì)于含有模糊查詢的數(shù)據(jù)庫(kù)服務(wù)來(lái)說(shuō)，LIKE對(duì)性能的危害是極大的。如果是需要對(duì)多個(gè)關(guān)鍵詞進(jìn)行模糊匹配：like"%keyword1%" and like "%keyword2%" ...其效率也就可想而知了。

　　通常比較厚的書籍后面常常附關(guān)鍵詞索引表（比如：北京：12, 34頁(yè)，上海：3,77頁(yè)……），它能夠幫助讀者比較快地找到相關(guān)內(nèi)容的頁(yè)碼。而數(shù)據(jù)庫(kù)索引能夠大大提高查詢的速度原理也是一樣，想像一下通過(guò)書后面的索引查找的速度要比一頁(yè)一頁(yè)地翻內(nèi)容高多少倍……而索引之所以效率高，另外一個(gè)原因是它是排好序的。對(duì)于檢索系統(tǒng)來(lái)說(shuō)核心是一個(gè)排序問(wèn)題。

　　所以建立一個(gè)高效檢索系統(tǒng)的關(guān)鍵是建立一個(gè)類似于科技索引一樣的反向索引機(jī)制，將數(shù)據(jù)源（比如多篇文章）排序順序存儲(chǔ)的同時(shí)，有另外一個(gè)排好序的關(guān)鍵詞列表，用于存儲(chǔ)關(guān)鍵詞==>文章映射關(guān)系，利用這樣的映射關(guān)系索引：[關(guān)鍵詞==>出現(xiàn)關(guān)鍵詞的文章編號(hào)，出現(xiàn)次數(shù)（甚至包括位置：起始偏移量，結(jié)束偏移量），出現(xiàn)頻率]，檢索過(guò)程就是把模糊查詢變成多個(gè)可以利用索引的精確查詢的邏輯組合的過(guò)程。從而大大提高了多關(guān)鍵詞查詢的效率，所以，全文檢索問(wèn)題歸結(jié)到最后是一個(gè)排序問(wèn)題。

　　由此可以看出模糊查詢相對(duì)數(shù)據(jù)庫(kù)的精確查詢是一個(gè)非常不確定的問(wèn)題，這也是大部分?jǐn)?shù)據(jù)庫(kù)對(duì)全文檢索支持有限的原因。Lucene最核心的特征是通過(guò)特殊的索引結(jié)構(gòu)實(shí)現(xiàn)了傳統(tǒng)數(shù)據(jù)庫(kù)不擅長(zhǎng)的全文索引機(jī)制，并提供了擴(kuò)展接口，以方便針對(duì)不同應(yīng)用的定制。

　　可以通過(guò)一下表格對(duì)比一下數(shù)據(jù)庫(kù)的模糊查詢：

全文檢索和數(shù)據(jù)庫(kù)應(yīng)用最大的不同在于：讓最相關(guān)的 頭100條結(jié)果滿足98%以上用戶的需求。
Lucene的創(chuàng)新之處：

　　大部分的搜索（數(shù)據(jù)庫(kù)）引擎都是用B樹(shù)結(jié)構(gòu)來(lái)維護(hù)索引，索引的更新會(huì)導(dǎo)致大量的IO操作，Lucene在實(shí)現(xiàn)中，對(duì)此稍微有所改進(jìn)：不是維護(hù)一個(gè)索引文件，而是在擴(kuò)展索引的時(shí)候不斷創(chuàng)建新的索引文件，然后定期的把這些新的小索引文件合并到原先的大索引中（針對(duì)不同的更新策略，批次的大小可以調(diào)整），這樣在不影響檢索的效率的前提下，提高了索引的效率。

Lucene和其他一些全文檢索系統(tǒng)/應(yīng)用的比較：

關(guān)于亞洲語(yǔ)言的的切分詞問(wèn)題(Word Segment)
　　對(duì)于中文來(lái)說(shuō)，全文索引首先還要解決一個(gè)語(yǔ)言分析的問(wèn)題，對(duì)于英文來(lái)說(shuō)，語(yǔ)句中單詞之間是天然通過(guò)空格分開(kāi)的，但亞洲語(yǔ)言的中日韓文語(yǔ)句中的字是一個(gè)字挨一個(gè)，所有，首先要把語(yǔ)句中按“詞”進(jìn)行索引的話，這個(gè)詞如何切分出來(lái)就是一個(gè)很大的問(wèn)題。
　　首先，肯定不能用單個(gè)字符作(si-gram)為索引單元，否則查“上海”時(shí)，不能讓含有“海上”也匹配。
但一句話：“北京天安門”，計(jì)算機(jī)如何按照中文的語(yǔ)言習(xí)慣進(jìn)行切分呢？
　　“北京 天安門” 還是“北 京 天安門”？讓計(jì)算機(jī)能夠按照語(yǔ)言習(xí)慣進(jìn)行切分，往往需要機(jī)器有一個(gè)比較豐富的詞庫(kù)才能夠比較準(zhǔn)確的識(shí)別出語(yǔ)句中的單詞。
　　另外一個(gè)解決的辦法是采用自動(dòng)切分算法：將單詞按照2元語(yǔ)法(bigram)方式切分出來(lái)，比如：
　　　　"北京天安門" ==> "北京 京天 天安 安門"。
這樣，在查詢的時(shí)候，無(wú)論是查詢"北京" 還是查詢"天安門"，將查詢?cè)~組按同樣的規(guī)則進(jìn)行切分："北京"，"天安安門"，多個(gè)關(guān)鍵詞之間按與"and"的關(guān)系組合，同樣能夠正確地映射到相應(yīng)的索引中。這種方式對(duì)于其他亞洲語(yǔ)言：韓文，日文都是通用的。
　　基于自動(dòng)切分的最大優(yōu)點(diǎn)是沒(méi)有詞表維護(hù)成本，實(shí)現(xiàn)簡(jiǎn)單，缺點(diǎn)是索引效率低，但對(duì)于中小型應(yīng)用來(lái)說(shuō)，基于2元語(yǔ)法的切分還是夠用的。基于2元切分后的索引一般大小和源文件差不多，而對(duì)于英文，索引文件一般只有原文件的30%-40%不同。

目前比較大的搜索引擎的語(yǔ)言分析算法一般是基于以上2個(gè)機(jī)制的結(jié)合。關(guān)于中文的語(yǔ)言分析算法，大家可以在Google查關(guān)鍵詞"wordsegment search"能找到更多相關(guān)的資料。

Lucene的結(jié)構(gòu)框架：
　　注意：Lucene中的一些比較復(fù)雜的詞法分析是用JavaCC生成的（JavaCC：JavaCompilerCompiler，純Java的詞法分析生成器），所以如果從源代碼編譯或需要修改其中的QueryParser、定制自己的詞法分析器，還需要從https://javacc.dev.java.net/下載javacc。
　　lucene的組成結(jié)構(gòu)：對(duì)于外部應(yīng)用來(lái)說(shuō)索引模塊(index)和檢索模塊(search)是主要的外部應(yīng)用入口。

從Lucene學(xué)到更多：
　　Luene的確是一個(gè)面對(duì)對(duì)象設(shè)計(jì)的典范。

1. 所有的問(wèn)題都通過(guò)一個(gè)額外抽象層來(lái)方便以后的擴(kuò)展和重用：你可以通過(guò)重新實(shí)現(xiàn)來(lái)達(dá)到自己的目的，而對(duì)其他模塊而不需要；
2. 簡(jiǎn)單的應(yīng)用入口Searcher, Indexer，并調(diào)用底層一系列組件協(xié)同的完成搜索任務(wù)；
3. 所有的對(duì)象的任務(wù)都非常專一：比如搜索過(guò)程：QueryParser分析將查詢語(yǔ)句轉(zhuǎn)換成一系列的精確查詢的組合(Query),通過(guò)底層的索引讀取結(jié)構(gòu)IndexReader進(jìn)行索引的讀取，并用相應(yīng)的打分器給搜索結(jié)果進(jìn)行打分/排序等。所有的功能模塊原子化程度非常高，因此可以通過(guò)重新實(shí)現(xiàn)而不需要修改其他模塊。 
4. 除了靈活的應(yīng)用接口設(shè)計(jì)，Lucene還提供了一些適合大多數(shù)應(yīng)用的語(yǔ)言分析器實(shí)現(xiàn)（SimpleAnalyser,StandardAnalyser），這也是新用戶能夠很快上手的重要原因之一。

這些優(yōu)點(diǎn)都是非常值得在以后的開(kāi)發(fā)中學(xué)習(xí)借鑒的。作為一個(gè)通用工具包，Lunece的確給予了需要將全文檢索功能嵌入到應(yīng)用中的開(kāi)發(fā)者很多的便利。
　　此外，通過(guò)對(duì)Lucene的學(xué)習(xí)和使用，我也更深刻地理解了為什么很多數(shù)據(jù)庫(kù)優(yōu)化設(shè)計(jì)中要求，比如：

1. 盡可能對(duì)字段進(jìn)行索引來(lái)提高查詢速度，但過(guò)多的索引會(huì)對(duì)數(shù)據(jù)庫(kù)表的更新操作變慢，而對(duì)結(jié)果過(guò)多的排序條件，實(shí)際上往往也是性能的殺手之一。
2. 很多商業(yè)數(shù)據(jù)庫(kù)對(duì)大批量的數(shù)據(jù)插入操作會(huì)提供一些優(yōu)化參數(shù)，這個(gè)作用和索引器的merge_factor的作用是類似的。
3. 20%/80%原則：查的結(jié)果多并不等于質(zhì)量好，尤其對(duì)于返回結(jié)果集很大，如何優(yōu)化這頭幾十條結(jié)果的質(zhì)量往往才是最重要的。
4. 盡可能讓應(yīng)用從數(shù)據(jù)庫(kù)中獲得比較小的結(jié)果集，因?yàn)榧词箤?duì)于大型數(shù)據(jù)庫(kù)，對(duì)結(jié)果集的隨機(jī)訪問(wèn)也是一個(gè)非常消耗資源的操作。

本文轉(zhuǎn)自：http://www.chedong.com/tech/lucene.html