Difference: FstQuickTour (1 vs. 112)

Revision 1122018-03-12 - KyleGorman

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 223 to 223
 # of input/output epsilons 0 # of input epsilons 0 # of output epsilons 0
Added:
>
>
input label multiplicity 1 output label multiplicity 1
 # of accessible states 3 # of coaccessible states 3 # of connected states 3
Line: 230 to 232
 # of strongly conn components 3 input matcher y output matcher y
Added:
>
>
input lookahead n output lookahead n
 expanded y mutable y
Added:
>
>
error n
 acceptor y input deterministic y output deterministic y
Line: 247 to 252
 accessible y coaccessible y string n
Added:
>
>
weighted cycles n
 

Revision 1102015-09-10 - KyleGorman

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 30 to 30
 from state 0 to 1 with input label a, output label x, and weight 0.5. This FST transduces, for instance, the string ac to xz with weight 6.5 (the sum of the arc and final weights). Note we have assumed the library default Weight type for this description.
Changed:
<
<
dot -Tpng -Gbgcolor=transparent
>
>
 

Creating FSTs

Revision 1092014-04-23 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 417 to 417
 
  fstencode [--encode_labels] [--encode_weights] in.fst encoder out.fst  
EpsNormalize EpsNormalize(A, &B, type); creates equiv. FST with any input (output) epsilons at path ends
  fstepsnormalize [--eps_norm_output] in.fst out.fst  
Changed:
<
<
Equal Equal(A, B) determines if FSTs A and B have the same states and transitions in the same order
>
>
Equal Equal(A, B) determines if FSTs A and B have the same states and transitions with the same numbering and order
 
  fstequal a.fst b.fst  
Equivalent Equivalent(A, B) determines if acceptors A and B accept the same strings with the same weights
  fstequivalent a.dfa b.dfa  
Line: 427 to 427
 
Invert Invert(&A); inverse binary relation; exchanges input and output labels
  InvertFst<Arc>(A);  
  fstinvert in.fst out.fst  
Changed:
<
<
Isomorphic Isomorphic(A, B) determines if FSTs A and B have the same states and transitions irrespective of order
>
>
Isomorphic Isomorphic(A, B) determines if FSTs A and B have the same states and transitions irrespective of numbering and order
 
  fstisomorphic a.fst b.fst  
Minimize Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
  Minimize(&A, &B); transforms to equiv. deterministic FST with fewest states and arcs

Revision 1082014-04-22 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 410 to 410
 
Difference Difference(A, B, &C); contains strings in A but not B; B unweighted
  DifferenceFst<Arc>(A, B);  
  fstdifference a.fsa b.dfa out.fsa  
Added:
>
>
Disambiguate Disambiguate(A, &B); creates equiv. FST with no two successful paths with the same input labels
  fstdisambiguate in.fst out.fst  
 
Encode Encode(&A, encoder); combines input labels with output labels and/or weights into new input labels
  EncodeFst(A, encoder);  
  fstencode [--encode_labels] [--encode_weights] in.fst encoder out.fst  
EpsNormalize EpsNormalize(A, &B, type); creates equiv. FST with any input (output) epsilons at path ends
  fstepsnormalize [--eps_norm_output] in.fst out.fst  
Added:
>
>
Equal Equal(A, B) determines if FSTs A and B have the same states and transitions in the same order
  fstequal a.fst b.fst  
 
Equivalent Equivalent(A, B) determines if acceptors A and B accept the same strings with the same weights
  fstequivalent a.dfa b.dfa  
Intersect Intersect(A, B, &C); contains strings both in A and B
Line: 423 to 427
 
Invert Invert(&A); inverse binary relation; exchanges input and output labels
  InvertFst<Arc>(A);  
  fstinvert in.fst out.fst  
Added:
>
>
Isomorphic Isomorphic(A, B) determines if FSTs A and B have the same states and transitions irrespective of order
  fstisomorphic a.fst b.fst  
 
Minimize Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
  Minimize(&A, &B); transforms to equiv. deterministic FST with fewest states and arcs
  fstminimize in.fst out1.fst [out2.fst]  

Revision 1072013-05-09 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 129 to 129
  numericfst.jpg
Changed:
<
<
Once a binary FST is created, it can be used with the other shell-level programs. It can be loaded inside C++ with:
>
>
Once a binary FST is created, it can be used with the other shell-level programs (on the same machine architecture). It can be loaded inside C++ with:
 
StdFst *fst = StdFst::Read("binary.fst");

Revision 1062012-05-13 - MichaelRiley

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

OpenFst Quick Tour

Below is a brief tutorial on the OpenFst library. After reading this, you may wish to browse

Changed:
<
<
the Advanced Usage topic for greater detail and read the library Conventions topic to ensure correct usage.
>
>
the Advanced Usage topic for greater detail, read the library Conventions topic to ensure correct usage and read the Efficiency topic for to ensure efficient usage.
 

Finding and Using the Library

Revision 1052012-02-03 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 458 to 458
 
  StateMap(A, &B, mapper);  
  StateMapFst<InArc, OutArc, StateMapper>(A, mapper);  
  fstmap [--map=$type] in.fst out.fst  
Changed:
<
<
Synchronize SynchronizeFst<Arc>(A); synchronizes an FST
>
>
Synchronize Synchronize(A, &B); synchronizes an FST
  SynchronizeFst<Arc>(A);  
 
  fstsynchronize in.fst out.fst  
TopSort TopSort(&A); sorts an acyclic FST so that all transitions are from lower to higher state IDs
  fsttopsort in.fst out.fst  

Revision 1042011-12-05 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 381 to 381
 Click on operation name for additional information.

Operation Usage Description
Added:
>
>
ArcMap ArcMap(&A, mapper); transforms arcs in an FST
  ArcMap(A, &B, mapper);  
  ArcMapFst<InArc, OutArc, ArcMapper>(A, mapper);  
  fstmap [--delta=$d] [--map=$type] [--weight=$w] in.fst out.fst  
 
ArcSort ArcSort(&A, compare); sorts arcs using compare function object
  ArcSortFst<Arc, Compare>(A, compare);  
  fstarcsort [--sort_type=$type] in.fst out.fst  
Line: 418 to 422
 
Invert Invert(&A); inverse binary relation; exchanges input and output labels
  InvertFst<Arc>(A);  
  fstinvert in.fst out.fst  
Deleted:
<
<
Map Map(&A, mapper); transforms arcs in an FST
  Map(A, &B, mapper);  
  MapFst<InArc, OutArc, Mapper>(A, mapper);  
  fstmap [--delta=$d] [--map=$type] [--weight=$w] in.fst out.fst  
 
Minimize Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
  Minimize(&A, &B); transforms to equiv. deterministic FST with fewest states and arcs
  fstminimize in.fst out1.fst [out2.fst]  
Line: 454 to 454
 
  fstshortestdistance [--reverse] in.fst [distance.txt]  
ShortestPath ShortestPath(A, &B, nshortest=1); N-best paths
  fstshortestpath [--nshortest=$n] in.fst out.fst  
Added:
>
>
StateMap StateMap(&A, mapper); transforms states in an FST
  StateMap(A, &B, mapper);  
  StateMapFst<InArc, OutArc, StateMapper>(A, mapper);  
  fstmap [--map=$type] in.fst out.fst  
 
Synchronize SynchronizeFst<Arc>(A); synchronizes an FST
  fstsynchronize in.fst out.fst  
TopSort TopSort(&A); sorts an acyclic FST so that all transitions are from lower to higher state IDs

Revision 1032011-04-13 - AntoineAmarilli

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 357 to 357
 }
Added:
>
>

FST Application from the Shell

# The FSTs must be sorted along the dimensions they will be joined.
# In fact, only one needs to be so sorted.
# This could have instead been done for "model.fst" when it was created. 
$ fstarcsort --sort_type=olabel input.fst input_sorted.fst
$ fstarcsort --sort_type=ilabel model.fst model_sorted.fst

# Creates the composed FST. 
$ fstcompose input_sorted.fst model_sorted.fst comp.fst

# Just keeps the output label 
$ fstproject --project_output comp.fst result.fst

# Do it all in a single command line. 
$ fstarcsort --sort_type=ilabel model.fst | fstcompose input.fst - | fstproject --project_output result.fst
 

Available FST Operations

Revision 1022011-04-13 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 330 to 330
 
#include <fst/fstlib.h>

