Openfst

Library for working with weighted finite-state transducers

OpenFst is a library for constructing, combining, optimizing, and searching weighted finite-state transducers FSTs. Weighted finite-state transducers are automata where each transition has an input label, an output label, and a weight. The more familiar finite-state acceptor is represented as a transducer with each transition’s input and output label equal. Finite-state acceptors are used to represent sets of strings specifically, regular or rational sets; finite-state transducers are used to represent binary relations between pairs of strings specifically, rational transductions. The weights can be used to represent the cost of taking a particular transition. FSTs have key applications in speech recognition and synthesis, machine translation, optical character recognition, pattern matching, string processing, machine learning, information extraction and retrieval among others. Often a weighted transducer is used to represent a probabilistic model e.g., an n-gram model, pronunciation model. FSTs can be optimized by determinization and minimization, models can be applied to hypothesis sets also represented as automata or cascaded by finite-state composition, and the best results can be selected by shortest-path algorithms.