有限狀態轉換器簡稱FST，中文通常翻譯為有限狀態轉換器或有限狀態傳感器。我更傾向於後者，因為它更接近初衷。FST廣泛應用於語音識別、自然語言搜索和處理。
FST的功能更類似於字典的功能。Lucene4.0使用FST算法快速定位$ Term的位置。FST的數據結構可以理解為(key，value)。
在SynonymFilter的實現中，甚至可以用HashMap來代替，但與HashMap相比，可以表示為:FST
它的優點是可以用O(length(key))即查詢時間復雜度，找到鍵對應的值。
在Lucene的$ term壓縮存儲中，FST以字節為單位存儲所有的$ Term，重用了$ Term索引的前綴和後綴，使得$ Term索引小到可以放入內存，減少了存儲空間，但相對占用了更多的cpu資源。
FST還可以用來快速確定系統中是否有$ term。
如何構建FST？假設有以下$ Term索引(已排序):
從上圖可以感受到FST的建造過程。
1.創建壹個節點作為所有鍵的入口。
2.如果您想要壹個未處理的鍵，請枚舉該鍵的每個標簽。
3.如果當前節點中存在帶有此標簽的邊，那麽如果Value包含該邊的out值，那麽Value = Value–out。
否則temp = out–value；Out =value並將temp添加到下壹個節點之外的所有邊。
如果下壹個節點是最終節點，則FinalOut += temp，並輸入下壹個節點。
否則:創建壹個out = Value且Value = 0的新節點。