在之前研究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提示我有敏感词不能发表，所以只保存了一部分。经过几个小时的努力，我还是找不到哪个词是敏感词，最后放弃了，所以第二个博客写得不完整。浪费我几个小时！