Changed:
<
<
int main(void) { using namespace fst;
>
>
namespace fst {
  // Reads in an input FST. StdVectorFst *input = StdVectorFst::Read("input.fst");

// Reads in the transduction model. StdVectorFst *model = StdVectorFst::Read("model.fst");

Deleted:
<
<
if (input || model) return 1;
  // The FSTs must be sorted along the dimensions they will be joined. // In fact, only one needs to be so sorted. // This could have instead been done for "model.fst" when it was created.
Line: 359 to 354
  // Writes the result FST to a file. result.Write("result.fst");
Deleted:
<
<
return 0;
 }

Revision 1012011-04-06 - AntoineAmarilli

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 328 to 328
 

FST Application from C++

Changed:
<
<
// Reads in an input FST. 
StdFst *input = StdFst::Read("input.fst");

// Reads in the transduction model. 
StdFst *model = StdFst::Read("model.fst");

// The FSTs must be sorted along the dimensions they will be joined.
// In fact, only one needs to be so sorted.
// This could have instead been done for "model.fst" when it was created. 

>
>
#include <fst/fstlib.h>

int main(void)
{
  using namespace fst;

  // Reads in an input FST. 
  StdVectorFst *input = StdVectorFst::Read("input.fst");

  // Reads in the transduction model. 
  StdVectorFst *model = StdVectorFst::Read("model.fst");

  if (!input || !model) return 1;

  // The FSTs must be sorted along the dimensions they will be joined.
  // In fact, only one needs to be so sorted.
  // This could have instead been done for "model.fst" when it was created. 

 ArcSort(input, StdOLabelCompare()); ArcSort(model, StdILabelCompare());
Changed:
<
<
// Container for composition result.
>
>
// Container for composition result.
 StdVectorFst result;
Changed:
<
<
// Create the composed FST.
>
>
// Creates the composed FST.
 Compose(*input, *model, &result);
Changed:
<
<
// Just keeps the output labels.
>
>
// Just keeps the output labels.
 Project(&result, PROJECT_OUTPUT);
Deleted:
<
<
 
Changed:
<
<

FST Application from the Shell

>
>
// Writes the result FST to a file. result.Write("result.fst");
 
Changed:
<
<
# The FSTs must be sorted along the dimensions they will be joined.
# In fact, only one needs to be so sorted.
# This could have instead been done for "model.fst" when it was created. 
$ fstarcsort --sort_type=olabel input.fst input_sorted.fst
$ fstarcsort --sort_type=ilabel model.fst model_sorted.fst

# Creates the composed FST. 
$ fstcompose input_sorted.fst model_sorted.fst comp.fst

# Just keeps the output label 
$ fstproject --project_output comp.fst result.fst

# Do it all in a single command line. 
$ fstarcsort --sort_type=ilabel model.fst | fstcompose input.fst - | fstproject --project_output result.fst

>
>
return 0; }
 

Revision 1002011-02-01 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 162 to 162
 
typedef StdArc::StateId StateId;


Changed:
<
<
# Gets the initial state; if == kNoState => empty FST.
>
>
# Gets the initial state; if == kNoState => empty FST.
 StateId initial_state = fst.Start();
Changed:
<
<
# Get state i's final weight; if == Weight::Zero() => non-final.
>
>
# Get state i's final weight; if == Weight::Zero() => non-final.
 Weight weight = fst.Final(i);
# Iterates over the FSTs states. 

Changed:
<
<
for (StateIterator siter(fst); siter.Done(); siter.Next())
>
>
for (StateIterator<StdFst> siter(fst); siter.Done(); siter.Next())
  StateId state_id = siter.Value();
# Iterates over state i's arcs. 

Changed:
<
<
for (ArcIterator aiter(fst, i); aiter.Done(); aiter.Next())
>
>
for (ArcIterator<StdFst> aiter(fst, i); aiter.Done(); aiter.Next())
  const StdArc &arc = aiter.Value();
# Iterates over state i's arcs that have input label l (FST must support this -
# in the simplest cases,  true when the input labels are sorted). 

Changed:
<
<
Matcher matcher(fst, MATCH_INPUT);
>
>
Matcher<StdFst> matcher(fst, MATCH_INPUT);
 matcher.SetState(i); if (matcher.Find(l)) for (; matcher.Done(); matcher.Next())
Line: 208 to 208
 
# Draw FST using symbol table files and Graphviz dot: 
$ fstdraw --isymbols=isyms.txt --osymbols=osyms.txt binary.fst binary.dot

Changed:
<
<
$ dot -Tps binary.dot >binary.ps
>
>
$ dot -Tps binary.dot >binary.ps
 

Summary information about an FST can be obtained with:

Revision 992010-12-08 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 36 to 36
 FSTs can be created with constructors and mutators from C++ or from text files at the shell-level. We will show how to create the above example FST both ways.
Added:
>
>
 

Creating FSTs Using Constructors and Mutators From C++

The following code will create our example FST within C++:

Line: 67 to 68
 fst.Write("binary.fst");
Added:
>
>
 

Creating FSTs Using Text Files from the Shell

FSTs can be specified using a text file in the

Revision 982010-08-28 - MichaelRiley

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

OpenFst Quick Tour

Below is a brief tutorial on the OpenFst library. After reading this, you may wish to browse

Changed:
<
<
the Advanced Usage topic for greater detail and read the library Conventions topic to ensure its correct use.
>
>
the Advanced Usage topic for greater detail and read the library Conventions topic to ensure correct usage.
 

Finding and Using the Library

Revision 962010-08-17 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 29 to 29
 from state 0 to 1 with input label a, output label x, and weight 0.5. This FST transduces, for instance, the string ac to xz with weight 6.5 (the sum of the arc and final weights). Note we have assumed the library default Weight type for this description.
Changed:
<
<
>
>
dot -Tpng -Gbgcolor=transparent
 

Creating FSTs

Line: 401 to 401
 
  fstencode [--encode_labels] [--encode_weights] in.fst encoder out.fst  
EpsNormalize EpsNormalize(A, &B, type); creates equiv. FST with any input (output) epsilons at path ends
  fstepsnormalize [--eps_norm_output] in.fst out.fst  
Changed:
<
<
EquivalentWork in progress, under construction Equivalent(A, B) determines if acceptors A and B accept the same strings with the same weights
>
>
Equivalent Equivalent(A, B) determines if acceptors A and B accept the same strings with the same weights
 
  fstequivalent a.dfa b.dfa  
Intersect Intersect(A, B, &C); contains strings both in A and B
IntersectFst<Arc>(A, B);  

Revision 952010-08-17 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 413 to 413
 
  Map(A, &B, mapper);  
  MapFst<InArc, OutArc, Mapper>(A, mapper);  
  fstmap [--delta=$d] [--map=$type] [--weight=$w] in.fst out.fst  
Changed:
<
<
MinimizeWork in progress, under construction Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
>
>
Minimize Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
 
  Minimize(&A, &B); transforms to equiv. deterministic FST with fewest states and arcs
  fstminimize in.fst out1.fst [out2.fst]  
Project Project(&A, type); creates acceptor of just the input or output strings

Revision 942010-08-10 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 492 to 492
  (See here for how to your define your own FST arcs and weights if desired.)
Deleted:
<
<
-- MichaelRiley - 23 Feb 2009
 
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462223" name="numericfst.jpg" path="numericfst.jpg" size="4881" user="Main.CyrilAllauzen" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462223" name="symbolicfst.jpg" path="symbolicfst.jpg" size="4768" user="Main.CyrilAllauzen" version="1"

Revision 922010-08-04 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 274 to 274
 
  • ConstFst<Arc>: a general-purpose expanded, immutable FST
  • ComposeFst<Arc>: an unexpanded, delayed composition of two FSTs
Changed:
<
<
(See here for how to define your own FST classes if desired.)
>
>
(See here for additional non-abstract FST class templates. See here for how to define your own FST classes if desired.)
  These classes are templated on the arc to allow customization. The class StdFst is a typedef for Fst<StdArc>. Similar typedefs exist for all the above templates.

Revision 912010-08-03 - JacobRatkiewicz

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 259 to 259
  The FST operations can be invoked either at the C++ level or from shell-level commands.
Added:
>
>
 

Calling FST Operations from C++

To invoke FST operations from C++, the FST class hierarchy must first be introduced:

Line: 321 to 322
 One of the most useful finite-state operations is composition, which produces the relational composition of two transductions. It can be used, for example, to apply a transduction to some input:
Added:
>
>
 

FST Application from C++

// Reads in an input FST. 

Revision 892010-05-07 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 82 to 82
 # final state format: state [weight] # lines may occur in any order except initial state must be first line # unspecified weights default to 0.0 (for the library-default Weight type)
Changed:
<
<
cat >text.fst <<EOF
>
>
$ cat >text.fst <<EOF
 0 1 a x .5 0 1 b y 1.5 1 2 c z 2.5

Revision 882009-03-30 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 382 to 382
 
  fstconcat a.fst b.fst out.fst  
Connect Connect(&A); removes states and arcs not on a path from the start to a final state
  fstconnect in.fst out.fst  
Changed:
<
<
DecodeWork in progress, under construction Decode(&A, encoder); decodes previously encoded Fst
>
>
Decode Decode(&A, encoder); decodes previously encoded Fst
 
  DecodeFst(A, encoder);  
  fstencode --decode in.fst encoder out.fst  
Determinize Determinize(A, &B); creates equiv. FST with no state with two arcs with the same input label
Line: 391 to 391
 
Difference Difference(A, B, &C); contains strings in A but not B; B unweighted
  DifferenceFst<Arc>(A, B);  
  fstdifference a.fsa b.dfa out.fsa  
Changed:
<
<
EncodeWork in progress, under construction Encode(&A, encoder); combines input labels with output labels and/or weights into new input labels
>
>
Encode Encode(&A, encoder); combines input labels with output labels and/or weights into new input labels
 
  EncodeFst(A, encoder);  
  fstencode [--encode_labels] [--encode_weights] in.fst encoder out.fst  
EpsNormalize EpsNormalize(A, &B, type); creates equiv. FST with any input (output) epsilons at path ends

Revision 872009-03-27 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 382 to 382
 
  fstconcat a.fst b.fst out.fst  
Connect Connect(&A); removes states and arcs not on a path from the start to a final state
  fstconnect in.fst out.fst  
Changed:
<
<
Decode Decode(&A, encoder); decodes previously encoded Fst
>
>
DecodeWork in progress, under construction Decode(&A, encoder); decodes previously encoded Fst
 
  DecodeFst(A, encoder);  
  fstencode --decode in.fst encoder out.fst  
Determinize Determinize(A, &B); creates equiv. FST with no state with two arcs with the same input label
Line: 391 to 391
 
Difference Difference(A, B, &C); contains strings in A but not B; B unweighted
  DifferenceFst<Arc>(A, B);  
  fstdifference a.fsa b.dfa out.fsa  
Changed:
<
<
Encode Encode(&A, encoder); combines input labels with output labels and/or weights into new input labels
>
>
EncodeWork in progress, under construction Encode(&A, encoder); combines input labels with output labels and/or weights into new input labels
 
  EncodeFst(A, encoder);  
  fstencode [--encode_labels] [--encode_weights] in.fst encoder out.fst  
EpsNormalize EpsNormalize(A, &B, type); creates equiv. FST with any input (output) epsilons at path ends

Revision 862009-03-27 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 418 to 418
 
  fstprune [--weight=$w] in.fst out.fst  
Push Push<Arc, Type>(&A, flags); creates equiv. FST pushing weights and/or output labels toward initial or final states
  fstpush [--push_labels] [--push_weights] [--to_final] in.fst out.fst  
Changed:
<
<
RandEquivalent RandEquivalent(A, B, npath); checks if transducers A and B transduce the same randomly-generated string pairs with the same weights
>
>
RandEquivalent RandEquivalent(A, B, npath); checks if transducers A and B transduce the same randomly-generated string pairs with the same weights
 
  fstequivalent --random [-npath=$n] a.fst b.fst  
RandGen RandGen(A, &B [, opts]); generates random path(s) through an FST
  fstrandgen [--max_length=$l] [--npath=$n] [--seed=$s] [--select=$sel] in.fst out.fst

Revision 852009-03-27 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 420 to 420
 
  fstpush [--push_labels] [--push_weights] [--to_final] in.fst out.fst  
RandEquivalent RandEquivalent(A, B, npath); checks if transducers A and B transduce the same randomly-generated string pairs with the same weights
  fstequivalent --random [-npath=$n] a.fst b.fst  
Changed:
<
<
RandGen RandGen(A, &B [, opts]); generates random path(s) through an FST
>
>
RandGen RandGen(A, &B [, opts]); generates random path(s) through an FST
 
  fstrandgen [--max_length=$l] [--npath=$n] [--seed=$s] [--select=$sel] in.fst out.fst
Relabel Relabel(&A, isyms, osyms); changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  

Revision 842009-03-26 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 422 to 422
 
  fstequivalent --random [-npath=$n] a.fst b.fst  
RandGen RandGen(A, &B [, opts]); generates random path(s) through an FST
  fstrandgen [--max_length=$l] [--npath=$n] [--seed=$s] [--select=$sel] in.fst out.fst
Changed:
<
<
RelabelWork in progress, under construction Relabel(&A, isyms, osyms); changes input and output label IDs
>
>
Relabel Relabel(&A, isyms, osyms); changes input and output label IDs
 
  RelabelFst<Arc>(A, isyms, osyms);  
  fstrelabel [--relabel_isymbols=$isyms] [--relabel_osymbols=$osyms] in.fst out.fst  
Replace Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN

Revision 832009-03-17 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 404 to 404
 
Invert Invert(&A); inverse binary relation; exchanges input and output labels
  InvertFst<Arc>(A);  
  fstinvert in.fst out.fst  
Changed:
<
<
MapWork in progress, under construction Map(&A, mapper); transforms arcs in an FST
>
>
Map Map(&A, mapper); transforms arcs in an FST
 
  Map(A, &B, mapper);  
  MapFst<InArc, OutArc, Mapper>(A, mapper);  
  fstmap [--delta=$d] [--map=$type] [--weight=$w] in.fst out.fst  

Revision 822009-03-14 - MichaelRiley

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

OpenFst Quick Tour

Added:
>
>
Below is a brief tutorial on the OpenFst library. After reading this, you may wish to browse the Advanced Usage topic for greater detail and read the library Conventions topic to ensure its correct use.
 

Finding and Using the Library

Changed:
<
<
The OpenFst Library is a C++ template library. From C++, include <fst/fstlib.h> in the installation include directory and link to libfst.so in the installation library directory. (You may instead use just those include files for
>
>
The OpenFst library is a C++ template library. From C++, include <fst/fstlib.h> in the installation include directory and link to libfst.so in the installation library directory. (You may instead use just those include files for
 the classes and functions that you will need.) All classes and functions are in the fst namespace; the examples below assume you are within that namespace for brevity. (Include <fst/fst-decl.h> if forward declaration of the public OpenFst classes is needed.)

Revision 812009-03-12 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 422 to 422
 
RelabelWork in progress, under construction Relabel(&A, isyms, osyms); changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  
  fstrelabel [--relabel_isymbols=$isyms] [--relabel_osymbols=$osyms] in.fst out.fst  
Changed:
<
<
ReplaceWork in progress, under construction Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN
>
>
Replace Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN
 
ReplaceFst<Arc>(fst_label_pairs, root_label);  
  fstreplace root.fst rootlabel [rule1.fst rule1.label ...] out.fst  
Reverse Reverse(A, &B); contains the reversed strings in A

Revision 802009-03-12 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 25 to 25
 final weight is a final state. There is an arc (or transition) from state 0 to 1 with input label a, output label x, and weight 0.5. This FST transduces, for instance, the string ac to xz with weight 6.5 (the sum of the arc and final weights).
Changed:
<
<
Note we have assumed the library default Weight type for this description.
>
>
Note we have assumed the library default Weight type for this description.
 

Creating FSTs

Revision 792009-03-10 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 6 to 6
 

Finding and Using the Library

Changed:
<
<
The OpenFst Library is a C++ template library. From C++, include <fst/fstlib.h> in the installation include directory and link to libfst.so in the installation library directory. (You may instead use just those include files for the classes and functions that you will need.) All classes and functions are in the fst namespace; the examples below assume you are within that namespace for brevity. (Include <fst/fst-decl.h> if forward declaration of the public OpenFst classes is needed.)
>
>
The OpenFst Library is a C++ template library. From C++, include <fst/fstlib.h> in the installation include directory and link to libfst.so in the installation library directory. (You may instead use just those include files for the classes and functions that you will need.) All classes and functions are in the fst namespace; the examples below assume you are within that namespace for brevity. (Include <fst/fst-decl.h> if forward declaration of the public OpenFst classes is needed.)

As an alternative interface, there are shell-level commands in the installation bin directory that operate on file representations of FSTs. The command-line flag --help will give usage information.

 
Deleted:
<
<
As an alternative interface, there are shell-level commands in the installation bin directory that operate on file representations of FSTs. The command-line flag --help will give usage information.
 

Example FST

Line: 16 to 20
  symbolicfst.jpg
Changed:
<
<
The initial state is label 0. There can only be one initial state. The final state is 2 with final weight of 3.5. Any state with non-infinite final weight is a final state. There is an arc (or transition) from state 0 to 1 with input label a, output label x, and weight 0.5. This FST transduces, for instance, the string ac to xz with weight 6.5 (the sum of the arc and final weights). Note we have assumed the library default Weight type for this description.
>
>
The initial state is label 0. There can only be one initial state. The final state is 2 with final weight of 3.5. Any state with non-infinite final weight is a final state. There is an arc (or transition) from state 0 to 1 with input label a, output label x, and weight 0.5. This FST transduces, for instance, the string ac to xz with weight 6.5 (the sum of the arc and final weights). Note we have assumed the library default Weight type for this description.
 

Creating FSTs

Changed:
<
<
FSTs can be created with constructors and mutators from C++ or from text files at the shell-level. We will show how to create the above example FST both ways.
>
>
FSTs can be created with constructors and mutators from C++ or from text files at the shell-level. We will show how to create the above example FST both ways.
 

Creating FSTs Using Constructors and Mutators From C++

The following code will create our example FST within C++:

Changed:
<
<
// A vector FST is a general mutable FST  StdVectorFst fst;  // Adds state 0 to the initially empty FST and make it the start state.  fst.AddState();   // 1st state will be state 0 (returned by AddState)  fst.SetStart(0);  // arg is state ID  // Adds two arcs exiting state 0. // Arc constructor args: ilabel, olabel, weight, dest state ID.  fst.AddArc(0, StdArc(1, 1, 0.5, 1));  // 1st arg is src state ID  fst.AddArc(0, StdArc(2, 2, 1.5, 1));   // Adds state 1 and its arc.  fst.AddState(); fst.AddArc(1, StdArc(3, 3, 2.5, 2));  // Adds state 2 and set its final weight.  fst.AddState(); fst.SetFinal(2, 3.5);  // 1st arg is state ID, 2nd arg weight  
>
>
// A vector FST is a general mutable FST 
StdVectorFst fst;

// Adds state 0 to the initially empty FST and make it the start state. 
fst.AddState();   // 1st state will be state 0 (returned by AddState) 
fst.SetStart(0);  // arg is state ID

// Adds two arcs exiting state 0.
// Arc constructor args: ilabel, olabel, weight, dest state ID. 
fst.AddArc(0, StdArc(1, 1, 0.5, 1));  // 1st arg is src state ID 
fst.AddArc(0, StdArc(2, 2, 1.5, 1)); 

// Adds state 1 and its arc. 
fst.AddState();
fst.AddArc(1, StdArc(3, 3, 2.5, 2));

// Adds state 2 and set its final weight. 
fst.AddState();
fst.SetFinal(2, 3.5);  // 1st arg is state ID, 2nd arg weight 
  We can save this FST to a file with:
Line: 37 to 66
 

Creating FSTs Using Text Files from the Shell

Changed:
<
<
FSTs can be specified using a text file in the AT&T FSM format Supporting this format permits interoperability with the AT&T FSM binary tools, which can be downloaded for non-commercial purposes.
>
>
FSTs can be specified using a text file in the AT&T FSM format Supporting this format permits interoperability with the AT&T FSM binary tools, which can be downloaded for non-commercial purposes.
  We can create the text FST file for our example as follows:
Changed:
<
<
# arc format: src dest ilabel olabel [weight] # final state format: state [weight] # lines may occur in any order except initial state must be first line # unspecified weights default to 0.0 (for the library-default Weight type)  cat >text.fst <
#SymbolTables The internal representation of an arc label is an integer. We must provide the mapping from symbols to integers explicitly with a symbol table file, also in AT&T format:
>
>
# arc format: src dest ilabel olabel [weight]
# final state format: state [weight]
# lines may occur in any order except initial state must be first line
# unspecified weights default to 0.0 (for the library-default Weight type) 
cat >text.fst <

The internal representation of an arc label is an integer. 
We must provide the mapping from symbols to integers explicitly with a symbol table file, also in AT&T format:
 
$ cat >isyms.txt <<EOF
Line: 59 to 106
 EOF
Changed:
<
<
You may use any string for a label; you may use any non-negative integer for a label ID. The zero label ID is reserved for the epsilon label, which is the empty string. We have included 0 in our table, even though it is not used in our example. Since subsequent FST operations might add epsilons, it is good practice to include a symbol for it.
>
>
You may use any string for a label; you may use any non-negative integer for a label ID. The zero label ID is reserved for the epsilon label, which is the empty string. We have included 0 in our table, even though it is not used in our example. Since subsequent FST operations might add epsilons, it is good practice to include a symbol for it.
 
Changed:
<
<
This text FST must be converted into a binary FST file before it can be used by the OpenFst library. #FstCompile
# Creates binary Fst from text file.  # The symbolic labels will be converted into integers using the symbol table files.  $ fstcompile --isymbols=isyms.txt --osymbols=osyms.txt text.fst binary.fst  # As above but the symbol tables are stored with the FST.  $ fstcompile --isymbols=isyms.txt --osymbols=osyms.txt --keep_isymbols --keep_osymbols text.fst binary.fst 
>
>
This text FST must be converted into a binary FST file before it can be used by the OpenFst library.
# Creates binary Fst from text file. 
# The symbolic labels will be converted into integers using the symbol table files. 
$ fstcompile --isymbols=isyms.txt --osymbols=osyms.txt text.fst binary.fst

# As above but the symbol tables are stored with the FST. 
$ fstcompile --isymbols=isyms.txt --osymbols=osyms.txt --keep_isymbols --keep_osymbols text.fst binary.fst
  If the labels are represented as non-negative integers in the text FST, then the symbol table files can be omitted. In any case, the internal representation of the FST is:
Line: 83 to 138
 

Accessing FSTs from C++

Changed:
<
<
Here is the standard representation of an arc:
>
>
Here is the standard representation of an arc:
 
Changed:
<
<
struct StdArc {  typedef int Label;  typedef TropicalWeight Weight;  // see "FST Weights" below   typedef int StateId;     Label ilabel;  Label olabel;  Weight weight;  StateId nextstate; }; 
>
>
struct StdArc {
 typedef int Label;
 typedef TropicalWeight Weight;  // see "FST Weights" below 
 typedef int StateId; 
 
 Label ilabel;
 Label olabel;
 Weight weight;
 StateId nextstate;
};
  Here are some example accesses of an FST:
Changed:
<
<
typedef StdArc::StateId StateId;  # Gets the initial state; if == kNoState => empty FST.  StateId initial_state = fst.Start();  # Get state i's final weight; if == Weight::Zero() => non-final.  Weight weight = fst.Final(i); 
#StateIterator
# Iterates over the FSTs states.  for (StateIterator siter(fst); !siter.Done(); siter.Next())    StateId state_id = siter.Value(); 
#ArcIterator
# Iterates over state i's arcs.  for (ArcIterator aiter(fst, i); !aiter.Done(); aiter.Next())   const StdArc &arc = aiter.Value(); 
#FstMatcher
# Iterates over state i's arcs that have input label l (FST must support this - # in the simplest cases,  true when the input labels are sorted).  Matcher matcher(fst, MATCH_INPUT); matcher.SetState(i); if (matcher.Find(l))    for (; !matcher.Done(); matcher.Next())      const StdArc &arc = matcher.Value(); 
>
>
typedef StdArc::StateId StateId;

# Gets the initial state; if == kNoState => empty FST. 
StateId initial_state = fst.Start();

# Get state i's final weight; if == Weight::Zero() => non-final. 
Weight weight = fst.Final(i);
# Iterates over the FSTs states. 
for (StateIterator siter(fst); !siter.Done(); siter.Next()) 
  StateId state_id = siter.Value();
# Iterates over state i's arcs. 
for (ArcIterator aiter(fst, i); !aiter.Done(); aiter.Next())
  const StdArc &arc = aiter.Value();
# Iterates over state i's arcs that have input label l (FST must support this -
# in the simplest cases,  true when the input labels are sorted). 
Matcher matcher(fst, MATCH_INPUT);
matcher.SetState(i);
if (matcher.Find(l)) 
  for (; !matcher.Done(); matcher.Next())
     const StdArc &arc = matcher.Value();
  More information on state iterators, arc iterators, and matchers are linked here.
Line: 97 to 189
 

Printing, Drawing and Summarizing FSTs from the Shell

Changed:
<
<
The following command will print out an FST in AT&T text format: #FstPrint
# Print FST using symbol table files.  $ fstprint --isymbols=isyms.txt --osymbols=osyms.txt binary.fst text.fst 

If the symbol table files are omitted, the FST will be printed with numeric labels unless the symbol tables are stored with the FST (e.g., with fstcompile --keep_isymbols --keep_osymbols).

>
>
The following command will print out an FST in AT&T text format:
# Print FST using symbol table files. 
$ fstprint --isymbols=isyms.txt --osymbols=osyms.txt binary.fst text.fst

If the symbol table files are omitted, the FST will be printed with numeric labels unless the symbol tables are stored with the FST (e.g., with fstcompile --keep_isymbols --keep_osymbols).

  The following command will draw an FST using Graphviz dot format.
Changed:
<
<
# Draw FST using symbol table files and Graphviz dot:  $ fstdraw --isymbols=isyms.txt --osymbols=osyms.txt binary.fst binary.dot $ dot -Tps binary.dot >binary.ps 
>
>
# Draw FST using symbol table files and Graphviz dot: 
$ fstdraw --isymbols=isyms.txt --osymbols=osyms.txt binary.fst binary.dot
$ dot -Tps binary.dot >binary.ps
  Summary information about an FST can be obtained with:
Line: 171 to 272
  These classes are templated on the arc to allow customization. The class StdFst is a typedef for Fst<StdArc>. Similar typedefs exist for all the above templates.
Changed:
<
<
For the state and arc iterators, you will get the greatest efficiency if you specify the most specific FST class as the iterator template argument (e.g., ArcIterator<StdVectorFst> rather than ArcIterator<StdFst> for a known StdVectorFst).
>
>
For the state and arc iterators, you will get the greatest efficiency if you specify the most specific FST class as the iterator template argument (e.g., ArcIterator<StdVectorFst> rather than ArcIterator<StdFst> for a known StdVectorFst).
  The C++ FST operations come in three general forms:
Line: 188 to 291
  ComposeFst(const Fst &fst1, const Fst &fst2);
Changed:
<
<
Delayed Fsts have constant time-class constructors. When components of delayed Fsts are accessed through the Fst interface, the automaton is built dynamically, just enough to respond to the accesses requested. It is important that the object access conventions are observed for correct operation.
>
>
Delayed Fsts have constant time-class constructors. When components of delayed Fsts are accessed through the Fst interface, the automaton is built dynamically, just enough to respond to the accesses requested. It is important that the object access conventions are observed for correct operation.
  Several operations, like Union, come in more than one of the above forms.

Calling FST Operations from the Shell

Changed:
<
<
The shell-level FST operations typically read one or more input binary FST files, call internally the corresponding C++ operation and then write an output binary FST file. If the output file is omitted, standard output is used. If the input file is also omitted (unary case) or is "-", then standard input is used. Specifically, they have the form:
>
>
The shell-level FST operations typically read one or more input binary FST files, call internally the corresponding C++ operation and then write an output binary FST file. If the output file is omitted, standard output is used. If the input file is also omitted (unary case) or is "-", then standard input is used. Specifically, they have the form:
 
  • Unary Operations:
Line: 208 to 313
 

Example Use: FST Application

Changed:
<
<
One of the most useful finite-state operations is composition, which produces the relational composition of two transductions. It can be used, for example, to apply a transduction to some input:
>
>
One of the most useful finite-state operations is composition, which produces the relational composition of two transductions. It can be used, for example, to apply a transduction to some input:
 

FST Application from C++

Changed:
<
<
// Reads in an input FST.  StdFst *input = StdFst::Read("input.fst");  // Reads in the transduction model.  StdFst *model = StdFst::Read("model.fst");  // The FSTs must be sorted along the dimensions they will be joined. // In fact, only one needs to be so sorted. // This could have instead been done for "model.fst" when it was created.  ArcSort(input, StdOLabelCompare()); ArcSort(model, StdILabelCompare());  // Container for composition result.  StdVectorFst result;  // Create the composed FST.  Compose(*input, *model, &result);  // Just keeps the output labels.  Project(&result,  PROJECT_OUTPUT); 
>
>
// Reads in an input FST. 
StdFst *input = StdFst::Read("input.fst");

// Reads in the transduction model. 
StdFst *model = StdFst::Read("model.fst");

// The FSTs must be sorted along the dimensions they will be joined.
// In fact, only one needs to be so sorted.
// This could have instead been done for "model.fst" when it was created. 
ArcSort(input, StdOLabelCompare());
ArcSort(model, StdILabelCompare());

// Container for composition result. 
StdVectorFst result;

// Create the composed FST. 
Compose(*input, *model, &result);

// Just keeps the output labels. 
Project(&result,  PROJECT_OUTPUT);
 

FST Application from the Shell

Changed:
<
<
# The FSTs must be sorted along the dimensions they will be joined. # In fact, only one needs to be so sorted. # This could have instead been done for "model.fst" when it was created.  $ fstarcsort --sort_type=olabel input.fst input_sorted.fst $ fstarcsort --sort_type=ilabel model.fst model_sorted.fst  # Creates the composed FST.  $ fstcompose input_sorted.fst model_sorted.fst comp.fst  # Just keeps the output label  $ fstproject --project_output comp.fst result.fst  # Do it all in a single command line.  $ fstarcsort --sort_type=ilabel model.fst | fstcompose input.fst - | fstproject --project_output result.fst 
>
>
# The FSTs must be sorted along the dimensions they will be joined.
# In fact, only one needs to be so sorted.
# This could have instead been done for "model.fst" when it was created. 
$ fstarcsort --sort_type=olabel input.fst input_sorted.fst
$ fstarcsort --sort_type=ilabel model.fst model_sorted.fst

# Creates the composed FST. 
$ fstcompose input_sorted.fst model_sorted.fst comp.fst

# Just keeps the output label 
$ fstproject --project_output comp.fst result.fst

# Do it all in a single command line. 
$ fstarcsort --sort_type=ilabel model.fst | fstcompose input.fst - | fstproject --project_output result.fst
 

Available FST Operations

Line: 278 to 418
 
RandEquivalent RandEquivalent(A, B, npath); checks if transducers A and B transduce the same randomly-generated string pairs with the same weights
  fstequivalent --random [-npath=$n] a.fst b.fst  
RandGen RandGen(A, &B [, opts]); generates random path(s) through an FST
Changed:
<
<
  fstrandgen [--max_length=$l] [--npath=$n] [--seed=$s] [--select=$sel] in.fst out.fst
>
>
  fstrandgen [--max_length=$l] [--npath=$n] [--seed=$s] [--select=$sel] in.fst out.fst
 
RelabelWork in progress, under construction Relabel(&A, isyms, osyms); changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  
  fstrelabel [--relabel_isymbols=$isyms] [--relabel_osymbols=$osyms] in.fst out.fst  
Line: 309 to 450
 

FST Weights

Changed:
<
<
An arc weight in an FST gives the cost of taking that transition. The OpenFst library supports multiple types of weights -- in fact, any C++ class that meets various properties can be used as the Weight type specified in the Arc template parameter of an Fst. Several Weight types are predefined in the library that will normally meet your needs. Among a weight's properties, it must have associated binary operations ⊕ and ⊗ and elements 0 and 1. These are implemented by a Weight type with functions Plus(x, y) and Times(x, y) and static member functions Zero() and One(), respectively. These must form a semiring; see here for a further description of the constraints on these operations and other properties of weights. ⊕ is used to combine the weight of two identically labeled alternative paths, while ⊗ is used to combine weights along a path or when matching paths in composition or intersection. A state is final if and only its final weight is not equal to 0 . A transition with weight 1 is, in essence, "free". A path with weight 0 is not allowed (since such paths present technical problems with some algorithms).
>
>
An arc weight in an FST gives the cost of taking that transition. The OpenFst library supports multiple types of weights -- in fact, any C++ class that meets various properties can be used as the Weight type specified in the Arc template parameter of an Fst. Several Weight types are predefined in the library that will normally meet your needs. Among a weight's properties, it must have associated binary operations ⊕ and ⊗ and elements 0 and 1. These are implemented by a Weight type with functions Plus(x, y) and Times(x, y) and static member functions Zero() and One(), respectively. These must form a semiring; see here for a further description of the constraints on these operations and other properties of weights. ⊕ is used to combine the weight of two identically labeled alternative paths, while ⊗ is used to combine weights along a path or when matching paths in composition or intersection. A state is final if and only its final weight is not equal to 0 . A transition with weight 1 is, in essence, "free". A path with weight 0 is not allowed (since such paths present technical problems with some algorithms).
  The following are some useful weight types:
Changed:
<
<
Name Set
(Plus)

(Times)
0
(Zero)
1
(One)
>
>
Name Set
(Plus)

(Times)
0
(Zero)
1
(One)
 
Boolean {0, 1} 0 1
Real [0, ∞] + * 0 1
Log [-∞, ∞] -log(e-x + e-y) + 0
Tropical [-∞, ∞] min + 0
Changed:
<
<
The boolean weight type is used for the familiar unweighted automata (but see tropical below). The real weight type is appropriate when the transition weights represent probabilities. The log weight type is appropriate when the transition weights represent negative log probabilities (more numerically stable than the isomorphic, under log(), real weight type). The tropical weight type is appropriate for shortest path operations and is identical to the log except it uses min for the Plus operation.

The OpenFst library predefines TropicalWeight doc and LogWeight doc as well as the corresponding StdArc and LogArc. These weight classes represent their weight in a single precision float that is a constructor argument. That float can be directly accessed with member function Value(). For unweighted automata, it is convenient and customary in this library to use TropicalWeight restricted to Zero and One. StdArc is the default arc type for the FST binaries. The Boolean and Real weight types not currently pre-defined. See here for all pre-defined weight types.

>
>
The boolean weight type is used for the familiar unweighted automata (but see tropical below). The real weight type is appropriate when the transition weights represent probabilities. The log weight type is appropriate when the transition weights represent negative log probabilities (more numerically stable than the isomorphic, under log(), real weight type). The tropical weight type is appropriate for shortest path operations and is identical to the log except it uses min for the Plus operation.

The OpenFst library predefines TropicalWeight doc and LogWeight doc as well as the corresponding StdArc and LogArc. These weight classes represent their weight in a single precision float that is a constructor argument. That float can be directly accessed with member function Value(). For unweighted automata, it is convenient and customary in this library to use TropicalWeight restricted to Zero and One. StdArc is the default arc type for the FST binaries. The Boolean and Real weight types not currently pre-defined. See here for all pre-defined weight types.

  From the shell-level, the FST arc type can be specified to fstcompile with the --arc_type flag; StdArc is the default.

Revision 782009-03-10 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 6 to 6
 

Finding and Using the Library

Changed:
<
<
The OpenFst Library is a C++ template library. From C++, include <fst/fstlib.h> in the installation include directory and link to libfst.so in the installation library directory. (You may instead use just those include files for the classes and functions that you will need.) All classes and functions are in the fst namespace; the examples below assume you are within that namespace for brevity. (Include <fst/fst-decl.h> if forward declaration of the public OpenFst classes is needed.)

As an alternative interface, there are shell-level commands in the installation bin directory that operate on file representations of FSTs. The command-line flag --help will give usage information.

>
>
The OpenFst Library is a C++ template library. From C++, include <fst/fstlib.h> in the installation include directory and link to libfst.so in the installation library directory. (You may instead use just those include files for the classes and functions that you will need.) All classes and functions are in the fst namespace; the examples below assume you are within that namespace for brevity. (Include <fst/fst-decl.h> if forward declaration of the public OpenFst classes is needed.)
 
Added:
>
>
As an alternative interface, there are shell-level commands in the installation bin directory that operate on file representations of FSTs. The command-line flag --help will give usage information.
 

Example FST

Line: 20 to 16
  symbolicfst.jpg
Changed:
<
<
The initial state is label 0. There can only be one initial state. The final state is 2 with final weight of 3.5. Any state with non-infinite final weight is a final state. There is an arc (or transition) from state 0 to 1 with input label a, output label x, and weight 0.5. This FST transduces, for instance, the string ac to xz with weight 6.5 (the sum of the arc and final weights). Note we have assumed the library default Weight type for this description.
>
>
The initial state is label 0. There can only be one initial state. The final state is 2 with final weight of 3.5. Any state with non-infinite final weight is a final state. There is an arc (or transition) from state 0 to 1 with input label a, output label x, and weight 0.5. This FST transduces, for instance, the string ac to xz with weight 6.5 (the sum of the arc and final weights). Note we have assumed the library default Weight type for this description.
 

Creating FSTs

Changed:
<
<
FSTs can be created with constructors and mutators from C++ or from text files at the shell-level. We will show how to create the above example FST both ways.
>
>
FSTs can be created with constructors and mutators from C++ or from text files at the shell-level. We will show how to create the above example FST both ways.
 

Creating FSTs Using Constructors and Mutators From C++

The following code will create our example FST within C++:

Changed:
<
<
// A vector FST is a general mutable FST 
StdVectorFst fst;

// Adds state 0 to the initially empty FST and make it the start state. 
fst.AddState();   // 1st state will be state 0 (returned by AddState) 
fst.SetStart(0);  // arg is state ID

// Adds two arcs exiting state 0.
// Arc constructor args: ilabel, olabel, weight, dest state ID. 
fst.AddArc(0, StdArc(1, 1, 0.5, 1));  // 1st arg is src state ID 
fst.AddArc(0, StdArc(2, 2, 1.5, 1)); 

// Adds state 1 and its arc. 
fst.AddState();
fst.AddArc(1, StdArc(3, 3, 2.5, 2));

// Adds state 2 and set its final weight. 
fst.AddState();
fst.SetFinal(2, 3.5);  // 1st arg is state ID, 2nd arg weight 
>
>
// A vector FST is a general mutable FST  StdVectorFst fst;  // Adds state 0 to the initially empty FST and make it the start state.  fst.AddState();   // 1st state will be state 0 (returned by AddState)  fst.SetStart(0);  // arg is state ID  // Adds two arcs exiting state 0. // Arc constructor args: ilabel, olabel, weight, dest state ID.  fst.AddArc(0, StdArc(1, 1, 0.5, 1));  // 1st arg is src state ID  fst.AddArc(0, StdArc(2, 2, 1.5, 1));   // Adds state 1 and its arc.  fst.AddState(); fst.AddArc(1, StdArc(3, 3, 2.5, 2));  // Adds state 2 and set its final weight.  fst.AddState(); fst.SetFinal(2, 3.5);  // 1st arg is state ID, 2nd arg weight  
  We can save this FST to a file with:
Line: 66 to 37
 

Creating FSTs Using Text Files from the Shell

Changed:
<
<
FSTs can be specified using a text file in the AT&T FSM format Supporting this format permits interoperability with the AT&T FSM binary tools, which can be downloaded for non-commercial purposes.
>
>
FSTs can be specified using a text file in the AT&T FSM format Supporting this format permits interoperability with the AT&T FSM binary tools, which can be downloaded for non-commercial purposes.
  We can create the text FST file for our example as follows:
Changed:
<
<
# arc format: src dest ilabel olabel [weight]
# final state format: state [weight]
# lines may occur in any order except initial state must be first line
# unspecified weights default to 0.0 (for the library-default Weight type) 
cat >text.fst <

The internal representation of an arc label is an integer. 
We must provide the mapping from symbols to integers explicitly with a symbol table file, also in AT&T format:
>
>
# arc format: src dest ilabel olabel [weight] # final state format: state [weight] # lines may occur in any order except initial state must be first line # unspecified weights default to 0.0 (for the library-default Weight type)  cat >text.fst <
#SymbolTables The internal representation of an arc label is an integer. We must provide the mapping from symbols to integers explicitly with a symbol table file, also in AT&T format:
 
$ cat >isyms.txt <<EOF
Line: 106 to 59
 EOF
Changed:
<
<
You may use any string for a label; you may use any non-negative integer for a label ID. The zero label ID is reserved for the epsilon label, which is the empty string. We have included 0 in our table, even though it is not used in our example. Since subsequent FST operations might add epsilons, it is good practice to include a symbol for it.
>
>
You may use any string for a label; you may use any non-negative integer for a label ID. The zero label ID is reserved for the epsilon label, which is the empty string. We have included 0 in our table, even though it is not used in our example. Since subsequent FST operations might add epsilons, it is good practice to include a symbol for it.
 
Changed:
<
<
This text FST must be converted into a binary FST file before it can be used by the OpenFst library.
# Creates binary Fst from text file. 
# The symbolic labels will be converted into integers using the symbol table files. 
$ fstcompile --isymbols=isyms.txt --osymbols=osyms.txt text.fst binary.fst

# As above but the symbol tables are stored with the FST. 
$ fstcompile --isymbols=isyms.txt --osymbols=osyms.txt --keep_isymbols --keep_osymbols text.fst binary.fst
>
>
This text FST must be converted into a binary FST file before it can be used by the OpenFst library. #FstCompile
# Creates binary Fst from text file.  # The symbolic labels will be converted into integers using the symbol table files.  $ fstcompile --isymbols=isyms.txt --osymbols=osyms.txt text.fst binary.fst  # As above but the symbol tables are stored with the FST.  $ fstcompile --isymbols=isyms.txt --osymbols=osyms.txt --keep_isymbols --keep_osymbols text.fst binary.fst 
  If the labels are represented as non-negative integers in the text FST, then the symbol table files can be omitted. In any case, the internal representation of the FST is:
Line: 138 to 83
 

Accessing FSTs from C++

Changed:
<
<
Here is the standard representation of an arc:
>
>
Here is the standard representation of an arc:
 
Changed:
<
<
struct StdArc {
 typedef int Label;
 typedef TropicalWeight Weight;  // see "FST Weights" below 
 typedef int StateId; 
 
 Label ilabel;
 Label olabel;
 Weight weight;
 StateId nextstate;
};
>
>
struct StdArc {  typedef int Label;  typedef TropicalWeight Weight;  // see "FST Weights" below   typedef int StateId;     Label ilabel;  Label olabel;  Weight weight;  StateId nextstate; }; 
  Here are some example accesses of an FST:
Changed:
<
<
typedef StdArc::StateId StateId;

# Gets the initial state; if == kNoState => empty FST. 
StateId initial_state = fst.Start();

# Get state i's final weight; if == Weight::Zero() => non-final. 
Weight weight = fst.Final(i);
# Iterates over the FSTs states. 
for (StateIterator siter(fst); !siter.Done(); siter.Next()) 
  StateId state_id = siter.Value();
# Iterates over state i's arcs. 
for (ArcIterator aiter(fst, i); !aiter.Done(); aiter.Next())
  const StdArc &arc = aiter.Value();
# Iterates over state i's arcs that have input label l (FST must support this -
# in the simplest cases,  true when the input labels are sorted). 
Matcher matcher(fst, MATCH_INPUT);
matcher.SetState(i);
if (matcher.Find(l)) 
  for (; !matcher.Done(); matcher.Next())
     const StdArc &arc = matcher.Value();
>
>
typedef StdArc::StateId StateId;  # Gets the initial state; if == kNoState => empty FST.  StateId initial_state = fst.Start();  # Get state i's final weight; if == Weight::Zero() => non-final.  Weight weight = fst.Final(i); 
#StateIterator
# Iterates over the FSTs states.  for (StateIterator siter(fst); !siter.Done(); siter.Next())    StateId state_id = siter.Value(); 
#ArcIterator
# Iterates over state i's arcs.  for (ArcIterator aiter(fst, i); !aiter.Done(); aiter.Next())   const StdArc &arc = aiter.Value(); 
#FstMatcher
# Iterates over state i's arcs that have input label l (FST must support this - # in the simplest cases,  true when the input labels are sorted).  Matcher matcher(fst, MATCH_INPUT); matcher.SetState(i); if (matcher.Find(l))    for (; !matcher.Done(); matcher.Next())      const StdArc &arc = matcher.Value(); 
  More information on state iterators, arc iterators, and matchers are linked here.
Line: 189 to 97
 

Printing, Drawing and Summarizing FSTs from the Shell

Changed:
<
<
The following command will print out an FST in AT&T text format:
# Print FST using symbol table files. 
$ fstprint --isymbols=isyms.txt --osymbols=osyms.txt binary.fst text.fst

If the symbol table files are omitted, the FST will be printed with numeric labels unless the symbol tables are stored with the FST (e.g., with fstcompile --keep_isymbols --keep_osymbols).

>
>
The following command will print out an FST in AT&T text format: #FstPrint
# Print FST using symbol table files.  $ fstprint --isymbols=isyms.txt --osymbols=osyms.txt binary.fst text.fst 

If the symbol table files are omitted, the FST will be printed with numeric labels unless the symbol tables are stored with the FST (e.g., with fstcompile --keep_isymbols --keep_osymbols).

  The following command will draw an FST using Graphviz dot format.
Changed:
<
<
# Draw FST using symbol table files and Graphviz dot: 
$ fstdraw --isymbols=isyms.txt --osymbols=osyms.txt binary.fst binary.dot
$ dot -Tps binary.dot >binary.ps
>
>
# Draw FST using symbol table files and Graphviz dot:  $ fstdraw --isymbols=isyms.txt --osymbols=osyms.txt binary.fst binary.dot $ dot -Tps binary.dot >binary.ps 
  Summary information about an FST can be obtained with:
Line: 272 to 171
  These classes are templated on the arc to allow customization. The class StdFst is a typedef for Fst<StdArc>. Similar typedefs exist for all the above templates.
Changed:
<
<
For the state and arc iterators, you will get the greatest efficiency if you specify the most specific FST class as the iterator template argument (e.g., ArcIterator<StdVectorFst> rather than ArcIterator<StdFst> for a known StdVectorFst).
>
>
For the state and arc iterators, you will get the greatest efficiency if you specify the most specific FST class as the iterator template argument (e.g., ArcIterator<StdVectorFst> rather than ArcIterator<StdFst> for a known StdVectorFst).
  The C++ FST operations come in three general forms:
Line: 291 to 188
  ComposeFst(const Fst &fst1, const Fst &fst2);
Changed:
<
<
Delayed Fsts have constant time-class constructors. When components of delayed Fsts are accessed through the Fst interface, the automaton is built dynamically, just enough to respond to the accesses requested. It is important that the object access conventions are observed for correct operation.
>
>
Delayed Fsts have constant time-class constructors. When components of delayed Fsts are accessed through the Fst interface, the automaton is built dynamically, just enough to respond to the accesses requested. It is important that the object access conventions are observed for correct operation.
  Several operations, like Union, come in more than one of the above forms.

Calling FST Operations from the Shell

Changed:
<
<
The shell-level FST operations typically read one or more input binary FST files, call internally the corresponding C++ operation and then write an output binary FST file. If the output file is omitted, standard output is used. If the input file is also omitted (unary case) or is "-", then standard input is used. Specifically, they have the form:
>
>
The shell-level FST operations typically read one or more input binary FST files, call internally the corresponding C++ operation and then write an output binary FST file. If the output file is omitted, standard output is used. If the input file is also omitted (unary case) or is "-", then standard input is used. Specifically, they have the form:
 
  • Unary Operations:
Line: 313 to 208
 

Example Use: FST Application

Changed:
<
<
One of the most useful finite-state operations is composition, which produces the relational composition of two transductions. It can be used, for example, to apply a transduction to some input:
>
>
One of the most useful finite-state operations is composition, which produces the relational composition of two transductions. It can be used, for example, to apply a transduction to some input:
 

FST Application from C++

Changed:
<
<
// Reads in an input FST. 
StdFst *input = StdFst::Read("input.fst");

// Reads in the transduction model. 
StdFst *model = StdFst::Read("model.fst");

// The FSTs must be sorted along the dimensions they will be joined.
// In fact, only one needs to be so sorted.
// This could have instead been done for "model.fst" when it was created. 
ArcSort(input, StdOLabelCompare());
ArcSort(model, StdILabelCompare());

// Container for composition result. 
StdVectorFst result;

// Create the composed FST. 
Compose(*input, *model, &result);

// Just keeps the output labels. 
Project(&result,  PROJECT_OUTPUT);
>
>
// Reads in an input FST.  StdFst *input = StdFst::Read("input.fst");  // Reads in the transduction model.  StdFst *model = StdFst::Read("model.fst");  // The FSTs must be sorted along the dimensions they will be joined. // In fact, only one needs to be so sorted. // This could have instead been done for "model.fst" when it was created.  ArcSort(input, StdOLabelCompare()); ArcSort(model, StdILabelCompare());  // Container for composition result.  StdVectorFst result;  // Create the composed FST.  Compose(*input, *model, &result);  // Just keeps the output labels.  Project(&result,  PROJECT_OUTPUT); 
 

FST Application from the Shell

Changed:
<
<
# The FSTs must be sorted along the dimensions they will be joined.
# In fact, only one needs to be so sorted.
# This could have instead been done for "model.fst" when it was created. 
$ fstarcsort --sort_type=olabel input.fst input_sorted.fst
$ fstarcsort --sort_type=ilabel model.fst model_sorted.fst

# Creates the composed FST. 
$ fstcompose input_sorted.fst model_sorted.fst comp.fst

# Just keeps the output label 
$ fstproject --project_output comp.fst result.fst

# Do it all in a single command line. 
$ fstarcsort --sort_type=ilabel model.fst | fstcompose input.fst - | fstproject --project_output result.fst
>
>
# The FSTs must be sorted along the dimensions they will be joined. # In fact, only one needs to be so sorted. # This could have instead been done for "model.fst" when it was created.  $ fstarcsort --sort_type=olabel input.fst input_sorted.fst $ fstarcsort --sort_type=ilabel model.fst model_sorted.fst  # Creates the composed FST.  $ fstcompose input_sorted.fst model_sorted.fst comp.fst  # Just keeps the output label  $ fstproject --project_output comp.fst result.fst  # Do it all in a single command line.  $ fstarcsort --sort_type=ilabel model.fst | fstcompose input.fst - | fstproject --project_output result.fst 
 

Available FST Operations

Line: 418 to 278
 
RandEquivalent RandEquivalent(A, B, npath); checks if transducers A and B transduce the same randomly-generated string pairs with the same weights
  fstequivalent --random [-npath=$n] a.fst b.fst  
RandGen RandGen(A, &B [, opts]); generates random path(s) through an FST
Changed:
<
<
  fstrandgen [--max_length=$l] [--npath=$n] [--seed=$s] [--select=$sel] in.fst out.fst
>
>
  fstrandgen [--max_length=$l] [--npath=$n] [--seed=$s] [--select=$sel] in.fst out.fst
 
RelabelWork in progress, under construction Relabel(&A, isyms, osyms); changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  
  fstrelabel [--relabel_isymbols=$isyms] [--relabel_osymbols=$osyms] in.fst out.fst  
Line: 450 to 309
 

FST Weights

Changed:
<
<
An arc weight in an FST gives the cost of taking that transition. The OpenFst library supports multiple types of weights -- in fact, any C++ class that meets various properties can be used as the Weight type specified in the Arc template parameter of an Fst. Several Weight types are predefined in the library that will normally meet your needs. Among a weight's properties, it must have associated binary operations ⊕ and ⊗ and elements 0 and 1. These are implemented by a Weight type with functions Plus(x, y) and Times(x, y) and static member functions Zero() and One(), respectively. These must form a semiring; see here for a further description of the constraints on these operations and other properties of weights. ⊕ is used to combine the weight of two identically labeled alternative paths, while ⊗ is used to combine weights along a path or when matching paths in composition or intersection. A state is final if and only its final weight is not equal to 0 . A transition with weight 1 is, in essence, "free". A path with weight 0 is not allowed (since such paths present technical problems with some algorithms).
>
>
An arc weight in an FST gives the cost of taking that transition. The OpenFst library supports multiple types of weights -- in fact, any C++ class that meets various properties can be used as the Weight type specified in the Arc template parameter of an Fst. Several Weight types are predefined in the library that will normally meet your needs. Among a weight's properties, it must have associated binary operations ⊕ and ⊗ and elements 0 and 1. These are implemented by a Weight type with functions Plus(x, y) and Times(x, y) and static member functions Zero() and One(), respectively. These must form a semiring; see here for a further description of the constraints on these operations and other properties of weights. ⊕ is used to combine the weight of two identically labeled alternative paths, while ⊗ is used to combine weights along a path or when matching paths in composition or intersection. A state is final if and only its final weight is not equal to 0 . A transition with weight 1 is, in essence, "free". A path with weight 0 is not allowed (since such paths present technical problems with some algorithms).
  The following are some useful weight types:
Changed:
<
<
Name Set
(Plus)

(Times)
0
(Zero)
1
(One)
>
>
Name Set
(Plus)

(Times)
0
(Zero)
1
(One)
 
Boolean {0, 1} 0 1
Real [0, ∞] + * 0 1
Log [-∞, ∞] -log(e-x + e-y) + 0
Tropical [-∞, ∞] min + 0
Changed:
<
<
The boolean weight type is used for the familiar unweighted automata (but see tropical below). The real weight type is appropriate when the transition weights represent probabilities. The log weight type is appropriate when the transition weights represent negative log probabilities (more numerically stable than the isomorphic, under log(), real weight type). The tropical weight type is appropriate for shortest path operations and is identical to the log except it uses min for the Plus operation.

The OpenFst library predefines TropicalWeight doc and LogWeight doc as well as the corresponding StdArc and LogArc. These weight classes represent their weight in a single precision float that is a constructor argument. That float can be directly accessed with member function Value(). For unweighted automata, it is convenient and customary in this library to use TropicalWeight restricted to Zero and One. StdArc is the default arc type for the FST binaries. The Boolean and Real weight types not currently pre-defined. See here for all pre-defined weight types.

>
>
The boolean weight type is used for the familiar unweighted automata (but see tropical below). The real weight type is appropriate when the transition weights represent probabilities. The log weight type is appropriate when the transition weights represent negative log probabilities (more numerically stable than the isomorphic, under log(), real weight type). The tropical weight type is appropriate for shortest path operations and is identical to the log except it uses min for the Plus operation.

The OpenFst library predefines TropicalWeight doc and LogWeight doc as well as the corresponding StdArc and LogArc. These weight classes represent their weight in a single precision float that is a constructor argument. That float can be directly accessed with member function Value(). For unweighted automata, it is convenient and customary in this library to use TropicalWeight restricted to Zero and One. StdArc is the default arc type for the FST binaries. The Boolean and Real weight types not currently pre-defined. See here for all pre-defined weight types.

  From the shell-level, the FST arc type can be specified to fstcompile with the --arc_type flag; StdArc is the default.

Revision 772009-03-06 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 86 to 86
 2 3.5 EOF
Changed:
<
<
>
>
 The internal representation of an arc label is an integer. We must provide the mapping from symbols to integers explicitly with a symbol table file, also in AT&T format:
Line: 110 to 110
 non-negative integer for a label ID. The zero label ID is reserved for the epsilon label, which is the empty string. We have included 0 in our table, even though it is not used in our example. Since subsequent FST operations might add epsilons, it is good practice to include a symbol for it.

This text FST must be converted into a binary FST file before it can be used by the OpenFst library.

Changed:
<
<
>
>
 
# Creates binary Fst from text file. 
# The symbolic labels will be converted into integers using the symbol table files. 
$ fstcompile --isymbols=isyms.txt --osymbols=osyms.txt text.fst binary.fst

Line: 190 to 190
 

Printing, Drawing and Summarizing FSTs from the Shell

The following command will print out an FST in AT&T text format:

Changed:
<
<
>
>
 
# Print FST using symbol table files. 
$ fstprint --isymbols=isyms.txt --osymbols=osyms.txt binary.fst text.fst

Revision 762009-03-05 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 291 to 291
  ComposeFst(const Fst &fst1, const Fst &fst2);
Added:
>
>
 Delayed Fsts have constant time-class constructors. When components of delayed Fsts are accessed through the Fst interface, the automaton is built dynamically, just enough to respond to the accesses requested. It is important that the object access conventions are observed for correct operation.

Several operations, like Union, come in more than one of the above forms.

Revision 752009-03-04 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 392 to 392
 
  fstencode [--encode_labels] [--encode_weights] in.fst encoder out.fst  
EpsNormalize EpsNormalize(A, &B, type); creates equiv. FST with any input (output) epsilons at path ends
  fstepsnormalize [--eps_norm_output] in.fst out.fst  
Changed:
<
<
Equivalent Equivalent(A, B) determines if acceptors A and B accept the same strings with the same weights
>
>
EquivalentWork in progress, under construction Equivalent(A, B) determines if acceptors A and B accept the same strings with the same weights
 
  fstequivalent a.dfa b.dfa  
Intersect Intersect(A, B, &C); contains strings both in A and B
IntersectFst<Arc>(A, B);  
Line: 400 to 400
 
Invert Invert(&A); inverse binary relation; exchanges input and output labels
  InvertFst<Arc>(A);  
  fstinvert in.fst out.fst  
Changed:
<
<
Map Map(&A, mapper); transforms arcs in an FST
>
>
MapWork in progress, under construction Map(&A, mapper); transforms arcs in an FST
 
  Map(A, &B, mapper);  
  MapFst<InArc, OutArc, Mapper>(A, mapper);  
  fstmap [--delta=$d] [--map=$type] [--weight=$w] in.fst out.fst  
Changed:
<
<
Minimize Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
>
>
MinimizeWork in progress, under construction Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
 
  Minimize(&A, &B); transforms to equiv. deterministic FST with fewest states and arcs
  fstminimize in.fst out1.fst [out2.fst]  
Project Project(&A, type); creates acceptor of just the input or output strings
Line: 418 to 418
 
  fstequivalent --random [-npath=$n] a.fst b.fst  
RandGen RandGen(A, &B [, opts]); generates random path(s) through an FST
  fstrandgen [--max_length=$l] [--npath=$n] [--seed=$s] [--select=$sel] in.fst out.fst
Changed:
<
<
Relabel Relabel(&A, isyms, osyms); changes input and output label IDs
>
>
RelabelWork in progress, under construction Relabel(&A, isyms, osyms); changes input and output label IDs
 
  RelabelFst<Arc>(A, isyms, osyms);  
  fstrelabel [--relabel_isymbols=$isyms] [--relabel_osymbols=$osyms] in.fst out.fst  
Changed:
<
<
Replace Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN
>
>
ReplaceWork in progress, under construction Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN
 
ReplaceFst<Arc>(fst_label_pairs, root_label);  
  fstreplace root.fst rootlabel [rule1.fst rule1.label ...] out.fst  
Reverse Reverse(A, &B); contains the reversed strings in A

Revision 742009-03-04 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 126 to 126
 Once a binary FST is created, it can be used with the other shell-level programs. It can be loaded inside C++ with:
Changed:
<
<
Fst *fst = StdFst::Read("binary.fst");
>
>
StdFst *fst = StdFst::Read("binary.fst");
 

(See here for more information on FST I/O.)

Line: 138 to 138
 

Accessing FSTs from C++

Added:
>
>
 Here is the standard representation of an arc:

struct StdArc {

Line: 459 to 460
  The following are some useful weight types:
Changed:
<
<
Name Set
(Plus)

(Times)
0
(Zero)
1
(One)
>
>
Name Set
(Plus)

(Times)
0
(Zero)
1
(One)
 
Boolean {0, 1} 0 1
Real [0, ∞] + * 0 1
Log [-∞, ∞] -log(e-x + e-y) + 0

Revision 732009-03-03 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 25 to 25
 final weight is a final state. There is an arc (or transition) from state 0 to 1 with input label a, output label x, and weight 0.5. This FST transduces, for instance, the string ac to xz with weight 6.5 (the sum of the arc and final weights).
Changed:
<
<
Note we have assumed the library default Weight type for this description.
>
>
Note we have assumed the library default Weight type for this description.
 

Creating FSTs

Line: 450 to 450
  An arc weight in an FST gives the cost of taking that transition. The OpenFst library supports multiple types of weights -- in fact, any C++ class that meets various properties can be used as the Weight type specified in the Arc template parameter of an Fst.
Changed:
<
<
A few Weight types are predefined in the library that will normally meet your needs.
>
>
Several Weight types are predefined in the library that will normally meet your needs.
 Among a weight's properties, it must have associated binary operations ⊕ and ⊗ and elements 0 and 1. These are
Changed:
<
<
implemented by a Weight type with functions Plus(x, y) and Times(x, y) and static member functions Zero() and One(), respectively. These must form a semiring; see FST Weights for a further description of the constraints on these operations and other properties of weights. ⊕
>
>
implemented by a Weight type with functions Plus(x, y) and Times(x, y) and static member functions Zero() and One(), respectively. These must form a semiring; see here for a further description of the constraints on these operations and other properties of weights. ⊕
 is used to combine the weight of two identically labeled alternative paths, while ⊗ is used to combine weights along a path or when matching paths in composition or intersection. A state is final if and only its final weight is not equal to 0 . A transition with weight 1 is, in essence, "free". A path with weight 0 is not allowed (since such paths present technical problems with some algorithms).
Changed:
<
<
The following are useful weight types:
>
>
The following are some useful weight types:
 
Name Set
(Plus)

(Times)
0
(Zero)
1
(One)
Boolean {0, 1} 0 1
Line: 470 to 469
 appropriate when the transition weights represent probabilities. The log weight type is appropriate when the transition weights represent negative log probabilities (more numerically stable than the isomorphic, under log(), real weight type). The tropical weight type is appropriate for shortest path operations and is identical to the log except it uses min for the Plus operation.
Added:
>
>
 The OpenFst library predefines TropicalWeight doc and LogWeight doc as well as the corresponding StdArc and LogArc. These weight classes represent their weight in a single precision float that is a constructor argument. That float can be directly accessed with member function Value(). For unweighted automata, it is convenient and customary in this library to use TropicalWeight restricted to Zero and One.
Changed:
<
<
StdArc is the default arc type for the FST binaries.
>
>
StdArc is the default arc type for the FST binaries. The Boolean and Real weight types not currently pre-defined. See here for all pre-defined weight types.
  From the shell-level, the FST arc type can be specified to fstcompile with the --arc_type flag; StdArc is the default.

Revision 722009-03-03 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 6 to 6
 

Finding and Using the Library

Changed:
<
<
The OpenFst Library is a C++ template library. From C++ use #include <fst/fstlib.h>, relative to the installation include directory, and link to libfst.{a,so} in the installation library directory. You may instead use just those include files for the classes and functions that you will need. All classes and functions are in the fst namespace; the examples below assume you are within that namespace for brevity.
>
>
The OpenFst Library is a C++ template library. From C++, include <fst/fstlib.h> in the installation include directory and link to libfst.so in the installation library directory. (You may instead use just those include files for the classes and functions that you will need.) All classes and functions are in the fst namespace; the examples below assume you are within that namespace for brevity. (Include <fst/fst-decl.h> if forward declaration of the public OpenFst classes is needed.)
  As an alternative interface, there are shell-level commands in the installation bin directory that operate on file representations of FSTs.
Changed:
<
<
The command-line flag --help will give usage information.
>
>
The command-line flag --help will give usage information.
 
Deleted:
<
<
(See here for how to set global library and other options from the command line and otherwise.)
 

Example FST

Line: 112 to 111
  This text FST must be converted into a binary FST file before it can be used by the OpenFst library.
Changed:
<
<
# Creates binary Fst from text file. 
# The symbolic labels will be converted into integers using the symbol table files

>
>
# Creates binary Fst from text file. 
# The symbolic labels will be converted into integers using the symbol table files. 

 $ fstcompile --isymbols=isyms.txt --osymbols=osyms.txt text.fst binary.fst # As above but the symbol tables are stored with the FST.
Line: 443 to 442
 
Union Union(&A, B); contains strings in A or B
  UnionFst<Arc>(A, B);  
  fstunion a.fst b.fst out.fst  
Changed:
<
<
Verify Verify(A); Tests sanity of FST's contents
>
>
Verify Verify(A); tests sanity of FST's contents
 

Revision 712009-03-03 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 38 to 38
  The following code will create our example FST within C++:
Changed:
<
<
// A vector FST is a general mutable FST
>
>
// A vector FST is a general mutable FST 

 StdVectorFst fst;
Changed:
<
<
// Adds state 0 to the initially empty FST and make it the start state. fst.AddState(); // 1st state will be state 0 (returned by AddState) fst.SetStart(0); // arg is state ID
>
>
// Adds state 0 to the initially empty FST and make it the start state. fst.AddState(); // 1st state will be state 0 (returned by AddState) fst.SetStart(0); // arg is state ID
  // Adds two arcs exiting state 0.
Changed:
<
<
// Arc constructor args: ilabel, olabel, weight, dest state ID. fst.AddArc(0, StdArc(1, 1, 0.5, 1)); // 1st arg is src state ID
>
>
// Arc constructor args: ilabel, olabel, weight, dest state ID. fst.AddArc(0, StdArc(1, 1, 0.5, 1)); // 1st arg is src state ID
 fst.AddArc(0, StdArc(2, 2, 1.5, 1));
Changed:
<
<
// Adds state 1 and its arc.
>
>
// Adds state 1 and its arc.
 fst.AddState(); fst.AddArc(1, StdArc(3, 3, 2.5, 2));
Changed:
<
<
// Adds state 2 and set its final weight.
>
>
// Adds state 2 and set its final weight.
 fst.AddState();
Changed:
<
<
fst.SetFinal(2, 3.5); // 1st arg is state ID, 2nd arg weight
>
>
fst.SetFinal(2, 3.5); // 1st arg is state ID, 2nd arg weight
  We can save this FST to a file with:
Line: 77 to 76
  We can create the text FST file for our example as follows:
Changed:
<
<
# arc format: src dest ilabel olabel [weight]
>
>
# arc format: src dest ilabel olabel [weight]

 # final state format: state [weight] # lines may occur in any order except initial state must be first line
Changed:
<
<
# unspecified weights default to 0.0 (for the library-default Weight type)
>
>
# unspecified weights default to 0.0 (for the library-default Weight type)
 cat >text.fst <<EOF 0 1 a x .5 0 1 b y 1.5 1 2 c z 2.5 2 3.5 EOF
Changed:
<
<
>
>
  The internal representation of an arc label is an integer. We must provide the mapping from symbols to integers explicitly with a symbol table file, also in AT&T format:
Line: 114 to 112
  This text FST must be converted into a binary FST file before it can be used by the OpenFst library.
Changed:
<
<
# Creates binary Fst from text file.
>
>
# Creates binary Fst from text file. 

 # The symbolic labels will be converted into integers using the symbol table files $ fstcompile --isymbols=isyms.txt --osymbols=osyms.txt text.fst binary.fst
Changed:
<
<
# As above but the symbol tables are stored with the FST.
>
>
# As above but the symbol tables are stored with the FST.
 $ fstcompile --isymbols=isyms.txt --osymbols=osyms.txt --keep_isymbols --keep_osymbols text.fst binary.fst
Changed:
<
<
>
>
  If the labels are represented as non-negative integers in the text FST, then the symbol table files can be omitted. In any case, the internal representation of the FST is:
Line: 144 to 141
  Here is the standard representation of an arc:
Changed:
<
<
struct StdArc {
>
>
struct StdArc {

  typedef int Label;
Changed:
<
<
typedef TropicalWeight Weight; // see "FST Weights" below
>
>
typedef TropicalWeight Weight; // see "FST Weights" below
  typedef int StateId;

Label ilabel;

Line: 155 to 151
  Weight weight; StateId nextstate; };
Changed:
<
<
>
>
  Here are some example accesses of an FST:
Changed:
<
<
typedef StdArc::StateId StateId;

# Gets the initial state; if == kNoState => empty FST.
>
>
typedef StdArc::StateId StateId;

# Gets the initial state; if == kNoState => empty FST. 

 StateId initial_state = fst.Start();
Changed:
<
<
# Get state i's final weight; if == Weight::Zero() => non-final.
>
>
# Get state i's final weight; if == Weight::Zero() => non-final.
 Weight weight = fst.Final(i);
Changed:
<
<
>
>
 
Changed:
<
<
# Iterates over the FSTs states.
>
>
# Iterates over the FSTs states. 

 for (StateIterator siter(fst); siter.Done(); siter.Next()) StateId state_id = siter.Value();
Changed:
<
<
>
>
 
Changed:
<
<
# Iterates over state i's arcs.
>
>
# Iterates over state i's arcs. 

 for (ArcIterator aiter(fst, i); aiter.Done(); aiter.Next()) const StdArc &arc = aiter.Value();
Changed:
<
<
>
>
 
Changed:
<
<
# Iterates over state i's arcs that have input label l (FST must support this -
#  in the simplest cases,  true when the input labels are sorted). 
>
>
# Iterates over state i's arcs that have input label l (FST must support this -
#  in the simplest cases,  true when the input labels are sorted). 

 Matcher matcher(fst, MATCH_INPUT); matcher.SetState(i); if (matcher.Find(l)) for (; matcher.Done(); matcher.Next()) const StdArc &arc = matcher.Value();
Changed:
<
<
>
>
  More information on state iterators, arc iterators, and matchers are linked here.
Line: 202 to 191
  The following command will print out an FST in AT&T text format:
Changed:
<
<
# Print FST using symbol table files.
>
>
# Print FST using symbol table files. 

 $ fstprint --isymbols=isyms.txt --osymbols=osyms.txt binary.fst text.fst
Changed:
<
<
>
>
  If the symbol table files are omitted, the FST will be printed with numeric labels unless the symbol tables are stored with the FST (e.g.,
Line: 213 to 201
  The following command will draw an FST using Graphviz dot format.
Changed:
<
<
# Draw FST using symbol table files and Graphviz dot:
>
>
# Draw FST using symbol table files and Graphviz dot: 

 $ fstdraw --isymbols=isyms.txt --osymbols=osyms.txt binary.fst binary.dot $ dot -Tps binary.dot >binary.ps
Changed:
<
<
>
>
  Summary information about an FST can be obtained with:
Line: 329 to 316
 composition of two transductions. It can be used, for example, to apply a transduction to some input:

FST Application from C++

Deleted:
<
<
// Reads in an input FST.
StdFst *input = StdFst::Read("input.fst");
 
Changed:
<
<
// Reads in the transduction model.
>
>
// Reads in an input FST. 
StdFst *input = StdFst::Read("input.fst");

// Reads in the transduction model. 

 StdFst *model = StdFst::Read("model.fst");
Changed:
<
<
>
>
 // The FSTs must be sorted along the dimensions they will be joined. // In fact, only one needs to be so sorted.
Changed:
<
<
// This could have instead been done for "model.fst" when it was created.
>
>
// This could have instead been done for "model.fst" when it was created.
 ArcSort(input, StdOLabelCompare()); ArcSort(model, StdILabelCompare());
Changed:
<
<
// Container for composition result.
>
>
// Container for composition result.
 StdVectorFst result;
Changed:
<
<
// Create the composed FST
>
>
// Create the composed FST.
 Compose(*input, *model, &result);
Changed:
<
<
// Just keeps the output labels
>
>
// Just keeps the output labels.
 Project(&result, PROJECT_OUTPUT);
Changed:
<
<
>
>
 

FST Application from the Shell

Changed:
<
<
# The FSTs must be sorted along the dimensions they will be joined.
>
>
# The FSTs must be sorted along the dimensions they will be joined.

 # In fact, only one needs to be so sorted.
Changed:
<
<
# This could have instead been done for "model.fst" when it was created.
>
>
# This could have instead been done for "model.fst" when it was created.
 $ fstarcsort --sort_type=olabel input.fst input_sorted.fst $ fstarcsort --sort_type=ilabel model.fst model_sorted.fst
Changed:
<
<
# Creates the composed FST
>
>
# Creates the composed FST.
 $ fstcompose input_sorted.fst model_sorted.fst comp.fst
Changed:
<
<
# Just keeps the output label
>
>
# Just keeps the output label
 $ fstproject --project_output comp.fst result.fst
Changed:
<
<
# Do it all in a single command line
>
>
# Do it all in a single command line.
 $ fstarcsort --sort_type=ilabel model.fst | fstcompose input.fst - | fstproject --project_output result.fst
Changed:
<
<
>
>
 

Available FST Operations

Revision 702009-03-02 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 418 to 418
 
  Map(A, &B, mapper);  
  MapFst<InArc, OutArc, Mapper>(A, mapper);  
  fstmap [--delta=$d] [--map=$type] [--weight=$w] in.fst out.fst  
Changed:
<
<
Minimize Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
>
>
Minimize Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
 
  Minimize(&A, &B); transforms to equiv. deterministic FST with fewest states and arcs
  fstminimize in.fst out1.fst [out2.fst]  
Project Project(&A, type); creates acceptor of just the input or output strings

Revision 692009-03-02 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 435 to 435
 
Relabel Relabel(&A, isyms, osyms); changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  
  fstrelabel [--relabel_isymbols=$isyms] [--relabel_osymbols=$osyms] in.fst out.fst  
Changed:
<
<
Replace Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN
>
>
Replace Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN
 
ReplaceFst<Arc>(fst_label_pairs, root_label);  
  fstreplace root.fst rootlabel [rule1.fst rule1.label ...] out.fst  
Reverse Reverse(A, &B); contains the reversed strings in A

Revision 682009-03-01 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 171 to 171
 
Changed:
<
<
# Iterates over the FSTs states. .
>
>
# Iterates over the FSTs states.
 for (StateIterator siter(fst); siter.Done(); siter.Next()) StateId state_id = siter.Value();
Added:
>
>
 
Added:
>
>
 # Iterates over state i's arcs. for (ArcIterator aiter(fst, i); aiter.Done(); aiter.Next()) const StdArc &arc = aiter.Value();
Line: 191 to 194
  const StdArc &arc = matcher.Value();
Changed:
<
<
See here for more information on matchers.
>
>
More information on state iterators, arc iterators, and matchers are linked here.
  There are various conventions that must be observed when accessing FSTs.
Line: 271 to 272
 To invoke FST operations from C++, the FST class hierarchy must first be introduced:

The FST interface hierarchy consists of the following abstract class templates:

Changed:
<
<
  • Fst<Arc> : supports access operations described above
  • ExpandedFst<Arc> : an Fst that additionally supports NumStates()
  • MutableFst<Arc> : an ExpandedFst that supports the various mutating operations like AddStates() and SetStart().
>
>
  • Fst<Arc>: supports access operations described above
  • ExpandedFst<Arc>: an Fst that additionally supports NumStates()
  • MutableFst<Arc>: an ExpandedFst that supports the various mutating operations like AddStates() and SetStart().
  Specific, non-abstract FSTs include these class templates:
  • VectorFst<Arc>: a general-purpose mutable FST
Line: 484 to 485
 appropriate when the transition weights represent probabilities. The log weight type is appropriate when the transition weights represent negative log probabilities (more numerically stable than the isomorphic, under log(), real weight type). The tropical weight type is appropriate for shortest path operations and is identical to the log except it uses min for the Plus operation.
Changed:
<
<
The OpenFst library predefines TropicalWeight [bad link?] and LogWeight [bad link?] as well as the corresponding
>
>
The OpenFst library predefines TropicalWeight doc and LogWeight doc as well as the corresponding
 StdArc and LogArc. These weight classes represent their weight in a single precision float that is a constructor argument. That float can be directly accessed with member function Value(). For unweighted automata, it

Revision 672009-03-01 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 171 to 171
 
Changed:
<
<
# Iterates over the FSTs states. See here for other traversal methods.
>
>
# Iterates over the FSTs states. .
 for (StateIterator siter(fst); siter.Done(); siter.Next()) StateId state_id = siter.Value();
Line: 182 to 182
 
Changed:
<
<
# Iterates over state i's arcs that have input label l (FST must support this - in the simplest cases, # true when the input labels are sorted). See here for more info.
>
>
# Iterates over state i's arcs that have input label l (FST must support this - # in the simplest cases, true when the input labels are sorted).
 Matcher matcher(fst, MATCH_INPUT); matcher.SetState(i); if (matcher.Find(l))
Line: 191 to 191
  const StdArc &arc = matcher.Value();
Added:
>
>
See here for more information on matchers.
 There are various conventions that must be observed when accessing FSTs.

Printing, Drawing and Summarizing FSTs from the Shell

Revision 652009-02-27 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 11 to 11
 All classes and functions are in the fst namespace; the examples below assume you are within that namespace for brevity.

As an alternative interface, there are shell-level commands in the installation bin directory that operate on file representations of FSTs.

Added:
>
>
The command-line flag --help will give usage information.
 
Changed:
<
<
See here for how to set global library and other options from the command line and otherwise.
>
>
(See here for how to set global library and other options from the command line and otherwise.)
 

Example FST

Line: 132 to 133
 Fst *fst = StdFst::Read("binary.fst");
Changed:
<
<
See here for more information on FST I/O.
>
>
(See here for more information on FST I/O.)
 

Accessing FSTs

Line: 274 to 275
 
  • ConstFst<Arc>: a general-purpose expanded, immutable FST
  • ComposeFst<Arc>: an unexpanded, delayed composition of two FSTs
Changed:
<
<
(See FstAdvancedUsage#NewFstClasses[here]] for how to define your own FST classes if desired.)
>
>
(See here for how to define your own FST classes if desired.)
  These classes are templated on the arc to allow customization. The class StdFst is a typedef for Fst<StdArc>. Similar typedefs exist for all the above templates.
Line: 487 to 488
  From the shell-level, the FST arc type can be specified to fstcompile with the --arc_type flag; StdArc is the default.
Changed:
<
<
(See FstAdvancedUsage#NewArcs[here]] for how to your define your own FST arcs and weights if desired.)
>
>
(See here for how to your define your own FST arcs and weights if desired.)
 

-- MichaelRiley - 23 Feb 2009

Revision 642009-02-27 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 12 to 12
  As an alternative interface, there are shell-level commands in the installation bin directory that operate on file representations of FSTs.
Added:
>
>
See here for how to set global library and other options from the command line and otherwise.
 

Example FST

The following picture depicts a finite state transducer:

Line: 130 to 132
 Fst *fst = StdFst::Read("binary.fst");
Added:
>
>
See here for more information on FST I/O.
 

Accessing FSTs

Line: 163 to 167
 # Get state i's final weight; if == Weight::Zero() => non-final. Weight weight = fst.Final(i);
Changed:
<
<
# Iterates over the FSTs states.
>
>
# Iterates over the FSTs states. See here for other traversal methods.
 for (StateIterator siter(fst); siter.Done(); siter.Next()) StateId state_id = siter.Value();
Line: 174 to 178
 
Changed:
<
<
# Iterates over state i's arcs that have input label l (FST must support this - # in the simplest cases, true when the input labels are sorted).
>
>
# Iterates over state i's arcs that have input label l (FST must support this - in the simplest cases, # true when the input labels are sorted). See here for more info.
 Matcher matcher(fst, MATCH_INPUT); matcher.SetState(i); if (matcher.Find(l))
Line: 270 to 274
 
  • ConstFst<Arc>: a general-purpose expanded, immutable FST
  • ComposeFst<Arc>: an unexpanded, delayed composition of two FSTs
Added:
>
>
(See FstAdvancedUsage#NewFstClasses[here]] for how to define your own FST classes if desired.)
 These classes are templated on the arc to allow customization. The class StdFst is a typedef for Fst<StdArc>. Similar typedefs exist for all the above templates.

For the state and arc iterators, you will get the greatest efficiency if you specify the

Line: 366 to 372
 
Operation Usage Description
ArcSort ArcSort(&A, compare); sorts arcs using compare function object
  ArcSortFst<Arc, Compare>(A, compare);  
Changed:
<
<
  fstarcsort [--sort_type=$type] a.fst out.fst  
>
>
  fstarcsort [--sort_type=$type] in.fst out.fst  
 
Closure Closure(&A, type); A* = {ε} ∪ A ∪ AA ∪ ....
  ClosureFst<Arc>(A, type);  
Changed:
<
<
  fstclosure a.fst out.fst  
>
>
  fstclosure in.fst out.fst  
 
Compose Compose(A, B, &C); composition of binary relations A and B
  ComposeFst<Arc>(A, B);  
  fstcompose a.fst b.fst out.fst  
Concat Concat(&A, B); contains the strings in A followed by B
Added:
>
>
  Concat(A, &B);  
 
  ConcatFst<Arc>(A,B);  
  fstconcat a.fst b.fst out.fst  
Connect Connect(&A); removes states and arcs not on a path from the start to a final state
Changed:
<
<
  fstconnect a.fst out.fst  
>
>
  fstconnect in.fst out.fst  
Decode Decode(&A, encoder); decodes previously encoded Fst
  DecodeFst(A, encoder);  
  fstencode --decode in.fst encoder out.fst  
 
Determinize Determinize(A, &B); creates equiv. FST with no state with two arcs with the same input label
  DeterminizeFst<Arc>(A);  
Changed:
<
<
  fstdeterminize a.fst out.fst  
>
>
  fstdeterminize in.fst out.fst  
 
Difference Difference(A, B, &C); contains strings in A but not B; B unweighted
  DifferenceFst<Arc>(A, B);  
  fstdifference a.fsa b.dfa out.fsa  
Added:
>
>
Encode Encode(&A, encoder); combines input labels with output labels and/or weights into new input labels
  EncodeFst(A, encoder);  
  fstencode [--encode_labels] [--encode_weights] in.fst encoder out.fst  
 
EpsNormalize EpsNormalize(A, &B, type); creates equiv. FST with any input (output) epsilons at path ends
Changed:
<
<
  fstepsnormalize [--eps_norm_output]  
>
>
  fstepsnormalize [--eps_norm_output] in.fst out.fst  
 
Equivalent Equivalent(A, B) determines if acceptors A and B accept the same strings with the same weights
  fstequivalent a.dfa b.dfa  
Intersect Intersect(A, B, &C); contains strings both in A and B
Line: 393 to 406
 
  fstintersect a.fsa b.fsa out.fsa  
Invert Invert(&A); inverse binary relation; exchanges input and output labels
  InvertFst<Arc>(A);  
Changed:
<
<
  fstinvert a.fst out.fst  
>
>
  fstinvert in.fst out.fst  
 
Map Map(&A, mapper); transforms arcs in an FST
  Map(A, &B, mapper);  
  MapFst<InArc, OutArc, Mapper>(A, mapper);  
  fstmap [--delta=$d] [--map=$type] [--weight=$w] in.fst out.fst  
Minimize Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
  Minimize(&A, &B); transforms to equiv. deterministic FST with fewest states and arcs
Changed:
<
<
  fstminimize a.fst out1.fst [out2.fst]  
>
>
  fstminimize in.fst out1.fst [out2.fst]  
 
Project Project(&A, type); creates acceptor of just the input or output strings
  ProjectFst<Arc>(A, type);  
Changed:
<
<
  fstproject [--project_output] a.fst out.fst  
Prune Prune(&A, threshold); remove paths outside a threshold of best path
  fstprune [--weight=$w] a.fst out.fst  
Push Push<Arc, Type>(&A, flags); create equiv. FST pushing weights and/or output labels toward initial or final states
  fstpush [--push_labels] [--push_weights] [--to_final] a.fst out.fst  
>
>
  fstproject [--project_output] in.fst out.fsa  
Prune Prune(&A, threshold); removes paths outside a threshold of best path
  fstprune [--weight=$w] in.fst out.fst  
Push Push<Arc, Type>(&A, flags); creates equiv. FST pushing weights and/or output labels toward initial or final states
  fstpush [--push_labels] [--push_weights] [--to_final] in.fst out.fst  
RandEquivalent RandEquivalent(A, B, npath); checks if transducers A and B transduce the same randomly-generated string pairs with the same weights
  fstequivalent --random [-npath=$n] a.fst b.fst  
RandGen RandGen(A, &B [, opts]); generates random path(s) through an FST
  fstrandgen [--max_length=$l] [--npath=$n] [--seed=$s] [--select=$sel] in.fst out.fst
 
Relabel Relabel(&A, isyms, osyms); changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  
  fstrelabel [--relabel_isymbols=$isyms] [--relabel_osymbols=$osyms] in.fst out.fst  
Line: 420 to 437
 
  fstreweight [--to_final] in.fst potentials.txt out.fst  
RmEpsilon RmEpsilon(&A); creates equiv. FST with no input/output epsilons
  RmEpsilonFst<Arc>(A);  
Changed:
<
<
  fstrmepsilon a.fst out.fst  
>
>
  fstrmepsilon in.fst out.fst  
 
ShortestDistance ShortestDistance(A, &distance); shortest distance from initial state to each state
  ShortestDistance(A, &distance, true); shortest distance from each state to final states
  fstshortestdistance [--reverse] in.fst [distance.txt]  
ShortestPath ShortestPath(A, &B, nshortest=1); N-best paths
Changed:
<
<
  fstshortestpath [--nshortest=$n] a.fst out.fst  
>
>
  fstshortestpath [--nshortest=$n] in.fst out.fst  
 
Synchronize SynchronizeFst<Arc>(A); synchronizes an FST
Changed:
<
<
  fstsynchronize a.fst out.fst  
>
>
  fstsynchronize in.fst out.fst  
 
TopSort TopSort(&A); sorts an acyclic FST so that all transitions are from lower to higher state IDs
Changed:
<
<
  fsttopsort a.fst out.fst  
>
>
  fsttopsort in.fst out.fst  
 
Union Union(&A, B); contains strings in A or B
  UnionFst<Arc>(A, B);  
  fstunion a.fst b.fst out.fst  
Added:
>
>
Verify Verify(A); Tests sanity of FST's contents
 

Line: 469 to 487
  From the shell-level, the FST arc type can be specified to fstcompile with the --arc_type flag; StdArc is the default.
Added:
>
>
(See FstAdvancedUsage#NewArcs[here]] for how to your define your own FST arcs and weights if desired.)
 -- MichaelRiley - 23 Feb 2009

META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462223" name="numericfst.jpg" path="numericfst.jpg" size="4881" user="Main.CyrilAllauzen" version="1"

Revision 632009-02-26 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 6 to 6
 

Finding and Using the Library

Changed:
<
<
The OpenFst Library is a C++ template library. From C++ use #include "fst/lib/fstlib.h" (the path must be relative to the OpenFst root directory) and link to fst/lib/libfst.{a,so}. You may instead use just those include files for
>
>
The OpenFst Library is a C++ template library. From C++ use #include <fst/fstlib.h>, relative to the installation include directory, and link to libfst.{a,so} in the installation library directory. You may instead use just those include files for
 the classes and functions that you will need. All classes and functions are in the fst namespace; the examples below assume you are within that namespace for brevity.
Changed:
<
<
As an alternative interface, there are shell-level commands in bin that operate on file representations of FSTs.
>
>
As an alternative interface, there are shell-level commands in the installation bin directory that operate on file representations of FSTs.
 

Example FST

Line: 158 to 157
 
typedef StdArc::StateId StateId;
Changed:
<
<
# Gets the initial state; if kNoState => empty FST.
>
>
# Gets the initial state; if == kNoState => empty FST.
 StateId initial_state = fst.Start();
Added:
>
>
# Get state i's final weight; if == Weight::Zero() => non-final. Weight weight = fst.Final(i);
 # Iterates over the FSTs states. for (StateIterator siter(fst); siter.Done(); siter.Next()) StateId state_id = siter.Value();
Line: 170 to 172
  const StdArc &arc = aiter.Value();
Added:
>
>
# Iterates over state i's arcs that have input label l (FST must support this -
# in the simplest cases, true when the input labels are sorted).
Matcher<StdFst> matcher(fst, MATCH_INPUT);
matcher.SetState(i);
if (matcher.Find(l)) 
  for (; !matcher.Done(); matcher.Next())
     const StdArc &arc = matcher.Value();
 There are various conventions that must be observed when accessing FSTs.

Printing, Drawing and Summarizing FSTs from the Shell

Line: 228 to 241
 top sorted y accessible y coaccessible y
Added:
>
>
string n
 
Line: 400 to 414
 
Replace Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN
ReplaceFst<Arc>(fst_label_pairs, root_label);  
  fstreplace root.fst rootlabel [rule1.fst rule1.label ...] out.fst  
Deleted:
<
<
Reweight Reweight(&A, potentials, type); creates equiv. FST changing arc weights based on potentials
  fstreweight [--to_final] in.fst potentials.txt out.fst  
 
Reverse Reverse(A, &B); contains the reversed strings in A
  fstreverse a.fst out.fst  
Added:
>
>
Reweight Reweight(&A, potentials, type); creates equiv. FST changing arc weights based on potentials
  fstreweight [--to_final] in.fst potentials.txt out.fst  
 
RmEpsilon RmEpsilon(&A); creates equiv. FST with no input/output epsilons
  RmEpsilonFst<Arc>(A);  
  fstrmepsilon a.fst out.fst  
Line: 455 to 469
  From the shell-level, the FST arc type can be specified to fstcompile with the --arc_type flag; StdArc is the default.
Changed:
<
<
-- MichaelRiley - 25 May 2007
>
>
-- MichaelRiley - 23 Feb 2009
 
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462223" name="numericfst.jpg" path="numericfst.jpg" size="4881" user="Main.CyrilAllauzen" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462223" name="symbolicfst.jpg" path="symbolicfst.jpg" size="4768" user="Main.CyrilAllauzen" version="1"

Revision 612008-04-10 - CyrilAllauzen

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

OpenFst Quick Tour

Line: 429 to 429
 0 and 1. These are implemented by a Weight type with functions Plus(x, y) and Times(x, y) and static member functions Zero() and One(), respectively. These must form a semiring; see FST Weights for a further description of the constraints on these operations and other properties of weights. ⊕ is used to combine the weight of two identically labeled alternative paths, while ⊗ is used to combine weights along a path or when matching
Changed:
<
<
paths in composition or intersection. A state is final if and only its final weight is not equal to 0 . A transition with weight 1 is, in essence, "free". A transition with weight 0 is not allowed (since weight 0 paths present technical problems with some algorithms).
>
>
paths in composition or intersection. A state is final if and only its final weight is not equal to 0 . A transition with weight 1 is, in essence, "free". A path with weight 0 is not allowed (since such paths present technical problems with some algorithms).
  The following are useful weight types:

Revision 602008-03-14 - MichaelRiley

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

OpenFst Quick Tour

Line: 380 to 380
 
  fstinvert a.fst out.fst  
Map Map(&A, mapper); transforms arcs in an FST
  Map(A, &B, mapper);  
Changed:
<
<
  MapFst<Arc, Mapper>(A, mapper);  
>
>
  MapFst<InArc, OutArc, Mapper>(A, mapper);  
 
  fstmap [--delta=$d] [--map=$type] [--weight=$w] in.fst out.fst  
Minimize Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
  Minimize(&A, &B); transforms to equiv. deterministic FST with fewest states and arcs

Revision 592007-07-16 - MichaelRiley

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

OpenFst Quick Tour

Line: 170 to 170
  There are various conventions that must be observed when accessing FSTs.
Changed:
<
<

Printing and Summarizing FSTs from the Shell

>
>

Printing, Drawing and Summarizing FSTs from the Shell

  The following command will print out an FST in AT&T text format:
Line: 183 to 183
 numeric labels unless the symbol tables are stored with the FST (e.g., with fstcompile --keep_isymbols --keep_osymbols).
Added:
>
>
The following command will draw an FST using Graphviz dot format.

# Draw FST using symbol table files and Graphviz dot:
$ fstdraw --isymbols=isyms.txt --osymbols=osyms.txt binary.fst binary.dot
$ dot -Tps binary.dot >binary.ps
 Summary information about an FST can be obtained with:

Revision 582007-07-15 - MichaelRiley

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

OpenFst Quick Tour

Line: 331 to 331
 $ fstproject --project_output comp.fst result.fst

# Do it all in a single command line

Changed:
<
<
$ fstarcsort --sort_type=ilabel model.fst | fstcompose input.fst - | fstproject --project_output >result.fst
>
>
$ fstarcsort --sort_type=ilabel model.fst | fstcompose input.fst - | fstproject --project_output result.fst
 

Revision 572007-07-12 - MichaelRiley

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

OpenFst Quick Tour

Line: 419 to 419
 A few Weight types are predefined in the library that will normally meet your needs. Among a weight's properties, it must have associated binary operations ⊕ and ⊗ and elements 0 and 1. These are
Changed:
<
<
implemented by a Weight type with functions Plus(x, y) and Times(x, y) and static member functions Zero() and One(), respectively. See FST Weights for constraints on these operations and other properties of weights. ⊕
>
>
implemented by a Weight type with functions Plus(x, y) and Times(x, y) and static member functions Zero() and One(), respectively. These must form a semiring; see FST Weights for a further description of the constraints on these operations and other properties of weights. ⊕
 is used to combine the weight of two identically labeled alternative paths, while ⊗ is used to combine weights along a path or when matching paths in composition or intersection. A state is final if and only its final weight is not equal to 0 . A transition with weight 1 is, in essence, "free". A transition with weight 0 is not allowed (since weight 0 paths present technical problems with some algorithms).

Revision 562007-07-12 - MichaelRiley

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

OpenFst Quick Tour

Finding and Using the Library

Changed:
<
<
The OpenFst Library is a C++ template library. To use it from C++ use #include "fst/lib/fstlib.h" (the path must be relative to the OpenFst root directory)
>
>
The OpenFst Library is a C++ template library. From C++ use #include "fst/lib/fstlib.h" (the path must be relative to the OpenFst root directory)
 and link to fst/lib/libfst.{a,so}. You may instead use just those include files for
Changed:
<
<
the classes and functions that you will need (again, the paths must be relative to the OpenFSt root directory).
>
>
the classes and functions that you will need.
 All classes and functions are in the fst namespace; the examples below assume you are within that namespace for brevity.

As an alternative interface, there are shell-level commands in bin that operate on file representations of FSTs.

Revision 552007-07-12 - MichaelRiley

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

OpenFst Quick Tour

Finding and Using the Library

Changed:
<
<
The OpenFst Library is a C++ template library. To use it from C++, include lib/fstlib.h and link to lib/libfst.{a,so}. You may instead use just those include files for the classes and functions that you will need. All classes and functions are in the fst namespace; the examples below assume you are within that namespace for brevity.
>
>
The OpenFst Library is a C++ template library. To use it from C++ use #include "fst/lib/fstlib.h" (the path must be relative to the OpenFst root directory) and link to fst/lib/libfst.{a,so}. You may instead use just those include files for the classes and functions that you will need (again, the paths must be relative to the OpenFSt root directory). All classes and functions are in the fst namespace; the examples below assume you are within that namespace for brevity.
  As an alternative interface, there are shell-level commands in bin that operate on file representations of FSTs.

Revision 542007-07-11 - MichaelRiley

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

OpenFst Quick Tour

Finding and Using the Library

Changed:
<
<
The OpenFst Library is a C++ template library. To use it from C++, include lib/fstlib-inl.h
>
>
The OpenFst Library is a C++ template library. To use it from C++, include lib/fstlib.h
 and link to lib/libfst.{a,so}. You may instead use just those include files for the classes and functions that you will need. All classes and functions are in the fst namespace; the examples below assume you are within that namespace for brevity.

Revision 532007-07-11 - MichaelRiley

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

OpenFst Quick Tour

Line: 415 to 415
  An arc weight in an FST gives the cost of taking that transition. The OpenFst library supports multiple types of weights -- in fact, any C++ class that meets various properties can be used as the Weight type specified in the Arc template parameter of an Fst.
Changed:
<
<
A few weight types are predefined in the library that will normally meet your needs. Among a weight's properties, it must have associated binary functions Plus(x, y) and Times(x, y) and static member functions Zero() and One(). See FST Weights for constraints on these operations and other properties of weights. Plus is used to combine the weight of two identically labeled alternative paths, while Times is used to combine weights along a path or when matching paths in composition or intersection. A state is final if and only its final weight is not equal to Zero. A transition with weight One is, in essense, "free". A transition with weight Zero is not allowed (since Zero weight paths present technical problems with some algorithms).
>
>
A few Weight types are predefined in the library that will normally meet your needs. Among a weight's properties, it must have associated binary operations ⊕ and ⊗ and elements 0 and 1. These are implemented by a Weight type with functions Plus(x, y) and Times(x, y) and static member functions Zero() and One(), respectively. See FST Weights for constraints on these operations and other properties of weights. ⊕ is used to combine the weight of two identically labeled alternative paths, while ⊗ is used to combine weights along a path or when matching paths in composition or intersection. A state is final if and only its final weight is not equal to 0 . A transition with weight 1 is, in essence, "free". A transition with weight 0 is not allowed (since weight 0 paths present technical problems with some algorithms).
  The following are useful weight types:
Changed:
<
<
Name Set Plus
(⊕)
Times
(⊗)
Zero
(0)
One
(1)
>
>
Name Set
(Plus)

(Times)
0
(Zero)
1
(One)
 
Boolean {0, 1} 0 1
Real [0, ∞] + * 0 1
Log [-∞, ∞] -log(e-x + e-y) + 0

Revision 522007-07-11 - MichaelRiley

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

OpenFst Quick Tour

Line: 112 to 112
 
# Creates binary Fst from text file.
# The symbolic labels will be converted into integers using the symbol table files
Changed:
<
<
$ fstcompile -isymbols=isyms.txt -osymbols=osyms.txt text.fst binary.fst
>
>
$ fstcompile --isymbols=isyms.txt --osymbols=osyms.txt text.fst binary.fst
  # As above but the symbol tables are stored with the FST.
Changed:
<
<
$ fstcompile -isymbols=isyms.txt -osymbols=osyms.txt -keep_isymbols -keep_osymbols text.fst binary.fst
>
>
$ fstcompile --isymbols=isyms.txt --osymbols=osyms.txt --keep_isymbols --keep_osymbols text.fst binary.fst
 

If the labels are represented as non-negative integers in the text FST, then the symbol table files can be omitted. In any case, the internal representation of the FST is:

Line: 175 to 175
 
# Print FST using symbol table files.
Changed:
<
<
$ fstprint -isymbols=isyms.txt -osymbols=osyms.txt binary.fst text.fst
>
>
$ fstprint --isymbols=isyms.txt --osymbols=osyms.txt binary.fst text.fst
 

If the symbol table files are omitted, the FST will be printed with numeric labels unless the symbol tables are stored with the FST (e.g.,

Changed:
<
<
with fstcompile -keep_isymbols -keep_osymbols).
>
>
with fstcompile --keep_isymbols --keep_osymbols).
  Summary information about an FST can be obtained with:
Line: 272 to 272
 

Calling FST Operations from the Shell

The shell-level FST operations typically read one or more input binary FST files, call internally the corresponding C++ operation
Changed:
<
<
and then write an output binary FST file. Specifically, they have the form:
>
>
and then write an output binary FST file. If the output file is omitted, standard output is used. If the input file is also omitted (unary case) or is "-", then standard input is used. Specifically, they have the form:
 
  • Unary Operations:
fstunaryop in.fst out.fst
Added:
>
>
fstunaryop <in.fst >out.fst
 
  • Binary Operations:
fstbinaryop in1.fst in2.fst out.fst
Added:
>
>
fstbinaryop - in2.fst <in1.fst >out.fst
 

Line: 318 to 320
 # The FSTs must be sorted along the dimensions they will be joined. # In fact, only one needs to be so sorted. # This could have instead been done for "model.fst" when it was created.
Changed:
<
<
$ arcsort --sort_type=olabel input.fst input_sorted.fst $ arcsort --sort_type=ilabel model.fst model_sorted.fst
>
>
$ fstarcsort --sort_type=olabel input.fst input_sorted.fst $ fstarcsort --sort_type=ilabel model.fst model_sorted.fst
  # Creates the composed FST $ fstcompose input_sorted.fst model_sorted.fst comp.fst

# Just keeps the output label

Changed:
<
<
$ fstproject -project_output comp.fst result.fst
>
>
$ fstproject --project_output comp.fst result.fst

# Do it all in a single command line $ fstarcsort --sort_type=ilabel model.fst | fstcompose input.fst - | fstproject --project_output >result.fst

 

Revision 512007-07-05 - CyrilAllauzen

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

OpenFst Quick Tour

Line: 374 to 374
 
Project Project(&A, type); creates acceptor of just the input or output strings
  ProjectFst<Arc>(A, type);  
  fstproject [--project_output] a.fst out.fst  
Changed:
<
<
Prune Prune(&A, threshold); remove paths outside a threshold of best path
>
>
Prune Prune(&A, threshold); remove paths outside a threshold of best path
 
  fstprune [--weight=$w] a.fst out.fst  
Changed:
<
<
[PushDoc][Push]] Push<Arc, Type>(&A, flags); create equiv. FST pushing weights and/or output labels toward initial or final states
>
>
Push Push<Arc, Type>(&A, flags); create equiv. FST pushing weights and/or output labels toward initial or final states
 
  fstpush [--push_labels] [--push_weights] [--to_final] a.fst out.fst  
Relabel Relabel(&A, isyms, osyms); changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  
Line: 391 to 391
 
RmEpsilon RmEpsilon(&A); creates equiv. FST with no input/output epsilons
  RmEpsilonFst<Arc>(A);  
  fstrmepsilon a.fst out.fst  
Changed:
<
<
ShortestDistance ShortestDistance(A, &distance); shortest distance from initial state to each state
>
>
ShortestDistance ShortestDistance(A, &distance); shortest distance from initial state to each state
 
  ShortestDistance(A, &distance, true); shortest distance from each state to final states
  fstshortestdistance [--reverse] in.fst [distance.txt]  
Changed:
<
<
ShortestPath ShortestPath(A, &B, nshortest=1); N-best paths
>
>
ShortestPath ShortestPath(A, &B, nshortest=1); N-best paths
 
  fstshortestpath [--nshortest=$n] a.fst out.fst  
Synchronize SynchronizeFst<Arc>(A); synchronizes an FST
  fstsynchronize a.fst out.fst  

Revision 502007-07-04 - CyrilAllauzen

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

OpenFst Quick Tour

Line: 376 to 376
 
  fstproject [--project_output] a.fst out.fst  
Prune Prune(&A, threshold); remove paths outside a threshold of best path
  fstprune [--weight=$w] a.fst out.fst  
Changed:
<
<
Push Push<Arc, Type>(&A, flags); create equiv. FST pushing weights and/or output labels toward initial or final states
>
>
[PushDoc][Push]] Push<Arc, Type>(&A, flags); create equiv. FST pushing weights and/or output labels toward initial or final states
 
  fstpush [--push_labels] [--push_weights] [--to_final] a.fst out.fst  
Relabel Relabel(&A, isyms, osyms); changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  

Revision 492007-07-04 - CyrilAllauzen

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

OpenFst Quick Tour

Line: 376 to 376
 
  fstproject [--project_output] a.fst out.fst  
Prune Prune(&A, threshold); remove paths outside a threshold of best path
  fstprune [--weight=$w] a.fst out.fst  
Changed:
<
<
Push Push<Arc, Type>(&A, flags); create equiv. FST pushing weights and/or output labels toward initial \or final states
>
>
Push Push<Arc, Type>(&A, flags); create equiv. FST pushing weights and/or output labels toward initial or final states
 
  fstpush [--push_labels] [--push_weights] [--to_final] a.fst out.fst  
Relabel Relabel(&A, isyms, osyms); changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  
Line: 384 to 384
 
Replace Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN
ReplaceFst<Arc>(fst_label_pairs, root_label);  
  fstreplace root.fst rootlabel [rule1.fst rule1.label ...] out.fst  
Changed:
<
<
Reweight Reweight(&A, potentials, type); creates equiv. FST changing arc weights based on potentials
>
>
Reweight Reweight(&A, potentials, type); creates equiv. FST changing arc weights based on potentials
 
  fstreweight [--to_final] in.fst potentials.txt out.fst  
Reverse Reverse(A, &B); contains the reversed strings in A
  fstreverse a.fst out.fst  

Revision 482007-07-04 - MichaelRiley

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

OpenFst Quick Tour

Line: 396 to 396
 
  fstshortestdistance [--reverse] in.fst [distance.txt]  
ShortestPath ShortestPath(A, &B, nshortest=1); N-best paths
  fstshortestpath [--nshortest=$n] a.fst out.fst  
Changed:
<
<
Synchronize SynchronizeFst<Arc>(A); synchronizes an Fst
>
>
Synchronize SynchronizeFst<Arc>(A); synchronizes an FST
 
  fstsynchronize a.fst out.fst  
TopSort TopSort(&A); sorts an acyclic FST so that all transitions are from lower to higher state IDs
  fsttopsort a.fst out.fst  

Revision 472007-07-03 - MichaelRiley

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

OpenFst Quick Tour

Line: 386 to 386
 
  fstreplace root.fst rootlabel [rule1.fst rule1.label ...] out.fst  
Reweight Reweight(&A, potentials, type); creates equiv. FST changing arc weights based on potentials
  fstreweight [--to_final] in.fst potentials.txt out.fst  
Changed:
<
<
Reverse Reverse(A, &B); contains the reversed strings in A
>
>
Reverse Reverse(A, &B); contains the reversed strings in A
 
  fstreverse a.fst out.fst  
RmEpsilon RmEpsilon(&A); creates equiv. FST with no input/output epsilons
  RmEpsilonFst<Arc>(A);  
Line: 398 to 398
 
  fstshortestpath [--nshortest=$n] a.fst out.fst  
Synchronize SynchronizeFst<Arc>(A); synchronizes an Fst
  fstsynchronize a.fst out.fst  
Changed:
<
<
TopSort TopSort(&A); sorts an acyclic FST so that all transitions are from lower to higher state IDs
>
>
TopSort TopSort(&A); sorts an acyclic FST so that all transitions are from lower to higher state IDs
 
  fsttopsort a.fst out.fst  
Union Union(&A, B); contains strings in A or B
  UnionFst<Arc>(A, B);  

Revision 462007-07-02 - MichaelRiley

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

OpenFst Quick Tour

Line: 361 to 361
 
Intersect Intersect(A, B, &C); contains strings both in A and B
IntersectFst<Arc>(A, B);  
  fstintersect a.fsa b.fsa out.fsa  
Changed:
<
<
Invert Invert(&A); inverse binary relation; exchanges input and output labels
>
>
Invert Invert(&A); inverse binary relation; exchanges input and output labels
 
  InvertFst<Arc>(A);  
  fstinvert a.fst out.fst  
Map Map(&A, mapper); transforms arcs in an FST
Line: 371 to 371
 
Minimize Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
  Minimize(&A, &B); transforms to equiv. deterministic FST with fewest states and arcs
  fstminimize a.fst out1.fst [out2.fst]  
Changed:
<
<
Project Project(&A, type); creates acceptor of just the input or output strings
>
>
Project Project(&A, type); creates acceptor of just the input or output strings
 
  ProjectFst<Arc>(A, type);  
  fstproject [--project_output] a.fst out.fst  
Prune Prune(&A, threshold); remove paths outside a threshold of best path

Revision 452007-07-01 - MichaelRiley

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

OpenFst Quick Tour

Line: 400 to 400
 
  fstsynchronize a.fst out.fst  
TopSort TopSort(&A); sorts an acyclic FST so that all transitions are from lower to higher state IDs
  fsttopsort a.fst out.fst  
Changed:
<
<
Union Union(&A, B); contains strings in A or B
>
>
Union Union(&A, B); contains strings in A or B
 
  UnionFst<Arc>(A, B);  
  fstunion a.fst b.fst out.fst  

Revision 442007-06-30 - MichaelRiley

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

OpenFst Quick Tour

Line: 14 to 14
  The following picture depicts a finite state transducer:
Deleted:
<
<
 symbolicfst.jpg
Deleted:
<
<
  The initial state is label 0. There can only be one initial state. The final state is 2 with final weight of 3.5. Any state with non-infinite
Line: 122 to 120
  If the labels are represented as non-negative integers in the text FST, then the symbol table files can be omitted. In any case, the internal representation of the FST is:
Deleted:
<
<
 numericfst.jpg
Deleted:
<
<
  Once a binary FST is created, it can be used with the other shell-level programs. It can be loaded inside C++ with:
Line: 341 to 337
 
ArcSort ArcSort(&A, compare); sorts arcs using compare function object
  ArcSortFst<Arc, Compare>(A, compare);  
  fstarcsort [--sort_type=$type] a.fst out.fst  
Changed:
<
<
Closure Closure(&A, type); A* = <eps> U A U AA U AAA ...
>
>
Closure Closure(&A, type); A* = {ε} ∪ A ∪ AA ∪ ....
 
  ClosureFst<Arc>(A, type);  
  fstclosure a.fst out.fst  
Compose Compose(A, B, &C); composition of binary relations A and B
Line: 424 to 420
  The following are useful weight types:
Changed:
<
<
Name Set Plus Times Zero One
Boolean { 0, 1 } or and 0 1
Real [0, inf] + * 0 1
Log [-inf, inf] -log(e^-x + e^-y) + inf 0
Tropical [-inf, inf] min + inf 0
>
>
Name Set Plus
(⊕)
Times
(⊗)
Zero
(0)
One
(1)
Boolean {0, 1} 0 1
Real [0, ∞] + * 0 1
Log [-∞, ∞] -log(e-x + e-y) + 0
Tropical [-∞, ∞] min + 0
  The boolean weight type is used for the familiar unweighted automata (but see tropical below). The real weight type is appropriate when the transition weights represent probabilities. The log weight type is appropriate when the transition weights represent negative log probabilities (more numerically stable than the isomorphic, under log(), real weight type). The tropical weight type

Revision 432007-06-30 - MichaelRiley

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

OpenFst Quick Tour

Line: 355 to 355
 
Determinize Determinize(A, &B); creates equiv. FST with no state with two arcs with the same input label
  DeterminizeFst<Arc>(A);  
  fstdeterminize a.fst out.fst  
Changed:
<
<
Difference Difference(A, B, &C); contains strings in A but not B; B unweighted
>
>
Difference Difference(A, B, &C); contains strings in A but not B; B unweighted
 
  DifferenceFst<Arc>(A, B);  
  fstdifference a.fsa b.dfa out.fsa  
Changed:
<
<
EpsilonNormalize EpsilonNormalize(A, &B, type); epsilon normalizes A
>
>
EpsNormalize EpsNormalize(A, &B, type); creates equiv. FST with any input (output) epsilons at path ends
 
  fstepsnormalize [--eps_norm_output]  
Equivalent Equivalent(A, B) determines if acceptors A and B accept the same strings with the same weights
  fstequivalent a.dfa b.dfa  
Changed:
<
<
Intersect Intersect(A, B, &C); contains strings both in A and B
>
>
Intersect Intersect(A, B, &C); contains strings both in A and B
 
IntersectFst<Arc>(A, B);  
  fstintersect a.fsa b.fsa out.fsa  
Invert Invert(&A); inverse binary relation; exchanges input and output labels
Line: 384 to 384
 
  fstpush [--push_labels] [--push_weights] [--to_final] a.fst out.fst  
Relabel Relabel(&A, isyms, osyms); changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  
Changed:
<
<
  fstrelabel [-relabel_isymbols=$isyms] [-relabel_osymbols=$osyms] in.fst out.fst  
>
>
  fstrelabel [--relabel_isymbols=$isyms] [--relabel_osymbols=$osyms] in.fst out.fst  
 
Replace Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN
ReplaceFst<Arc>(fst_label_pairs, root_label);  
  fstreplace root.fst rootlabel [rule1.fst rule1.label ...] out.fst  
Line: 441 to 441
 is convenient and customary in this library to use TropicalWeight restricted to Zero and One. StdArc is the default arc type for the FST binaries.
Changed:
<
<
From the shell-level, the FST arc type can be specified to fstcompile with the -arc_type flag; StdArc is the default.
>
>
From the shell-level, the FST arc type can be specified to fstcompile with the --arc_type flag; StdArc is the default.
  -- MichaelRiley - 25 May 2007

Revision 422007-06-30 - MichaelRiley

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

OpenFst Quick Tour

Line: 78 to 78
 # arc format: src dest ilabel olabel [weight] # final state format: state [weight] # lines may occur in any order except initial state must be first line
Added:
>
>
# unspecified weights default to 0.0 (for the library-default Weight type)
 cat >text.fst <<EOF 0 1 a x .5 0 1 b y 1.5

Revision 412007-06-25 - CyrilAllauzen

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

OpenFst Quick Tour

Line: 391 to 391
 
  fstreweight [--to_final] in.fst potentials.txt out.fst  
Reverse Reverse(A, &B); contains the reversed strings in A
  fstreverse a.fst out.fst  
Changed:
<
<
RmEpsilon RmEpsilon(&A); creates equiv. FST with no input/output epsilons
>
>
RmEpsilon RmEpsilon(&A); creates equiv. FST with no input/output epsilons
 
  RmEpsilonFst<Arc>(A);  
  fstrmepsilon a.fst out.fst  
ShortestDistance ShortestDistance(A, &distance); shortest distance from initial state to each state

Revision 402007-06-23 - CyrilAllauzen

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

OpenFst Quick Tour

Line: 399 to 399
 
  fstshortestdistance [--reverse] in.fst [distance.txt]  
ShortestPath ShortestPath(A, &B, nshortest=1); N-best paths
  fstshortestpath [--nshortest=$n] a.fst out.fst  
Changed:
<
<
Synchronize SynchronizeFst<Arc>(A); synchronizes an Fst
>
>
Synchronize SynchronizeFst<Arc>(A); synchronizes an Fst
 
  fstsynchronize a.fst out.fst  
TopSort TopSort(&A); sorts an acyclic FST so that all transitions are from lower to higher state IDs
  fsttopsort a.fst out.fst  

Revision 392007-06-23 - MichaelRiley

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

OpenFst Quick Tour

Line: 291 to 291
 One of the most useful finite-state operations is composition, which produces the relational composition of two transductions. It can be used, for example, to apply a transduction to some input:
Changed:
<
<

Fst Application from C++

>
>

FST Application from C++

 
// Reads in an input FST.
StdFst *input = StdFst::Read("input.fst");
Line: 315 to 315
 Project(&result, PROJECT_OUTPUT);
Changed:
<
<

Fst Application from the Shell

>
>

FST Application from the Shell

 
# The FSTs must be sorted along the dimensions they will be joined.
Line: 333 to 333
 

Available FST Operations

Changed:
<
<
Click on doc or more under Description for descriptive, graphical documentation; click on text under Usage for detailed code documentation.
>
>
Click on operation name for additional information.
 
Operation Usage Description
Changed:
<
<
doc ArcSort ArcSort(&A, compare); [bad link?] sorts arcs using compare function object (more)
  ArcSortFst<Arc, Compare>(A, compare);  
>
>
ArcSort ArcSort(&A, compare); sorts arcs using compare function object
  ArcSortFst<Arc, Compare>(A, compare);  
 
  fstarcsort [--sort_type=$type] a.fst out.fst  
Changed:
<
<
doc Closure Closure(&A, type); [bad link?] A* = <eps> U A U AA U AAA ... (more)
  ClosureFst<Arc>(A, type);  
>
>
Closure Closure(&A, type); A* = <eps> U A U AA U AAA ...
  ClosureFst<Arc>(A, type);  
 
  fstclosure a.fst out.fst  
Changed:
<
<
doc Compose Compose(A, B, &C); composition of binary relations A and B (more)
  ComposeFst<Arc>(A, B);  
>
>
Compose Compose(A, B, &C); composition of binary relations A and B
  ComposeFst<Arc>(A, B);  
 
  fstcompose a.fst b.fst out.fst  
Changed:
<
<
doc Concat Concat(&A, B); [bad link?] contains the strings in A followed by B (more)
  ConcatFst<Arc>(A,B);  
>
>
Concat Concat(&A, B); contains the strings in A followed by B
  ConcatFst<Arc>(A,B);  
 
  fstconcat a.fst b.fst out.fst  
Changed:
<
<
doc Connect Connect(&A); [bad link?] removes states and arcs not on a path from the start to a final state (more)
>
>
Connect Connect(&A); removes states and arcs not on a path from the start to a final state
 
  fstconnect a.fst out.fst  
Changed:
<
<
doc Determinize Determinize(A, &B); creates equiv. FST with no state with two arcs with the same input label (more)
  DeterminizeFst<Arc>(A);  
>
>
Determinize Determinize(A, &B); creates equiv. FST with no state with two arcs with the same input label
  DeterminizeFst<Arc>(A);  
 
  fstdeterminize a.fst out.fst  
Difference Difference(A, B, &C); contains strings in A but not B; B unweighted
Changed:
<
<
  DifferenceFst<Arc>(A, B);  
>
>
  DifferenceFst<Arc>(A, B);  
 
  fstdifference a.fsa b.dfa out.fsa  
Changed:
<
<
EpsilonNormalize EpsilonNormalize(A, &B, type); [bad link?] epsilon normalizes A
>
>
EpsilonNormalize EpsilonNormalize(A, &B, type); epsilon normalizes A
 
  fstepsnormalize [--eps_norm_output]  
Changed:
<
<
Equivalent Equivalent(A, B) [bad link?] determines if acceptors A and B accept the same strings with the same weights
>
>
Equivalent Equivalent(A, B) determines if acceptors A and B accept the same strings with the same weights
 
  fstequivalent a.dfa b.dfa  
Intersect Intersect(A, B, &C); contains strings both in A and B
Changed:
<
<
IntersectFst<Arc>(A, B);  
>
>
IntersectFst<Arc>(A, B);  
 
  fstintersect a.fsa b.fsa out.fsa  
Changed:
<
<
Invert Invert(&A); [bad link?] inverse binary relation; exchanges input and output labels
  InvertFst<Arc>(A);  
>
>
Invert Invert(&A); inverse binary relation; exchanges input and output labels
  InvertFst<Arc>(A);  
 
  fstinvert a.fst out.fst  
Changed:
<
<
Map Map(&A, mapper); [bad link?] transforms arcs in an FST
  Map(A, &B, mapper); [bad link?]  
  MapFst<Arc, Mapper>(A, mapper);  
>
>
Map Map(&A, mapper); transforms arcs in an FST
  Map(A, &B, mapper);  
  MapFst<Arc, Mapper>(A, mapper);  
 
  fstmap [--delta=$d] [--map=$type] [--weight=$w] in.fst out.fst  
Changed:
<
<
Minimize Minimize(&A); [bad link?] transforms to equiv. deterministic FSA with fewest states and arcs
  Minimize(&A, &B); [bad link?] transforms to equiv. deterministic FST with fewest states and arcs
>
>
Minimize Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
  Minimize(&A, &B); transforms to equiv. deterministic FST with fewest states and arcs
 
  fstminimize a.fst out1.fst [out2.fst]  
Changed:
<
<
Project Project(&A, type); [bad link?] creates acceptor of just the input or output strings
  ProjectFst<Arc>(A, type);  
>
>
Project Project(&A, type); creates acceptor of just the input or output strings
  ProjectFst<Arc>(A, type);  
 
  fstproject [--project_output] a.fst out.fst  
Changed:
<
<
Prune Prune(&A, threshold); [bad link?] remove paths outside a threshold of best path
>
>
Prune Prune(&A, threshold); remove paths outside a threshold of best path
 
  fstprune [--weight=$w] a.fst out.fst  
Changed:
<
<
Push Push<Arc, Type>(&A, flags); [bad link?] create equiv. FST pushing weights and/or output labels toward initial or final states
>
>
Push Push<Arc, Type>(&A, flags); create equiv. FST pushing weights and/or output labels toward initial \or final states
 
  fstpush [--push_labels] [--push_weights] [--to_final] a.fst out.fst  
Changed:
<
<
Relabel Relabel(&A, isyms, osyms); [bad link?] changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  
>
>
Relabel Relabel(&A, isyms, osyms); changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  
 
  fstrelabel [-relabel_isymbols=$isyms] [-relabel_osymbols=$osyms] in.fst out.fst  
Changed:
<
<
Replace Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN
ReplaceFst<Arc>(fst_label_pairs, root_label);  
>
>
Replace Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN
ReplaceFst<Arc>(fst_label_pairs, root_label);  
 
  fstreplace root.fst rootlabel [rule1.fst rule1.label ...] out.fst  
Changed:
<
<
Reweight Reweight(&A, potentials, type); [bad link?] creates equiv. FST changing arc weights based on potentials
>
>
Reweight Reweight(&A, potentials, type); creates equiv. FST changing arc weights based on potentials
 
  fstreweight [--to_final] in.fst potentials.txt out.fst  
Changed:
<
<
Reverse Reverse(A, &B); [bad link?] contains the reversed strings in A
>
>
Reverse Reverse(A, &B); contains the reversed strings in A
 
  fstreverse a.fst out.fst  
Changed:
<
<
RmEpsilon RmEpsilon(&A); [bad link?] creates equiv. FST with no input/output epsilons
  RmEpsilonFst<Arc>(A); [bad link?]  
>
>
RmEpsilon RmEpsilon(&A); creates equiv. FST with no input/output epsilons
  RmEpsilonFst<Arc>(A);  
 
  fstrmepsilon a.fst out.fst  
Changed:
<
<
ShortestDistance ShortestDistance(A, &distance); [bad link?] shortest distance from initial state to each state
  ShortestDistance(A, &distance, true); [bad link?] shortest distance from each state to final states
>
>
ShortestDistance ShortestDistance(A, &distance); shortest distance from initial state to each state
  ShortestDistance(A, &distance, true); shortest distance from each state to final states
 
  fstshortestdistance [--reverse] in.fst [distance.txt]  
Changed:
<
<
ShortestPath ShortestPath(A, &B, nshortest=1); [bad link?] N-best paths
>
>
ShortestPath ShortestPath(A, &B, nshortest=1); N-best paths
 
  fstshortestpath [--nshortest=$n] a.fst out.fst  
Changed:
<
<
Synchronize SynchronizeFst<Arc>(A); synchronizes an Fst
>
>
Synchronize SynchronizeFst<Arc>(A); synchronizes an Fst
 
  fstsynchronize a.fst out.fst  
Changed:
<
<
TopSort TopSort(&A); [bad link?] sorts an acyclic FST so that all transitions are from lower to higher state IDs
>
>
TopSort TopSort(&A); sorts an acyclic FST so that all transitions are from lower to higher state IDs
 
  fsttopsort a.fst out.fst  
Changed:
<
<
Union Union(&A, B); [bad link?] contains strings in A or B
  UnionFst<Arc>(A, B);  
>
>
Union Union(&A, B); contains strings in A or B
  UnionFst<Arc>(A, B);  
 
  fstunion a.fst b.fst out.fst  
Added:
>
>
 

FST Weights

Revision 382007-06-22 - MichaelRiley

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

OpenFst Quick Tour

Line: 437 to 437
 These weight classes represent their weight in a single precision float that is a constructor argument. That float can be directly accessed with member function Value(). For unweighted automata, it is convenient and customary in this library to use TropicalWeight restricted to Zero and One.
Added:
>
>
StdArc is the default arc type for the FST binaries.
 
Changed:
<
<
From the shell-level, the FST arc type can be specified to fstcompile with the -arc_type flag.
>
>
From the shell-level, the FST arc type can be specified to fstcompile with the -arc_type flag; StdArc is the default.
  -- MichaelRiley - 25 May 2007

Revision 372007-06-22 - MichaelRiley

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

OpenFst Quick Tour

Line: 296 to 296
 // Reads in an input FST. StdFst *input = StdFst::Read("input.fst");
Changed:
<
<
// Reads in the transducion model.
>
>
// Reads in the transduction model.
 StdFst *model = StdFst::Read("model.fst");

// The FSTs must be sorted along the dimensions they will be joined.

Line: 442 to 442
  -- MichaelRiley - 25 May 2007
Changed:
<
<
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1175185417" name="numericfst.jpg" path="numericfst.jpg" size="4881" user="Main.CyrilAllauzen" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1175185417" name="symbolicfst.jpg" path="symbolicfst.jpg" size="4768" user="Main.CyrilAllauzen" version="1"
>
>
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462223" name="numericfst.jpg" path="numericfst.jpg" size="4881" user="Main.CyrilAllauzen" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462223" name="symbolicfst.jpg" path="symbolicfst.jpg" size="4768" user="Main.CyrilAllauzen" version="1"

Revision 362007-06-20 - MichaelRiley

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

OpenFst Quick Tour

Line: 351 to 351
 
  fstconcat a.fst b.fst out.fst  
doc Connect Connect(&A); [bad link?] removes states and arcs not on a path from the start to a final state (more)
  fstconnect a.fst out.fst  
Changed:
<
<
Determinize Determinize(A, &B); creates equiv. FST with no state with two arcs with the same input label (currently subsequential only)
>
>
doc Determinize Determinize(A, &B); creates equiv. FST with no state with two arcs with the same input label (more)
 
  DeterminizeFst<Arc>(A);  
  fstdeterminize a.fst out.fst  
Difference Difference(A, B, &C); contains strings in A but not B; B unweighted

Revision 352007-06-19 - MichaelRiley

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

OpenFst Quick Tour

Line: 349 to 349
 
doc Concat Concat(&A, B); [bad link?] contains the strings in A followed by B (more)
  ConcatFst<Arc>(A,B);  
  fstconcat a.fst b.fst out.fst  
Changed:
<
<
Connect Connect(&A); [bad link?] removes states and arcs not on a path from the start to a final state
>
>
doc Connect Connect(&A); [bad link?] removes states and arcs not on a path from the start to a final state (more)
 
  fstconnect a.fst out.fst  
Determinize Determinize(A, &B); creates equiv. FST with no state with two arcs with the same input label (currently subsequential only)
  DeterminizeFst<Arc>(A);  

Revision 342007-06-16 - MichaelRiley

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

OpenFst Quick Tour

Line: 334 to 334
 

Available FST Operations

Click on doc or more under Description for descriptive, graphical documentation;
Changed:
<
<
click on text under Usage for code documentation.
>
>
click on text under Usage for detailed code documentation.
 
Operation Usage Description
doc ArcSort ArcSort(&A, compare); [bad link?] sorts arcs using compare function object (more)

Revision 332007-06-16 - MichaelRiley

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

OpenFst Quick Tour

Line: 337 to 337
 click on text under Usage for code documentation.

Operation Usage Description
Changed:
<
<
ArcSort doc ArcSort(&A, compare); [bad link?] sorts arcs using compare function object (more)
>
>
doc ArcSort ArcSort(&A, compare); [bad link?] sorts arcs using compare function object (more)
 
  ArcSortFst<Arc, Compare>(A, compare);  
  fstarcsort [--sort_type=$type] a.fst out.fst  
Changed:
<
<
Closure doc Closure(&A, type); [bad link?] A* = <eps> U A U AA U AAA ... (more)
>
>
doc Closure Closure(&A, type); [bad link?] A* = <eps> U A U AA U AAA ... (more)
 
  ClosureFst<Arc>(A, type);  
  fstclosure a.fst out.fst  
Changed:
<
<
Compose Compose(A, B, &C); composition of binary relations A and B
>
>
doc Compose Compose(A, B, &C); composition of binary relations A and B (more)
 
  ComposeFst<Arc>(A, B);  
  fstcompose a.fst b.fst out.fst  
Changed:
<
<
Concat Concat(&A, B); [bad link?] contains the strings in A followed by B
>
>
doc Concat Concat(&A, B); [bad link?] contains the strings in A followed by B (more)
 
  ConcatFst<Arc>(A,B);  
  fstconcat a.fst b.fst out.fst  
Connect Connect(&A); [bad link?] removes states and arcs not on a path from the start to a final state
Line: 438 to 438
 can be directly accessed with member function Value(). For unweighted automata, it is convenient and customary in this library to use TropicalWeight restricted to Zero and One.
Changed:
<
<
From the shell-level, the FST arc type can be specified to fstcompile with the --arc_type flag.
>
>
From the shell-level, the FST arc type can be specified to fstcompile with the -arc_type flag.
  -- MichaelRiley - 25 May 2007

Revision 322007-06-15 - MichaelRiley

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

OpenFst Quick Tour

Line: 337 to 337
 click on text under Usage for code documentation.

Operation Usage Description
Changed:
<
<
ArcSort ArcSort(&A, compare); [bad link?] sorts arcs using compare function object
>
>
ArcSort doc ArcSort(&A, compare); [bad link?] sorts arcs using compare function object (more)
 
  ArcSortFst<Arc, Compare>(A, compare);  
  fstarcsort [--sort_type=$type] a.fst out.fst  
Closure doc Closure(&A, type); [bad link?] A* = <eps> U A U AA U AAA ... (more)

Revision 312007-06-15 - CyrilAllauzen

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

OpenFst Quick Tour

Line: 383 to 383
 
  fstpush [--push_labels] [--push_weights] [--to_final] a.fst out.fst  
Relabel Relabel(&A, isyms, osyms); [bad link?] changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  
Changed:
<
<
  fstrelabel [-relabel_isymbols=$isyms] [-relabel_osymbols=$osyms] in.fst out.fst
>
>
  fstrelabel [-relabel_isymbols=$isyms] [-relabel_osymbols=$osyms] in.fst out.fst  
 
Replace Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN
ReplaceFst<Arc>(fst_label_pairs, root_label);  
Changed:
<
<
  fstreplace root.fst rootlabel [rule1.fst rule1.label ...] out.fst
>
>
  fstreplace root.fst rootlabel [rule1.fst rule1.label ...] out.fst  
 
Reweight Reweight(&A, potentials, type); [bad link?] creates equiv. FST changing arc weights based on potentials
Changed:
<
<
  fstreweight [--to_final] in.fst potentials.txt out.fst
>
>
  fstreweight [--to_final] in.fst potentials.txt out.fst  
 
Reverse Reverse(A, &B); [bad link?] contains the reversed strings in A
  fstreverse a.fst out.fst  
RmEpsilon RmEpsilon(&A); [bad link?] creates equiv. FST with no input/output epsilons
Line: 396 to 396
 
  fstrmepsilon a.fst out.fst  
ShortestDistance ShortestDistance(A, &distance); [bad link?] shortest distance from initial state to each state
  ShortestDistance(A, &distance, true); [bad link?] shortest distance from each state to final states
Changed:
<
<
  fstshortestdistance [--reverse] in.fst [distance.txt]
>
>
  fstshortestdistance [--reverse] in.fst [distance.txt]  
 
ShortestPath ShortestPath(A, &B, nshortest=1); [bad link?] N-best paths
  fstshortestpath [--nshortest=$n] a.fst out.fst  
Synchronize SynchronizeFst<Arc>(A); synchronizes an Fst

Revision 302007-06-14 - MichaelRiley

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

OpenFst Quick Tour

Line: 410 to 410
 

FST Weights

Changed:
<
<
An arc weight in an FST gives the cost of taking that transition. The OpenFst library supports multiple types of weights --
>
>
An arc weight in an FST gives the cost of taking that transition. The OpenFst library supports multiple types of weights --
 in fact, any C++ class that meets various properties can be used as the Weight type specified in the Arc template parameter of an Fst. A few weight types are predefined in the library that will normally meet your needs. Among a weight's properties, it must have associated binary functions Plus(x, y) and Times(x, y) and static member functions Zero() and One().

Revision 292007-06-13 - CyrilAllauzen

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

OpenFst Quick Tour

Line: 362 to 362
 
Equivalent Equivalent(A, B) [bad link?] determines if acceptors A and B accept the same strings with the same weights
  fstequivalent a.dfa b.dfa  
Intersect Intersect(A, B, &C); contains strings both in A and B
Changed:
<
<
%DOX{fst::IntersectFst[IntersectFst<Arc>(A, B);]}  
>
>
IntersectFst<Arc>(A, B);  
 
  fstintersect a.fsa b.fsa out.fsa  
Invert Invert(&A); [bad link?] inverse binary relation; exchanges input and output labels
  InvertFst<Arc>(A);  

Revision 282007-06-13 - MichaelRiley

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

OpenFst Quick Tour

Line: 333 to 333
 

Available FST Operations

Changed:
<
<
Click on text under Usage for code documentation; click on more under Description for descriptive, graphical documentation.
>
>
Click on doc or more under Description for descriptive, graphical documentation; click on text under Usage for code documentation.
 
Operation Usage Description
ArcSort ArcSort(&A, compare); [bad link?] sorts arcs using compare function object
  ArcSortFst<Arc, Compare>(A, compare);  
  fstarcsort [--sort_type=$type] a.fst out.fst  
Changed:
<
<
Closure Closure(&A, type); [bad link?] A* = <eps> U A U AA U AAA ... (more)
>
>
Closure doc Closure(&A, type); [bad link?] A* = <eps> U A U AA U AAA ... (more)
 
  ClosureFst<Arc>(A, type);  
  fstclosure a.fst out.fst  
Compose Compose(A, B, &C); composition of binary relations A and B

Revision 272007-06-13 - MichaelRiley

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

OpenFst Quick Tour

Line: 333 to 333
 

Available FST Operations

Changed:
<
<
Click on text under Operation for operation documentation; click on text under Usage for code documentation:
>
>
Click on text under Usage for code documentation; click on more under Description for descriptive, graphical documentation.
 
Operation Usage Description
ArcSort ArcSort(&A, compare); [bad link?] sorts arcs using compare function object
  ArcSortFst<Arc, Compare>(A, compare);  
  fstarcsort [--sort_type=$type] a.fst out.fst  
Changed:
<
<
Closure Closure(&A, type); [bad link?] A* = <eps> U A U AA U AAA ...
>
>
Closure Closure(&A, type); [bad link?] A* = <eps> U A U AA U AAA ... (more)
 
  ClosureFst<Arc>(A, type);  
  fstclosure a.fst out.fst  
Compose Compose(A, B, &C); composition of binary relations A and B

Revision 262007-06-13 - MichaelRiley

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

OpenFst Quick Tour

Line: 334 to 334
 

Available FST Operations

Changed:
<
<
Click on text under Operation for a graphical example; click on text under Usage for more documentation:
>
>
Click on text under Operation for operation documentation; click on text under Usage for code documentation:
 
Operation Usage Description
ArcSort ArcSort(&A, compare); [bad link?] sorts arcs using compare function object
  ArcSortFst<Arc, Compare>(A, compare);  
  fstarcsort [--sort_type=$type] a.fst out.fst  
Changed:
<
<
Closure Closure(&A, type); [bad link?] A* = <eps> U A U AA U AAA ...
>
>
Closure Closure(&A, type); [bad link?] A* = <eps> U A U AA U AAA ...
 
  ClosureFst<Arc>(A, type);  
  fstclosure a.fst out.fst  
Compose Compose(A, B, &C); composition of binary relations A and B
  ComposeFst<Arc>(A, B);  
  fstcompose a.fst b.fst out.fst  
Changed:
<
<
Concat Concat(&A, B); [bad link?] contains the strings in A followed by B
>
>
Concat Concat(&A, B); [bad link?] contains the strings in A followed by B
 
  ConcatFst<Arc>(A,B);  
  fstconcat a.fst b.fst out.fst  
Connect Connect(&A); [bad link?] removes states and arcs not on a path from the start to a final state
Line: 374 to 374
 
Minimize Minimize(&A); [bad link?] transforms to equiv. deterministic FSA with fewest states and arcs
  Minimize(&A, &B); [bad link?] transforms to equiv. deterministic FST with fewest states and arcs
  fstminimize a.fst out1.fst [out2.fst]  
Changed:
<
<
Project Project(&A, type); [bad link?] creates acceptor of just the input or output strings
>
>
Project Project(&A, type); [bad link?] creates acceptor of just the input or output strings
 
  ProjectFst<Arc>(A, type);  
  fstproject [--project_output] a.fst out.fst  
Prune Prune(&A, threshold); [bad link?] remove paths outside a threshold of best path
Line: 403 to 403
 
  fstsynchronize a.fst out.fst  
TopSort TopSort(&A); [bad link?] sorts an acyclic FST so that all transitions are from lower to higher state IDs
  fsttopsort a.fst out.fst  
Changed:
<
<
Union Union(&A, B); [bad link?] contains strings in A or B
>
>
Union Union(&A, B); [bad link?] contains strings in A or B
 
  UnionFst<Arc>(A, B);  
  fstunion a.fst b.fst out.fst  

Revision 252007-06-11 - CyrilAllauzen

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

OpenFst Quick Tour

Line: 381 to 381
 
  fstprune [--weight=$w] a.fst out.fst  
Push Push<Arc, Type>(&A, flags); [bad link?] create equiv. FST pushing weights and/or output labels toward initial or final states
  fstpush [--push_labels] [--push_weights] [--to_final] a.fst out.fst  
Changed:
<
<
Relabel Relabel(&A, isyms, osyms); changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  
>
>
Relabel Relabel(&A, isyms, osyms); [bad link?] changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  
 
  fstrelabel [-relabel_isymbols=$isyms] [-relabel_osymbols=$osyms] in.fst out.fst
Changed:
<
<
Replace Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN
ReplaceFst<Arc>(fst_label_pairs, root_label);  
>
>
Replace Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN
ReplaceFst<Arc>(fst_label_pairs, root_label);  
 
  fstreplace root.fst rootlabel [rule1.fst rule1.label ...] out.fst
Changed:
<
<
Reweight Reweight(&A, potentials, type); creates equiv. FST changing arc weights based on potentials
>
>
Reweight Reweight(&A, potentials, type); [bad link?] creates equiv. FST changing arc weights based on potentials
 
  fstreweight [--to_final] in.fst potentials.txt out.fst
Changed:
<
<
Reverse Reverse(A, &B); contains the reversed strings in A
>
>
Reverse Reverse(A, &B); [bad link?] contains the reversed strings in A
 
  fstreverse a.fst out.fst  
Changed:
<
<
RmEpsilon RmEpsilon(&A); creates equiv. FST with no input/output epsilons
  RmEpsilonFst<Arc>(A);  
>
>
RmEpsilon RmEpsilon(&A); [bad link?] creates equiv. FST with no input/output epsilons
  RmEpsilonFst<Arc>(A); [bad link?]  
 
  fstrmepsilon a.fst out.fst  
Changed:
<
<
ShortestDistance ShortestDistance(A, &distance); shortest distance from initial state to each state
  ShortestDistance(A, &distance, true); shortest distance from each state to final states
>
>
ShortestDistance ShortestDistance(A, &distance); [bad link?] shortest distance from initial state to each state
  ShortestDistance(A, &distance, true); [bad link?] shortest distance from each state to final states
 
  fstshortestdistance [--reverse] in.fst [distance.txt]
Changed:
<
<
ShortestPath ShortestPath(A, &B, nshortest=1); N-best paths
>
>
ShortestPath ShortestPath(A, &B, nshortest=1); [bad link?] N-best paths
 
  fstshortestpath [--nshortest=$n] a.fst out.fst  
Changed:
<
<
Synchronize Synchronize(A, &B); synchronizes an Fst
>
>
Synchronize SynchronizeFst<Arc>(A); synchronizes an Fst
 
  fstsynchronize a.fst out.fst  
Changed:
<
<
TopSort TopSort(&A); sorts an acyclic FST so that all transitions are from lower to higher state IDs
>
>
TopSort TopSort(&A); [bad link?] sorts an acyclic FST so that all transitions are from lower to higher state IDs
 
  fsttopsort a.fst out.fst  
Union Union(&A, B); [bad link?] contains strings in A or B
  UnionFst<Arc>(A, B);  

Revision 242007-06-11 - CyrilAllauzen

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

OpenFst Quick Tour

Line: 337 to 337
 Click on text under Operation for a graphical example; click on text under Usage for more documentation:

Operation Usage Description
Changed:
<
<
ArcSort ArcSort(&A, compare); sorts arcs using compare function object
  ArcSortFst<Arc, Compare>(A, compare);  
>
>
ArcSort ArcSort(&A, compare); [bad link?] sorts arcs using compare function object
  ArcSortFst<Arc, Compare>(A, compare);  
 
  fstarcsort [--sort_type=$type] a.fst out.fst  
Closure Closure(&A, type); [bad link?] A* = <eps> U A U AA U AAA ...
Changed:
<
<
  ClosureFst<Arc>(A, type);  
>
>
  ClosureFst<Arc>(A, type);  
 
  fstclosure a.fst out.fst  
Compose Compose(A, B, &C); composition of binary relations A and B
Changed:
<
<
  ComposeFst<Arc>(A, B);  
>
>
  ComposeFst<Arc>(A, B);  
 
  fstcompose a.fst b.fst out.fst  
Concat Concat(&A, B); [bad link?] contains the strings in A followed by B
  ConcatFst<Arc>(A,B);  
  fstconcat a.fst b.fst out.fst  
Changed:
<
<
Connect Connect(&A); removes states and arcs not on a path from the start to a final state
>
>
Connect Connect(&A); [bad link?] removes states and arcs not on a path from the start to a final state
 
  fstconnect a.fst out.fst  
Determinize Determinize(A, &B); creates equiv. FST with no state with two arcs with the same input label (currently subsequential only)
Changed:
<
<
  DeterminizeFst<Arc>(A);  
>
>
  DeterminizeFst<Arc>(A);  
 
  fstdeterminize a.fst out.fst  
Difference Difference(A, B, &C); contains strings in A but not B; B unweighted
Changed:
<
<
  DifferenceFst<Arc>(A, B);  
>
>
  DifferenceFst<Arc>(A, B);  
 
  fstdifference a.fsa b.dfa out.fsa  
Changed:
<
<
EpsNormalize EpsNormalize(A, &B, type); epsilon normalizes A
>
>
EpsilonNormalize EpsilonNormalize(A, &B, type); [bad link?] epsilon normalizes A
 
  fstepsnormalize [--eps_norm_output]  
Changed:
<
<
Equivalent Equivalent(A, B) determines if acceptors A and B accept the same strings with the same weights
>
>
Equivalent Equivalent(A, B) [bad link?] determines if acceptors A and B accept the same strings with the same weights
 
  fstequivalent a.dfa b.dfa  
Intersect Intersect(A, B, &C); contains strings both in A and B
Changed:
<
<
IntersectFst<Arc>(A, B);  
>
>
%DOX{fst::IntersectFst[IntersectFst<Arc>(A, B);]}  
 
  fstintersect a.fsa b.fsa out.fsa  
Invert Invert(&A); [bad link?] inverse binary relation; exchanges input and output labels
  InvertFst<Arc>(A);  
  fstinvert a.fst out.fst  
Changed:
<
<
Map Map(&A, mapper); transforms arcs in an FST
  Map(A, &B, mapper);  
  MapFst<Arc, Mapper>(A, mapper);  
>
>
Map Map(&A, mapper); [bad link?] transforms arcs in an FST
  Map(A, &B, mapper); [bad link?]  
  MapFst<Arc, Mapper>(A, mapper);  
 
  fstmap [--delta=$d] [--map=$type] [--weight=$w] in.fst out.fst  
Changed:
<
<
Minimize Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
  Minimize(&A, &B); transforms to equiv. deterministic FST with fewest states and arcs
>
>
Minimize Minimize(&A); [bad link?] transforms to equiv. deterministic FSA with fewest states and arcs
  Minimize(&A, &B); [bad link?] transforms to equiv. deterministic FST with fewest states and arcs
 
  fstminimize a.fst out1.fst [out2.fst]  
Project Project(&A, type); [bad link?] creates acceptor of just the input or output strings
  ProjectFst<Arc>(A, type);  
  fstproject [--project_output] a.fst out.fst  
Changed:
<
<
Prune Prune(&A, threshold); remove paths outside a threshold of best path
>
>
Prune Prune(&A, threshold); [bad link?] remove paths outside a threshold of best path
 
  fstprune [--weight=$w] a.fst out.fst  
Changed:
<
<
Push Push<Arc, Type>(&A, flags); create equiv. FST pushing weights and/or output labels toward initial or final states
>
>
Push Push<Arc, Type>(&A, flags); [bad link?] create equiv. FST pushing weights and/or output labels toward initial or final states
 
  fstpush [--push_labels] [--push_weights] [--to_final] a.fst out.fst  
Relabel Relabel(&A, isyms, osyms); changes input and output label IDs
  RelabelFst<Arc>(A, isyms, osyms);  

Revision 232007-06-09 - MichaelRiley

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

OpenFst Quick Tour

Line: 370 to 370
 
Map Map(&A, mapper); transforms arcs in an FST
  Map(A, &B, mapper);  
  MapFst<Arc, Mapper>(A, mapper);  
Changed:
<
<
  fstmap [--delta=$d] [--map=$type] [--weight=$w]
>
>
  fstmap [--delta=$d] [--map=$type] [--weight=$w] in.fst out.fst  
 
Minimize Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
  Minimize(&A, &B); transforms to equiv. deterministic FST with fewest states and arcs
  fstminimize a.fst out1.fst [out2.fst]  

Revision 222007-06-08 - MichaelRiley

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

OpenFst Quick Tour

Added:
>
>

Finding and Using the Library

The OpenFst Library is a C++ template library. To use it from C++, include lib/fstlib-inl.h and link to lib/libfst.{a,so}. You may instead use just those include files for the classes and functions that you will need. All classes and functions are in the fst namespace; the examples below assume you are within that namespace for brevity.

As an alternative interface, there are shell-level commands in bin that operate on file representations of FSTs.

 

Example FST

The following picture depicts a finite state transducer:

Line: 362 to 370
 
Map Map(&A, mapper); transforms arcs in an FST
  Map(A, &B, mapper);  
  MapFst<Arc, Mapper>(A, mapper);  
Changed:
<
<
Minimize Minimize(&A); transforms to equiv. deterministic FST with fewest states and arcs
  fstminimize a.fst out.fst  
>
>
  fstmap [--delta=$d] [--map=$type] [--weight=$w]
Minimize Minimize(&A); transforms to equiv. deterministic FSA with fewest states and arcs
  Minimize(&A, &B); transforms to equiv. deterministic FST with fewest states and arcs
  fstminimize a.fst out1.fst [out2.fst]  
 
Project Project(&A, type); [bad link?] creates acceptor of just the input or output strings
  ProjectFst<Arc>(A, type);  
  fstproject [--project_output] a.fst out.fst  
Prune Prune(&A, threshold); remove paths outside a threshold of best path
Changed:
<
<
  fstprune [--weight_threshold=$w] a.fst out.fst  
>
>
  fstprune [--weight=$w] a.fst out.fst  
 
Push Push<Arc, Type>(&A, flags); create equiv. FST pushing weights and/or output labels toward initial or final states
  fstpush [--push_labels] [--push_weights] [--to_final] a.fst out.fst  
Relabel Relabel(&A, isyms, osyms); changes input and output label IDs

Revision 212007-06-08 - MichaelRiley

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

OpenFst Quick Tour

Line: 386 to 386
 
  fstrmepsilon a.fst out.fst  
ShortestDistance ShortestDistance(A, &distance); shortest distance from initial state to each state
  ShortestDistance(A, &distance, true); shortest distance from each state to final states
Changed:
<
<
  fstshortestdistance [--reverse] in.fst distance.txt
>
>
  fstshortestdistance [--reverse] in.fst [distance.txt]
 
ShortestPath ShortestPath(A, &B, nshortest=1); N-best paths
  fstshortestpath [--nshortest=$n] a.fst out.fst  
Synchronize Synchronize(A, &B); synchronizes an Fst

Revision 202007-06-08 - MichaelRiley

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

OpenFst Quick Tour

Revision 192007-06-08 - MichaelRiley

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

OpenFst Quick Tour

Line: 100 to 100
 You may use any string for a label; you may use any non-negative integer for a label ID. The zero label ID is reserved for the epsilon label, which is the empty string. We have included 0 in our table, even though it is not used in our example. Since subsequent FST operations might add epsilons, it is good practice to include a symbol for it.
Changed:
<
<
This text FST must be converted into a binary FST file before it can be used by the FST library.
>
>
This text FST must be converted into a binary FST file before it can be used by the OpenFst library.
 
# Creates binary Fst from text file.
Line: 378 to 378
 
ReplaceFst<Arc>(fst_label_pairs, root_label);  
  fstreplace root.fst rootlabel [rule1.fst rule1.label ...] out.fst
Reweight Reweight(&A, potentials, type); creates equiv. FST changing arc weights based on potentials
Added:
>
>
  fstreweight [--to_final] in.fst potentials.txt out.fst
 
Reverse Reverse(A, &B); contains the reversed strings in A
  fstreverse a.fst out.fst  
RmEpsilon RmEpsilon(&A); creates equiv. FST with no input/output epsilons
Line: 385 to 386
 
  fstrmepsilon a.fst out.fst  
ShortestDistance ShortestDistance(A, &distance); shortest distance from initial state to each state
  ShortestDistance(A, &distance, true); shortest distance from each state to final states
Added:
>
>
  fstshortestdistance [--reverse] in.fst distance.txt
 
ShortestPath ShortestPath(A, &B, nshortest=1); N-best paths
  fstshortestpath [--nshortest=$n] a.fst out.fst  
Synchronize Synchronize(A, &B); synchronizes an Fst
Line: 398 to 400
 

FST Weights

Changed:
<
<
An arc weight in an FST gives the cost of taking that transition. The FST library supports multiple types of weights --
>
>
An arc weight in an FST gives the cost of taking that transition. The OpenFst library supports multiple types of weights --
 in fact, any C++ class that meets various properties can be used as the Weight type specified in the Arc template parameter of an Fst. A few weight types are predefined in the library that will normally meet your needs. Among a weight's properties, it must have associated binary functions Plus(x, y) and Times(x, y) and static member functions Zero() and One().
Line: 420 to 422
 appropriate when the transition weights represent probabilities. The log weight type is appropriate when the transition weights represent negative log probabilities (more numerically stable than the isomorphic, under log(), real weight type). The tropical weight type is appropriate for shortest path operations and is identical to the log except it uses min for the Plus operation.
Changed:
<
<
The FST library predefines TropicalWeight [bad link?] and LogWeight [bad link?] as well as the corresponding
>
>
The OpenFst library predefines TropicalWeight [bad link?] and LogWeight [bad link?] as well as the corresponding
 StdArc and LogArc. These weight classes represent their weight in a single precision float that is a constructor argument. That float can be directly accessed with member function Value(). For unweighted automata, it

Revision 182007-06-08 - MichaelRiley

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

OpenFst Quick Tour

Line: 329 to 329
 Click on text under Operation for a graphical example; click on text under Usage for more documentation:

Operation Usage Description
Changed:
<
<
ArcSort ArcSort(&A, compare); sort arcs using compare function object
>
>
ArcSort ArcSort(&A, compare); sorts arcs using compare function object
 
  ArcSortFst<Arc, Compare>(A, compare);  
  fstarcsort [--sort_type=$type] a.fst out.fst  
Closure Closure(&A, type); [bad link?] A* = <eps> U A U AA U AAA ...
Line: 341 to 341
 
Concat Concat(&A, B); [bad link?] contains the strings in A followed by B
  ConcatFst<Arc>(A,B);  
  fstconcat a.fst b.fst out.fst  
Changed:
<
<
Connect Connect(&A); remove states and arcs not on a path from the start to a final state
>
>
Connect Connect(&A); removes states and arcs not on a path from the start to a final state
 
  fstconnect a.fst out.fst  
Changed:
<
<
Determinize Determinize(A, &B); create equiv. FST with no state with two arcs with the same input label (currently subsequential only)
>
>
Determinize Determinize(A, &B); creates equiv. FST with no state with two arcs with the same input label (currently subsequential only)
 
  DeterminizeFst<Arc>(A);  
  fstdeterminize a.fst out.fst  
Difference Difference(A, B, &C); contains strings in A but not B; B unweighted
  DifferenceFst<Arc>(A, B);  
  fstdifference a.fsa b.dfa out.fsa  
Changed:
<
<
EpsNormalize EpsNormalize(A, &B, type); epsilon normalize A
>
>
EpsNormalize EpsNormalize(A, &B, type); epsilon normalizes A
 
  fstepsnormalize [--eps_norm_output]  
Changed:
<
<
Equivalent Equivalent(A, B) determine if acceptors A and B accept the same strings with the same weights
>
>
Equivalent Equivalent(A, B) determines if acceptors A and B accept the same strings with the same weights
 
  fstequivalent a.dfa b.dfa  
Intersect Intersect(A, B, &C); contains strings both in A and B
IntersectFst<Arc>(A, B);  
Line: 359 to 359
 
Invert Invert(&A); [bad link?] inverse binary relation; exchanges input and output labels
  InvertFst<Arc>(A);  
  fstinvert a.fst out.fst  
Changed:
<
<
Map Map(&A, mapper); transform arcs in an FST
>
>
Map Map(&A, mapper); transforms arcs in an FST
 
  Map(A, &B, mapper);  
  MapFst<Arc, Mapper>(A, mapper);  
Changed:
<
<
Minimize Minimize(&A); transform to equiv. deterministic FST with fewest states and arcs
>
>
Minimize Minimize(&A); transforms to equiv. deterministic FST with fewest states and arcs
 
  fstminimize a.fst out.fst  
Project Project(&A, type); [bad link?] creates acceptor of just the input or output strings
  ProjectFst<Arc>(A, type);  
Line: 371 to 371
 
  fstprune [--weight_threshold=$w] a.fst out.fst  
Push Push<Arc, Type>(&A, flags); create equiv. FST pushing weights and/or output labels toward initial or final states
  fstpush [--push_labels] [--push_weights] [--to_final] a.fst out.fst  
Changed:
<
<
Relabel Relabel(&A, isyms, osyms); change input and output label IDs
>
>
Relabel Relabel(&A, isyms, osyms); changes input and output label IDs
 
  RelabelFst<Arc>(A, isyms, osyms);  
Changed:
<
<
Replace ReplaceFst<Arc>(fst_array, root); replaces non-terminals with FSTs analogous to an RTN
Reweight Reweight(&A, potentials, type); create equiv. FST changing arc weights based on potentials
>
>
  fstrelabel [-relabel_isymbols=$isyms] [-relabel_osymbols=$osyms] in.fst out.fst
Replace Replace(fst_label_pairs, &B, root_label); replaces non-terminals with FSTs analogous to an RTN
ReplaceFst<Arc>(fst_label_pairs, root_label);  
  fstreplace root.fst rootlabel [rule1.fst rule1.label ...] out.fst
Reweight Reweight(&A, potentials, type); creates equiv. FST changing arc weights based on potentials
 
Reverse Reverse(A, &B); contains the reversed strings in A
  fstreverse a.fst out.fst  
Changed:
<
<
RmEpsilon RmEpsilon(&A); create equiv. FST with no input/output epsilons
>
>
RmEpsilon RmEpsilon(&A); creates equiv. FST with no input/output epsilons
 
  RmEpsilonFst<Arc>(A);  
  fstrmepsilon a.fst out.fst  
ShortestDistance ShortestDistance(A, &distance); shortest distance from initial state to each state
  ShortestDistance(A, &distance, true); shortest distance from each state to final states
ShortestPath ShortestPath(A, &B, nshortest=1); N-best paths
  fstshortestpath [--nshortest=$n] a.fst out.fst  
Changed:
<
<
TopSort TopSort(&A); sort an acyclic FST so that all transitions are from lower to higher state IDs
>
>
Synchronize Synchronize(A, &B); synchronizes an Fst
  fstsynchronize a.fst out.fst  
TopSort TopSort(&A); sorts an acyclic FST so that all transitions are from lower to higher state IDs
 
  fsttopsort a.fst out.fst  
Union Union(&A, B); [bad link?] contains strings in A or B
  UnionFst<Arc>(A, B);  

Revision 172007-06-07 - MichaelRiley

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

OpenFst Quick Tour

Line: 335 to 335
 
Closure Closure(&A, type); [bad link?] A* = <eps> U A U AA U AAA ...
  ClosureFst<Arc>(A, type);  
  fstclosure a.fst out.fst  
Added:
>
>
Compose Compose(A, B, &C); composition of binary relations A and B
  ComposeFst<Arc>(A, B);  
  fstcompose a.fst b.fst out.fst  
 
Concat Concat(&A, B); [bad link?] contains the strings in A followed by B
  ConcatFst<Arc>(A,B);  
  fstconcat a.fst b.fst out.fst  
Connect Connect(&A); remove states and arcs not on a path from the start to a final state
  fstconnect a.fst out.fst  
Deleted:
<
<
Compose Compose(A, B, &C); composition of binary relations A and B
  ComposeFst<Arc>(A, B);  
  fstcompose a.fst b.fst out.fst  
 
Determinize Determinize(A, &B); create equiv. FST with no state with two arcs with the same input label (currently subsequential only)
  DeterminizeFst<Arc>(A);  
  fstdeterminize a.fst out.fst  
Difference Difference(A, B, &C); contains strings in A but not B; B unweighted
  DifferenceFst<Arc>(A, B);  
  fstdifference a.fsa b.dfa out.fsa  
Added:
>
>
EpsNormalize EpsNormalize(A, &B, type); epsilon normalize A
  fstepsnormalize [--eps_norm_output]  
 
Equivalent Equivalent(A, B) determine if acceptors A and B accept the same strings with the same weights
  fstequivalent a.dfa b.dfa  
Intersect Intersect(A, B, &C); contains strings both in A and B
Line: 364 to 366
 
  fstminimize a.fst out.fst  
Project Project(&A, type); [bad link?] creates acceptor of just the input or output strings
  ProjectFst<Arc>(A, type);  
Changed:
<
<
  fstproject --project_type=$type a.fst out.fst  
>
>
  fstproject [--project_output] a.fst out.fst  
 
Prune Prune(&A, threshold); remove paths outside a threshold of best path
  fstprune [--weight_threshold=$w] a.fst out.fst  
Push Push<Arc, Type>(&A, flags); create equiv. FST pushing weights and/or output labels toward initial or final states

Revision 162007-06-07 - CyrilAllauzen

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

OpenFst Quick Tour

Line: 332 to 332
 
ArcSort ArcSort(&A, compare); sort arcs using compare function object
  ArcSortFst<Arc, Compare>(A, compare);  
  fstarcsort [--sort_type=$type] a.fst out.fst  
Changed:
<
<
Closure Closure(&A, type); A* = <eps> U A U AA U AAA ...
>
>
Closure Closure(&A, type); [bad link?] A* = <eps> U A U AA U AAA ...