lucene字典實現原理

1 lucene字典

使用lucene進行查詢不可避免都會使用到其提供的字典功能，即根據給定的term找到該term所對應的倒排文檔id列表等信息。實際上lucene索引文件後綴名為tim和tip的文件實現的就是lucene的字典功能。

怎麼實現一個字典呢？我們馬上想到排序數組，即term字典是一個已經按字母順序排序好的數組，數組每一項存放著term和對應的倒排文檔id列表。每次載入索引的時候隻要將term數組載入內存，通過二分查找即可。這種方法查詢時間複雜度為Log(N)，N指的是term數目，占用的空間大小是O(N*str(term))。排序數組的缺點是消耗內存，即需要完整存儲每一個term，當term數目多達上千萬時，占用的內存將不可接受。

2 常用字典數據結構

很多數據結構均能完成字典功能，總結如下。

數據結構	優缺點
排序列表Array/List	使用二分法查找，不平衡
HashMap/TreeMap	性能高，內存消耗大，幾乎是原始數據的三倍
Skip List	跳躍表，可快速查找詞語，在lucene、redis、Hbase等均有實現。相對於TreeMap等結構，特別適合高並發場景（Skip List介紹）
Trie	適合英文詞典，如果係統中存在大量字符串且這些字符串基本沒有公共前綴，則相應的trie樹將非常消耗內存（數據結構之trie樹）
Double Array Trie	適合做中文詞典，內存占用小，很多分詞工具均采用此種算法（深入雙數組Trie）
Ternary Search Tree	三叉樹，每一個node有3個節點，兼具省空間和查詢快的優點（Ternary Search Tree）
Finite State Transducers (FST)	一種有限狀態轉移機，Lucene 4有開源實現，並大量使用

3 FST原理簡析

lucene從4開始大量使用的數據結構是FST（Finite State Transducer）。FST有兩個優點：1）空間占用小。通過對詞典中單詞前綴和後綴的重複利用，壓縮了存儲空間；2）查詢速度快。O(len(str))的查詢時間複雜度。

下麵簡單描述下FST的構造過程（工具演示：https://examples.mikemccandless.com/fst.py?terms=&cmd=Build+it%21）。我們對“cat”、 “deep”、 “do”、 “dog” 、“dogs”這5個單詞進行插入構建FST（注：必須已排序）。

1）插入“cat”

插入cat，每個字母形成一條邊，其中t邊指向終點。

2）插入“deep”

與前一個單詞“cat”進行最大前綴匹配，發現沒有匹配則直接插入，P邊指向終點。

3）插入“do”

與前一個單詞“deep”進行最大前綴匹配，發現是d，則在d邊後增加新邊o，o邊指向終點。

4）插入“dog”

與前一個單詞“do”進行最大前綴匹配，發現是do，則在o邊後增加新邊g，g邊指向終點。

5）插入“dogs”

與前一個單詞“dog”進行最大前綴匹配，發現是dog，則在g後增加新邊s，s邊指向終點。

最終我們得到了如上一個有向無環圖。利用該結構可以很方便的進行查詢，如給定一個term “dog”，我們可以通過上述結構很方便的查詢存不存在，甚至我們在構建過程中可以將單詞與某一數字、單詞進行關聯，從而實現key-value的映射。

4 FST使用與性能評測

我們可以將FST當做Key-Value數據結構來進行使用，特別在對內存開銷要求少的應用場景。Lucene已經為我們提供了開源的FST工具，下麵的代碼是使用說明。

 1 public static void main(String[] args) {
 2         try {
 3             String inputValues[] = {"cat", "deep", "do", "dog", "dogs"};
 4             long outputValues[] = {5, 7, 17, 18, 21};
 5             PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton(true);
 6             Builder<Long> builder = new Builder<Long>(FST.INPUT_TYPE.BYTE1, outputs);
 7             BytesRef scratchBytes = new BytesRef();
 8             IntsRef scratchInts = new IntsRef();
 9             for (int i = 0; i < inputValues.length; i++) {
10                 scratchBytes.copyChars(inputValues[i]);
11                 builder.add(Util.toIntsRef(scratchBytes, scratchInts), outputValues[i]);
12             }
13             FST<Long> fst = builder.finish();
14             Long value = Util.get(fst, new BytesRef("dog"));
15             System.out.println(value); // 18
16         } catch (Exception e) {
17             ;
18         }
19     }