FST（Finite-State Transducer) 原理
参考依据
简介
Finite StateTransducers 简称 FST，通常中文译作有穷状态转换器或者有限状态传感器，我更偏向于后者，因为后者更加贴近原意。FST目前在语音识别和自然语言搜索、处理等方向被广泛应用。
原理
FST的功能更类似于字典，Lucene4.0在查找Term时使用了FST算法，用来快速定位Term的位置。FST的数据结构可以理解成（key,value）的形式， 在同义词过滤器SynonymFilter的实现中甚至可以用HashMap代替，不过相比较于HashMap，可以表示成：FST<key,value>的形式。 它的优点是：
- 可以用O(length(key)) 也就是查询时间复杂度来找到key对应的value。
- 在Lucene的term压缩存储中，FST以字节的方式来存储所有的Term，重复利用Term Index的前缀和后缀，使Term Index小到可以放进内存，减少存储空间，不过相对的也会占用更多的cpu资源。
- FST还可以用来快速确定term是否在系统中。 如何构建一个FST？假设有如下的Term Index（是排序过的）：
String inputValues[] = {"mop","moth","pop","star","stop","top"};
long outputValues[] = {0,1,2,3,4,5};
从上图我们可以感知一下FST的构建过程 1.创建一个节点node作为所有key的入口 2.如果还要未处理的key，则枚举出该key的每一个label 3.如果当前节点存在含此label的边， 则如果Value包含该边的out值，则 value = value – out 否则 temp=out–Value； out =value并使下一个节点的所有边out都加上temp。 如果下一节点是Final节点 则FinalOut += temp 进入下一个节点 否则： 新建一个节点另其out = Value， Value = 0。
使用场景
to be continue…