I skimmed your paper. It's good stuff! The implementation in the OP is loosely based off this paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.2

I skimmed your paper. It's good stuff! The implementation in the OP is loosely based off this paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.3698&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.... --- The algorithm in your paper is roughly similar, but the key difference is the observation that the output tape of the transducer can itself be compressed---so long as your outputs follow a certain algebra.[1] There are two other critical pieces to a non-toy implementation that most papers don't cover, particularly with respect to very large sets (billions of entries): 1. Representation of the FST itself. To squeeze the most juice, you ideally want most states to occupy no more than 1 byte. Anything by Jan Daciuk[2] in this space is excellent. 2. The hash map used during construction of the FST is universally glossed over, but it is absolutely critical. A standard hash map will store all states, which means you'll need to fit your entire FST into memory. Throwing away the hash map means that your FST isn't compressed very well. So you need something in between that's bounded and tuned to give the best bang for your buck. All of these considerations make FSTs like these non-trivial to implement. :-) [1] - https://docs.rs/fst/0.1.38/fst/raw/struct.Output.html https://docs.rs/fst/0.1.38/fst/raw/struct.Output.html [2] - http://www.cs.put.poznan.pl/dweiss/site/publications/download/fsacomp.pdf http://www.cs.put.poznan.pl/dweiss/site/publications/downloa...