Module rustfst::algorithms

Provides algorithms that are generic to all Fst.

Modules

• closure
  Functions to compute Kleene closure (star or plus) of an FST.
• compose
  Functions to compose FSTs.
• concat
  Functions to concatenate FSTs.
• determinize
  Functions to determinize FSTs.
• encode
  Functions to encode FSTs as FSAs and vice versa.
• factor_weight
  Functions to factor various weight types.
• lazy
  Module providing the necessary functions to implement a new Delayed Fst.
• queues
  Module providing different structures implementing the Queue trait.
• randgen
  Functions to randomly generate paths through an Fst. A static and a delayed version are available.
• replace
  Functions for lazy replacing transitions in an FST.
• rm_epsilon
  Functions to remove epsilon transitions from an Fst. A static and a delayed version are available.
• 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
  Functions to compute the union of FSTs.
• weight_converters
  Module providing 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
  Configuration for isomorphic comparison.
• MinimizeConfig
  Configuration for minimization.
• PushConfig
  Configuration for push_with_config.
• PushType
  Configuration to control the behaviour of the pushing algorithm.
• PushWeightsConfig
  Configuration for push_weights_with_config.
• ShortestDistanceConfig
  Configuration for shortest distance computation
• ShortestPathConfig
  Configuration for N-shortest path computation

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
  Compute 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
  Return an acyclic FST where each SCC in the input FST has been condensed to a single state with transitions between SCCs retained and within SCCs dropped.
• connect
  Trim 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
  Invert the transduction corresponding to an FST by exchanging the FST’s input and output labels.
• isomorphic
  Determine 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
  Determine, with configurable comparison delta, 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
  General optimization (determinization and minimization) of a WFST
• 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 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.
• push_weights
  Push the weights in an FST.
• push_weights_with_config
  Push the weights in an FST, optionally removing the total weight.
• push_with_config
  Push 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
  Replace input and/or output labels using pairs of labels.
• reverse
  Reverse an FST.
• reweight
  Reweight an FST according to a vector of potentials in a given direction.
• rm_final_epsilon
  Removes final states that have epsilon-only input trs.
• shortest_distance
  Compute 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_distance_with_config
  Compute the shortest distance from the initial state to every state, with configurable delta for comparison.
• shortest_path
  Create an FST containing the single shortest path in the input FST. The shortest path is the lowest weight paths w.r.t. the natural semiring order.
• shortest_path_with_config
  Create 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
  Sort the input states of an FST.
• top_sort
  Topologically sort an FST. 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.