The following operations are provided for SFSTs. Care must be taken that the input FSTs meet the specified requirements (e.g. canonical, backoff or 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 |
---|---|---|---|

Approx | Approx(ifst, &backoff_fst, phi_label, delta) | approximates a normalized stochastic FST wrt a provided backoff FST | same as ShortestDistance on the intersection of the input and output FSTs |

sfstapprox[--phi_label=$l][--delta=$d] in.fst backoff.fst out.fst | |||

IsCanonical | IsCanonical(fst, phi_label) | checks the second property here holds for a weighted FST | Time, Space: O(V + E) |

IsNormalized | IsNormalized(fst, phi_label, delta) | checks the two properties here hold for a weighted FST | Time, Space: O(V + E) |

GlobalNormalize | GlobalNormalize(&fst, phi_label, delta) | globally normalizes, when possible^{1}, a canonical weighted FST preserving total path weights (up to a global constant) |
same as ShortestDistance |

sfstnormalize [--method=global] [--phi_label=$l][--delta=$d] in.fst out.fst | |||

LocalNormalize | 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 | |||

NGramApprox | NGramApprox(ifst, &ofst, order, phi_label, delta) | approximates a normalized stochastic FST as an n-gram model (having `phi_labels` in OpenGrm NGram format) |
same as ShortestDistance on the intersection of the input and output FSTs |

sfstngramapprox [--order=$o][--phi_label=$l][--delta=$d] in.fst out.fst | |||

Perplexity | Perplexity(fst, phi_label, unknown_label, unknown_class_size) | computes perplexity for a stochastic FST | |

sfstperplexity [--phi_label=$l] [-unknown_label=$u][--unknown_class_size=$s] in.fst test.far | (test sentences are in FST archive format) | ||

PhiNormalize | 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 | |||

RandGen | fst::RandGen(ifst, &ofst, fst::RandGenOptions<SFstArcSelector |
randomly generates paths in a stochastic FST (correctly dealing with failure transitions) | see RandGen |

sfstrandgen [--phi_label=$l] [--max_length=$l] [--npath=$n] [--seed=$s] in.fst out.fst | |||

Trim | 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 |

Topic revision: r3 - 2018-07-17 - MichaelRiley

Copyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback