[−][src]Module rustfst::algorithms

Provides algorithms that are generic to all wFST.

Modules

arc_compares	Functions to compare / sort the Arcs of an FST.
arc_filters	Function objects to restrict which arcs are traversed in an FST.
arc_mappers	Module that provide structures implementing the `ArcMapper` trait.
queues
weight_converters	Module that provide structures implementing the `WeightConverter` trait.

Structs

FinalArc	Struct used to map final weights when performing an arc 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.
PushType

Enums

DeterminizeType	Determinization type.
MapFinalAction	Determines how final weights are mapped.
ProjectType	Different types of labels projection in a FST.
QueueType
ReweightType	Different types of reweighting.

Traits

ArcMapper	The ArcMapper interfaces defines how arcs and final weights are mapped. This is useful for implementing operations that do not change the number of arcs.
Queue
WeightConverter	The WeightConverter interfaces defines how a weight should be turned into another one. Useful for changing the semiring of an FST.

Functions

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`.
arc_map	Maps every arc in the FST using an `ArcMapper` object.
arc_sort	Sorts arcs leaving each state of the FST using a compare function
arc_sum	Plus-Sum weights of arcs leaving the same state, going to the same state and with the same input and output labels.
arc_unique
closure_plus	This operation computes the concatenative closure. If A transduces string `x` to `y` with weight `a`, then the closure transduces `x` to `y` with weight `a`, `xx` to `yy` with weight `a ⊗ a`, `xxx` to `yyy` with weight `a ⊗ a ⊗ a`, etc.
closure_star	This operation computes the concatenative closure. If A transduces string `x` to `y` with weight `a`, then the closure transduces `x` to `y` with weight `a`, `xx` to `yy` with weight `a ⊗ a`, `xxx` to `yyy` with weight `a ⊗ a ⊗ a`, etc. The empty string is transduced to itself with weight `1` as well.
compose	This operation computes the composition of two transducers. If `A` transduces string `x` to `y` with weight `a` and `B` transduces `y` to `z` with weight `b`, then their composition transduces string `x` to `z` with weight `a ⊗ b`.
concat	Performs the concatenation of two wFSTs. If `A` transduces string `x` to `y` with weight `a` and `B` transduces string `w` to `v` with weight `b`, then their concatenation transduces string `xw` to `yv` with weight `a ⊗ b`.
connect	This operation trims an FST, removing states and arcs that are not on successful paths.
decode	The `decode` operation takes as input an encoded FST and the corresponding `EncodeTable` object and reverts the encoding.
determinize	This operations creates an equivalent FST that has the property that no state has two transitions with the same input label. For this algorithm, epsilon transitions are treated as regular symbols.
determinize_with_distance
encode	The `encode` operation allows the representation of a weighted transducer as a weighted automaton, an unweighted transducer or an unweighted automaton by considering the pair (input label, output), the pair (input label, weight) or the triple (input label, output label, weight) as a single label depending on the value of the encode flags: `encode_labels` and `encode_weights`.
fst_convert
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.
minimize
project	This operation projects an FST onto its domain or range by either copying each arc's input label to its output label or vice versa.
push
push_weights	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.
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_epsilon	This operation removes epsilon-transitions (when both the input and output labels are an epsilon) from a transducer. The result will be an equivalent FST that has no such epsilon transitions.
rm_final_epsilon	Removes final states that have epsilon-only input arcs.
shortest_distance	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
single_source_shortest_distance	This operation computes the shortest distance from the state `state_id` to every state. The shortest distance from `p` to `q` is the ⊕-sum of the weights of all the paths between `p` and `q`.
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
union	Performs the union of two wFSTs. If A transduces string `x` to `y` with weight `a` and `B` transduces string `w` to `v` with weight `b`, then their union transduces `x` to `y` with weight `a` and `w` to `v` with weight `b`.
weight_convert	Convert an FST in a given Semiring to another Semiring using a WeightConverter to specify how the conversion should be performed.