Labs 5: WFST operations
This lab introduces several WFST operations. You’ll see how these can be used to implement solutions to the problem of matching phoneme sequences to entries in a lexicon, and also incorporating a grammar. We use the following operations:
Note
Please go to the github repo to view the jupyter notebook file for this lab.
We use the following operations in this lab. See the API reference for complete documentation of all operations.
determinize(ifst, delta=1e-6, det_type="functional", |
|
|
Constructively composes two FSTs. |
shortestpath(ifst, delta=1e-6, nshortest=1, nstate=NO_STATE_ID, |
|
Minimizes the FST. |
|
Converts the FST to an acceptor using input or output labels. |
|
rmepsilon(self, queue_type="auto", connect=True, weight=None, |
|
Sorts arcs leaving each state of the FST. |
Detailed description of operations
The way in which the documentation is auto-generated adds additional information before the function descriptions themselves that we cannot remove – feel free to ignore this!
Python interface to the FST scripting API.
Operations which construct new FSTs are implemented as traditional functions, as are two-argument boolean functions like equal and equivalent. Destructive operations—those that mutate an FST, in place—are instance methods, as is write. Operator overloading is not used. The following example, based on Mohri et al. 2002, shows the construction of an ASR system given a pronunciation lexicon L, grammar G, a transducer from context-dependent phones to context-independent phones C, and an HMM set H:
L = fst.Fst.read(“L.fst”) G = fst.Fst.read(“G.fst”) C = fst.Fst.read(“C.fst”) H = fst.Fst.read(“H.fst”) LG = fst.determinize(fst.compose(L, G)) CLG = fst.determinize(fst.compose(C, LG)) HCLG = fst.determinize(fst.compose(H, CLG)) HCLG.minimize() # NB: works in-place.
Python variables here use snake_case and constants are in all caps, minus the normal k prefix.
- openfst_python.pywrapfst.compose(ifst1, ifst2, compose_filter='auto', connect=True)
Constructively composes two FSTs.
This operation computes the composition of two FSTs. 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 otimes b. The output labels of the first transducer or the input labels of the second transducer must be sorted (or otherwise support appropriate matchers).
- Args:
ifst1: The first input FST. ifst2: The second input FST. compose_filter: A string matching a known composition filter; one of:
“alt_sequence”, “auto”, “match”, “no_match”, “null”, “sequence”, “trivial”.
connect: Should output be trimmed?
- Returns:
An FST.
See also: arcsort.
- openfst_python.pywrapfst.determinize()
- determinize(ifst, delta=1e-6, det_type=”functional”,
nstate=NO_STATE_ID, subsequential_label=0, weight=None, incremental_subsequential_label=False)
Constructively determinizes a weighted FST.
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 (cf. rmepsilon).
- Args:
ifst: The input FST. delta: Comparison/quantization delta. det_type: Type of determinization; one of: “functional” (input transducer is
functional), “nonfunctional” (input transducer is not functional) and disambiguate” (input transducer is not functional but only keep the min of ambiguous outputs).
nstate: State number threshold. subsequential_label: Input label of arc corresponding to residual final
output when producing a subsequential transducer.
- weight: A Weight or weight string indicating the desired weight threshold
below which paths are pruned; if omitted, no paths are pruned.
- increment_subsequential_label: Increment subsequential when creating
several arcs for the residual final output at a given state.
- Returns:
An equivalent deterministic FST.
- Raises:
FstArgError: Unknown determinization type.
See also: disambiguate, rmepsilon.
- openfst_python.pywrapfst.shortestpath()
- shortestpath(ifst, delta=1e-6, nshortest=1, nstate=NO_STATE_ID,
queue_type=”auto”, unique=False, weight=None)
Construct an FST containing the shortest path(s) in the input FST.
This operation produces 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. The single path that can be read from the ith of at most n transitions leaving the initial state of the resulting FST is the ith shortest path. The weights need to be right distributive and have the path property. They also need to be left distributive as well for n-shortest with n > 1 (e.g., TropicalWeight).
- Args:
ifst: The input FST. delta: Comparison/quantization delta. nshortest: The number of paths to return. nstate: State number threshold. queue_type: A string matching a known queue type; one of: “auto”, “fifo”,
“lifo”, “shortest”, “state”, “top”.
- unique: Should the resulting FST only contain distinct paths? (Requires
the input FST to be an acceptor; epsilons are treated as if they are regular symbols.)
- weight: A Weight or weight string indicating the desired weight threshold
below which paths are pruned; if omitted, no paths are pruned.
- Returns:
An FST containing the n-shortest paths.
(No constructor.)
Mutable FST class, wrapping MutableFstClass.
This class extends _Fst by adding mutation operations.
- openfst_python.pywrapfst._MutableFst.arcsort(self, sort_type='ilabel')
Sorts arcs leaving each state of the FST.
This operation destructively sorts arcs leaving each state using either input or output labels.
- Args:
- sort_type: Either “ilabel” (sort arcs according to input labels) or
“olabel” (sort arcs according to output labels).
- Returns:
self.
- Raises:
FstArgError: Unknown sort type.
- openfst_python.pywrapfst._MutableFst.minimize(self, delta=1e-06, allow_nondet=False)
Minimizes the FST.
This operation destructively performs the minimization of deterministic weighted automata and transducers. If the input FST A is an acceptor, this operation produces the minimal acceptor B equivalent to A, i.e. the acceptor with a minimal number of states that is equivalent to A. If the input FST A is a transducer, this operation internally builds an equivalent transducer with a minimal number of states. However, this minimality is obtained by allowing transition having strings of symbols as output labels, this known in the litterature as a real-time transducer. Such transducers are not directly supported by the library. This function will convert such transducer by expanding each string-labeled transition into a sequence of transitions. This will results in the creation of new states, hence losing the minimality property.
- Args:
delta: Comparison/quantization delta. allow_nondet: Attempt minimization of non-deterministic FST?
- Returns:
self.
- openfst_python.pywrapfst._MutableFst.project(self, project_output=False)
Converts the FST to an acceptor using input or output labels.
This operation destructively projects an FST onto its domain or range by either copying each arc’s input label to its output label (the default) or vice versa.
- Args:
project_output: Should the output labels be projected?
- Returns:
self.
See also: decode, encode, relabel_pairs, relabel_symbols.
- openfst_python.pywrapfst._MutableFst.rmepsilon()
- rmepsilon(self, queue_type=”auto”, connect=True, weight=None,
nstate=NO_STATE_ID, delta=1e-6):
Removes epsilon transitions.
This operation destructively removes epsilon transitions, i.e., those where both input and output labels are epsilon) from an FST.
- Args:
- queue_type: A string matching a known queue type; one of: “auto”, “fifo”,
“lifo”, “shortest”, “state”, “top”.
connect: Should output be trimmed? weight: A Weight or weight string indicating the desired weight threshold
below which paths are pruned; if omitted, no paths are pruned.
nstate: State number threshold. delta: Comparison/quantization delta.
- Returns:
self.