附: Lucene 倒排序索引 原理
Lucene 倒排序索引 原理
Lucene 是apache軟件基金會[4] jakarta項目組的壹個子項目,是壹個高性能的java全文檢索框架。 lucene 索引 結構 中最核心的部分是 倒排序索引 。
用壹個例子描述壹下倒排序。
假設有兩篇文章:
文章1的內容是:***和國。
文章2的內容是:中國。
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的倒排序索引就是:
關鍵詞
文章號
***和國
明顯地,索引記錄數等於違禁詞數。這樣,通過壹次建倒排序索引的過程就直接找出目標記錄,可大大提高計算效率。