Crate sicada 

A weighted finite-state transducer library, file-compatible with OpenFst.

An FST is a graph whose arcs carry an input label, an output label and a weight, so it holds a relation between strings together with a cost for each pairing. Composing two of them applies one after the other, and searching one answers what the cheapest pairing is. Speech recognition, morphology and text normalisation are the usual reasons to want that.

use sicada::prelude::*;

let mut fst = StdVectorFst::new();
let start = fst.add_state();
let middle = fst.add_state();
let end = fst.add_state();
fst.set_start(start);
fst.set_final(end, TropicalWeight::one());

// Two ways from the start to the end, one cheaper than the other.
fst.add_arc(start, StdArc::new(1, 1, TropicalWeight(0.5), middle));
fst.add_arc(middle, StdArc::new(2, 2, TropicalWeight(0.5), end));
fst.add_arc(start, StdArc::new(1, 1, TropicalWeight(3.0), end));

let mut best = StdVectorFst::new();
shortest_path(&fst, &mut best, &ShortestPathOptions::default())?;
assert_eq!(best.num_states(), 3);

How it is put together

Everything is generic over an Arc, which fixes the weight and the integer types the labels and state ids use, rather than over the weight alone. StdArc is the usual one: tropical weights with 32-bit labels.

• fst holds the trait hierarchy. Fst is what an algorithm reads, ExpandedFst adds a state count in constant time, and MutableFst adds building.
• fsts holds the implementations: VectorFst to build one, ConstFst to map a file, CompactFst to hold one compressed, and ExpanderFst to produce states as they are asked for.
• weight is the semiring trait and weights the semirings themselves, from the tropical and log weights up to the product, string, lexicographic and expectation ones.
• algorithms holds the operations, each stating in its bounds which semiring properties it needs.
• properties carries the bitmask OpenFst files record, and on top of it Verified, which checks a property once and then holds it in the type.
• prelude is all of the above that a caller normally names, in one use.

Reading and writing OpenFst’s files

The binary format is upstream’s, so an FST written by OpenFst can be read here and one written here can be read there. read and write on each FST type take the byte stream; AnyFst reads one whose type is only known from its header.

Re-exports

pub use properties::Acceptor;

pub use properties::Acyclic;

pub use properties::DetEpsFreeAcceptor;

pub use properties::StringFst;

pub use properties::UnweightedDetEpsFreeAcceptor;

pub use properties::Verified;

pub use properties::VerifyExt;

pub use fsts::*;

pub use weights::*;

Modules

add_on

Attaching an arbitrary serializable object to an FST.

algorithms

arc

arc_filter

cache

A cache for FSTs whose states are computed on demand.

data_structures

Container types the FST algorithms are built on.

error

expander_cache

Caches for FSTs that are produced a state at a time.

fst

The FST interface, and the options and shared header handling around it.

fst_header

The header every FST file begins with.

fst_type

Strongly-typed names for the FST, arc and weight types a file header carries.

fsts

macros

matcher

memory

Allocation helpers.

prelude

Everything a user of the library normally wants, in one use.

properties

queue

Disciplines for choosing which state to visit next.

string

Compiling a string into a linear FST, and reading one back out.

symbol_table

symbol_table_ops

Operations over symbol tables.

utils

weight

weights

Macros

fst_linear

Creates a linear FST from a string or a list of labels.

Type Aliases

AtomicRc