Line: 1 to 1  

 
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  
Line: 1 to 1  

 
Line: 73 to 73  
Creating FSTs Using Text Files from the ShellFSTs can be specified using a text file in the  
Changed:  
< <  AT&T FSM format Supporting this format permits interoperability with the AT&T FSM binary tools, which can be downloaded for noncommercial purposes.  
> >  AT&T FSM format.  
We can create the text FST file for our example as follows: 
Line: 1 to 1  

 
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 
Line: 1 to 1  

 
Line: 417 to 417  
 
Changed:  
< < 
 
> > 
 
 
Line: 427 to 427  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

 
Line: 410 to 410  
 
Added:  
> > 
 
 
Added:  
> > 
 
 
Line: 423 to 427  
 
Added:  
> > 
 

Line: 1 to 1  

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

OpenFst Quick TourBelow 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 
Line: 1 to 1  

 
Line: 458 to 458  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

 
Line: 381 to 381  
Click on operation name for additional information.
 
Added:  
> > 
 
 
Line: 418 to 422  
 
Deleted:  
< < 
 
 
Line: 454 to 454  
 
Added:  
> > 
 

Line: 1 to 1  

 
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;  
} 
Line: 1 to 1  

 
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; }  
Line: 1 to 1  

 
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() => nonfinal.  
> >  # Get state i's final weight; if == Weight::Zero() => nonfinal.  
Weight weight = fst.Final(i);
# Iterates over the FSTs states.
 
Changed:  
< <  for (StateIterator  
> >  for (StateIterator<StdFst> siter(fst); siter.Done(); siter.Next())  
StateId state_id = siter.Value();
# Iterates over state i's arcs.
 
Changed:  
< <  for (ArcIterator  
> >  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<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: 
Line: 1 to 1  

 
Line: 36 to 36  
FSTs can be created with constructors and mutators from C++ or from text files at the shelllevel. 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 ShellFSTs can be specified using a text file in the 
Line: 1 to 1  

OpenFst Quick TourBelow 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 
Line: 1 to 1  


Line: 1 to 1  

 
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  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

 
Line: 413 to 413  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

 
Line: 492 to 492  
(See here for how to your define your own FST arcs and weights if desired.)  
Deleted:  
< <   MichaelRiley  23 Feb 2009  

Line: 1 to 1  

 
Line: 227 to 227  
# of accessible states 3 # of coaccessible states 3 # of connected states 3  
Added:  
> >  # of connected components 1  
# of strongly conn components 3 input matcher y output matcher y 
Line: 1 to 1  

 
Line: 274 to 274  
 
Changed:  
< <  (See here for how to define your own FST classes if desired.)  
> >  (See here for additional nonabstract 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. 
Line: 1 to 1  

 
Line: 259 to 259  
The FST operations can be invoked either at the C++ level or from shelllevel 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 finitestate 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.

Line: 1 to 1  

 
Line: 228 to 228  
# of coaccessible states 3 # of connected states 3 # of strongly conn components 3  
Added:  
> >  input matcher y output matcher y  
expanded y mutable y acceptor y 
Line: 1 to 1  

 
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 librarydefault 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 
Line: 1 to 1  

 
Line: 382 to 382  
 
Changed:  
< < 
 
> > 
 
 
Line: 391 to 391  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

 
Line: 382 to 382  
 
Changed:  
< < 
 
> > 
 
 
Line: 391 to 391  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

 
Line: 418 to 418  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

 
Line: 420 to 420  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

 
Line: 422 to 422  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

 
Line: 404 to 404  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

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/fstdecl.h> if forward declaration of the public OpenFst
classes is needed.) 
Line: 1 to 1  

 
Line: 422 to 422  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

 
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: 1 to 1  

 
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/fstdecl.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/fstdecl.h> if forward declaration of the public OpenFst
classes is needed.)
As an alternative interface, there are shelllevel commands in the installation  
Deleted:  
< <  As an alternative interface, there are shelllevel commands in the installation bin directory that operate on file representations of FSTs. The commandline flag help will give usage information.  
Example FST  
Line: 16 to 20  
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 noninfinite 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 noninfinite
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 shelllevel. 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 shelllevel. 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 noncommercial 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 noncommercial 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 librarydefault 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 librarydefault Weight type) cat >text.fst <  
$ cat >isyms.txt <<EOF  
Line: 59 to 106  
EOF  
Changed:  
< <  You may use any string for a label; you may use any nonnegative 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 nonnegative 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 nonnegative 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() => nonfinal. 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() => nonfinal. Weight weight = fst.Final(i); # Iterates over the FSTs states. for (StateIterator # Iterates over state i's arcs. for (ArcIterator # 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  
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  
> >  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  
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  
Changed:  
< <  Delayed Fsts have constant timeclass 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 timeclass 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 shelllevel 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 shelllevel 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:  
 
