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.1-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f13f9e505e7740f68f7d7cf1f71540752e39d12075b9f27ca852a6ee88ad7b34 |
|
MD5 | ac9ab5aaf987946c10a9e5080532739d |
|
BLAKE2b-256 | 72edc0d739a2a03965a4bb4dcd26e2ad9b3861c2b9c14c1198cda2cfe20c1b70 |
Hashes for rustfst_python-0.13.1-pp39-pypy39_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3734a76c8bb122fb6ccdb6fb16e495518409cf93de26e2df88565e9547e4ccd8 |
|
MD5 | 5e4c4ef7d86b73cf724b3b0496181cd0 |
|
BLAKE2b-256 | 4a23740e70bb07f9f5bfb345ae3e3ecf856fa8e4581aa003b99b7e808f59fcdd |
Hashes for rustfst_python-0.13.1-pp39-pypy39_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 05c6426dae98b10767a9d00dc3551f6426acb81ca26632816c45fbc7044100ed |
|
MD5 | 404e13b849f6cd82605749519b8fdf18 |
|
BLAKE2b-256 | c62c87c93b39431fdb91d56284ed37e1cde819f09113200bd6eadd7d15475889 |
Hashes for rustfst_python-0.13.1-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d4d00c46dc1d7b10f61d3027e07f85a8a87558cf17efb7b15c8a94de8893d068 |
|
MD5 | 39cb512cd45a94112d21c7c7c4dd8989 |
|
BLAKE2b-256 | 5c0f86b4d69ddd9b9bfe4e0872cd24f894f3e56bacd50ce531e1d4a3ee883fd9 |
Hashes for rustfst_python-0.13.1-pp38-pypy38_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | de1dd64e0cc9088c5fdac5788c3c621f298e3a36150f6ace11b401738f4fdc17 |
|
MD5 | 7c6d7a0aef74b865d364c971131f07b8 |
|
BLAKE2b-256 | d97f30af6b8b1208f0aa58f159ed5ca556fa662a5041a7dfc7c14e2d51d7f583 |
Hashes for rustfst_python-0.13.1-pp38-pypy38_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 919bd23394ad8eeb3c3040a2d47c6bb1d2ab80d54c780464d747e074206f5195 |
|
MD5 | 4313e5347eaf6a0c7a2dc28ac567361b |
|
BLAKE2b-256 | 2b5ba59f5a096c1d218d31de421e2b6850d53b8a26ff8bb018f0c0e0a29f4cb1 |
Hashes for rustfst_python-0.13.1-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 958c78c37c18564fc883610b9aa3cb0fa90ad4f995a3d94ad01541674c0ad407 |
|
MD5 | 40471d1fde07b8454e52c1d8cd141e78 |
|
BLAKE2b-256 | db7353172f9bd6c72185f89a3a93d7bcbfe538a98d1c5caef7a8a43d32ab211e |
Hashes for rustfst_python-0.13.1-pp37-pypy37_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 113385698482790383bd4409ca144ad8ea653518b9de9474d823ab24b3b9b17d |
|
MD5 | 939b9bd512b063241eca4859d2334b31 |
|
BLAKE2b-256 | 62512537d113084bba4953585a40a1aeb6a303511d3ad1b16f755e57524214a1 |
Hashes for rustfst_python-0.13.1-pp37-pypy37_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ce317c0537718bf4ee9fdf2df914c5e0dc89a0697d09f48ecffebf43b1d04080 |
|
MD5 | 3b9718c1555319361bfdbb7a50ed56d9 |
|
BLAKE2b-256 | 24abfbe4dd48aca55d8de18b4ac07c7d7d706e7d878fce0c47712e8cf0f58371 |
Hashes for rustfst_python-0.13.1-cp310-cp310-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8af16e00b64622ee9571e61a8912a98e3fae6b0bf578947694c7f783406e946d |
|
MD5 | bd246796a5563bae5e0c4a5f3a4511ee |
|
BLAKE2b-256 | 8083a8b5e02154efa021b71d444ecf955d3dd35efcfe905a7940c389cde7b068 |
Hashes for rustfst_python-0.13.1-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ca6aa9e699e4202dd3817b485a516f0c4b00e36867544ddb85318e7e2231835c |
|
MD5 | 14b551ddab8850721baf3132ce5d423f |
|
BLAKE2b-256 | 72f517a26dc84e2fca42804f72b0b6a072e76ac1e3d0b81032348fc904444607 |
Hashes for rustfst_python-0.13.1-cp310-cp310-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 06f9cd60433088985470fec0b8c2a8d9968e95f353c6adbd08738175a6dfcbd9 |
|
MD5 | 514c2674fc199ed9365de383b3211865 |
|
BLAKE2b-256 | 65a7e40e686296663ce6d4b229d0399bed1abe94cf66d0249c8a1038d3ee06cf |
Hashes for rustfst_python-0.13.1-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 323b0474d2e254b052773636e771f6bca35cf0ae75dc5f479387ddfb1a773552 |
|
MD5 | 75eea744cd7e28ccd98f5110ebbd04f7 |
|
BLAKE2b-256 | 32039d9b16f68be65504c64f2803db075848e5f84603c714a403f977c6bd7316 |
Hashes for rustfst_python-0.13.1-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8eaa52f7f85a6852dfc372375ea056b45c392392f78ce121655d89d2e2aa6ef3 |
|
MD5 | 69aa02f4c1965dcdedfd99eafb0c1d6f |
|
BLAKE2b-256 | 4ca292e06d7951dcdcafb85780a7fee27b9dedea84b54bb382beb606a7c6c732 |
Hashes for rustfst_python-0.13.1-cp310-cp310-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bcec7ad0eaf5f25132b07c64db91121b146a22848bd1c7a5aa7b00a608d01059 |
|
MD5 | 9196a09d0749a90b717f5a0b43675134 |
|
BLAKE2b-256 | dd51f3e9ac9ae15b3b0634e00d01a1294946ff4552b0937acc40b62b413f861d |
Hashes for rustfst_python-0.13.1-cp39-cp39-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e677070fa88964c890a026340161f05744470055335b717fcd7225d889988213 |
|
MD5 | abf0754da80550ffe171e0dee910bfbd |
|
BLAKE2b-256 | 27d5445ad1083e045345fc6005634a6655d8418533736d59200b62151c761737 |
Hashes for rustfst_python-0.13.1-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 450c30934e6a65ba39d462bcb6e6c519cf96dc1bfb47fb3698ea092084a0ca07 |
|
MD5 | 713d1dfd5fa049004ec350e66ab331d0 |
|
BLAKE2b-256 | 29062c0565050ba8cc1edf0352db6d5ff673b15bbd091ddc80be329e77a902eb |
Hashes for rustfst_python-0.13.1-cp39-cp39-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d698b383cccc39d7f18a598bb71b68064225ee25100fc63432ab961d66139c78 |
|
MD5 | 3d61e8493e0ee83e7c401037468c4b01 |
|
BLAKE2b-256 | 07bb41871ba7d53ebe3b607480b9e9c19d467de9c4f0b87cbac764b1d1b3fde6 |
Hashes for rustfst_python-0.13.1-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5ca95eec9cd2a17dba9cad782ead802cba4e450d6123714af3ed43bdeefffafe |
|
MD5 | 95a5d19cbb64b433df61e2121b303d0e |
|
BLAKE2b-256 | 3b62fe3e0a7c1565744f42954a06aed17841b108405bd3bd8a6d9b9e0bdb30ec |
Hashes for rustfst_python-0.13.1-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 955f20df5b61e30f1f2cc2511de00cf62f58d2140294231f317c9e658342a30b |
|
MD5 | 32bb448d7fdbe865f986236af22f54a8 |
|
BLAKE2b-256 | eb1548c4436921ca57a77fb2630393c6ad3af68b3cc1f2c9d6bb311fed5b1307 |
Hashes for rustfst_python-0.13.1-cp39-cp39-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 33a73fd8c876dab227deca96cf0566920852f5c4705a3c618f84cef8a5470b84 |
|
MD5 | f95802d8223ba1f6ef6ce776f2cdb1cc |
|
BLAKE2b-256 | aea97df5d710e46dce254c435e3cc8fbed36f62c01086828351a6583d2e83c60 |
Hashes for rustfst_python-0.13.1-cp38-cp38-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c89cae5555496c47b11a23fb29edba95f6fe9df2622f043d53bb8597e57dc7bc |
|
MD5 | 6fc103e4faa75806b3146c274e5f2766 |
|
BLAKE2b-256 | caf8342d40a16aa111b8047d72f7dc4af5e2eee0d6603ef9625d667819bcc391 |
Hashes for rustfst_python-0.13.1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 42f112ff4c4d52400a3dae14803c06d3eaea02d6c2406e6c401d626004dbf74a |
|
MD5 | 8ad7927016d11621072b867d8b6f0ea5 |
|
BLAKE2b-256 | 48260f63176ebe9d02e0a8ebc9d43becda2d6d1e3276172d5c7b09188efb30b9 |
Hashes for rustfst_python-0.13.1-cp38-cp38-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 403c94fe7551987e21f3a30119a5b4e0939eeb5704757b31eaa158a535fef426 |
|
MD5 | 6e700cbd5019617dcb0e04bd445bba31 |
|
BLAKE2b-256 | 172d6cfffe7e9b28b3969d57b6f3bb4367a06c8e365f46084cfe8897ec4fdd84 |
Hashes for rustfst_python-0.13.1-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f6cb2ef31c6f99bbe4506befda6957ec28a81f91bf3629c2037fe182cc78b736 |
|
MD5 | ff4a80ae412e8268265f6fe20fe175c7 |
|
BLAKE2b-256 | 6518fede3b43ef3760d59a09d21f426218c9fd9f0893a9f6e7a6bfda0ba9b0c8 |
Hashes for rustfst_python-0.13.1-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 29a301ff7d84a0a8bb0522c8407a750196d1443f56037649067880f333fb8e00 |
|
MD5 | bc2e4b866ab7ac7296725f8c0b2b5309 |
|
BLAKE2b-256 | 8d7a4fe4c0c5e7247485981147fcb59fcac157e2541aeff9871a9fe684742786 |
Hashes for rustfst_python-0.13.1-cp38-cp38-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2872b5965f451ba706733c718360393247ce7a9fc56fd44d71c872f2ad62de67 |
|
MD5 | 79ef5e38dc029b1c03d250c9e9079898 |
|
BLAKE2b-256 | f8e3bb46dfc0fe26e197fa2bf35c19777c121e6371af480054f7e99e0f8a1d32 |
Hashes for rustfst_python-0.13.1-cp37-cp37m-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2d42730cd1c283a0f7e6c4d48ead712ec3cab8342ea91fd7e535a5c1238611fb |
|
MD5 | 87035a073c9c2455a3b84d6438bfd315 |
|
BLAKE2b-256 | 285b0e43af118a33d45c55b8e0d9233611a05038d6d71884a54d22a62d10b7bd |
Hashes for rustfst_python-0.13.1-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 57ee61ac30c33ffb0b4c7d59d7c9a674e9d6b5486319f9ffa327c59a723b4650 |
|
MD5 | f45b234d6fc5665aed5b20a23c947091 |
|
BLAKE2b-256 | f9f74765409313998f6cfdaae13eba0e66398ef6e00967462c7cbf7e61e82a94 |
Hashes for rustfst_python-0.13.1-cp37-cp37m-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | af6444c89a58b20210ac8572d1e40abf649c4c4deca0478e634b349fe0fe53f6 |
|
MD5 | 0709b181ae39a8f4191bab596e801ca7 |
|
BLAKE2b-256 | 612ad409934c456113459b9d8474ff5a80d48d63cf67abbccb5b9fc6a33e50db |
Hashes for rustfst_python-0.13.1-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5ad4e118856ddd39b7e21a50c2ee32e12bd2d988f3c0e4b1e9d1bd4e47c52119 |
|
MD5 | 000182568f718996885970033a61a9c9 |
|
BLAKE2b-256 | b4321b9b9c60ac2e3e347b8e4041aabce050bc229f5d078579c52e366e9ac4c4 |