Module rustfst::algorithms

Provides algorithms that are generic for all wFST.

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.

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.

determinize

invert

This operation inverts the transduction corresponding to an FST by exchanging the FST’s input and output labels.

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.

project_input

This operation projects an FST onto its domain or range by copying each arc’s input label to its output label.

project_output

This operation projects an FST onto its domain or range by copying each arc’s output label to its input label.

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.

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.

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.

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.