Lucene中的FST算法描述

Lucene中的FST算法描述

FST（Finite State Transducer，一种有限自动机，或者称为Mealy machine）是lucene中的一个核心算法，用于检索term信息存储的位置。在lucene中，term按照其字典顺序排序（term在存储时称为input），term相关的信息按照term排序的次序存储在磁盘上（其存储的位置为outPut），（input/output)二元组将以FST的形式存储在内存中（input和output都是有序的）。检索时，根据input，通过计算FST中的路径上的权值信息，获取到output数据，最终在磁盘上定位term的其它附加信息。同时FST还能够快速的判断一个term是否在lucene中。

实际上FST相当于term在内存中的一个索引，lucene使用FST能够快速确定系统中是否存在查询的term，如果存在，能够快速定位其信息存放的具体位置。

FST与trie tree结构提供相似的功能，但是，在内存中存储更高效。

Please read full article from Lucene中的FST算法描述