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.13.0-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 958ff27c5d7c4e1769f86e7f3755f11acd6d8ecc438818ad03501cfc31cc6f36 |
|
MD5 | 9e3c99575726edaa2ce236c823e6a0c8 |
|
BLAKE2b-256 | 1ac36930a62566afd542fa0bf59460f47434193680bc70f03a20545d442979b8 |
Hashes for rustfst_python-0.13.0-pp39-pypy39_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 66ec4b39d170228711fcd00a5f7a20e949f7bf86da2ce2b65801e93bccbf632d |
|
MD5 | 75a28dcefbd9f5a313e5403457c8dd4a |
|
BLAKE2b-256 | 3054294b794d946bf4a05ca4c7e894388e73cf59e7618d1d566723e0ab53334d |
Hashes for rustfst_python-0.13.0-pp39-pypy39_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a8462ecf70f5ce791e452470b1ce34ef01e4a7fe61970304cdf0af03932b1fc5 |
|
MD5 | f08ad60b215cc90a23e451cc325deb73 |
|
BLAKE2b-256 | 92e6820c8a08393c4dbf9b105dab30afb65e7a62ba0403abbd968966eac4edcf |
Hashes for rustfst_python-0.13.0-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b9539614a17d7125ccde57a7dc720c2981c44047c8f6fb3f46b56123be007de7 |
|
MD5 | d739f77c8c33a42aec4ee5e96105a4bc |
|
BLAKE2b-256 | 8492847573925b653d84cf30988364edc8972526f6db085bda06fce5efa564b8 |
Hashes for rustfst_python-0.13.0-pp38-pypy38_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c6a1e0e7aeaebb7c117a2e228d3dc1b87887a02e2f4fd40837c20c8884a373cd |
|
MD5 | ca8ce1b8923b45001cd69d42bd8e8b36 |
|
BLAKE2b-256 | 7ec983774b41545442959b2e5e4d8729f6af1c21fd28c5f8e2f35d5f79af9200 |
Hashes for rustfst_python-0.13.0-pp38-pypy38_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 754b33fec749842ce522a98912d51f2d9baf20d8cc52a149b3cba83d971e164d |
|
MD5 | 94439bf130c8026fd951149430ba53b5 |
|
BLAKE2b-256 | a56335a48b9258d1fcb0b31d6a20a266875f9c36114448050e1f0346e2677b14 |
Hashes for rustfst_python-0.13.0-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bd660ddc13f90985e9948fcc2f8a0bd136c425e1afc2d81a117dc1c8a2325327 |
|
MD5 | 23eb8f55cb96e6087c5d192cb6cf3573 |
|
BLAKE2b-256 | cf85c30d196547d6edd58d6a059fa796ec6831eb521b5f1307d3a28700532a79 |
Hashes for rustfst_python-0.13.0-pp37-pypy37_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 79e2739a8ebcbba5d9238d53f3267d8bb687066ede98d3b13d2b6834ffb37300 |
|
MD5 | a43ef35801c7d31067247bef994bdaf3 |
|
BLAKE2b-256 | db0e756373eed98452956e9231463dc47ee90ca9612afb3fcf062d40962c902f |
Hashes for rustfst_python-0.13.0-pp37-pypy37_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 010b6cc02cf976923887358431fe9b457b2099846fe3c2c6cda269715023b75c |
|
MD5 | bd7153c8bac6c749e2ea3305526fc385 |
|
BLAKE2b-256 | fb29454a8394e24f4601bc1cba9c56faf1f0893afba00f134ebd985bd2b2f3bf |
Hashes for rustfst_python-0.13.0-cp310-cp310-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b8d7ce9e7ac8e3de48cf8dcfa19f13382b4adf53f5ac3a31fc959956e3a5b7fa |
|
MD5 | c9c1a24565ec4c78c21f4ce1b0739b1a |
|
BLAKE2b-256 | 38b96a72bc729b680d37fca52009a8b6f245a607b7e05baf2aae7691141b5ca6 |
Hashes for rustfst_python-0.13.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 28fb9fc786b8429167326239145e955a8430cabe89efa1ec0b6c0208bf54453a |
|
MD5 | 20286a9bce36a10a02cb47718199fae1 |
|
BLAKE2b-256 | 5e7ebf3905bf66a14d7e4e11383e91f5b0004fab90b627eddf079992b7af9032 |
Hashes for rustfst_python-0.13.0-cp310-cp310-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2bf0800f8744780f93e83ad398f0630a3728e32eccc40695310f8d9640e7d802 |
|
MD5 | 0e2a33dd5f50d1b61a9c8a630bd3442e |
|
BLAKE2b-256 | f2e0eb11dd9fbc4f6fa7bc335fcbbece385e271aad014a22493b89f385948ba5 |
Hashes for rustfst_python-0.13.0-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | de3577d13876779575554e57152b3325a6737b79627a338db19073e8c4b4c92e |
|
MD5 | b1c1b7a21d209c7dc7629a3a61cd37b5 |
|
BLAKE2b-256 | 9c29aa9b7133ac3c0c9498b7632a621b159f63e72645290259511c8d73dd7db3 |
Hashes for rustfst_python-0.13.0-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a57dd2f208fe179aa8d28bf851895855b11c6a680ffbadb0e6f68f06fb8bab04 |
|
MD5 | c6a81c9f09bc9b63cb3ebb78f9f08c05 |
|
BLAKE2b-256 | 3c6c18cbd263ddffce3c06e8e173699ad86c45932a07ff323cd908d27588d12d |
Hashes for rustfst_python-0.13.0-cp310-cp310-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f7dbef861e9b4c304b505687b277f572406dd1575f8056b1d7067f8cc12bedf0 |
|
MD5 | 01c9f9dcfe362cd85c63041314cb6697 |
|
BLAKE2b-256 | 92b308aa21644b90cf633f7ba60829cfcae5c17c91a4e04495aa5a6a5c8f9f40 |
Hashes for rustfst_python-0.13.0-cp39-cp39-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3ea6b4c5e56914b8a3e1f809393f6adfdb6a7881b1d19949c9758e62149b0830 |
|
MD5 | 739c54235a914cde696a8b06bf025ead |
|
BLAKE2b-256 | c8b8fe1519c9d36bddb1dcec81b38421151b87676fecf8ff6d4f61f5283b2310 |
Hashes for rustfst_python-0.13.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2fe9b882dbebf2b142fe28eb5d0d34b35d1724db6d422b0c6e946094792a39bd |
|
MD5 | 402a91114ce1cdd651fd29013b29ef6b |
|
BLAKE2b-256 | 3bc5e54993c01d02ebab16ea92639f0b39cd17f4647540da55b43f48c333ec5e |
Hashes for rustfst_python-0.13.0-cp39-cp39-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fda38d968852c68d5a0a8e8ee38f2aa2d47cc2815812f5782ffc789e578ac01a |
|
MD5 | 70f1e9c3440053cf9dedb2e1c1e43678 |
|
BLAKE2b-256 | e062e55dfbaafdfffb8318d3e555ca97621869dd5113fd78132f520b3957396b |
Hashes for rustfst_python-0.13.0-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c493c396112cc556f7da9e1b627e4d4e61f6e60900eb48ea1fed73fe56dec793 |
|
MD5 | 1dd2f8493d85cc8fa555f872522486c3 |
|
BLAKE2b-256 | 5437c4747a5f0320f4b6371c78394f4baff21826bf3fbd87bd7513577523ab53 |
Hashes for rustfst_python-0.13.0-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 72388f9d11708590b9123c22f1d6b3281e9ea341230ab0a1614d9babf6cafdc4 |
|
MD5 | d75e1572830569c6411c32c35e18006d |
|
BLAKE2b-256 | 0bb96a7c0e049ce0677ac6a688747ee4c606c579e25252468503799e9c11bd9c |
Hashes for rustfst_python-0.13.0-cp39-cp39-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 299abaa02b1f8c9fa7932701e0f541c9b1c82092edd657218a6c2a285b5a0e6e |
|
MD5 | 54d0bd01ac66204c2accbfad15edfbd0 |
|
BLAKE2b-256 | 1f21db130c2f8b3250d39f9002ecdf4fa475f28b65aa89584b1036ec252e18a7 |
Hashes for rustfst_python-0.13.0-cp38-cp38-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0ab08d57e2441784b3b938d31225f57ecf5ce6d3c76a3e4f1353e5d89bb429d9 |
|
MD5 | e1807b8869be4fbacf71e4c9d13b6d64 |
|
BLAKE2b-256 | c7a598a6d932dbec10ab0d5ba11a82ad7cd52779eceafe5205b6c4cfd4f1ab59 |
Hashes for rustfst_python-0.13.0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d45507a65da7b268f67b59f6f3864d36cb1d67f5b37ee3ed8a4aba567d225fbe |
|
MD5 | a7b457e854bb02c17bf209632968b053 |
|
BLAKE2b-256 | 512fb816bc322f6efa6e8dbb7eda0725c77012a9364584509b2f9b8ccc44a07c |
Hashes for rustfst_python-0.13.0-cp38-cp38-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f94ddd876336719b7abcc929a90a1e6f4f67debba0d4bcbbbc1037d3c3ef785e |
|
MD5 | 30963623f293a3878b1c205e469aef17 |
|
BLAKE2b-256 | b7ecc846c4d2cc77eb68fc41387718cc40ad8c8b4493f896de2323dfb3b182d9 |
Hashes for rustfst_python-0.13.0-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 83a2860204372e39d1f3952e5e2b37858785985d7b8f71170e876f01bb64ce68 |
|
MD5 | db40fdd209b1adb3f43c8fb6f95515dd |
|
BLAKE2b-256 | eebe6d67433992a5e64e9eed6d4ca4e82163fb06a315e5e396592035a534d4ae |
Hashes for rustfst_python-0.13.0-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6cbd7eae3f4846e0a5618b4f32c1f957cea557032693f30e31e2561008e0d139 |
|
MD5 | db31308513e18404caecdddacc321b22 |
|
BLAKE2b-256 | 5e283faecbf312f86e8ad82afd8867f95ef670d4427c3cd26734fff89a0621d7 |
Hashes for rustfst_python-0.13.0-cp38-cp38-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7b7e06777f1ed63d70419ec6291fe2df6aef852fa4b4753bc7e486c84cc73d0f |
|
MD5 | 3f079384092c3ce8a884c939baaa72d6 |
|
BLAKE2b-256 | e6b0f762283edfd307f3747d1fc02680f63c245562420dd3cb94f1977e30269e |
Hashes for rustfst_python-0.13.0-cp37-cp37m-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bd28d00b8899e24bc016c730a4a0975046700db45e73f5506e31fda31ac4b354 |
|
MD5 | 3391c1d740d6161f432c765c6a5d7e94 |
|
BLAKE2b-256 | 62b29cdeb91d7f19629ac0ccd361f156c531d44a5f397edf43d21f59e744d182 |
Hashes for rustfst_python-0.13.0-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3267357289804a1806567ed059c3f1b1792abbcb58a9ce39a387f9079de961d6 |
|
MD5 | 500cf5c5bee786567d4d08fb8905741d |
|
BLAKE2b-256 | ed6d981b49dd3d7cd1bb1b7b7e9f25ff30c36a6c54af703144056403f567cfe7 |
Hashes for rustfst_python-0.13.0-cp37-cp37m-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2f622d09cb24b7fb8c4c1c56db89569d98a6c667b88f24a2ddc60bed8fb6ad00 |
|
MD5 | 6c2248549a5c571fec934051f7abe902 |
|
BLAKE2b-256 | fa75a8836e887a63231dfa6f16a663ad55acc7bf1e8729cd75d661c22debfb46 |
Hashes for rustfst_python-0.13.0-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 157f03a00629b239d2893e92d164e27c5723ce1ea72287d6c9dd5cbaf71136f4 |
|
MD5 | f15b404a8222dcd96ed9b06c203f6a74 |
|
BLAKE2b-256 | 7295ff1534484011a655815a19fd2bcc933a49e3e07e18c1f3da3e4b9d323e47 |