FST(有限状态转换器)

定义

FST(Finite State Transducer,有限状态转换器)是一种把"有序字符串到值"的映射编码为状态机的数据结构:从起始状态沿字符转移到达终止状态即命中一个词,路径上的输出值累加即该词对应的值。在搜索引擎领域,它是压缩词典的标准方案。

原理

FST 同时共享词项的公共前缀与公共后缀(可视为 Trie 的进一步最小化),因此体积远小于哈希表或跳表词典,大词典也能常驻内存。查询单词的时间只与词长有关,与词典规模无关;由于按字典序组织,还天然支持前缀匹配、范围遍历,配合自动机求交可高效实现通配符与模糊(编辑距离)查询。构建要求输入按字典序排序,构建后不可变。

应用

Apache Lucene 用 FST 存储倒排词典的 term index 与词到词条元数据的映射,Elasticsearch 的 completion suggester(自动补全)整个建立在 FST 上;Rust 的 fst 库等也提供通用实现。中文分词器的词典加载同样常用 FST 压缩。