Library for constructing, combining, optimizing, and searching weighted finite-state transducers (FSTs). Re-implementation of OpenFst in Rust.
Project description
Rustfst
Rust
Python
This repo contains a Rust implementation of Weighted Finite States Transducers. Along with a Python binding.
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.
References
Implementation heavily inspired from Mehryar Mohri's, Cyril Allauzen's and Michael Riley's work :
- Weighted automata algorithms
- The design principles of a weighted finite-state transducer library
- OpenFst: A general and efficient weighted finite-state transducer library
- Weighted finite-state transducers in speech recognition
Example
use anyhow::Result;
use rustfst::prelude::*;
use rustfst::algorithms::determinize::{DeterminizeType, determinize};
use rustfst::algorithms::rm_epsilon::rm_epsilon;
fn main() -> Result<()> {
// 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
fst.set_start(s0)?;
// Add a transition from s0 to s1
fst.add_tr(s0, Tr::new(3, 5, 10.0, s1))?;
// Add a transition from s0 to s2
fst.add_tr(s0, Tr::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)?;
// - 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)?;
Ok(())
}
Benchmark with OpenFST
I did a benchmark some time ago on almost every linear fst algorithm and compared the results with OpenFst
. You can find the results here :
Spoiler alert: Rustfst
is faster on all those algorithms 😅
Documentation
The documentation of the last released version is available here : https://docs.rs/rustfst
Release process
- Use the script
update_version.sh
to update the version of every package. - Push
- Push a new tag with the prefix
rustfst-v
Example :
./update_version.sh 0.9.1-alpha.6
git commit -am "Release 0.9.1-alpha.6"
git push
git tag -a rustfst-v0.9.1-alpha.6 -m "Release rustfst 0.9.1-alpha.6"
git push --tags
Optionally, if this is a major release, create a GitHub release in the UI.
Projects contained in this repository
This repository contains two main projects:
rustfst
is the Rust re-implementation.rustfst-python
is the python binding ofrustfst
.
License
Licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT) or http://opensource.org/licenses/MIT)
at your option.
Contribution
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.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distributions
Hashes for rustfst_python-0.11.5-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ce8bc66be70da08516d6223299959be4d0f7a8f571f14896f463551f10e6f149 |
|
MD5 | ec5f59cb1933f3a1d8e519f917cd1b42 |
|
BLAKE2b-256 | dc70585a952bba0c48b461c79787694c1ea7e855d34aff7fe2158a31feca52db |
Hashes for rustfst_python-0.11.5-pp39-pypy39_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0b70eba04363d092ae2c3ad80428503fd42de5b91b1a8873315439d7629e88d7 |
|
MD5 | bc8b5ff85d35ef274054931d93a0205c |
|
BLAKE2b-256 | 7dc997dffe6df31890590d8acd6f582c0addc5ad2b9c8532a54ea7cc57f0af09 |
Hashes for rustfst_python-0.11.5-pp39-pypy39_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 95396c3b38261d8ab5acb113ecf420860720d6cabf31550f02c1a7202830bee5 |
|
MD5 | 40af529405fc9fe17eee49f15089dbe7 |
|
BLAKE2b-256 | 3ea394565e3d0c61fc3770c064931aae20d0a64d98db36cd30e6ac0afe3e4227 |
Hashes for rustfst_python-0.11.5-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0275b1cd31a13441561ee2080c75e700361c7a2a8c9b7313ef02af90b531a05c |
|
MD5 | 0b51c535907b07798e78e0afc95805fb |
|
BLAKE2b-256 | e7243da4450237808c28074efbb871ea6d3b03c0a517d36c2b3727f3cc5708af |
Hashes for rustfst_python-0.11.5-pp38-pypy38_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a283d2934edc97322806b88d684a43961045afec97b08686c8d28c1021a88419 |
|
MD5 | a45e55f9191c4633f5b5e9c01bf2578b |
|
BLAKE2b-256 | cbb47a35168ff3523d880ed98e9095110c438aa072d60f274d4db65d8fbb51de |
Hashes for rustfst_python-0.11.5-pp38-pypy38_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 91bbdaf15b53e09d4082b3934e80e69410b7f49c109aff4ab630121349d741ac |
|
MD5 | 41300bb355c1e29aa38a3873fe87e05d |
|
BLAKE2b-256 | 0caecca908609260717e847b0f0419b62bcd710696b7a143e2a8f7aeffec1393 |
Hashes for rustfst_python-0.11.5-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3e33184902ae9d661e09948aea2147a93691c62a0705e654c712fdc99ce9611d |
|
MD5 | 000f31dbf3200aeeb7747e55d2205339 |
|
BLAKE2b-256 | a8bc2bbc41710848c9103a8d486171de341f03b3054d06059dcff20df13cc9ce |
Hashes for rustfst_python-0.11.5-pp37-pypy37_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 92f703d6292e767c91a5fc7434de5a4f6758251bb5fd2af522779595a188340f |
|
MD5 | 06b373ae29fdbfec8146989264047d7b |
|
BLAKE2b-256 | 19b9367c74cb3569fc0ea411c4c22744e1c88cd0a86db1c375e16e8988f54b66 |
Hashes for rustfst_python-0.11.5-pp37-pypy37_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2151ce0c4ef7b37dbf3f7fe9619fdf633c1e872127f6dbb3ae1e43a6ed5a28ff |
|
MD5 | e675474ac882a806bfd3960c1c204a1f |
|
BLAKE2b-256 | 3b92686661a5ba9471c5ed54ef31bf2c3b94165d4661c772d55154618354df37 |
Hashes for rustfst_python-0.11.5-cp310-cp310-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 502941847bb1a4d5870c734a2ea23d35e495d6ce3c25cbcf7f0ea8179adbc82f |
|
MD5 | fd9ac823effb6e6868d0eef73632d3e9 |
|
BLAKE2b-256 | 8aba529a76ce5abe163cb447c12703f4ad0a20a85e80316058d9974c9b7ea745 |
Hashes for rustfst_python-0.11.5-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9805d5ffd3a2bf0a8a0234e4f87817296ffa9318f788ba5068b7cff0a28050ed |
|
MD5 | 7f40d97bf56a80c9a7eceddeb76845f3 |
|
BLAKE2b-256 | 7a5402afe0edfee6048ceaadc91d87ad4841d5986178a242583ba3da2d20de77 |
Hashes for rustfst_python-0.11.5-cp310-cp310-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | aa05d6724fc2364be4afc691f651d3fecbc5408dd761063a7023d232ec634770 |
|
MD5 | 08de9bfa2bacbcb5cc144363d69d8ee9 |
|
BLAKE2b-256 | b9ce595814e92d08db8e265533137cfff1472c9a40691dc61df16af7b9d2bf84 |
Hashes for rustfst_python-0.11.5-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | aca44ee343bb6136bd7834f5ab96717a6c4d003d69caa801afa64d90f77c488f |
|
MD5 | 789a9dd5b353b69da9a2bd1a5ccaf386 |
|
BLAKE2b-256 | d385a2559dbdb698aeb876b8971de3d90e5dc97e79838291a03e4a6a0a30f53a |
Hashes for rustfst_python-0.11.5-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3f18af467cb7fceb82c32ea4e4c01ce87b5393646ec281e0ae3c9ea92057b2a5 |
|
MD5 | b9cfd26562569d2dc2a2a1adcb133b5e |
|
BLAKE2b-256 | 836259b9420d5fc2844ef426f9b4634745b7fd2767d27fc0eaa2708b5a4bb9fb |
Hashes for rustfst_python-0.11.5-cp310-cp310-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c2b37ab967e90359f7c41d0df6eb3bcead42525c27265009c61063a1f118a701 |
|
MD5 | c38dcf5308aac1440726b87176ab46d8 |
|
BLAKE2b-256 | d6fcf94fe24c0fe3e6c6f271d595ad9fc6f195828eba55f7e534b71caf499a24 |
Hashes for rustfst_python-0.11.5-cp39-cp39-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d4f687a265feb5b7dd0029ff7e0052be61f730a5eef751995b401e6f9ec6483d |
|
MD5 | d66ec2173b99cdad4d9a42fff4670538 |
|
BLAKE2b-256 | 159a8c416ef73ff86590313c19eedcdc55eaa44420fdf7103880fafc5cbd4a66 |
Hashes for rustfst_python-0.11.5-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4223f244a6d44dba9330911bc8b8a4f6b23955aa1a3e5662aa76e80826d8e5fb |
|
MD5 | 00a6f8a5b7fd1f6eb0aa6034cb594d3f |
|
BLAKE2b-256 | 5c8c96c5892841eb5b34a38172ccc0fe182e559b08d71eadf2446e7615419d45 |
Hashes for rustfst_python-0.11.5-cp39-cp39-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 32797f9708cc6f0c404206ea8fddf541b8b19ab32eaa9a9a34daa9623421b03e |
|
MD5 | 119be68020ffd32dbb29a6b511816dcf |
|
BLAKE2b-256 | 493e738c07bfadc1c08ba46c1b7fa6afe2ba3d6c2a104b2b0fb9d0f0396dce4b |
Hashes for rustfst_python-0.11.5-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bbb70980114c15a2d361d452624e40b12bfe4a351ab6e7c1dc010ea2a4fb143c |
|
MD5 | 4ff015fe43041e6c5cef02bb82abf26b |
|
BLAKE2b-256 | f2ded132d669f99571103d2a0fb71afabc7eed542e0c0e313965bdc2cf1dedf9 |
Hashes for rustfst_python-0.11.5-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b859b9d663c07b1376cf2d374b1fa180b8cc7e81947d01360949d5213c6f0df0 |
|
MD5 | e077f6838216e9bb18bd74c11953c3c1 |
|
BLAKE2b-256 | 4d1d06360b5c4f37df9075417d91a45e53ac90b7279b9c44112bdb60b2bec2fb |
Hashes for rustfst_python-0.11.5-cp39-cp39-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a5758d9c5c5dbb76bdc86ae58065a075acdaca061ed8c2d359e848134a8583a2 |
|
MD5 | f9f27eb810945c374cf02716a32dcd69 |
|
BLAKE2b-256 | 38101aa24d7407ee89dbb88894a335673f791905c369cce8c9afb7f522435d3c |
Hashes for rustfst_python-0.11.5-cp38-cp38-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1514389baa16439d0e2ba12b20ba8d048201c46cea0f8de340d57167e0c5e5e1 |
|
MD5 | fd1a391974ad3c7534cdd55e12c80416 |
|
BLAKE2b-256 | 091ef68c2d2e370c42d73b0a6dd3e17d515d306b63b7e7e047f59cee7c508783 |
Hashes for rustfst_python-0.11.5-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7db1d67b5ecfe12b94c8b0da31506568a7d0a290ca6b5facff70b0315d7575e9 |
|
MD5 | ea974359d80d697d0b29bfc137f5048e |
|
BLAKE2b-256 | f6676e4ffdcf2520bd92c581ee5811ecc7e7c3ed61fea6478c0c8a89a23a6080 |
Hashes for rustfst_python-0.11.5-cp38-cp38-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ef0ff01c588be61cb17b6760d82c090c0cc562bcc63fa76747e10727d68dd6df |
|
MD5 | af4d61043a75599bbc5c9044094b390b |
|
BLAKE2b-256 | 5cc5420b47b2815f70c23c5b210568fba9029b7534e72c6cea71f5cb9abd5d74 |
Hashes for rustfst_python-0.11.5-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ab239897c4f333c299303603c10e839f2666cbde34d8367e72e52f56eb63ba92 |
|
MD5 | b1428cd0d0dd82fe59cd2f1021151164 |
|
BLAKE2b-256 | e512149579881ba5f5d9c2d55f7732808f1f83094c4124662b229548feb3177c |
Hashes for rustfst_python-0.11.5-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 85bc8fb256ca0715eb2f73766f361c3aca977193495e3e4f42189e89490ca960 |
|
MD5 | 1962a0fbfef915e42bff5c542fc3726c |
|
BLAKE2b-256 | f38d664266f3fe85f27604b8c3876212fade7ae965d7693bfa7a7a2b27a086e0 |
Hashes for rustfst_python-0.11.5-cp38-cp38-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a41527db78874a85ca00bf60e50b2956d4962f3c2f141be563c75e463a913055 |
|
MD5 | 515e44ecc1fb1f971461df58815fb42f |
|
BLAKE2b-256 | 94cd6448c032c6de0f8259ab1f99aadb0b1ac9dc4d628fd46966bb0eb8bded07 |
Hashes for rustfst_python-0.11.5-cp37-cp37m-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f55f58a38f52c359779d0963daa6a25cf2472e12aeaa56616b7e11ced76ffa4d |
|
MD5 | 276314587eb45b39a98a7c57658203ae |
|
BLAKE2b-256 | 65d0094d5395b8d0f7dc3982f5c94b358bf520dbeea81ca8ac9374cc07c68649 |
Hashes for rustfst_python-0.11.5-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 53c72dd3546e7f6e7f04df0c9b7dab120d474dde333fbd2024436ef480df9cf1 |
|
MD5 | 3e01e9d25b7cc60f49c158ad11ceeac2 |
|
BLAKE2b-256 | 8b493155a4e807560aa2a7c4db7441513428d2ce9220b288057c01ad98b96876 |
Hashes for rustfst_python-0.11.5-cp37-cp37m-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1ac302e9ef289047e37a822daeb01cba8541622fd58c2bfe553adda653d6124f |
|
MD5 | b67f5df5f8c07dcb367a6fbd5361cd98 |
|
BLAKE2b-256 | b079ea1e6e70a4490f9326cedd2961b0e1416af9e6c1742c54cc564bc7ebf28e |
Hashes for rustfst_python-0.11.5-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d4f7079faf43c858fa391d23979b7b01ca7e36b4036a6ccbdbcfeb66653faa45 |
|
MD5 | ca143abf743ced6d52d55651e7e81fb7 |
|
BLAKE2b-256 | bb202afd0febdaf3d2985387196cf1b122eb74cdc2fda6660fe00b35b483a03a |