Module 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.