Line: 208 to 313  
Example Use: FST Application  
Changed:  
< <  One of the most useful finitestate 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 finitestate 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  
 
Changed:  
< < 
 
> > 
 
 
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:  
< < 
 
> > 
 
 
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  
> >  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  
From the shelllevel, the FST arc type can be specified to fstcompile with the arc_type flag; StdArc is the default. 
Line: 1 to 1  

 
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/fstdecl.h> if forward declaration of the public OpenFst
classes is needed.)
As an alternative interface, there are shelllevel commands in the installation  
> >  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/fstdecl.h> if forward declaration of the public OpenFst classes is needed.)  
Added:  
> >  As an alternative interface, there are shelllevel commands in the installation bin directory that operate on file representations of FSTs. The commandline flag help will give usage information.  
Example FST  
Line: 20 to 16  
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 noninfinite
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 noninfinite 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 shelllevel. 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 shelllevel. 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 noncommercial 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 noncommercial 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 librarydefault Weight type) cat >text.fst <  
> >  # 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 librarydefault 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 nonnegative 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 nonnegative 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 nonnegative 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() => nonfinal. Weight weight = fst.Final(i); # Iterates over the FSTs states. for (StateIterator # Iterates over state i's arcs. for (ArcIterator # 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  
> >  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() => nonfinal. 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  
> >  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  
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  
Changed:  
< < 
Delayed Fsts have constant timeclass 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 timeclass 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 shelllevel 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 shelllevel 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:  
 
Line: 313 to 208  
Example Use: FST Application  
Changed:  
< <  One of the most useful finitestate 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 finitestate 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  
 
Changed:  
< < 
 
> > 
 
 
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:  
< < 
 
> > 
 
 
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  
> >  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  
From the shelllevel, the FST arc type can be specified to fstcompile with the arc_type flag; StdArc is the default. 
Line: 1 to 1  

 
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  
nonnegative 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 ShellThe 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

Line: 1 to 1  

 
Line: 291 to 291  
ComposeFst  
Added:  
> >  
Delayed Fsts have constant timeclass 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 
Line: 1 to 1  

 
Line: 392 to 392  
 
Changed:  
< < 
 
> > 
 
 
Line: 400 to 400  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Line: 418 to 418  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

 
Line: 126 to 126  
Once a binary FST is created, it can be used with the other shelllevel 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:  
< < 
 
> > 
 

Line: 1 to 1  

 
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:  
 
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 and LogWeight 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 predefined.
See here for all predefined weight types.  
From the shelllevel, the FST arc type can be specified to fstcompile with the arc_type flag; StdArc is the default. 
Line: 1 to 1  

 
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/fstdecl.h> if forward declaration of the public OpenFst
classes is needed.)  
As an alternative interface, there are shelllevel commands in the installation bin directory that operate on file representations of FSTs.  
Changed:  
< <  The commandline flag help will give usage information.  
> >  The commandline 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  
 
Changed:  
< < 
 
> > 
 
Line: 1 to 1  

 
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 librarydefault Weight type)  
> >  # unspecified weights default to 0.0 (for the librarydefault 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 nonnegative 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() => nonfinal.  
> >  # Get state i's final weight; if == Weight::Zero() => nonfinal.  
Weight weight = fst.Final(i);  
Changed:  
< <  
> >  
Changed:  
< <  # Iterates over the FSTs states.  
> >  # Iterates over the FSTs states.
 
