附:Lucene反向排序索引原理
Lucene反向排序索引原則
Lucene是apache軟件基金會Jakarta項目組的子項目[4]，是壹個高性能的java全文檢索框架。lucene索引結構的核心部分是反向排序索引。
用壹個例子來描述反向排序。
假設有兩篇文章:
第1條的內容是:* *和中國。
第二條的內容是:中國。
1，Lucene在建立索引之前通過分詞器找出文章中的關鍵詞。我們用壹元分詞作為例子。那麽第1條的關鍵詞是[* *][和][國]，第二條的關鍵詞是[中國][國]。
2、反向排序索引
分詞找到的對應關系是文章到關鍵詞的映射，所以處理後的結果不利於檢索，幾乎是全掃描。然後Lucene使用逆向排序建立索引，將這種關系轉化為關鍵詞到文章的映射，將關鍵詞排序為字符串。當然，lucene也在文章中加入了關鍵詞出現的頻率和位置等信息，這裏就不贅述了。排序後的結果見下表:
關鍵字
編號
***
國家
1,2
和
中間
簡單來說，lucene的逆向排序就是把分詞映射到文章的位置，按照分詞對這些記錄進行排序。
對於這樣的存儲結構，lucene使用二分搜索法算法進行搜索。這也是lucene高效的原因之壹。
本文簡要介紹了二分搜索法算法:二分搜索法算法或半搜索算法。對於n個元素的數組，二分搜索法算法最多進行1+log2(n)次比較，即有2的n次方個元素，比較最多n+1次。那麽1024 * 1024 * 1024個元素，也就是31次。
關於禁用詞分詞過濾的思考
禁用詞分詞的思路:建立禁用詞詞典，詞元為禁用詞(包括特殊符號，且不考慮正向和反向的最大匹配)。然後，用禁語參與者進行分詞後的逆向排序，就是把禁語映射到文章的位置，按照禁語對這些記錄進行排序。
比如，* * *和中國都是禁語。
第1條和第2條的倒排索引為:
關鍵字
編號
* * *中華民國
顯然，索引記錄的數量等於禁用詞的數量。這樣通過壹次建立倒排索引的過程就可以直接找到目標記錄，可以大大提高計算效率。