Operation 
Usage 
Description 
Complexity 
Condition 
Condition(fst, phi_label, delta) 
modifies input moving towards a globally normalizable FST, controlled by delta >= 0 
Time, Space: O(V + E) 
Approx 
Approx(ifst, &ofst, phi_label, delta) 
approximates a normalized stochastic FST wrt a provided backoff model 
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 above holds for a weighted FST 
Time, Space: O(V + E) 
IsNormalized 
IsNormalized(fst, phi_label, delta) 
checks the above two properties 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 outgoing arc weights up to a statespecific 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 ngram 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 * maxphiorder) 

sfsttrim phi_label=$l in.fst out.fst 

