OpenFst is a library for constructing, combining, optimizing and searching weighted finite-state transducers (FSTs).