Data Structure - Finite State Transducer

Introduction

A finite state transducer (FST) is a finite state machine that consumes input symbols and emits output symbols. It is similar to finite state automaton (FSA), but in addition transducer produces output while consuming input symbols. Finite state transducer encodes relation between a set of inputs and a set of outputs.

For example the following FST represents dictionary:

              pms    -> 2017
              petro  -> 1984
              peter  -> 1977
              pavlo  -> 1957
            

Implementation

Finite State Transducer (FST) Library for .NET Core

Source Repository

Examples of usage

• Data Structure for Terms Dictionary in PMS full-text search engine.

Links

• Index 1,600,000,000 Keys with Automata and Rust
• Using Finite State Transducers in Lucene
• S. Mihov, D. Maurel, Direct Construction of Minimal Acyclic Subsequential Transducers