原文作者：sbp810050504

原文地址：lucene (42)源代碼學習之FST(Finite State Transducer)在SynonymFilter中的實現思想

在Lucene4中，很重要的一種數據結構就是FST(Finite State Transducer),又稱Mealy Machine。在SynonymFilter的實現中，FST可以用HashMap代替。但是相比HashMap，FST有以下優點：

• 緊湊的結構，通過對詞典中單詞前綴和后綴的重復利用，壓縮了存儲空間。
• O(len(str))的查詢時間復雜度。

如果不考慮FST的輸出，FST本質上是一個最小的，有向無環DFA。

經過差不多一個星期的學習，終于對Lucene中FST的構造過程有了初步的了解。為了簡化問題，我們把FST的輸出都置為相同的因子。

案例：

對aaaa,bbaa,ccbaa,ddcbaa這4個單詞構建FST。(注意：單詞插入前必須先進行排序，否則就無法生成最小FST)

先給出最終的結果：

(注：這副圖來自于http://examples.mikemccandless.com/fst.py)

那么其構造的過程是怎么樣的呢？我們從Lucene42的org.apache.lucene.util.fst.Builder類的add()方法作為切入口。對于Lucene42的源代碼，有這樣幾點需要理解。

1、UnCompiledNode類和CompiledNode類

UnCompiledNode可以理解為沒有編入FST的結點，CompliedNode為已經編入FST的結點。在Builder類中，初始化了一個UnCompiledNode數組。這個數組中存儲的是什么呢？論文《Direct Buildingof Mimimal Automation for A Given List》中描述構造一個偽最小FST的方法：假設有{w1,w2....,wn} n個單詞。

a、先構造一個除單詞w1外，最小的FST。（此時FST中有w1一個單詞）

b、構造一個除w2外，最小的FST。（此時FST中有w1,w2兩個單詞）

c、構造一個除w3外，最小的FST。（此時FST中有w1,w2,w3三個單詞）

d、構造一個除w4外，最小的FST。（此時FST中有w1,w2,w3,w4四個單詞）

e、構造一個除ε(空串)外，最小的FST。此時FST最小。

這其實就是一種迭代的思想：UnCompiledNode存儲的就是上文提到的單詞w1，w2……。

2、freezeTail方法的作用

freezeTail方法的作用就是把UnCompiledNode進行Compile成CompiledNode。也就是構造一個除wi外，最小的FST。通過方法名稱，也可以理解為把后綴(tail)固定(freeze)下來。看論文不如走代碼，我們一步步看代碼是怎么走吧。

第一步：往FST中插入第一個單詞aaaa：

插入的代碼如下：

此時FST的結構如下：(狀態的編號代表Builder中frontier數組的下標；紅色的箭頭代表是結束邊)

上圖的FST即是除字符串aaaa外最小的FST，（其實最小FST為空）。

第二步：往FST中插入第二個單詞bbaa：

在插入之前，需要對aaaa進行freezeTail，即把除aaaa和bbaa前綴之外的部分compile到最小FST中。Compile的過程是從后往前的，也就是先處理State4，然后處理State3，FST把單詞的后綴存儲到HashNode這種數據結構中去，如果新插入的字符串在compile過程中，與前面的單詞有公共后綴，則直接使用其后綴，而不創建新的結點。其過程依次如下：(具體的代碼參考freezeTail函數)

freezeTail的過程中，把frontier的位置空出來了。然后將新的字符串插入到frontier中。

第三步：往FST中插入ccbaa：

在插入ccbaa之前，仍然需要將bbaa進行freezeTail。由于aaaa和bbaa有{a},{aa}這兩個共同的后綴，所以C2?、C4節點可以重復利用。

這個過程就是在利用后綴對狀態進行壓縮。

第四步：往FST中插入ddcbaa.

在插入之前對ccbaa進行freezeTail操作。

有了前面的基礎，這里就只畫出來了它的變化。經過freezeTail后，frontier數組又空出來了。接下來就把ddcbaa插入到FST中去。

最后一步，Builder.finish()。

在這一步中，會調用freezeTail(0)。這樣的話，整個FST就變成了一個最小的，無環FST了。

將兩副圖進行對比：

是不是一樣的？圖中狀態里面的數字，如?-1, 2，4?是程序處理過程中后綴存儲在NodeHash中的位置。可以這樣理解，FST用NodeHash存儲了字符串所有可能的后綴狀態。這里的分析過程，忽略了FST對output的處理。Output對FST的結構是沒有影響的。FST作為一種數據結構，在自然語言處理中應用非常廣泛，比如語音識別，機器翻譯等。在Lucene中也有廣泛的應用，比如同義詞處理、FuzzyQuery、拼寫檢查、自動補全等。其理論基礎就是有限狀態機。本文略過了論文中數學證明等知識點，(其實是我自己也沒弄清楚?)從Lucene源代碼實現的過程對FST的構造思想進行追蹤。

參考資料：

Build your own finite state transducer(http://blog.mikemccandless.com/2013/06/build-your-own-finite-state-transducer.html)

Lucene&solr4?實踐（4）(http://blog.sina.com.cn/s/blog_4d58e3c001016gg4.html)

《自動機理論、語言和計算導論(第二版)》

《編譯原理》

《Direct Building of Mimimal Automation for A Given List》

《Direct Construction of Mimimal Structure Acyclic SubsequentialTransducers》

總結

以上是生活随笔為你收集整理的常见索引结构—FST的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。