Module rustfst::algorithms
source · Expand description
Provides algorithms that are generic to all Fst.
Modules
Module providing the necessary functions to implement a new Delayed Fst.
Module providing different structures implementing the
Queue trait.Module providing functions to randomly generate paths through an Fst. A static and a delayed version are available.
Module providing functions to remove epsilon transitions from an Fst. A static and a delayed version are available.
Functions to compare / sort the Trs of an FST.
Function objects to restrict which trs are traversed in an FST.
Module that provides structures implementing the
TrMapper trait.Module providing structures implementing the
WeightConverter trait.Structs
Struct used to map final weights when performing a transition mapping.
It will always be of the form
(EPS_LABEL, EPS_LABEL, final_weight)
where final_weight is the final_weight of the current state.Configuration to control the behaviour of the pushing algorithm.
Enums
Determines how final weights are mapped.
Different types of labels projection in a FST.
Defines the different types of Queues usable.
Different types of reweighting.
Traits
Unified interface to use different implementation of Queues.
The TrMapper interfaces defines how trs and final weights are mapped.
This is useful for implementing operations that do not change the number of
trs.
The WeightConverter interfaces defines how a weight should be turned into another one.
Useful for changing the semiring of an FST.
Functions
In place minimization for weighted final state acceptor.
If
allow_acyclic_minimization is true and the input is acyclic, then a specific
minimization is applied.Add, if needed, a super final state to the given FST. The super final state
is returned if it is possible.
This operation computes the shortest distance from each state to every other states.
The shortest distance from
p to q is the ⊕-sum of the weights
of all the paths between p and q.This operation trims an Fst, removing states and trs that are not on successful paths.
Generic method to convert an Fst into any other types implementing the MutableFst trait.
Generic method to convert an Fst into any other types implementing the MutableFst trait.
This operation inverts the transduction corresponding to an FST
by exchanging the FST’s input and output labels.
This operation determines if two transducers with a certain required determinism
have the same states, irrespective of numbering, and the same transitions with
the same labels and weights, irrespective of ordering.
This operation determines if two transducers with a certain required determinism
have the same states, irrespective of numbering, and the same transitions with
the same labels and weights, irrespective of ordering.
In place minimization of deterministic weighted automata and transducers,
and also non-deterministic ones if they use an idempotent semiring.
For transducers, the algorithm produces a compact factorization of the minimal transducer.
In place minimization of deterministic weighted automata and transducers,
and also non-deterministic ones if they use an idempotent semiring.
For transducers, the algorithm produces a compact factorization of the minimal transducer.
This operation projects an FST onto its domain or range by either copying
each transition input label to its output label or vice versa.
Pushes the weights in FST in the direction defined by TYPE. If
pushing towards the initial state, the sum of the weight of the
outgoing transitions and final weight at a non-initial state is
equal to One() in the resulting machine. If pushing towards the
final state, the same property holds on the reverse machine.
Pushes the weights and/or labels of the input FST into the output
mutable FST by pushing weights and/or labels towards the initial state or final states.
Replaces input and/or output labels using pairs of labels.
Reverses an FST. The reversed result is written to an output mutable FST.
If A transduces string x to y with weight a, then the reverse of A
transduces the reverse of x to the reverse of y with weight a.Reverse().
Reweights an FST according to a vector of potentials in a given direction.
The weight must be left distributive when reweighting towards the initial
state and right distributive when reweighting towards the final states.
Removes final states that have epsilon-only input trs.
This operation computes the shortest distance from the initial state to every state.
The shortest distance from
p to q is the ⊕-sum of the weights
of all the paths between p and q.Creates an FST containing the n-shortest paths in the input FST. The n-shortest paths are the
n-lowest weight paths w.r.t. the natural semiring order.
Sorts the input states of an FST. order[i] gives the the state ID after
sorting that corresponds to the state ID i before sorting; it must
therefore be a permutation of the input FST’s states ID sequence.
This operation topologically sorts its input. When sorted, all transitions are from
lower to higher state IDs.
Maps every transition in the FST using an
TrMapper object.Sorts trs leaving each state of the FST using a compare function
Plus-Sum weights of trs leaving the same state, going to the same state
and with the same input and output labels.
Keep a single instance of trs leaving the same state, going to the same state and
with the same input labels, output labels and weight.
Convert an FST in a given Semiring to another Semiring using a WeightConverter
to specify how the conversion should be performed.