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.12.0-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ce73172c8365480de112b852e5ec06581be57b4e7f1c8f90206bb7a2674f035d |
|
MD5 | fcf8944e59d55b9998f66f659457b600 |
|
BLAKE2b-256 | 4d25340a77fd3144fad661c8327ffb9828c1490385a4cf1f99d995aec4d0e087 |
Hashes for rustfst_python-0.12.0-pp39-pypy39_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | aa0faccc8c14f0e51f8b7de57e64cad93de4a28629438d8a639046f5925e18e5 |
|
MD5 | 2047cfa5681b5744a390cb1d46b2cffb |
|
BLAKE2b-256 | 56fcceb35599c48bf06b9e097588afbfbdcdcbe7c6966e5ec7e97ab746c35e91 |
Hashes for rustfst_python-0.12.0-pp39-pypy39_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 64bdd9eafa172c1fb2fd2e8a8f322a8a0bf6c98cfcffc42cddfcaea2096e1b4c |
|
MD5 | 538925cbeddf4e50f33071b0c99d883c |
|
BLAKE2b-256 | e7ed7cf355b58fe81a2446f5d898ea3b73e5c835141ac880a9606430329bd38a |
Hashes for rustfst_python-0.12.0-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 34745ab15f7860a338aa806010e6354a51f6967f407b87366f3701e7b435c15a |
|
MD5 | cbaa488bf3e0737530e497afa3f70b28 |
|
BLAKE2b-256 | 7976d992026ad39daed85a5fcbd52ed0cfa7cfb8d099f13bdcb21fcd121df789 |
Hashes for rustfst_python-0.12.0-pp38-pypy38_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e8b024799fadba648acec3c31b14067aaa3ac84a919427ba1f9430baedf746c4 |
|
MD5 | ce4f277b3ed020e36e6448e3fe2ea02c |
|
BLAKE2b-256 | a05c5517cb4a4072571a8975f7734d9e3e34f10ab09987433b69a21c0160e654 |
Hashes for rustfst_python-0.12.0-pp38-pypy38_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1c67420ea3517e856543614634f3fb265ae5540a1ceccae4c08c5be36f8f015c |
|
MD5 | 12cc358d122a589e879adf56b3b7d4b3 |
|
BLAKE2b-256 | c1132cd7d0e7afc1b35d9be3f0a061ea1af8c481613682170abc3b06834ce341 |
Hashes for rustfst_python-0.12.0-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 22020cd586e18ab63db604e95d300cd3e771e6ab1b44d1862f64563e752d194e |
|
MD5 | 7efc161faaf63154a969ed838e127ebe |
|
BLAKE2b-256 | 63a2461bfe0ebeb7f8661a7d751564bddca2762792ed902d409cecaffd8c40ab |
Hashes for rustfst_python-0.12.0-pp37-pypy37_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 96916307f733ce241738bda0491f77482091c67608f3695d79652e375b913f33 |
|
MD5 | be2e072c2a8b6478aa95c9e81822aa56 |
|
BLAKE2b-256 | 53416111dd9be034d2c0d74639ee3817bdce1f06aa438cebf3d7b16cb764c2f1 |
Hashes for rustfst_python-0.12.0-pp37-pypy37_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 98de33ed3594eb6be289d024ba58f6f3a71068d03d574d556cf8090757fca815 |
|
MD5 | 91a33e9375a83a3b5ca7b32470907339 |
|
BLAKE2b-256 | a493e8e6083bb4cf80e8ac186e25f440b6dcf310b336bd0817ddaea2997f7da5 |
Hashes for rustfst_python-0.12.0-cp310-cp310-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cfc98f63bfaef0d59233161044b188d3be0996cf82046e742bdcac6af03b47e3 |
|
MD5 | 1adb5d25b7b09138b935f365da275ce4 |
|
BLAKE2b-256 | 2d8670d7f1c7c8b8ff2aedd81d06ee0cb617ec4a8d99be6e108a744bbff176cb |
Hashes for rustfst_python-0.12.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 83ef000baede45f0c58d05953dc6970bedd030028eb8e20f4ef6e64ff132f07b |
|
MD5 | d29121f6269c686ccc142c4ffca1ae60 |
|
BLAKE2b-256 | 0eff32632ce84820d7f2ba87d000287b62769312ae20996c23b93d69abd426c7 |
Hashes for rustfst_python-0.12.0-cp310-cp310-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0d730592481ed301f99e4f261023598ee45e9789530c302b3f04af63a18ffb7e |
|
MD5 | a79fdd58ca510cbdb22fb7b70e08596b |
|
BLAKE2b-256 | d604f81849edfbf07db4402fc998e83bf76023116323cb0456359f8ed283380f |
Hashes for rustfst_python-0.12.0-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 87aa40be1f5d7bdedabeb260acee1c9f5b68452679fdbaf521eabce36105c517 |
|
MD5 | 2e74f025bab90e751b71a6d305595230 |
|
BLAKE2b-256 | a9bd97cf3d31b7451450b44a8b9c78717612dad19518a0cb359b70bf2c9216e0 |
Hashes for rustfst_python-0.12.0-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1350c5e72a7df805155e505e1f7b33a1e4fd4558512e5874a94731c805f9513f |
|
MD5 | e7180dbe77972941e250d35912741e69 |
|
BLAKE2b-256 | 02dd5049720e288471119cc388225a2ce09da210ce254e21b2516d45bc1ba0a8 |
Hashes for rustfst_python-0.12.0-cp310-cp310-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9e0c6e9689cd37069fd69f1973aca6db8fdf3a7e4021f70d95d4dd05f1d17283 |
|
MD5 | c0406195bc85b0b98ac7c9b8dcee1c9b |
|
BLAKE2b-256 | 193230d011cce40a6b1aaa19541b7a5c8d46966d9ef2472fd9183b29178c1658 |
Hashes for rustfst_python-0.12.0-cp39-cp39-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 47bc9102b3a2c45d1dbbd493171e42931294bc123fc68a6cd66e33c53251ffd4 |
|
MD5 | 8dfe33a35dc799092ef9595123fabec0 |
|
BLAKE2b-256 | aa7696206e50dd781cb517d2a9d2bc20e45e972fd9d5c73cc209363f8e20e313 |
Hashes for rustfst_python-0.12.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7144d535840f8a20fd365eeaa620200cb8c8efd42e3c987edba87ca8d74c8ae4 |
|
MD5 | 533c55666c62d3e93666c0e5fb93a40b |
|
BLAKE2b-256 | ce86dc2051f65abdb4e53252de81b2f3058940234492888485862ebd385274a9 |
Hashes for rustfst_python-0.12.0-cp39-cp39-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3807d47066593b49f9ab5858301fa040ff163b85d09a8828bd227706c38b719f |
|
MD5 | 786928a97ce221206d02e0f218eadd57 |
|
BLAKE2b-256 | 0ab2d6c0610e17435066deeb3bbd525cf99b5c96b9342d424200e57ca2de77ce |
Hashes for rustfst_python-0.12.0-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d1b56f73059ab0f62438f3ec1155f24e3a9815491f452f4d9a605580fef1af30 |
|
MD5 | 0779b2bf5b526b501b68ef85f495a1cf |
|
BLAKE2b-256 | 348d8fc2f7d3f69e4d05c4b1a4d01253bf16c397e2c98a9bb8b4ae4df5357a97 |
Hashes for rustfst_python-0.12.0-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c9e07a4031db420f7e87631edd38cae3fc9122d6c941d452f492fc93155f99f4 |
|
MD5 | b0a153e6b23e6ce1a0c45c97a54b3a5b |
|
BLAKE2b-256 | 7a1fb439c13bb02a473176a50b7ca0032b83ad8e95db80384862bba01a45e78e |
Hashes for rustfst_python-0.12.0-cp39-cp39-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7c36f0a53ba0e8b934c92572b7cc29aa82e8c19d10715a357952107a1daf9ade |
|
MD5 | e0d3b155f48a51f6a3a04484c21f5766 |
|
BLAKE2b-256 | ec35a431ba9d47d2745819c988e743c3d2b7e2ecab7bb3d11a63f73e30489a19 |
Hashes for rustfst_python-0.12.0-cp38-cp38-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 076969037dbde45100c88cfc2e7aae8144d9c719d3e561fa760d38699d025336 |
|
MD5 | ec64751182d58e15d9e8c1dc8902274c |
|
BLAKE2b-256 | 09b484c5ade298131ab938751f15e8dcef53867dc2155667bc271a14ccb4d237 |
Hashes for rustfst_python-0.12.0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d49fbde05a1b7256b4b6e70dd189982e972466bf35b67cb29f15100b609d4869 |
|
MD5 | 0418999c793a8392216d82dd3cbb65c0 |
|
BLAKE2b-256 | 152adb13b5477df07df85545af0ae831f1808666d77a6c5f3efed73046a8ef6b |
Hashes for rustfst_python-0.12.0-cp38-cp38-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d5ea1d6137eef670b9b2bd8c659c8c0d919d51dd6a3e876b8b954a4f600a63cc |
|
MD5 | 8050b2c378b8dcfaa75dd890f0a1bd42 |
|
BLAKE2b-256 | 693066d6acccae76cd57396ab13d90d178caa9cae5a2d4e53b7eb11a5f7e090d |
Hashes for rustfst_python-0.12.0-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8bc25d845ef1f02150289e9c88f46b16d59f32e28ece21deed62367cf0dda237 |
|
MD5 | ae7d5c2de13774da330e181b32eea00f |
|
BLAKE2b-256 | 85aa5539083a2ff4246dd6d9b796289f5b02513d7020b294021cbf04527f2843 |
Hashes for rustfst_python-0.12.0-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 62489136925536a27a77b0ccd6e186c014fc76d3d9544e616adbb0def9364316 |
|
MD5 | 3a58a38a87bbac03b3a25833511d6a50 |
|
BLAKE2b-256 | 96c177833341bf5dee36acc11a85f598b280c8e7cd75342afc127123b3efb335 |
Hashes for rustfst_python-0.12.0-cp38-cp38-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 02e2e64761790edf6e16fd5e8a2531a5068231f40fc3e0f83e8e11055e8fbe19 |
|
MD5 | 869c3d26d1d6720320358fc9d43ee95c |
|
BLAKE2b-256 | af05467336672b942f1da4e03d46e957d433a3dc139b783931c66c1bee3afb76 |
Hashes for rustfst_python-0.12.0-cp37-cp37m-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8639071e2d4772bde8ae8116abd92cbaaa8b3c2271d2e84961742bd84f2a2082 |
|
MD5 | f681dd420d0ddd4629514b1ff7285211 |
|
BLAKE2b-256 | 17cc5f7df968dd22b3d91d80d6634adbbd0bced5cead4e57378a0def115a784e |
Hashes for rustfst_python-0.12.0-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3aa5e241611c187c18a0f8a72b26cb2272eb37be47dae44264b562d3e9f7f378 |
|
MD5 | 156bbcdc084fc9686c42a6cb6e867ec4 |
|
BLAKE2b-256 | caa6ca2257b6e10685b913828fc346d656ab7d7d118eb225f520156f720398ac |
Hashes for rustfst_python-0.12.0-cp37-cp37m-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d4c7f5c0dc9008dd7f336f582008b9324193874560bad92ec40746aedc92efe7 |
|
MD5 | 0693f585fb1ecc2b471ef73b3001ab84 |
|
BLAKE2b-256 | 9eb25c07101e8abbaa531de326bf57799f03ee4f68154df88810bd4065195b30 |
Hashes for rustfst_python-0.12.0-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2eba806649f73bc17150e1440c1520c48e969b160fd3b7fee4c92051fa09fd0f |
|
MD5 | 817980911bce8f13382617958a0739e6 |
|
BLAKE2b-256 | 4d84d61efce0ac5662f400f41dc877d0478b945e35f4a219f7315ec2df65f903 |