The algorithm used for implementing an FST in Lucene is based on the paper Direct Construction of Minimal Acyclic Subsequential Transducers published by Stoyan Mihov and Denis Maurel. This algorithm can be used to build a minimal acyclic sub-sequential transducer (a type of FST) that represents a finite relation, given a sorted list of input words and their outputs. As this algorithm constructs the minimal transducer directly, it has better efficiency than other algorithms. It is the perfect fit for a Lucene FST, as all the terms in the Lucene index are stored in a sorted order.
Note
The following paper was referred to for building the algorithm: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.3698.
An FST is implemented in Lucene under the following package:
org.apache.lucene.util.fst
Let us see a few of the classes inside the package that can be used to work with an FST:
