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.6-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1cb61ced4a7342db2dd4bd4612569db4fc34aab111bbd74c2d9f349f5f5deb01 |
|
MD5 | 183266133c5249c344e4569ba329f2e4 |
|
BLAKE2b-256 | 9adc01b72a31c0352404f69e37a10d89175e211b63389f75952f5e7e4604fb00 |
Hashes for rustfst_python-0.11.6-pp39-pypy39_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e44d869c96695da008f803e22b56b1e8c242de88851bcbef986463e62d8dde76 |
|
MD5 | e24f711ee1fc1654696507a603f281b8 |
|
BLAKE2b-256 | 7de97daef3c834c2c3259b7dea626a5b0d7b2f742db2582f12f24a179e3a57cd |
Hashes for rustfst_python-0.11.6-pp39-pypy39_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a886783cbf141cd7dac9c6ed0a1757eceee83617b85cf4f327c1960914ec7997 |
|
MD5 | 97708d95fbda66e582e937e0db1bbea1 |
|
BLAKE2b-256 | afddbf43e2618d44fa89b5e387bc07e5dc8bc8de052fb8ea76c08a6b01483fec |
Hashes for rustfst_python-0.11.6-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d0d326228f197b02adc0ac77cac51cdcd173df7aae67a886261f4f5477f61a98 |
|
MD5 | 7fe65b695cadb79b3664879eea910439 |
|
BLAKE2b-256 | 888aeca921c47ccdcda0fa692ed7f2f519f142a3401383bcb6886f3c4d4a0024 |
Hashes for rustfst_python-0.11.6-pp38-pypy38_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 73021db2090ea4ac6e64fe3d087a83bd550d95b291cb36c9d1526e4ca6a367a3 |
|
MD5 | 1186379cbba353a6070f23148ce49e01 |
|
BLAKE2b-256 | c20bb1aad725321cdf4a321cd714693ae3f99222a8198260460e222effb80a27 |
Hashes for rustfst_python-0.11.6-pp38-pypy38_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0ef4c98c84d80360605abc749591b87d9bd52b4185f7cb9852e91dff01e19115 |
|
MD5 | 730630be134a292a5af0e1d6e825b411 |
|
BLAKE2b-256 | 74f7dcaa2e3fa86fc9c68030915669375c72995840a40b004ef2f57b5f76c657 |
Hashes for rustfst_python-0.11.6-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3e425731cf7af57cb8ef2f378b1c958844fc875a1db96384277ad9fe11a27d4d |
|
MD5 | a4dc50c530fbf69cf454ea199d4d2cb0 |
|
BLAKE2b-256 | e09af47b27b6d5124803dc1021dada09d88146c5f124434b7ad56e53b905d810 |
Hashes for rustfst_python-0.11.6-pp37-pypy37_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6dbd32da0e70f45305bd1da66754fba620b5150b3877de140a1a0d0c197d70f6 |
|
MD5 | 4fd6b90493869a50737bad7b44b6bd4b |
|
BLAKE2b-256 | 81a690e0a53c52c33c7301d139015e90c4ad36e7943c6d67cd8f2c080a19f2d7 |
Hashes for rustfst_python-0.11.6-pp37-pypy37_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4a5551adb5ec5ba6a9c1db9b4a123fecb729d2516842c83b42b314116af33582 |
|
MD5 | dfc4424e2eb56ddadd61b6b13d1dbe0d |
|
BLAKE2b-256 | 1221b0e4abe178088b01381f39b8911ab07d398ececa6bf4599cc7a9f43bce09 |
Hashes for rustfst_python-0.11.6-cp310-cp310-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8eaa707b2c9aca39a815c3abc2035f69cf62a183b7cfd9616b1b09e84e534a9e |
|
MD5 | cd720552083d335a61ec79f731f7d5d4 |
|
BLAKE2b-256 | 3e3a12150134979684d2c92696f30e82e71a34555e72660384b09264130ec5ed |
Hashes for rustfst_python-0.11.6-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1f2f9ebdd6bef541cbd32ef9227eba7fba29fabff148317d06e8f3922543b6d5 |
|
MD5 | d11cb2c26572ca22f0ecd02fbe002805 |
|
BLAKE2b-256 | 96b7f299c057a60adc4b9946ea10c847bb74941773444c23291100a752c85036 |
Hashes for rustfst_python-0.11.6-cp310-cp310-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ee008d71815987c239db9371dd2cdff5d0ba35560357c0e8b8c9ad13e1c2f3d6 |
|
MD5 | 4231cb11c902b77c1c4f740e112fc396 |
|
BLAKE2b-256 | ed7dfaff76e19cae4f0465cca220a630ccb7f6513ffbe75cc836d5aa25419a1d |
Hashes for rustfst_python-0.11.6-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4940847079f90b0ec3804c823c322fac79434eae5052246b4940a4d9d78428b6 |
|
MD5 | 195e250a586d9307e7b94b3b0d79c5dd |
|
BLAKE2b-256 | bc4c9232a0c030fff1123949b2c8dec6980cb39eea52331e9d27a4b30d76de3f |
Hashes for rustfst_python-0.11.6-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c20f88c548d6940bf6f0ebb2d4a792de80cf8af65a4827e681e0e42bb67cefdd |
|
MD5 | 106a083edf37ad29bb22a5457a75342e |
|
BLAKE2b-256 | b1eb687c3c639ef49ddf8f5a01e7cfeb651e5af7740d0e661ba3759ccc3b1998 |
Hashes for rustfst_python-0.11.6-cp310-cp310-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d663fa26e84bb4aa09b86d16d2b7d36fd50096cb9eb7fc8099b05ee1459fae45 |
|
MD5 | a202186d359b67c3d92cf39a82d4b8e8 |
|
BLAKE2b-256 | 18949fa3851915200b72d3e148c25176d283bca774245ff133e3e0e479e63be7 |
Hashes for rustfst_python-0.11.6-cp39-cp39-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0d47ae1ea69bbfccecef334e718e9de00163b42dcad116ee4f3e475706f4a7cf |
|
MD5 | d673d30736b98c31155c7a6e100dd90f |
|
BLAKE2b-256 | 28d587c9083af0a129efa466f5cec5dfb8818da2b03e5f1c3dbdbbb3e6acd15a |
Hashes for rustfst_python-0.11.6-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a287ddefc1fe141b295e405a5df7e65ccb1cd2e1ab3b8484bd78ca13a87ffb6f |
|
MD5 | 8e1859a3beb808649455a9bf021f6982 |
|
BLAKE2b-256 | dacd5452d6615b736d0e2735565afec485c7650d226f52dcbd0dbc2cdb90cd27 |
Hashes for rustfst_python-0.11.6-cp39-cp39-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9d7938f8837bf708b8ed99bbddc2d791e229b427058cd1c63c9813cee2c6519b |
|
MD5 | fe7d84cbda4544dd636d885cda617616 |
|
BLAKE2b-256 | 36e9546779ebec7268fac437334a45b0d7bfb3b27734e58666359b7787351dbb |
Hashes for rustfst_python-0.11.6-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4ac80420fae63050d52c0b24d394aa37199db7801a180ee197b0f3294401d2e0 |
|
MD5 | d9d4baee9c78a1711aa7ff3bb24ca771 |
|
BLAKE2b-256 | a62d462f5a9856b6998486cf8fe6a1540f19fdeb60176dcd1af3d8bf8dc9eb2a |
Hashes for rustfst_python-0.11.6-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1dc3814f4afea88b969cba2928eb121e7c3cdab3519bd72da14486d3508e9fb4 |
|
MD5 | df7cf8fac424f61ce0ef5d60b846797c |
|
BLAKE2b-256 | e466c9e709aca33adf2b7ffc061666bb0a9a3659c4945b84d2ce1137a4dbf7d3 |
Hashes for rustfst_python-0.11.6-cp39-cp39-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 16f6ea140f50a31b027c6fb5647e8b8e7d811c9df9244fa9c45d9068479f2ad2 |
|
MD5 | 4dfdd086c269675c4d19a3ad11fa4f12 |
|
BLAKE2b-256 | 7921f009d61a5ded52007ca94579d07323ee3320e4bd739f2bdaa838ffb8d29c |
Hashes for rustfst_python-0.11.6-cp38-cp38-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e7a56804e78d8b1579c070b3e3026a308c0ac4dddeb4c248d3dba9ee0b856095 |
|
MD5 | 34e33f011bb8968aa7b36ed57a7c9fbd |
|
BLAKE2b-256 | 20eec4549e37f5da7ce9152660455b71dbd6d4c8479817999bfd2c96a47d9585 |
Hashes for rustfst_python-0.11.6-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 85528f285a778cc78b5fd1774a7f770934367eb30b10bb045b1bfa34cf67edb8 |
|
MD5 | 08f80277f3e8d3e73af5e55ff6f1ef01 |
|
BLAKE2b-256 | ebe273a25d54bb957635e7ab39e62a165a8667cf24480699c70a390c363bd8c3 |
Hashes for rustfst_python-0.11.6-cp38-cp38-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ae04dccd3258b5ecbe1437a1649b0d9101856241c820eb8fd32e11b25d92fc5c |
|
MD5 | cb2dc7a4a10713daee791f3286b34740 |
|
BLAKE2b-256 | b4644142749c6c78444a30f4ad94f03490c35870e8ac59c26d54a2dc801ab7b8 |
Hashes for rustfst_python-0.11.6-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 24a824b4cf131f8c1481a08a5333d5ddbf42128ff567b110fc3aed765c599519 |
|
MD5 | fd19781578ead560e6029d8731bdb800 |
|
BLAKE2b-256 | 356e77aa2313996031208ed9daff447312a16d8409a777db8752abea83d56964 |
Hashes for rustfst_python-0.11.6-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d8d00de15db72f252b2a9de59c1277a6a16e042bc192d0e896c6ce72ec06b2e5 |
|
MD5 | 9857173299a4d3e45108c5a36dc8e30b |
|
BLAKE2b-256 | fb68d1fb935631e93b7af19436798a0ada203cb253e01464696e23fc5a377c0a |
Hashes for rustfst_python-0.11.6-cp38-cp38-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 94a1974f9e666807d944351b0af0466fdd18958dfc1aa41707edffca95c7a339 |
|
MD5 | 791c07a48d2574d15f5afc03b72bc6f9 |
|
BLAKE2b-256 | aab9094f9f247cba0ad7fb84509a5dc786c2878cf1562592ae6804b493b81d60 |
Hashes for rustfst_python-0.11.6-cp37-cp37m-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3bde514a6c408aafcf4458d378bf06ce2c28da77671c0801ff727769dcf40d71 |
|
MD5 | 7079435d24d9f8040cd7c8cee8ea35d1 |
|
BLAKE2b-256 | 9b8e8835abc2fb8df1659e74a2f62f485e4b76c59452f785c9066a607d7c45f6 |
Hashes for rustfst_python-0.11.6-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | deca16cbc9f031241a2f7dafd405a47a5c0c408d24d05b20ae53d02f8f232b46 |
|
MD5 | 0a4a7fa1ee251361f8b527e53c354b6d |
|
BLAKE2b-256 | 6ee5cdd24bc2bce8d76f677185126049c7a33df33914c3d9a8c14e7c35646ebb |
Hashes for rustfst_python-0.11.6-cp37-cp37m-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | db69bd198ce47725db7149b6bc84c0ed10ecfb54b5af6a2873aff6b61b26d83e |
|
MD5 | ebe3a504c50fc91bc1ae6071878714fc |
|
BLAKE2b-256 | 5bb22cf9741a249abb8479e59db1295510cac60796f162f9ca40d020b3e093b8 |
Hashes for rustfst_python-0.11.6-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 171ea148481a96a6749e5039298a47f559ea95a1d9dae9b8349ebee186df399a |
|
MD5 | e0c3bbdd8639ad7f5228368531755583 |
|
BLAKE2b-256 | 7ba35527296fb973ec75ece6bf8d084e14d5b3e248621133a9cc907524c986ad |