for (StateIterator  
Changed:  
< <  
> >  
Changed:  
< <  # Iterates over state i's arcs.  
> >  # Iterates over state i's arcs.
 
for (ArcIterator  
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  
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 
Line: 1 to 1  

 
Line: 418 to 418  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

 
Line: 435 to 435  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

 
Line: 171 to 171  
Changed:  
< <  # Iterates over the FSTs states. .  
> >  # Iterates over the FSTs states.  
for (StateIterator  
Added:  
> >  
Added:  
> >  
# Iterates over state i's arcs.
for (ArcIterator  
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:  
< < 
 
> > 
 
Specific, nonabstract FSTs include these class templates:
 
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 and LogWeight 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 
Line: 1 to 1  

 
Line: 171 to 171  
Changed:  
< <  # Iterates over the FSTs states. See here for other traversal methods.  
> >  # Iterates over the FSTs states. .  
for (StateIterator  
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  
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 
Line: 1 to 1  

 
Line: 167 to 167  
# Get state i's final weight; if == Weight::Zero() => nonfinal. Weight weight = fst.Final(i);  
Added:  
> >  
Added:  
> >  
# Iterates over the FSTs states. See here for other traversal methods.
for (StateIterator 
Line: 1 to 1  

 
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 shelllevel commands in the installation  
Added:  
> >  The commandline 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  
 
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 shelllevel, 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 
Line: 1 to 1  

 
Line: 12 to 12  
As an alternative interface, there are shelllevel 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 FSTThe 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() => nonfinal. Weight weight = fst.Final(i);  
Changed:  
< <  # Iterates over the FSTs states.  
> >  # Iterates over the FSTs states. See here for other traversal methods.  
for (StateIterator  
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  
Line: 270 to 274  
 
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  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Added:  
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Added:  
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Line: 393 to 406  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Line: 420 to 437  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Added:  
> > 
 
Line: 469 to 487  
From the shelllevel, 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

Line: 1 to 1  

 
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 shelllevel commands in bin that operate on file representations of FSTs.  
> >  As an alternative interface, there are shelllevel 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() => nonfinal. Weight weight = fst.Final(i);  
# Iterates over the FSTs states.
for (StateIterator  
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  
 
Deleted:  
< < 
 
 
Added:  
> > 
 
 
Line: 455 to 469  
From the shelllevel, 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  

Line: 1 to 1  

 
Added:  
> >  
OpenFst Quick Tour
Finding and Using the Library 
Line: 1 to 1  

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: 
Line: 1 to 1  

OpenFst Quick Tour  
Line: 380 to 380  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

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: 
Line: 1 to 1  

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  
Line: 1 to 1  

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). 
Line: 1 to 1  

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 shelllevel commands in 
Line: 1 to 1  

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 shelllevel commands in bin that operate on file representations of FSTs. 
Line: 1 to 1  

OpenFst Quick Tour
Finding and Using the Library  
Changed:  
< <  The OpenFst Library is a C++ template library. To use it from C++, include lib/fstlibinl.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. 
Line: 1 to 1  

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

Line: 1 to 1  

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 nonnegative 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 ShellThe shelllevel 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:  
fstunaryop in.fst out.fst  
Added:  
> >  fstunaryop <in.fst >out.fst  
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  
Line: 1 to 1  

OpenFst Quick Tour  
Line: 374 to 374  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Line: 391 to 391  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 376 to 376  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 376 to 376  
 
Changed:  
< < 
 
> > 
 
 
Line: 384 to 384  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 396 to 396  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 386 to 386  
 
Changed:  
< < 
 
> > 
 
 
Line: 398 to 398  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 361 to 361  
 
Changed:  
< < 
 
> > 
 
 
Line: 371 to 371  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 400 to 400  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 14 to 14  
The following picture depicts a finite state transducer:  
Deleted:  
< <  
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 noninfinite  
Line: 122 to 120  
If the labels are represented as nonnegative integers in the text FST, then the symbol table files can be omitted. In any case, the internal representation of the FST is:  
Deleted:  
< <  
Deleted:  
< <  
Once a binary FST is created, it can be used with the other shelllevel programs. It can be loaded inside C++ with:  
Line: 341 to 337  
 
Changed:  
< < 
 
> > 
 
 
Line: 424 to 420  
The following are useful weight types:  
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 
Line: 1 to 1  

OpenFst Quick Tour  
Line: 355 to 355  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Line: 384 to 384  
 
Changed:  
< < 
 
> > 
 
 
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 shelllevel, the FST arc type can be specified to fstcompile with the arc_type flag; StdArc is the default.  
> >  From the shelllevel, the FST arc type can be specified to fstcompile with the arc_type flag; StdArc is the default.  
 MichaelRiley  25 May 2007 
Line: 1 to 1  

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 librarydefault Weight type)  
cat >text.fst <<EOF 0 1 a x .5 0 1 b y 1.5 
Line: 1 to 1  

OpenFst Quick Tour  
Line: 391 to 391  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 399 to 399  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 291 to 291  
One of the most useful finitestate 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 or more under Description for descriptive, graphical documentation; click on text under Usage for detailed code documentation.  
> >  Click on operation name for additional information.  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Added:  
> >  
FST Weights 
Line: 1 to 1  

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 shelllevel, the FST arc type can be specified to fstcompile with the arc_type flag.  
> >  From the shelllevel, the FST arc type can be specified to fstcompile with the arc_type flag; StdArc is the default.  
 MichaelRiley  25 May 2007 
Line: 1 to 1  

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

Line: 1 to 1  

OpenFst Quick Tour  
Line: 351 to 351  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 349 to 349  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 334 to 334  
Available FST OperationsClick on 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.  

Line: 1 to 1  

OpenFst Quick Tour  
Line: 337 to 337  
click on text under Usage for code documentation.
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
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 shelllevel, the FST arc type can be specified to fstcompile with the arc_type flag.  
> >  From the shelllevel, the FST arc type can be specified to fstcompile with the arc_type flag.  
 MichaelRiley  25 May 2007 
Line: 1 to 1  

OpenFst Quick Tour  
Line: 337 to 337  
click on text under Usage for code documentation.
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 383 to 383  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Line: 396 to 396  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

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() . 
Line: 1 to 1  

OpenFst Quick Tour  
Line: 362 to 362  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

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 or more under Description for descriptive, graphical documentation; click on text under Usage for code documentation.  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

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.  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

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:  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Line: 374 to 374  
 
Changed:  
< < 
 
> > 
 
 
Line: 403 to 403  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 381 to 381  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 337 to 337  
Click on text under Operation for a graphical example; click on text under Usage for more documentation:
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 370 to 370  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Added:  
> >  Finding and Using the Library
The OpenFst Library is a C++ template library. To use it from C++, include
As an alternative interface, there are shelllevel commands in  
Example FSTThe following picture depicts a finite state transducer:  
Line: 362 to 370  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 386 to 386  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour 
Line: 1 to 1  

OpenFst Quick Tour  
Line: 100 to 100  
You may use any string for a label; you may use any nonnegative 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  
 
Added:  
> > 
 
 
Line: 385 to 386  
 
Added:  
> > 
 
 
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 
Line: 1 to 1  

OpenFst Quick Tour  
Line: 329 to 329  
Click on text under Operation for a graphical example; click on text under Usage for more documentation:
 
Changed:  
< < 
 
> > 
 
 
Line: 341 to 341  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Line: 359 to 359  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Line: 371 to 371  
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 335 to 335  
 
Added:  
> > 
 
 
Deleted:  
< < 
 
 
Added:  
> > 
 
 
Line: 364 to 366  
 
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

OpenFst Quick Tour  
Line: 332 to 332  
 
Changed:  
< < 
 
> > 
 
