trie、FSA、FST（转）
add by zhj:在學(xué)習(xí)Lucene的存儲結(jié)構(gòu)時，看到其使用了FST，這篇文章寫的不錯。
trie，F(xiàn)SA，F(xiàn)ST都是用來解決有限狀態(tài)機的存儲，trie是樹，它進一步演化為FSA和FST，這兩者是圖
該文的原標(biāo)題是“使用自動機來索引1,600,000,000個鍵”，我改了一下，原標(biāo)題其實是
說這三類數(shù)據(jù)結(jié)構(gòu)的使用場景。
原文：https://steflerjiang.github.io/2017/03/18/%E4%BD%BF%E7%94%A8Automata%E6%9D%A5%E7%B4%A2%E5%BC%951-600-000-000%E4%B8%AA%E9%94%AE/
本文翻譯自Index 1,600,000,000 Keys with Automata and Rust，所以標(biāo)題也直譯過來。
有限狀態(tài)機(FSM, finite state machine)可以用來緊密地存儲有序集合和有序鍵值對，并且可以實現(xiàn)快速搜索。本文中，我會表明怎樣用FSM來作為數(shù)據(jù)結(jié)構(gòu)存儲這樣的數(shù)據(jù)。
FSM作為數(shù)據(jù)結(jié)構(gòu)
FSM是一個狀態(tài)的集合和狀態(tài)轉(zhuǎn)移的集合。一個起始狀態(tài)，0個或多個結(jié)束狀態(tài)。一個FSM在同一時間只有一個狀態(tài)。
FSM非常常見，并且可以用來描述一系列過程。比如我家貓咪Cauchy一天的日常生活:
里面有一些”asleep”或者”eating”的狀態(tài)，一些轉(zhuǎn)移”food is served”, “something moved”。這里沒有結(jié)束狀態(tài)，如果結(jié)束了，那真是太恐怖了！
FSM近似的表達了現(xiàn)實中的情況。Cauchy不可能同時吃飯和睡覺，這跟FSM中同一時刻只有一個狀態(tài)是一樣的。并且，從一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)需要外部環(huán)境的一個輸出。需要睡覺，可能是因為”吃飽了”, “累了”等等。不管他睡得多死，”聽到外面的聲音”，它總會醒過來。
有序集合
有序集合里的鍵按照字典序排序。典型的應(yīng)用是二叉查找樹和B樹。無序集合，典型應(yīng)用就是哈希表。這里，我們先描述一個確定無環(huán)有限狀態(tài)接收器(deterministic acyclic finite state acceptor)，即FSA。
一個FSA需要滿足以下條件：
確定性的。給定已給輸入，最多只能轉(zhuǎn)移到一個狀態(tài)。
無環(huán)的。不能反序遍歷。
接收器。FSA可以接收一系列特定的輸入。
那么，怎么用這些特性來表示一個集合呢。訣竅在于，key作為FSA的狀態(tài)轉(zhuǎn)移。這樣，給定一個輸入key，我們可以知道這個key這個key是否在FSA中。
假設(shè)一個集合，只有一個key”jul”。FSA就像下面這樣：
這時候如果問FSA，是否包含”jul”。處理順序如下：
給定j，F(xiàn)SA狀態(tài)從0變?yōu)?.
給定u，F(xiàn)SA狀態(tài)從1變?yōu)?.
給定l，F(xiàn)SA狀態(tài)從2變?yōu)?.
輸入結(jié)束，這時候判斷一下FSA是否處在final狀態(tài)(圖中用雙圈表示)，表明jul確實在set中。
這時候如果問FSA，是否包含”jun”。處理順序如下：
給定j，F(xiàn)SA狀態(tài)從0變?yōu)?.
給定u，F(xiàn)SA狀態(tài)從1變?yōu)?.
給定l，F(xiàn)SA不動，處理結(jié)束。
FSA不動，因為狀態(tài)2只接收’l’的轉(zhuǎn)移，但是當(dāng)前輸入為’n’。因此處理結(jié)束，也表明集合中不包含”jun”。
這時候如果問FSA，是否包含”ju”。處理順序如下：
給定j，F(xiàn)SA狀態(tài)從0變?yōu)?.
給定u，F(xiàn)SA狀態(tài)從1變?yōu)?.
判斷一下，此時是否處于final狀態(tài)。
值得注意的是，判斷一個key是否存在，受限于key的長度，而不是set的大小。
下面把key”mar”添加到FSA中去，這時候FSA的表現(xiàn)如下：
FSA變得稍微復(fù)雜一點，狀態(tài)0可以有兩個轉(zhuǎn)移。如果起始輸入mar，它會先轉(zhuǎn)移到1狀態(tài)。
還有一個需要注意的是，狀態(tài)3被jul和mar兩個key共享。即，狀態(tài)3可以由l和r轉(zhuǎn)移過來。這種共享的方式，可以用更少的空間保存更多的信息。
如果再加入jun，F(xiàn)SA表現(xiàn)如下：
看到變化了么？只有一點點變化。FSA看起來和之前的幾乎沒什么區(qū)別。唯一變化的地方在狀態(tài)5多了一個轉(zhuǎn)移。FSA其實沒有新增狀態(tài)節(jié)點，因為jun和jul共享了前綴ju
下面展示一個更復(fù)雜的FSA，包含三個key，october，november，december。
因為有相同的后綴ber，在FSA中只需要編碼一次就行了。兩個key有更大的相同的后綴，ember。
在介紹FST之前，我們先看看，如何來遍歷FSA中所有的key呢？
為了闡述這個過程，還用一個之前的一個簡單的圖，有三個key，jul，jun和mar。
遍歷方式如下：
初始化狀態(tài)0
移動到狀態(tài)4，把j添加到key中
移動到狀態(tài)5，把u添加到key中
移動到狀態(tài)3，把l添加到key中，輸出jul
返回狀態(tài)5，把key中的l拋棄掉
移動到狀態(tài)3，把n添加到key中，輸出jun
返回狀態(tài)5，把key中的n拋棄掉
返回狀態(tài)4，把key中的u拋棄掉
返回狀態(tài)0，把key中的j拋棄掉
移動到狀態(tài)1，把m添加到key中
移動到狀態(tài)2，把a添加到key中
移動到狀態(tài)3，把r添加到key中，輸出mar
這個算法直接應(yīng)用一個棧存儲訪問過的狀態(tài)，和一個棧存儲相應(yīng)的轉(zhuǎn)移。時間復(fù)雜度為O(n)，空間復(fù)雜度O(k)，k是set中最長的鍵的大小。
有序map
和有序集合類似，只是多了一個輸出。有序map常用在二叉查找樹和b樹，無序map就是hashtbale。這里我們介紹一個deterministic acyclic finite state transducer，確定無環(huán)有限狀態(tài)轉(zhuǎn)移器，F(xiàn)ST。
FST滿足以下特性：
確定性。
無環(huán)。
一個轉(zhuǎn)移器。給定一系列輸入，會輸出一個值。當(dāng)且僅當(dāng)輸入會達到FST的final狀態(tài)。
FST和FSA很像，但是對于一個key，F(xiàn)SA只回答了”yer or no”，F(xiàn)ST不僅回答”yes or no”，還好返回和這個key相關(guān)的一個值。
在有序集合中，只需要把key保存在轉(zhuǎn)移時。但是在這里，還需返回與key對于的value。
一種方法是，在每次轉(zhuǎn)移的時候添加一些值。當(dāng)輸入序列在狀態(tài)之間轉(zhuǎn)移的時候，輸出序列也在慢慢增加。
還是看一個簡單的例子吧。map中只包含一個數(shù)據(jù)jul，對應(yīng)的value為7:
這和上面的集合差不多，只是在第一個轉(zhuǎn)移狀態(tài)j之后多了一個相關(guān)聯(lián)的輸出7.另外的轉(zhuǎn)移u和l對應(yīng)的輸出都是0，所以圖中就不顯示了.
如果要判斷，F(xiàn)ST中是否存在key”jul”，并且需要對應(yīng)的返回值，處理過程如下：
初始化value為0
給定輸入j,FST從狀態(tài)0轉(zhuǎn)移到1，value+7
給定輸入u，F(xiàn)ST從狀態(tài)1轉(zhuǎn)移到2，value+0
給定輸入l，F(xiàn)ST從狀態(tài)2轉(zhuǎn)移到3，value+0
輸入結(jié)束，狀態(tài)3為final狀態(tài)，因此key存在，value為7
下面把k-v,”mar 3”添加到FST中
在起始節(jié)點，多了一個新的轉(zhuǎn)移m，對應(yīng)輸出為3.如果我們查詢jul，那么應(yīng)該和上面是一樣的處理過程。
繼續(xù)，當(dāng)添加一個有相同前綴的key，會發(fā)生什么呢？
添加key jun，value 6
在狀態(tài)5和狀態(tài)3之間添加了一個轉(zhuǎn)移n。但是還有另外兩個變化
0->4轉(zhuǎn)移j輸入對應(yīng)輸出從7變成了6.
5->3轉(zhuǎn)移l輸入對應(yīng)輸出從0變成了1.
這個變化之后們可以正確查詢jun和jul，并且返回正確的值。
這種key的屬性確保了，即使共享前綴，對于每一個key，然后只有一個唯一的路徑可以貫穿整個machine。因此，每個key也有唯一的value。我們要做的就是怎么把這些輸出放在轉(zhuǎn)移中去。
其實不僅可以共享前綴，還可以共享后綴。對于兩個key tuesday和thursday，分別對于輸出3和5.
這兩個key有相同的前綴t，相同的后綴sday，按照圖里的方式可以保證輸出的正確性。
這里在描述輸出的時候，其實有一點局限，如果輸出不是整形。確實，在FST里用做輸出的類型必須滿足以下特性：
加法
減法
取前綴（對于整數(shù)來說就是min）
構(gòu)建
Trie樹構(gòu)建
trie樹，前綴樹。和FSA的區(qū)別在于，F(xiàn)SA可以共享前綴和后綴。對于鍵mon，tues，thus來說，F(xiàn)SA如下：
而trie樹只共享前綴，如下：
構(gòu)建trie樹很直接的，對于一個給定的輸入，只需要去看看有沒有相同的前綴。直到找出相同的前綴，余下的直接轉(zhuǎn)移到一個final狀態(tài)就可以了。
FSA構(gòu)建
FSA和trie的區(qū)別在于，共享后綴。因此一個FSA的空間會比trie少很多，但是構(gòu)建起來卻更復(fù)雜，因此我們?nèi)绻凑誯ey的字典序插入的話，會好很多，還是用圖片來說明。
對于三個key，mon，tues和thurs。按照字典序，插入順序mon，thurs和tues。先插入mon：
下面插入thurs:
插入thurs的時候，會導(dǎo)致之前的mon被凍結(jié)。當(dāng)FSA中一部分被凍結(jié)的時候，我們知道，它以后再也不會被更改了。因為按照字典序排序的，后面的key肯定都是大于等于thurs的。因此不會和mon有相同前綴的key插入了。藍色的state代表被凍結(jié)住，以后不會被更改但是可以被復(fù)用。
虛線的狀態(tài)表示thurs還沒有被真正加入到FSA中去，下面插入tues：
在這一步里，我們可以確定hurs會被凍住。因為將會不會有和它有相同前綴的詞插入進來了。因為thurs和mon可以有相同的final state了。
這里狀態(tài)4仍然是虛線，因為還不能確定t開頭的key還有沒有了。如果下面插入zon：
看到，這時狀態(tài)4已經(jīng)被凍住了，因為不會在有t開頭的key出現(xiàn)了，另外thurs和tues有一個共同的后綴s，因此狀態(tài)7和狀態(tài)9被合并了。
最后，在結(jié)束操作以后，把FSA的最后一部分凍住，一個完整的沒有重復(fù)的結(jié)構(gòu)如下：
因為mon和zon有相同的后綴，因此它們除了第一個狀態(tài)轉(zhuǎn)移不一樣，剩下的可以重復(fù)利用。
FST構(gòu)建
下面快速說一下FST構(gòu)建，插入鍵值對 mon-2，tues-3，thurs-5.
直接上圖，插入mon-2
對于第一步，我們也可以這樣分配輸出的值
其實這樣也是可以的，但是在算法上來說，把輸出放在靠近初始狀態(tài)的地方，代碼寫起來更簡單。
插入thurs-5
插入tues-3
在把狀態(tài)0-4之間的輸出從5變?yōu)?的之后，需要把4之后所有的輸出全部加2，除了新添加的key，這樣就可以保持輸出的平衡。
下面插入一個tye-99
最后的完全形態(tài)
總結(jié)
以上是生活随笔為你收集整理的trie、FSA、FST（转）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
