OpenGrm SFst Library: Stochastic Finite-State Transducer Library
SFst is a library for normalizing, sampling, combining, and approximating
stochastic (or
probabilistic) finite-state transducers. These are weighted finite-state transducers, represented in
OpenFst library format, that have the following two properties:
- normalized: the weights of the paths into the future from each state sum to Weight::One()1
- canonical topology:
- the states are sorted by input label
- there may be failure transitions (see phi-labeled transitions) but
- there is at most one such transition per state
- there are no failure-transition (and/or epsilon-transition) cycles
- no assumption is made of general determinism or what transitions must be present on failure (unlike in a canonical n-gram model).
For example, an n-gram model produced by the
OpenGrm NGram Library is a stochastic FST
2 but many other topologies are possible.
1Computation is done internally assuming the weights are negative log probabilities using
Log64Weight. Conversion from the input weight type is done using a
WeightConvert
functor, pre-defined for common weight types like
TropicalWeight
and
LogWeight
.
2Provided the
phi_label
is specified to match the backoff label, typically 0, of the n-gram model.