Module rustfst::algorithms

Provides algorithms that are generic to all wFST.

Modules

closure
compose
concat
determinize
encode
factor_weight
lazy
queues	Module that provides different structures implementing the Queue trait.
replace
rm_epsilon
tr_compares	Functions to compare / sort the Trs of an FST.
tr_filters	Function objects to restrict which trs are traversed in an FST.
tr_mappers	Module that provides structures implementing the TrMapper trait.
union
weight_converters	Module that provides structures implementing the WeightConverter trait.

Structs

FinalTr	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.
IsomorphicConfig
MinimizeConfig
PushConfig
PushType	Configuration to control the behaviour of the pushing algorithm.
PushWeightsConfig
ShortestDistanceConfig
ShortestPathConfig

Enums

MapFinalAction	Determines how final weights are mapped.
ProjectType	Different types of labels projection in a FST.
QueueType	Defines the different types of Queues usable.
ReweightType	Different types of reweighting.

Traits

Queue	Unified interface to use different implementation of Queues.
TrMapper	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.
WeightConverter	The WeightConverter interfaces defines how a weight should be turned into another one. Useful for changing the semiring of an FST.

Functions

acceptor_minimize	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_super_final_state	Add, if needed, a super final state to the given FST. The super final state is returned if it is possible.
all_pairs_shortest_distance	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.
condense
connect	This operation trims an FST, removing states and trs that are not on successful paths.
fst_convert	Generic method to convert an Fst into any other types implementing the MutableFst trait.
fst_convert_from_ref	Generic method to convert an Fst into any other types implementing the MutableFst trait.
invert	This operation inverts the transduction corresponding to an FST by exchanging the FST’s input and output labels.
isomorphic	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.
isomorphic_with_config	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.
minimize	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.
minimize_with_config	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.
optimize
project	This operation projects an FST onto its domain or range by either copying each transition input label to its output label or vice versa.
push
push_weights
push_weights_with_config	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.
push_with_config	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.
relabel_pairs	Replaces input and/or output labels using pairs of labels.
reverse	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().
reweight	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.
rm_final_epsilon	Removes final states that have epsilon-only input trs.
shortest_distance
shortest_distance_with_config	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.
shortest_path
shortest_path_with_config	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.
state_sort	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.
top_sort	This operation topologically sorts its input. When sorted, all transitions are from lower to higher state IDs.
tr_map	Maps every transition in the FST using an TrMapper object.
tr_sort	Sorts trs leaving each state of the FST using a compare function
tr_sum	Plus-Sum weights of trs leaving the same state, going to the same state and with the same input and output labels.
tr_unique	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.
weight_convert	Convert an FST in a given Semiring to another Semiring using a WeightConverter to specify how the conversion should be performed.