本文主要介绍了Finite State Transducers, 中文名叫做有穷状态转换器。 我是在学习Elasticsearch内部工作原理的时候接触到的。

了解FST

在了解FST之前，先来了解下Finite Automata，中文叫做有穷自动机。

有一点解释下，对于字符串001001, 是可以通过路径x0->x0->x1->x2，到达终点， 这样就可以停止了。

FST就是在FA的基础上，在路径上多了一个output label

FST中一个路径的写法

WFST, weighted finite state transducers, 就是在FST的state transition上增加了一个权重

更多资料在视频出处：https://www.youtube.com/watch?v=Qrf5SYEQjL8

FST与ES

FST在Lucene4.0以后的版本中用于快速定位所查单词在字典中的位置即FST<IntsRef，byteSequence>，由于Lucene是以二进制存储的，所以byteSecquence相当于一个数值，即用多个byte去表示一个数。 https://blog.csdn.net/fightingforcv/article/details/42709355

一个快速的(常量，或者1)定位词典的数据结构-FST https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/

实现共享状态的关键点是：每一个key,都在FST中对应一个唯一的路径。因此，对于任何一个特定的key，总会有一些value的转移组合使得路径是唯一的。我们需要做的就是如何来在转移中分配这些组合。 https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/

因为ES是倒排索引。假如有两个文档doc1,doc2,形成了一个倒排索引：

当查询单词textworld的时候，首先得确认这个单词在不在集合中，因此需要用到FST