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.3-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7b66c74d33b505d021177596b112307216935e85ceb06195de58a67801281a5c |
|
MD5 | aa5737d711d044f4b5b98234fe23dfdb |
|
BLAKE2b-256 | b775c19c5407a0ddcc875cb3f0e8df2424e6248ae7a20a5ff9dbeb24c30071c2 |
Hashes for rustfst_python-0.11.3-pp39-pypy39_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3df09ce136761523178fc245491e005be423a79f2071de1a3dc650386b3031a1 |
|
MD5 | f693446b1ed5b28cc156e1e3784a7e1e |
|
BLAKE2b-256 | 54de4ec0a8918a441a70f373680d9f2c1538151d975739dbfb5c775e860c2732 |
Hashes for rustfst_python-0.11.3-pp39-pypy39_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c816cc8d41cc52f016f4d29018ed2bdbdbc1ad12ed4a33adcb6a326cd85234a4 |
|
MD5 | 1ab373efbd2df829c0f1a4bddc27c82c |
|
BLAKE2b-256 | dcc6afe89e51ccd8f57a930168ddf696372f035d3b515fc0967f47a6acc5f199 |
Hashes for rustfst_python-0.11.3-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7057e5bfad3a7435e455fb081ad06131a3cf42a3342e0711806987e5b73fe87a |
|
MD5 | e020edb925ac117e488c8a767cdb298e |
|
BLAKE2b-256 | c13ea086ca7addd7b671f37bdb20b7488750874bd5ea0a411e6f5c317f680b6e |
Hashes for rustfst_python-0.11.3-pp38-pypy38_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 922777076d1799bc598d957bc470ae776bc174728fd26607dc98367b602cd797 |
|
MD5 | 3136ecd08d36de770fd898ff8a4f62db |
|
BLAKE2b-256 | 8d3c704413cc2b1e901a020602e1ef349c30a298c2a090ed85d090385754832a |
Hashes for rustfst_python-0.11.3-pp38-pypy38_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9219072d0e4da46d9da0c24b8fb05b3e30f6252a37e7ca02f8b2190a34a13956 |
|
MD5 | 8e6c346c2b74785675c725a9604b2c69 |
|
BLAKE2b-256 | 48399176f9f8ff915472a33cdfd40383c1e16b3c745005051ac1927acbc3ec02 |
Hashes for rustfst_python-0.11.3-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1a48e55156f007185fbe5e873f1c663e5cdb942ce61f7c294550a0ab9c7cf450 |
|
MD5 | baa1c969a15eed4bef275f15b836319a |
|
BLAKE2b-256 | bc7e30786480205779802c181f725e5cca5657ce3b6e19c250e7cf2df0d641f3 |
Hashes for rustfst_python-0.11.3-pp37-pypy37_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b53f36e1f73c827d95ca5e0267d82eb0e7f1cac4a72713070e0fb75f550479eb |
|
MD5 | 88072a179f463065f93a23214adeda74 |
|
BLAKE2b-256 | 2fc61c476db38e27ca3724436f18c09af303278777c1d92138704fdf484b571b |
Hashes for rustfst_python-0.11.3-pp37-pypy37_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d387b0d124913e8e42df2940261f02a174bc5a019af0b7f8e372521fa462f565 |
|
MD5 | 0c7a554354f63781f1542bae5cf9ffa4 |
|
BLAKE2b-256 | f7c7d1f586ec27718491a11a86200f7c4d6b353377778ce81f989453637a9601 |
Hashes for rustfst_python-0.11.3-cp310-cp310-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9a78cc0f1eedd4a6e2ca966f267a33e52eb3f0dd59e547e7e9a2e7332e43fe96 |
|
MD5 | 64a9e4669ae51c6ed0ca99f6f5d1c281 |
|
BLAKE2b-256 | 4f433c7b2e99453dfd626c93f26d5f289ac88bd1c9ae83677255de3d48601d7f |
Hashes for rustfst_python-0.11.3-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 294ab28660ccf869d4697adb7ab9b72195c2a2523582b75aae655c2bb266ee1e |
|
MD5 | 9343a33694656179ec4e55e270f6c180 |
|
BLAKE2b-256 | 1319bb83c1aef745ff559e0fd492a034606bf6badf72915a21ebd74dadfce6cf |
Hashes for rustfst_python-0.11.3-cp310-cp310-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7c1bf5bee29b68cdb4db697a9e8cbce0cd8d0134ea137de46c73aff255647d36 |
|
MD5 | 102415d9822ec4d636d5d6870a80bebc |
|
BLAKE2b-256 | 5042a3b68abe8acf02c7ea78e9fba39e096413e898ba3fdb91fe1c10845a44cd |
Hashes for rustfst_python-0.11.3-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 14d694ea50b29faa67fbb362369496c90def259ed503257361b35303d1d9f285 |
|
MD5 | 013b2b6dcc1cb469d8a727b072a94954 |
|
BLAKE2b-256 | ece70cc9c54f470ba7504c9462c7f11a028a51abc75eb56c47b139486efee76b |
Hashes for rustfst_python-0.11.3-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | edb9c5f8a5673ebb392e4abd02105a0750167a9e5f409bb83ae322c66e7e07bf |
|
MD5 | db8d2ecefbc84eb21c5862ec140aab2c |
|
BLAKE2b-256 | dacb15d2365a7cc0452195029a487bb8ab3c9cdd84e0209f45c75b2c445e267f |
Hashes for rustfst_python-0.11.3-cp310-cp310-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6b672c856fd52f20b768432f45432927cf7443fe8e54417f28c0cf97d8042532 |
|
MD5 | 26d5adb9e4597dd37374075ce9115ec9 |
|
BLAKE2b-256 | 809168bf1982079e54615aafaa43d327f7aecc0f1c5609fba9e651097633d79e |
Hashes for rustfst_python-0.11.3-cp39-cp39-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fcfa6ba3dcd5bbce10895f04d1b2b8a00519370fbaf203df0b986fd00e820b9a |
|
MD5 | 505a3fb3beda5e354c679b7ec6ad70ae |
|
BLAKE2b-256 | e9b755a4b4eced02251d805f5023596d2858c77ac38a5038b48b313b42e7c204 |
Hashes for rustfst_python-0.11.3-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c59cf6e52fb83c6278cdd945dd9cd335ba2ba9664a33f071e1f60f5a6f46c87e |
|
MD5 | bd870d6b7266a63011004fcc326d9b0b |
|
BLAKE2b-256 | 2d303994763d3dd56e972e83f78784a6efa4cd6e07f0adf2f61a10d69a9f63a0 |
Hashes for rustfst_python-0.11.3-cp39-cp39-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b816b2523cc0786602e50c3522076242b004d7232378ddb24f87d7b4bcc6451e |
|
MD5 | ed48cbfe35356d43558aaecf0d8f4522 |
|
BLAKE2b-256 | c84092ba78dea70af3e18869cb3099f950f9c8016e679e22fe4d95cbede8d9f5 |
Hashes for rustfst_python-0.11.3-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4e1b2a42500b035cd5a833d991d8428968aec4f99b129fc5f6faca1bd162f6b1 |
|
MD5 | ad2e8c1f9a4b473d2ab77605bd654ed9 |
|
BLAKE2b-256 | 08009e45e4963f50eefe70e2c65be7fab15be7877bff0b5117c2f4c58d944cf2 |
Hashes for rustfst_python-0.11.3-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7f0525aa338159b7b25c5c93cfe49163eae4f19f4ecb60efa76d69f8eace537e |
|
MD5 | d8fa3988d9b96210852963906b44b8ab |
|
BLAKE2b-256 | 745c0e9c5a731bfc0dfb6a422c7ecb77e5353fc0ea7aad498c16b0ce55941a6f |
Hashes for rustfst_python-0.11.3-cp39-cp39-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3519f6c2030ae4eecc04835b1fda56f7819deb9f526e4e29f19c53edc44ce222 |
|
MD5 | ae28a0cca0277d6a71fb47dc07fb3739 |
|
BLAKE2b-256 | d8119efe4b860823bd572e5c71a25b31c2ec85e900c3b91db4e2a33a280e1c18 |
Hashes for rustfst_python-0.11.3-cp38-cp38-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 084e8bed9101f1f7462db0dd450622538d19608ac822d4a968b2f1a66958beb3 |
|
MD5 | 139fa13f5b498bec45764ef0a865e762 |
|
BLAKE2b-256 | c6b6bd19f290dfc8e208aac106785e2feac1d70abab4b5b17f45f06de11b542d |
Hashes for rustfst_python-0.11.3-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dc9506c8d5680316336e93558960e10e6ac339b516f1348b4c450b1cdf069482 |
|
MD5 | e5239a52a62dec96b704bb6af756015e |
|
BLAKE2b-256 | 965d25f207f6d9ec337c724651b4572f2ed7d11c4fffff8b21f148f88efa321e |
Hashes for rustfst_python-0.11.3-cp38-cp38-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | af031d1652c4ceb933eb65a344246cbe5e2b5c39c4cb9c852bfbd6e2332d7372 |
|
MD5 | bb96923abe13c88bf78b943ed20977f4 |
|
BLAKE2b-256 | 6d8a6fb252a42a3d4caccf82c6253437f77daca1f045d6cd4118c82acb85d1c2 |
Hashes for rustfst_python-0.11.3-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 67c645deda670991d095f157c017e9db6fad6854a54ccc8d4b6cff1928db8d94 |
|
MD5 | 37c0132c7cd90a0c8f0b1ccad2eca877 |
|
BLAKE2b-256 | d4f6d8d309a37fbce7c44acdeff261e36f1bc4ac7565c1790f7143e1f14ebfff |
Hashes for rustfst_python-0.11.3-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7e6ddac87bcd0d54007bc2cb71007585a973ac23841244f636ab1d832c75663c |
|
MD5 | 72d3d53727adcb473defcbe4eaeac31f |
|
BLAKE2b-256 | f541474f10f47859b01002d62157827d16ca92a093c6d211d5d117e4aae4e3d6 |
Hashes for rustfst_python-0.11.3-cp38-cp38-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f85ffe8efaae504382ddefd9acc3ee99009922fef8db35a268caab577e0e6f57 |
|
MD5 | 723513e6eddb9fdcb80667a7e55b0ab1 |
|
BLAKE2b-256 | 6cb984d245ffd62f50fe2d871acfefbf64896a2e1844ff423770da87ec15f5e0 |
Hashes for rustfst_python-0.11.3-cp37-cp37m-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c1c22598b1b51b56af416c133772640b2073d440e712de36ce772a5be0a070d7 |
|
MD5 | 29d8af9f22005b192cca9012425ad900 |
|
BLAKE2b-256 | 7457eb4f35b1685256b4efe20176830905f8bea783a05242dfa2e6ed879441cf |
Hashes for rustfst_python-0.11.3-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bf15a01a2ae358deaab5ef63941bd510fb96a2197ff60f0b9f0c844fe8a43259 |
|
MD5 | c738eab2f6f50291eea7a1100c1fc6fb |
|
BLAKE2b-256 | 2a71c67a4b13364478cc67e80ed525da889a4d84c32a7bb4792de4586e0cd744 |
Hashes for rustfst_python-0.11.3-cp37-cp37m-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d2077917ec6df2d3a006ee7b69dd1c1c3f4f11c39fcc0a43bc3844ca44e50818 |
|
MD5 | db3775ff6fe1271be3c710bcbfe7f85c |
|
BLAKE2b-256 | 19ba832f85ec74c95cbc2b14455bd9890ecaa880023a22a2e2dfe9a475a3c985 |
Hashes for rustfst_python-0.11.3-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 69f82d4121f68aedae45426019e9734d7d93ffa1e91993b2449fa9f15d4a97f8 |
|
MD5 | 12ec963ca46f07956e710c5c7302772e |
|
BLAKE2b-256 | 20bc73c9a1ff26dd2da442fbd958b5020642e522f40ae0ee9d92116b01a2ec43 |