Difference: SFstAvailableOperations (1 vs. 5)

Revision 52019-07-19 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="SFstLibrary"

OpenGrm SFst Available Operations

Line: 8 to 8
 
Operation Usage Description Complexity
Approx Approx(ifst, &backoff_fst, phi_label, delta) approximates a normalized stochastic FST wrt a provided backoff-complete 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    
Changed:
<
<
Count    
>
>
Count Count() counts from stochastic FST wrt to a provided backoff-complete FST same as ShortestDistance on the intersection of the input and output FSTs
 
  sfstcount    
Changed:
<
<
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)
>
>
CountNormalize CountNormalize(&fst) normalizes a count FST (e.g. as output by Count()) Time, Space:
  sfstnormalize -method={kl_min,summed} in.fst out.fst    
 
GlobalNormalize GlobalNormalize(&fst, phi_label, delta) globally normalizes, when possible1, 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    
Added:
>
>
Info sfstinfo prints out information about a stochastic FST Time, Space: O(V + E * max-phi-order)
Intersect Intersect() intersects two canonical stochastic FSAs Time2: O(E1V2(max-label-multiplicity2 + max-phi-order2 log(max-out-degree2))
  sfstintersect    
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)
 
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    
Changed:
<
<
Perplexity Perplexity(fst, phi_label, unknown_label, unknown_class_size) computes perplexity for a stochastic FST  
>
>
Perplexity Perplexity(fst, phi_label, unknown_label, unknown_class_size) computes perplexity for a stochastic FST Time, Space:
 
  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    
Added:
>
>
ShortestDistance ShortestDistance() computes the shortest distance in the presence of failure transitions same as ShortestDistance
  sfstshorttestdistance    
Topology Topology() algorithms for constructing specific FST topologies Time, Space: O(V + E)
  sfsttopology    
 
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    
Line: 31 to 41
 
1Possible when the sum of weight of all successful paths from the initial state is finite (and the input is trim).
Changed:
<
<
Michael Riley - 2018-07-16
>
>
2Assumes 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.

Revision 42019-07-18 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="SFstLibrary"

OpenGrm SFst Available Operations

Changed:
<
<
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 following operations are provided for SFSTs. Care must be taken that the input FSTs meet the specified requirements (e.g. canonical, backoff-complete 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).
Deleted:
<
<
 
Operation Usage Description Complexity
Changed:
<
<
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
>
>
Approx Approx(ifst, &backoff_fst, phi_label, delta) approximates a normalized stochastic FST wrt a provided backoff-complete 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    
Added:
>
>
Count    
  sfstcount    
 
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 possible1, a canonical weighted FST preserving total path weights (up to a global constant) same as ShortestDistance

Revision 32018-07-17 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="SFstLibrary"

OpenGrm SFst Available Operations

Changed:
<
<
The following operations are provided for SFSTs:
>
>
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
Changed:
<
<
Approx Approx(ifst, &ofst, phi_label, delta) approximates a normalized stochastic FST wrt a provided backoff model topology same as ShortestDistance on the intersection of the input and output FSTs
>
>
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)

Revision 22018-07-17 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="SFstLibrary"
Changed:
<
<

Available Operations

>
>

OpenGrm SFst Available Operations

  The following operations are provided for SFSTs:

Operation Usage Description Complexity
Changed:
<
<
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
>
>
Approx Approx(ifst, &ofst, phi_label, delta) approximates a normalized stochastic FST wrt a provided backoff model topology same as ShortestDistance on the intersection of the input and output FSTs
 
  sfstapprox[--phi_label=$l][--delta=$d] in.fst backoff.fst out.fst    
Changed:
<
<
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)
>
>
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 possible1, 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)
Line: 22 to 21
 
  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    
Changed:
<
<
Trim Trim(&fst, phi_label) Removes useless states and transitions in stochastic automata (irrespective of weights) Time, Space: O(V + E * max-phi-order)
>
>
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    
Deleted:
<
<
1Possible when the sum of weight of all successful paths from the initial state is finite (and the input is trim).

-- Michael Riley - 2018-07-16

 
Changed:
<
<

Comments

>
>

1Possible when the sum of weight of all successful paths from the initial state is finite (and the input is trim).
 
Changed:
<
<
<--/commentPlugin-->
>
>
Michael Riley - 2018-07-16

Revision 12018-07-16 - MichaelRiley

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="SFstLibrary"

Available Operations

The following operations are provided for SFSTs:

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 possible1, 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    

1Possible when the sum of weight of all successful paths from the initial state is finite (and the input is trim).

-- Michael Riley - 2018-07-16

Comments

<--/commentPlugin-->
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback