add by zhj:在学习Lucene当使用存储结构时，看到它使用FST，这篇文章写得很好。
trie，FSA，FST用于解决有限状态机的存储，trie是树，它进一步演变成树FSA和FST，这两者是图
这篇文章的原标题是用自动机索引1.6万个键。我改了。原标题其实是
谈谈这三种数据结构的使用场景。
有限状态机(FSM, finite state machine)可用于紧密存储有序集合和有序键值对，实现快速搜索。在本文中，我将展示如何使用它FSM存储此类数据作为数据结构。
FSM作为数据结构
FSM是状态的集合和状态转移的集合。起始状态，0或多个结束状态。FSM同时只有一个状态。
FSM它很常见，可以用来描述一系列的过程。例如，我的猫Cauchy一天的日常生活:
里面有一些asleep”或者”eating”的状态，一些转移”food is served”, “something moved。这里没有结束状态，如果结束了，那就太可怕了！
FSM近似地表达了现实中的情况。Cauchy不可能同时吃饭睡觉。FSM在同一时刻，只有一个状态是相同的。此外，从一个状态转移到另一个状态需要外部环境的输出。我需要睡觉，可能是因为我吃饱了， 累了等等。不管他睡得多死，听到外面的声音，它总会醒来。
有序集合
有序集合中的键按字典顺序排序。典型的应用程序是二叉搜索树和B树。无序集合，典型的应用程序是哈希表。在这里，我们首先描述无环有限状态的接收器(deterministic acyclic finite state acceptor)，即FSA。
一个FSA满足以下条件：
确定性。给定已经输入，最多只能转移到一个状态。
无环。不能反序遍历。
接收器。FSA可接收一系列特定输入。
那么，如何用这些特征来表示一个集合呢？诀窍是，key作为FSA状态转移。这样，给定输入key，我们可以知道这一点key这个key是否在FSA中。
假设一个集合只有一个key”jul”。FSA如下：
这时候如果问FSA，是否包含”jul。处理顺序如下：
给定j，FSA状态从0变为1.
给定u，FSA状态从1变为2.
给定l，FSA状态从2变为3.
此时判断输入结束FSA是否处在final状态(图中用双圈表示)jul确实在set中。
如果这个时候问FSA，是否包含”jun。处理顺序如下：
给定j，FSA状态从0变为1.
给定u，FSA状态从1变为2.
给定l，FSA不动，处理结束。
FSA不动，因为状态2只接收l但目前的输入是‘转移’n因此，处理结束，也表明集合不包括在内。jun”。
如果这个时候问FSA，是否包含”ju。处理顺序如下：
给定j，FSA状态从0变为1.
给定u，FSA状态从1变为2.
判断此时是否在这里final状态。
值得注意的是，判断一个key是否存在，受限key而不是set的大小。
下面把key”mar”添加到FSA此时中去FSA表现如下：
FSA有点复杂，状态0可以转移两次。如果开始输入mar，它将首先转移到1状态。
还有一点需要注意的是，状态3被注意到了jul和mar两个key共享。也就是说，状态3可以由l和r转移过来。这种共享的方式，可以用更少的空间保存更多的信息。
如果再加入jun，FSA表现如下：
看到变化了吗？只有一点变化。FSA看起来和以前几乎没什么区别。唯一的变化是状态5以上的转移。FSA其实没有新的状态节点，因为jun和jul共享了前缀ju
下面展示一个更复杂的FSA，包含三个key，october，november，december。
因为有相同的后缀ber，在FSA只需编码一次。key后缀更大，ember。
在介绍FST在此之前，我们先来看看如何来遍历FSA中所有的key呢？
为了解释这个过程，还使用了以前的简单图片，有三个key，jul，jun和mar。
如下如下：
初始化状态0
移动到状态4，将j添加到状态4key中
移动到状态5，把u添加到key中
移动到状态3，将l添加到状态3key中，输出jul
返回状态5，把key抛弃中l
移动到状态3，将n添加到状态3key中，输出jun
返回状态5，把key放弃中n
返回状态4，把key抛弃中间的u
返回状态0，把key放弃中的j
移动到状态1，将m添加到状态1key中
移动到状态2，将a添加到状态2key中
移动到状态3，将R添加到状态3key中，输出mar
该算法直接应用于栈存储访问状态，并与栈存储相应转移。时间的复杂性是O(n)，空间复杂度O(k)，k是set最长键的大小。
有序map
和有序集合类似，只是多了一个输出。有序map常用于二叉查找树和b树，无序map就是hashtbale。我们在这里介绍一个deterministic acyclic finite state transducer，确定无环有限状态转移器，FST。
FST满足以下特点：
确定性。
无环。
一个转移器。给定一系列输入，输出一个值。当输入达到时FST的final状态。
FST和FSA很像，但是对于一个key，FSA只回答了”yer or no”，FST不仅回答”yes or no幸运的是，回到这里key相关值。
在有序集合中，只需要把它放在一起key转移时保存。但在这里，还需要返回和返回key对于的value。
一种方法是在每次转移中添加一些值。当输入序列在状态之间转移时，输出序列也在缓慢增加。
看一个简单的例子。map只包含一个数据jul，对应的value为7:
这类似于上述集合，但在第一个转移状态j之后，有一个相关的输出7。其他转移u和l相应的输出是0，所以图中没有显示.
若要判断，FST中是否存在key”jul处理过程如下：
初始化value为0
给定输入j,FST从状态0到1，value 7
给定输入u，FST从状态1到2，value 0
给定输入l，FST从状态2到3，value 0
状态3为输入结束final状态，因此key存在，value为7
下面把k-v,”mar 3”添加到FST中
在起始节点，有一个新的转移m，如果我们查询相应的输出3jul，所以应该和上面一样。
继续，当添加相同的前缀时key，会发生什么？
添加key jun，value 6
在状态5和状态3之间增加了一个转移n。但还有另外两个变化
0->转移j输入对应输出从7变为6.
5->转移l输入对应输出从0到1.
这个变化可以正确查询jun和jul，并返回正确的值。
这种key即使共享前缀，也保证了每一个属性key，然后只有一条路径可以贯穿整个过程machine。因此，每个key也有唯一的value。我们要做的就是如何将这些输出转移。
其实前缀不仅可以共享，后缀也可以共享。key tuesday和thursday，分别输出3和5.
这两个key前缀相同t，相同的后缀sday，输出的正确性可以通过图中的方式来保证。
在描述输出时，如果输出不是整形手术，实际上有一点局限性。的确，在FST输出类型必须满足以下特点：
加法
减法
取前缀(对整数而言)min)
构建
Trie树构建
trie树，前缀树FSA区别在于，FSA可以共享前缀和后缀。对于键mon，tues，thus来说，FSA如下：
而trie前缀如下：
构建trie树很直接。对于给定的输入，你只需要看看是否有相同的前缀。直到找到相同的前缀，剩下的直接转移到一个final状态可以。
FSA构建
FSA和trie区别在于共享后缀。所以一个FSA的空间会比trie它要少得多，但它更复杂，所以如果我们遵循它key插入字典序，会好很多，或者用图片来解释。
对于三个key，mon，tues和thurs。按字典顺序插入mon，thurs和tues。先插入mon：
下面插入thurs:
插入thurs以前的时间会导致mon被冻结。当FSA当其中一部分被冻结时，我们知道它将来永远不会被改变。因为按字典排序，后者key大于等于thurs所以不和mon前缀相同key插入。蓝色的state代表被冻结，以后不会改变，但可以重用。
虚线状态表示thurs还没有真正加入FSA中去，下面插入tues：
在这一步中，我们可以肯定hurs它会被冻住。因为会不会插入和它有相同前缀的词？thurs和mon有相同的final state了。
这里的状态4仍然是虚线，因为t开头还不确定key还有吗？如果下面插入zon：
看，状态4已经冻结了，因为它不会从t开始ky出现了，另外thurs和tues有一个共同的后缀s，因此状态7和状态9被合并了。
最后，在结束操作以后，把FSA的最后一部分冻住，一个完整的没有重复的结构如下：
因为mon和zon有相同的后缀，因此它们除了第一个状态转移不一样，剩下的可以重复利用。
FST构建
下面快速说一下FST构建，插入键值对 mon-2，tues-3，thurs-5.
直接上图，插入mon-2
对于第一步，我们也可以这样分配输出的值
其实这样也是可以的，但是在算法上来说，把输出放在靠近初始状态的地方，代码写起来更简单。
插入thurs-5
插入tues-3
在把状态0-4之间的输出从5变为3的之后，需要把4之后所有的输出全部加2，除了新添加的key，这样就可以保持输出的平衡。
下面插入一个tye-99
最后的完全形态