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


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

10 releases

✓ Uses Rust 2018 edition

0.3.0 Apr 3, 2019
0.2.0 Jan 7, 2019
0.1.7 Oct 28, 2018

#287 in Data structures

Download history 28/week @ 2019-07-09 8/week @ 2019-07-16 3/week @ 2019-07-30 32/week @ 2019-08-06 184/week @ 2019-08-20 31/week @ 2019-08-27 38/week @ 2019-09-03 23/week @ 2019-09-10 115/week @ 2019-09-17 12/week @ 2019-09-24 24/week @ 2019-10-01 12/week @ 2019-10-15

68 downloads per month




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

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 Alluzen's and Michael Riley's work :


Add it to your Cargo.toml:

rustfst = "*"

Add extern crate rustfst to your crate root and you are good to go!


extern crate rustfst;

use rustfst::utils::transducer;
use rustfst::semirings::{Semiring, IntegerWeight};
use rustfst::fst_impls::VectorFst;
use rustfst::fst_traits::{MutableFst, PathsIterator};
use rustfst::Arc;

fn main() {
    // Creates a empty wFST
    let mut fst = VectorFst::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, IntegerWeight::new(10), s1))
    // Add an arc from s0 to s2
    fst.add_arc(s0, Arc::new(5, 7, IntegerWeight::new(18), s2))
    // Set s1 and s2 as final states
    fst.set_final(s1, IntegerWeight::new(31)).unwrap();
    fst.set_final(s2, IntegerWeight::new(45)).unwrap();
    // Iter over all the paths in the wFST
    for p in fst.paths_iter() {
         println!("{:?}", p);


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


Not all the algorithms are (yet) implemented. This is work in progress.


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.


~28K SLoC