ElasticSearch实战（五）-FST有限状态转换算法（索引数据压缩算法）
狄阳秋
Lucene使用FST算法以字节的方式来存储所有的Term，重复利用Term Index的前缀和后缀，使Term Index小到可以放进内存，减少存储空间，不过相对的也会占用更多的cpu资源。FST在Lucene4.0以后的版本中用于快速定位所查单词在字典中的位置。
Finite StateTransducers，简称 FST，通常中文译作有穷状态转换器，在语音识别和自然语言搜索、处理等方向被广泛应用。
FST的功能类似于字典，可以表示成FST<Key, Value>的形式。其最大的特点是，可以用O(length(key))的复杂度来找到key对应的value，也就是说查找复杂度仅取决于所查找的key长度。
假设我们现在要将以下term index映射到term dictionary的block序号：
“cat” —— > 5
“deep” —— > 10
“do” —— > 15
“dog” —— > 2
“dogs” —— > 8
最简单的做法就是定义个Map<string, integer="">，大家找到自己的位置对应入座就好了，但从内存占用少的角度想想，有没有更优的办法呢？答案就是FST。
对于经典FST算法来说，要求Key必须按字典序从小到大加入到FST中。上面的例子中key已经排好序了。
按照以下步骤建立FST：
类似资料：