#FST #graph #transducer #acceptor #shortest-path


Library for constructing, combining, optimizing, and searching weighted finite-state transducers (FSTs)

12 unstable releases (4 breaking)

✓ Uses Rust 2018 edition

0.5.0 Feb 4, 2020
0.4.0 Nov 12, 2019
0.3.0 Apr 3, 2019
0.2.0 Jan 7, 2019
0.1.7 Oct 28, 2018

#135 in Data structures

Download history 16/week @ 2020-01-30 5/week @ 2020-02-06 37/week @ 2020-02-13 24/week @ 2020-02-20 72/week @ 2020-02-27 24/week @ 2020-03-05 12/week @ 2020-03-12 48/week @ 2020-03-19 12/week @ 2020-03-26 4/week @ 2020-04-02 61/week @ 2020-04-09 36/week @ 2020-04-16 1/week @ 2020-04-23 2/week @ 2020-04-30 15/week @ 2020-05-07

117 downloads per month


16K SLoC


Build Status Current version Documentation License: MIT/Apache-2.0 Code Coverage Coverage Status

Rust implementation of Weighted Finite States Transducers.

Rustfst 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.



Implementation heavily inspired from Mehryar Mohri's, Cyril Allauzen's and Michael Riley's work :


use failure::Fallible;
use rustfst::prelude::*;

fn main() -> Fallible<()> {
    // Creates a empty wFST
    let mut fst = VectorFst::<TropicalWeight>::new();

    // Add some states
    let s0 = fst.add_state();
    let s1 = fst.add_state();
    let s2 = fst.add_state();

    // Set s0 as the start state

    // Add an arc from s0 to s1
    fst.add_arc(s0, Arc::new(3, 5, 10.0, s1))?;

    // Add an arc from s0 to s2
    fst.add_arc(s0, Arc::new(5, 7, 18.0, s2))?;

    // Set s1 and s2 as final states
    fst.set_final(s1, 31.0)?;
    fst.set_final(s2, 45.0)?;

    // Iter over all the paths in the wFST
    for p in fst.paths_iter() {
         println!("{:?}", p);

    // A lot of operations are available to modify/optimize the FST.
    // Here are a few examples :

    // - Remove useless states.
    connect(&mut fst)?;

    // - Optimize the FST by merging states with the same behaviour.
    minimize(&mut fst, true)?;

    // - Copy all the input labels in the output.
    project(&mut fst, ProjectType::ProjectInput);

    // - Remove epsilon transitions.
    rm_epsilon(&mut fst)?;

    // - Compute an equivalent FST but deterministic.
    fst = determinize(&fst, DeterminizeType::DeterminizeFunctional)?;



A big number of algorithms are already implemented. The main one missing is the Composition.


The documentation of the last released version is available here : https://docs.rs/rustfst


Licensed under either of

at your option.


Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.


~18K SLoC