SFstAvailableOperations < GRM

---+ !OpenGrm !SFst Available Operations

The following operations are provided for SFSTs. Care must be taken that the input FSTs meet the specified requirements (e.g. [[SFstGlossary#Canonical][canonical]],  [[SFstGlossary#Backoff][backoff-complete]] or  [[SFstGlossary#Normalized][normalized]]).
The binary commands typically check their input requirements are satisfied or raise an error but the C++ versions may not check for efficiency (see the source code documentation for specific cases).

| *Operation* | *Usage* | *Description* | *Complexity* |
| <nop>Approx | <nop>Approx(ifst, &backoff_fst, phi_label, delta) | approximates a normalized stochastic FST wrt a provided [[SFstGlossary#BackoffDef][backoff-complete FST]]| same as  [[http://www.openfst.org/twiki/bin/view/FST/ShortestDistanceDoc][ShortestDistance]] on the intersection of the input and output FSTs |
|   | sfstapprox[--phi_label=$l][--delta=$d] in.fst backoff.fst out.fst | |  |
| <nop>Count  | <nop>Count() | counts from stochastic FST wrt to a provided [[SFstGlossary#BackoffDef][backoff-complete FST]] | same as  [[http://www.openfst.org/twiki/bin/view/FST/ShortestDistanceDoc][ShortestDistance]] on the intersection of the input and output FSTs |
| | sfstcount | | |
| <nop>CountNormalize | <nop>CountNormalize(&fst) | normalizes a count FST (e.g. as output by Count()) | Time: O(sE) where s is max iterations per state, Space:  O(V) |
|   | sfstnormalize -method={kl_min,summed} in.fst out.fst | | |
| <nop>GlobalNormalize | <nop>GlobalNormalize(&fst, phi_label, delta) | globally normalizes, when possible<sup>1</sup>, a canonical weighted FST preserving total path weights (up to a global constant) | same as  [[http://www.openfst.org/twiki/bin/view/FST/ShortestDistanceDoc][ShortestDistance]] |
|   | sfstnormalize  [--method=global] [--phi_label=$l][--delta=$d] in.fst out.fst | | |
| <nop>Info  | sfstinfo | prints out information about a stochastic FST | Time, Space: O(V + E * max-phi-order) |
| <nop>Intersect | <nop>Intersect() | intersects two canonical stochastic FSAs | Time<sup>2</sup>: O(E<sub>1</sub>V<sub>2</sub>(max-label-multiplicity<sub>2</sub> + max-phi-order<sub>2</sub> log(max-out-degree<sub>2</sub>)) |
| | sfstintersect | | |
| <nop>IsCanonical | <nop>IsCanonical(fst, phi_label) | checks the second property [[SFstLibrary#SFSTProperties][here]] holds for a weighted FST | Time, Space: _O(V + E)_ |
| <nop>IsNormalized | <nop>IsNormalized(fst, phi_label, delta) | checks the two properties [[SFstLibrary#SFSTProperties][here]] hold for a weighted FST | Time, Space: _O(V + E)_ |
| <nop>LocalNormalize | <nop>LocalNormalize(&fst) | locally normalizes, when possible, a canonical weighted FST preserving each state's out-going arc weights up to a state-specific constant | Time, Space: _O(V + E)_  |
|   | sfstnormalize -method=local in.fst out.fst | | |
| <nop>NGramApprox | <nop>NGramApprox(ifst, &ofst, order, phi_label, delta) | approximates a normalized stochastic FST as an n-gram model  (having =phi_labels= in [[NGramQuickTour#ModelFormat][OpenGrm NGram format]]) | same as  [[http://www.openfst.org/twiki/bin/view/FST/ShortestDistanceDoc][ShortestDistance]] on the intersection of the input and output FSTs |
|   | sfstngramapprox [--order=$o][--phi_label=$l][--delta=$d] in.fst out.fst | | |
| Perplexity | Perplexity(qfst, phi_label, unknown_label) | computes self/cross perplexity for stochastic FSTs | same as  [[http://www.openfst.org/twiki/bin/view/FST/ShortestDistanceDoc][ShortestDistance]] on the intersection of the source and target FSTs  |
| | sfstperplexity [--phi_label=$l] [--unknown_label=$u] q.fst [p.{fst,far}] | (p.far is in [[http://www.openfst.org/twiki/bin/view/FST/FstExtensions#FstArchive][FST archive]] format) | |
| <nop>PhiNormalize | <nop>PhiNormalize(&fst, phi_label) | normalizes, when possible, a canonical weighted FST by only modifying the failure transitions | Time, Space: _O(V + E)_ |
|   | sfstnormalize --method=phi [--phi_label=$l][--delta=$d] in.fst out.fst | | |
| <nop>RandGen| <nop>fst::RandGen(ifst, &ofst, <nop>fst::RandGenOptions<SFstArcSelector<Arc>>(...)) | randomly generates paths in a stochastic FST (correctly dealing with failure transitions)  | see [[http://www.openfst.org/twiki/bin/view/FST/RandGenDoc][RandGen]]  |
|   | sfstrandgen [--phi_label=$l] [--max_length=$l] [--npath=$n] [--seed=$s]  in.fst out.fst | | |
| <nop>ShortestDistance  | <nop>ShortestDistance() | computes the shortest distance in the presence of failure transitions | same as  [[http://www.openfst.org/twiki/bin/view/FST/ShortestDistanceDoc][ShortestDistance]] |
| | sfstshorttestdistance | | |
| <nop>Topology  | <nop>Topology() | algorithms for constructing specific FST topologies | Time, Space: _O(V + E)_ |
| | sfsttopology | | |
| <nop>Trim | <nop>Trim(&fst, phi_label) | removes useless states and transitions in stochastic automata (irrespective of weights) | Time, Space: _O(V + E * max-phi-order)_ |
|   | sfsttrim -phi_label=$l in.fst out.fst | | |



---
<sup>1</sup>Possible when the sum of weight of all successful paths from the initial state is finite (and the input is [[http://www.openfst.org/twiki/bin/view/FST/FstGlossary#Trim][trim]]).

<sup>2</sup>Assumes for each state (s1, s2) in the output, the out-degree of state s1 in FST1 is less than state s2 in FST2; otherwise the term for that state's contribution swaps s1 and s2.
This topic: GRM > WebHome > SFstLibrary > SFstAvailableOperations
Topic revision: r7 - 2020-07-06 - MichaelRiley