fst 共享后缀_FST源代码解读1——FST是什么

在之前研究IK的时候，看了他存储词典的格式，接触到了前缀树这种数据结构，他的好处是可以共享前缀，但是并不能共享后缀，而FST就能共享后缀，实现更加高效的存储或者查找。当然FST比前缀树添加了一个要求：必须是按照字典顺序添加的，而前缀树则没有这个要求。FST除了能存东西，判断某个东西是否存在，即起到Set的功能外，还能实现Map的功能，即存储、查找key-value。在lucene的词典表、同义词的模块中都使用了FST，另外，我自己在工作中，也用到了，用来保存分词的权重，使用FST的确是能大大的降低内存，当然他的查找复杂度是要比HashMap要慢一些，他的查找复杂度是O(length(input))，查找的内容越长需要的时间也就越多，但是他得内存消耗比起Hashmap来说真的是太小了。

通过上面的两天博客，可以大概了解FST的组成包括两部分，一个是节点(Node)，另一个是边(Arc)，一个arc指向一个节点，在这个arc上有一个输入叫做label，还有输出(也可能没有输出)，还有一个可能的finalOutput(最终输出，以后会介绍这个的作用)。一个节点可能有多个arc指向，但是一个arc只能指向一个节点。arc上的label其实就是输入的一部分，比如输入是abc，则会有三个arc，四个node，每个arc上的输出分别是a、b、，至于输出的话需要配合其他的节点才能确定。在FST的形成过程中，始终有一个叫做frontier的数组，也就是刚刚添加的一个term(或者说路线)，frontier的存在就是为了做共享前缀，当下一个term过来的时候，先计算共享前缀(所以这里要求FST必须是按照排序顺序写入的)，将现在的frontier中除去共享前缀以外的部分都会编译进入到fst中，然后将新的term出去共享前缀以外的部分写入到frontier，重新更新frontier，直到最后写入完成，调用Builder.finish方法将最后的frontier写入到fst中，然后再将root节点(也就是第一个节点，实际上就是所有的开头的arc)编译进fst，然后再经过压缩(不压缩也是可以用的，只是使用的内存会稍微一点)。在编译进入fst的时候，会查找共享后缀，比如之前写的是ab、现在突然来了一个bb，此时需要把aa编译进入fst，frontier中保存的是bb，等到下一个term过来时，假设来的是c，则需要把bb也编译进入，如果这里能用共享后缀的话，ab和bb就可以使用同一个边b指向结束的node了。看到这里估计会大概对fst有个初步的概念了。

FST很难以理解，但是真的很有用，理解了FST，也算是把自己的能力又提升了一个台阶。我个人用了一周的课余时间才把FST的代码看完，也算是收货颇丰，接下来我将分别介绍FST的生成、压缩、读取。先说一下我看的是lucene6.6版本的。

后续：第二篇博客，FST的生成并没有发表完全，ITEYE提示我有敏感词没法发表，所以仅仅保存了一部分，经过几个小时的努力仍然没有找到哪个词是敏感词最终放弃了，所以第二篇博客写的不全。浪费我好几个小时！