Difference: FstAdvancedUsage (1 vs. 70)

Revision 702018-08-15 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 273 to 273
 
  • Minimal caching: It is generally not possible to avoid all caching in such an FST since the cache is used to implement the arc iterators efficiently (creating an iterator computes and writes the state's arcs to the cache, iterating reads from the cache). However, if (1) gc is true, (2) gc_limit is 0, and (3) arcs iterators have been created (and then destroyed) only one state at a time, then only information for that state is cached and this case is especially optimized. This case is useful when states are not revisited (e.g. when a cached FST is simply being copied to a mutable FST).
Added:
>
>
The default cache storage (VectorCacheStore) maintains a vector of state pointers; the pointed to objects are GCed but the vector is never shrunk (see cache.h for other cache stores). Also delayed operations typically maintain an internal state table between the output state and the essential computation state (such as the corresponding state pair in composition) that is not GCed (since the consumer may come back to that state). As such, delayed operations that continue to grow in states will continue to consume memory. Some key operations, like ComposeFst, let you change the cache store and the state table to allow customization such as described here.
 

Command Line Flags

Revision 692018-04-27 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 307 to 307
 SetFlags(usage, &argc, &argv, true);
Changed:
<
<
In that case, the user can set his own flags as well, following the conventions in <fst/flags.h>.
>
>
In that case, the user can set his own flags as well, following the conventions in <fst/flags.h>.
  Alternatively, the user can process options in his own way and directly assign to any of the above global options if he wishes to modify their defaults.
Line: 389 to 389
 
PushLabelsComposeFilter Adds label-pushing to a lookahead composition filter doc

SequenceComposeFilter is the default composition filter. It can be changed by using the version of ComposeFst that accepts

Changed:
<
<
ComposeFstOptions. doc [bad link?]
>
>
ComposeFstOptions.
  See lookahead matchers for more information about composition with lookahead.
Line: 703 to 703
 
compactN_unweighted N=8,16,64 CompactFst<A, UnweightedCompactor<A>, uintN> Compact, immutable, unweighted FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted-fst.{a,so} doc
compact_unweighted_acceptor CompactFst<A, UnweightedAcceptorCompactor<A>> Compact, immutable, unweighted FSA (# arcs < 232) libfst.{a,so} doc
compactN_unweighted_acceptor, N=8,16,64 CompactFst<A, UnweightedAcceptorCompactor<A>, uintN> Compact, immutable, unweighted FSA (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted_acceptor-fst.{a,so} doc
Changed:
<
<
ilabel_lookahead {Std,Log}ILabelLookAheadFst Immutable FST with input label lookahead matcher fst/libfstlookahead.{a,so}, fst/ilabel_lookahead-fst.{a,so} doc [bad link?]
olabel_lookahead {Std,Log}OLabelLookAheadFst Immutable FST with output label lookahead matcher fst/libfstllookahead.{a,so}, fst/olabel_lookahead-fst.{a,so} doc [bad link?]
arc_lookahead {Std,Log}ArcLookAheadFst Immutable FST with arc lookahead matcher fst/libfstllookahead.{a,so}, fst/arc_lookahead-fst.{a,so} doc [bad link?]
ngram NGramFst<A> Immutable FST for n-gram language models fst/libfstngram.{a,so} doc [bad link?]
>
>
ilabel_lookahead {Std,Log}ILabelLookAheadFst Immutable FST with input label lookahead matcher fst/libfstlookahead.{a,so}, fst/ilabel_lookahead-fst.{a,so}  
olabel_lookahead {Std,Log}OLabelLookAheadFst Immutable FST with output label lookahead matcher fst/libfstllookahead.{a,so}, fst/olabel_lookahead-fst.{a,so}  
arc_lookahead {Std,Log}ArcLookAheadFst Immutable FST with arc lookahead matcher fst/libfstllookahead.{a,so}, fst/arc_lookahead-fst.{a,so}  
ngram NGramFst<A> Immutable FST for n-gram language models fst/libfstngram.{a,so} doc
  These FST types are registered for StdArc and LogArc in the indicated libraries. The user must register other types themselves for general FST I/O.
Line: 908 to 908
  The template Matcher<F> selects the pre-designated matcher for Fst type F; it is typically SortedMatcher. Composition uses this matcher by default. It can be changed by using the version of ComposeFst that accepts
Changed:
<
<
ComposeFstOptions doc [bad link?]. Note two matchers (usually of the same C++ type but different
>
>
ComposeFstOptions. Note two matchers (usually of the same C++ type but different
 MatchType) are used in composition -- one for each FST. Whether actual match queries are performed on one or both FSTs depends on the matcher constructor arguments, the matcher capabilities (queried by Type()) and composition itself.

An example access of an FST's matcher is here. An example use of a ρ matcher in composition is here; σ and φ matcher usage is similar.

Line: 1239 to 1239
 };
Changed:
<
<
A specific state tuple is a ComposeStateTuple doc [bad link?] that has data members StateId state_id1, StateId state_id2, and FilterState filter_state.
>
>
A specific state tuple is a ComposeStateTuple that has data members StateId state_id1, StateId state_id2, and FilterState filter_state.
  The following state tables are defined in the OpenFst library:
Line: 1265 to 1265
 
EraseableComposeStateTable ErasableStateTable Allows composition state tuple erasure doc

GenericComposeStateTable is the default composition state table. It can be changed by using the version of ComposeFst that accepts

Changed:
<
<
ComposeFstOptions. doc [bad link?]
>
>
ComposeFstOptions.
 

Symbol Tables

Line: 1311 to 1311
  A very general traversal method is to use:

Changed:
<
<
Visit(fst, visitor, queue); doc [bad link?]
>
>
Visit(fst, visitor, queue);
 

where the visitor object specfies the actions taken in the traversal while the state queue

Line: 1347 to 1347
  While a depth-first search can be implemented using Visit() with the LifoQueue(), it is often better to use the more specialized
Changed:
<
<
DFSVisit()doc [bad link?] in <fst/dfs-visit.h> since it is somewhat more space-efficient and the specialized visitor interface described there has additional funcitionality for a DFS.
>
>
DFSVisit() in <fst/dfs-visit.h> since it is somewhat more space-efficient and the specialized visitor interface described there has additional funcitionality for a DFS.
  Pre-defined FST visitors include:

Revision 682018-01-10 - KyleGorman

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 874 to 874
 
Name Description
SortedMatcher Binary search on sorted input doc
Changed:
<
<
RhoMatcher<M> ρ symbol handling; templated on underlying matcher doc
SigmaMatcher<M> σ symbol handling; templated on underlying matcher doc
PhiMatcher<M> φ symbol handling; templated on underlying matcher doc
>
>
RhoMatcher<M> ρ-symbol handling; templated on underlying matcher doc
SigmaMatcher<M> σ-symbol handling; templated on underlying matcher doc
PhiMatcher<M> φ-symbol handling; templated on underlying matcher doc
 
MultiEpsMatcher<M> Treats specified non-0 labels as non-consuming labels (in addition to 0) doc
ExplicitMatcher<M> Suppresses any implicit matches of non-consuming labels doc
Changed:
<
<
SortedMatcher requires the underlying Fst be sorted on the appropriate side. How it matches epsilons requires some explanation. Find(0) matches any epsilons on the underlying Fst explicitly (as if they were any other symbol) but also returns an
>
>
SortedMatcher expects the underlying FST be sorted on the appropriate side. Find(0) matches any epsilons on the underlying FST explicitly (as if they were any other symbol) but also returns an
 implicit self-loop (namely Arc(kNoLabel, 0, Weight::One(), current_state) if the match_type is MATCH_INPUT and
Changed:
<
<
Arc(0, kNoLabel, Weight::One(), current_state) if the match_type is MATCH_OUTPUT). In other words, an epsilon matches at every state without moving forward on the matched FST, a natural interpretation. This behavior implements epsilon-transition handling in composition, or, more generally, a 'non-consuming' match as with the MultiEpsMatcher (with kNoLabel informing composition of such a match). A
>
>
Arc(0, kNoLabel, Weight::One(), current_state) if the match_type is MATCH_OUTPUT); in other words, an epsilon matches at every state without moving forward on the matched FST, a natural interpretation. This behavior implements epsilon-transition handling in composition, or, more generally, a 'non-consuming' match as with the MultiEpsMatcher (with kNoLabel informing composition of such a match). A
 composition filter determines which of these epsilon transitions are ultimately accepted. Any matcher used in composition and related algorithms must implement these implicit matches for correct epsilon handling. In some other uses, the implicit matches may not be needed. In that case, an ExplicitMatcher can be used to conveniently suppress them (or the user can recognize the kNoLabel loop and skip them).

Revision 672018-01-05 - KyleGorman

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 1272 to 1272
  Symbol tables store the bijective mapping between textual labels, used in reading and printing an FST textual file, and their integer assignment, used in the FST's internal representation. Symbol tables are usually read in with fstcompile, can
Changed:
<
<
be stored by the FST, and used to print out the FST with fstprint,. Here are /amples of manipulating symbol tables directly:
>
>
be stored by the FST, and used to print out the FST with fstprint,. Here are a examples of symbol table manipulation:
 
// Various ways to reading symbol tables 
StdFst *fst = StdFst::Read("some.fst");

Revision 662016-03-29 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 179 to 179
 
GallicArc<A, S> A::Label A::StateId GallicWeight<A::Label, A::Weight, S>  
LexicographicArc<W1, W2> int int LexicographicWeight<W1, W2>  
LogArc int int LogWeight DONE
Added:
>
>
Log64Arc int int Log64Weight DONE
 
MinMaxArc int int MinMaxWeight  
PowerArc<A, n> int int PowerWeight<A::Weight, n>
ProductArc<W1, W2> int int ProductWeight<W1, W2>  
SignedLogArc int int SignedLogWeight DONE
Added:
>
>
SignedLog64Arc int int SignedLog64Weight DONE
 
SparsePowerArc<A> int int SparsePowerWeight<A::Weight>
StdArc int int TropicalWeight DONE
StringArc<S> int int StringWeight<int, S>  
Line: 1381 to 1383
 
Name Type
GallicWeight<L, W, S> ProductWeight<StringWeight<L, S>, W>
LogWeight LogWeightTpl<float>
Added:
>
>
Log64Weight LogWeightTpl<double>
 
MinMaxWeight MinMaxWeightTpl<float>
SignedLogWeight SignedLogWeightTpl<float>
Added:
>
>
SignedLog64Weight SignedLogWeightTpl<double>
 
TropicalWeight TropicalWeightTpl<float>

Composite weights, such as ProductWeight and LexicographicWeight, can use command line flags to control

Revision 652015-06-26 - KyleGorman

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

fst::script

Changed:
<
<
The OpenFst library offers an additional abstraction layer that facilitates scripting with FSTs of different arc types. It allows users to load FSTs and perform various operations on them without specifying the underlying FST arc types. This higher-level layer, found in the fst::script namespace, is somewhat less efficient, due to indirection, and in general exposes fewer methods and options. It is used principally to implement the shell-level FST commands and future Python bindings. From C++, users are encouraged in most circumstances to use the lower-level templated classes and operations for their efficiency and completeness. However, for simple 'glue' code that will work seamlessly with different arc types (esp. I/O), this higher-level might be appropriate. To use the scripting layer, include <fst/fstscript.h> in the installation include directory and link to libfstscript.{a,so} in the installation library directory. The extension libraries work similarly; e.g. for the FAR extension,
>
>
The OpenFst library offers an additional abstraction layer that facilitates scripting with FSTs of different arc types. It allows users to load FSTs and perform various operations on them without specifying the underlying FST arc types. This higher-level layer, found in the fst::script namespace, is somewhat less efficient, due to indirection, and in general exposes fewer methods and options. It is used principally to implement the shell-level FST commands and Python bindings. From C++, users are encouraged in most circumstances to use the lower-level templated classes and operations for their efficiency and completeness. However, for simple 'glue' code that will work seamlessly with different arc types (esp. I/O), this higher-level might be appropriate. To use the scripting layer, include <fst/fstscript.h> in the installation include directory and link to libfstscript.{a,so} in the installation library directory. The extension libraries work similarly; e.g. for the FAR extension,
 include <fst/extension/farscript.h> and link to lib/libfstfarscript.{a,so}.

In the following, all classes and methods mentioned are in the namespace fst::script.

Revision 632014-08-29 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 1379 to 1379
 
SignedLogWeight SignedLogWeightTpl<float>
TropicalWeight TropicalWeightTpl<float>
Changed:
<
<
Weight pairs, such as ProductWeight and LexicographicWeight, can use command line flags to control their textual formatting. FLAGS_fst_pair_weight_separator is printed between the weights (default: ","). FLAGS_fst_pair_parentheses (default: "") brackets the pair; if you create complex nested pairs (i.e., tuples), they may need to be printed with non-empty brackets (e.g. "()") to ensure correct parsing if read back in. These affect only textual (not binary) I/O.
>
>
Composite weights, such as ProductWeight and LexicographicWeight, can use command line flags to control their textual formatting. FLAGS_fst_weight_separator is printed between the weights (default: ","). FLAGS_fst_weight_parentheses (default: "") brackets the weight; if you create nested composite weights, they need to be printed with non-empty brackets (e.g. "()") to ensure correct parsing if read back in. These affect only textual (not binary) I/O.
  Additional weight information:

Revision 622014-04-23 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 874 to 874
  SortedMatcher requires the underlying Fst be sorted on the appropriate side. How it matches epsilons requires some explanation. Find(0) matches any epsilons on the underlying Fst explicitly (as if they were any other symbol) but also returns an implicit self-loop (namely Arc(kNoLabel, 0, Weight::One(), current_state) if the match_type is MATCH_INPUT and
Changed:
<
<
Arc(0, kNoLabel, Weight::One(), current_state) if the match_type is MATCH_OUTPUT). In other words, an epsilon matches at every state without moving forward on the matched FST, a natural interpretation. This behavior implements epsilon-transition handling in composition, or, more generally, a 'non-consuming' match (with kNoLabel informing composition that this is the case). A
>
>
Arc(0, kNoLabel, Weight::One(), current_state) if the match_type is MATCH_OUTPUT). In other words, an epsilon matches at every state without moving forward on the matched FST, a natural interpretation. This behavior implements epsilon-transition handling in composition, or, more generally, a 'non-consuming' match as with the MultiEpsMatcher (with kNoLabel informing composition of such a match). A
 composition filter determines which of these epsilon transitions are ultimately accepted. Any matcher used in composition and related algorithms must implement these implicit matches for correct epsilon handling. In some other uses, the implicit matches may not be needed. In that case, an ExplicitMatcher can be used to conveniently suppress them (or the user can recognize the kNoLabel loop and skip them).

Revision 612014-04-23 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 872 to 872
 
MultiEpsMatcher<M> Treats specified non-0 labels as non-consuming labels (in addition to 0) doc
ExplicitMatcher<M> Suppresses any implicit matches of non-consuming labels doc
Changed:
<
<
SortedMatcher requires the underlying Fst be sorted on the appropriate side. Find(0) matches any epsilons on the underlying Fst explicitly (as if they were any other symbol) but also returns an implicit self-loop (namely Arc(kNoLabel, 0, Weight::One(), current_state) if the match_type is MATCH_INPUT and Arc(0, kNoLabel, Weight::One(), current_state) if the match_type is MATCH_OUTPUT). This loop implements a 'non-consuming' match in composition (with kNoLabel informing composition that this is the case). A
>
>
SortedMatcher requires the underlying Fst be sorted on the appropriate side. How it matches epsilons requires some explanation. Find(0) matches any epsilons on the underlying Fst explicitly (as if they were any other symbol) but also returns an implicit self-loop (namely Arc(kNoLabel, 0, Weight::One(), current_state) if the match_type is MATCH_INPUT and Arc(0, kNoLabel, Weight::One(), current_state) if the match_type is MATCH_OUTPUT). In other words, an epsilon matches at every state without moving forward on the matched FST, a natural interpretation. This behavior implements epsilon-transition handling in composition, or, more generally, a 'non-consuming' match (with kNoLabel informing composition that this is the case). A
 composition filter determines which of these epsilon transitions are ultimately
Changed:
<
<
accepted. An ExplicitMatcher can be used to suppress these implicit matches on an underlying matcher.
>
>
accepted. Any matcher used in composition and related algorithms must implement these implicit matches for correct epsilon handling. In some other uses, the implicit matches may not be needed. In that case, an ExplicitMatcher can be used to conveniently suppress them (or the user can recognize the kNoLabel loop and skip them).
  The special symbols referenced above behave as described in this table:
Line: 903 to 900
  The template Matcher<F> selects the pre-designated matcher for Fst type F; it is typically SortedMatcher. Composition uses this matcher by default. It can be changed by using the version of ComposeFst that accepts
Changed:
<
<
ComposeFstOptions doc [bad link?]. Note two matchers (of the same C++ type but different
>
>
ComposeFstOptions doc [bad link?]. Note two matchers (usually of the same C++ type but different
 MatchType) are used in composition -- one for each FST. Whether actual match queries are performed on one or both FSTs depends on the matcher constructor arguments, the matcher capabilities (queried by Type()) and composition itself.

An example access of an FST's matcher is here. An example use of a ρ matcher in composition is here; σ and φ matcher usage is similar.

Revision 602014-04-23 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 850 to 850
  // Advance to next arc (when Done) void Next();
Added:
>
>
// Indicates preference for being the side used for matching // in composition/intersection. ssize_t Priority(StateId s);
  // Return matcher FST. const F& GetFst() const;
Line: 866 to 870
 
SigmaMatcher<M> σ symbol handling; templated on underlying matcher doc
PhiMatcher<M> φ symbol handling; templated on underlying matcher doc
MultiEpsMatcher<M> Treats specified non-0 labels as non-consuming labels (in addition to 0) doc
Added:
>
>
ExplicitMatcher<M> Suppresses any implicit matches of non-consuming labels doc
  SortedMatcher requires the underlying Fst be sorted on the appropriate side. Find(0) matches any epsilons on the underlying Fst explicitly (as if they were any other symbol) but also returns an
Line: 874 to 879
 Arc(0, kNoLabel, Weight::One(), current_state) if the match_type is MATCH_OUTPUT). This loop implements a 'non-consuming' match in composition (with kNoLabel informing composition that this is the case). A composition filter determines which of these epsilon transitions are ultimately
Changed:
<
<
accepted.
>
>
accepted. An ExplicitMatcher can be used to suppress these implicit matches on an underlying matcher.
  The special symbols referenced above behave as described in this table:
Line: 891 to 896
 (used for the ρ, σ, and φ matchers) or return it (used for epsilon-handling). The first case is equivalent to (but more efficient than) applying special-symbol removal prior to composition (c.f., epsilon removal). This case requires that only
Changed:
<
<
one of the FSTs in composition contain such symbols.
>
>
one of the FSTs in composition contain such symbols for any paired states.
 The second case requires well-defined semantics and that composition proper identify and handle any non-consuming symbols on each FST. (The result of Find(kNoLabel) identifies on one FST, while the matcher's returning a kNolabel loop handles the other, both described above.)

Revision 592013-11-27 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 901 to 901
 ComposeFstOptions doc [bad link?]. Note two matchers (of the same C++ type but different MatchType) are used in composition -- one for each FST. Whether actual match queries are performed on one or both FSTs depends on the matcher constructor arguments, the matcher capabilities (queried by Type()) and composition itself.
Changed:
<
<
An example use of a matcher is here and an example use of a ρ matcher in composition is here.
>
>
An example access of an FST's matcher is here. An example use of a ρ matcher in composition is here; σ and φ matcher usage is similar.
 

Mutable Fsts

Revision 572013-05-07 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 541 to 541
  public: // Construct an FstClass from a templated Fst, hiding its arc type. template<class Arc>
Changed:
<
<
explicit FstClass(Fst<Arc> *fst);
>
>
explicit FstClass(const Fst<Arc> &fst);
  // Copy constructor explicit FstClass(const FstClass &other); // Read an arc-templated Fst from disk, and return as an FstClass
Line: 580 to 580
  public: // Construct a MutableFstClass from some kind of MutableFst<> template<class Arc>
Changed:
<
<
explicit MutableFstClass(MutableFst<Arc> *fst);
>
>
explicit MutableFstClass(const MutableFst<Arc> &fst);
  // If your code knows the arc type of the underlying MutableFst<>, it // can use this method to extract a pointer to it. This pointer can be used // to change the underlying MutableFst<>

Revision 562012-06-01 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 695 to 695
 
ilabel_lookahead {Std,Log}ILabelLookAheadFst Immutable FST with input label lookahead matcher fst/libfstlookahead.{a,so}, fst/ilabel_lookahead-fst.{a,so} doc [bad link?]
olabel_lookahead {Std,Log}OLabelLookAheadFst Immutable FST with output label lookahead matcher fst/libfstllookahead.{a,so}, fst/olabel_lookahead-fst.{a,so} doc [bad link?]
arc_lookahead {Std,Log}ArcLookAheadFst Immutable FST with arc lookahead matcher fst/libfstllookahead.{a,so}, fst/arc_lookahead-fst.{a,so} doc [bad link?]
Added:
>
>
ngram NGramFst<A> Immutable FST for n-gram language models fst/libfstngram.{a,so} doc [bad link?]
  These FST types are registered for StdArc and LogArc in the indicated libraries. The user must register other types themselves for general FST I/O.

Revision 552012-05-13 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 24 to 24
  bool Done() const; // Current arc (when Done) const Arc& Value() const;
Changed:
<
<
// Advance to next arc (when Done)
>
>
// Advances to next arc (when Done)
  void Next();
Changed:
<
<
// Return current position
>
>
// Returns current position
  size_t Position();
Changed:
<
<
// Return to initial position
>
>
// Returns to initial position
  void Reset(); // Arc access by position
Changed:
<
<
void Seek(size_t pos);
>
>
void Seek(size_t pos); // Returns arc flags uint32 Flags() const; // Sets arc flags void SetFlags(uint32 flags, uint32 mask);
 };

Revision 542012-03-01 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 276 to 276
 
FLAGS_fst_compat_symbols bool true Require symbol tables to match when appropriate
FLAGS_fst_default_cache_gc bool true Enable garbage collection of cached Fsts
FLAGS_fst_default_cache_gc_limit int64 1048576 Byte size that triggers garbage collection of cached Fsts
Added:
>
>
FLAGS_fst_error_fatal bool true FST errors are fatal; o.w. return objects flagged as bad: e.g., FSTs - kError prop. true, FST weights - not a Member()
 
FLAGS_fst_field_separator string " \t" Set of characters used as a separator between printed fields
FLAGS_fst_weight_parentheses string "" Characters enclosing the first weight of a printed composite weight (and derived classes) to ensure proper I/O of nested composite weights; must have size 0 (none) or 2 (open and close parenthesis)
FLAGS_fst_weight_separator string "," Character separator between printed composite weights; must be a single character
Line: 284 to 285
 The first ensures the arguments of binary FST operations (e.g. composition) have compatible symbol tables (e..g output symbol table matches input symbol table for composition). The second two are used to control the caching of expanded state and arc information found in most
Changed:
<
<
delayed Fst classes; the default values should normally be satisfactory. The next is used in the textual representation of FSTs and symbol tables.
>
>
delayed Fst classes; the default values should normally be satisfactory. The next determines how errors are handled. The next is used in the textual representation of FSTs and symbol tables.
 The next two are used to control the text formating of ProductWeight and other weight tuples. The last is used to ensure that the properties of an FST have been correctly set; it is used for debugging only since it incurs considerable computational cost.
Line: 385 to 387
  See lookahead matchers for more information about composition with lookahead.
Added:
>
>

Error Handling

If FLAGS_fst_error_fatal is true (the default), then most serious errors cause program exit. The exception are most functions and methods that return NULL, a boolean, or NoWeight() on error - typically I/O and weight operations. If FLAGS_fst_error_fatal is false, then no operation is fatal. In that case, operations that return FSTs set the kError property bit. Otherwise classes have an Error() method that should be checked and functions return a boolean. It is intended that a sequence of operations preserve the kError property bit and the NoWeight(), so that it should suffice to check for error at the end of the sequence.
 

Expanded Fsts

Line: 999 to 1007
 if true and not set if false. The binary Fst properties are:

Name Description
Added:
>
>
kError an error was detected while constructing/using the FST
 
kExpanded Is an ExpandedFst
kMutable Is a MutableFst

Revision 532012-01-19 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 279 to 279
 
FLAGS_fst_field_separator string " \t" Set of characters used as a separator between printed fields
FLAGS_fst_weight_parentheses string "" Characters enclosing the first weight of a printed composite weight (and derived classes) to ensure proper I/O of nested composite weights; must have size 0 (none) or 2 (open and close parenthesis)
FLAGS_fst_weight_separator string "," Character separator between printed composite weights; must be a single character
Changed:
<
<
FLAGS_fst_verify_properties bool false Verify Fst properites are correctly set when queried
>
>
FLAGS_fst_verify_properties bool false Verify Fst properties are correctly set when queried
  The first ensures the arguments of binary FST operations (e.g. composition) have compatible symbol tables (e..g output symbol table matches input symbol table for composition).
Line: 1040 to 1040
 The call fst.Properties(mask, true) returns the stored property bits set in the mask bits after computing and updating any of those set in the mask that are unknown. It is a linear-time (O(V + E)) operation if any of the requested bits were unknown.
Added:
>
>
Note fstinfo --test_properties=false will show the stored properties bits, while fstinfo or fstinfo --test_properties=true will compute unknown properties.
 

State Iterators

Revision 522011-12-06 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 107 to 107
  class SomeArcMapper { public:
Added:
>
>
// Assumes input arc type is A and result arc type is B typedef A FromArc; typedef B ToArc;
  // Maps an arc type A to arc type B. B operator()(const A &arc); // Specifies final action the mapper requires (see above).
Line: 1068 to 1072
  An example use of a state iterator is shown here.
Added:
>
>

State Mappers

State mappers are function objects used by the StateMap operation to transform states. A state mapper has the form:

// This determines how symbol tables are mapped.  
enum MapSymbolsAction { 
  // Symbols should be cleared in the result by the map.  
  MAP_CLEAR_SYMBOLS,

  // Symbols should be copied from the input FST by the map. 
  MAP_COPY_SYMBOLS,

  // Symbols should not be modified in the result by the map itself.
  // (They may set by the mapper). 
  MAP_NOOP_SYMBOLS
};

class SomeStateMapper {
  public: 
   // Assumes input arc type is A and result arc type is B 
   typedef A FromArc;
   typedef B ToArc; 

   // Typical constructor. 
   SomeStateMapper(const Fst<A> &fst);
   // Required copy constructor that allows updating Fst argument.
   SomeStateMapper(const SomStateMapper &mapper, const Fst<A&ft; *fst = 0);

   // Specifies initial state of result
   B::StateId Start() const;
   // Specifies state's final weight in result
   B::Weight Final(B::StateId s) const;

   // These methods iterate through a state's arcs in result
   // Specifies state to iterator over 
   void SetState(B::StateId s); 
   // End of arcs? 
   bool Done() const; 
   // Current arc 
   const B &Value() const; 
   // Advance to next arc (when !Done) 
   void Next(); 

   // Specifies input symbol table action the mapper requires (see above). 
   MapSymbolsAction InputSymbolsAction() const;  
   // Specifies output symbol table action the mapper requires (see above). 
   MapSymbolsAction OutputSymbolsAction() const; 
   // This specifies the known properties of an Fst mapped by this
   // mapper. It takes as argument the input Fst's known properties   
   uint64 Properties(uint64 props) const;
};

The following state mappers are defined in the OpenFst library:

Name Description
ArcSumMapper Sums weights of identically labeled multi-arcs doc
ArcUniqueMapper Keeps one of identically labelled and weighted multi-arcs doc
IdentityStateMapper Maps to self doc

Another specialized state mapper is used to implement ArcSort.

 

State Queues

Revision 512011-12-05 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 69 to 69
 
InputEpsilonArcFilter Accept only arcs with input epsilons doc
OutputEpsilonArcFilter Accept only arcs with output epsilons doc
Added:
>
>

Arc Mappers

Arc mappers are function objects used by the ArcMap operation to transform arcs and/or final states. An arc mapper has the form:

// This determines how final weights are mapped.  
enum MapFinalAction { 
  // A final weight is mapped into a final weight. An error
  // is raised if this is not possible.  
  MAP_NO_SUPERFINAL,

  // A final weight is mapped to an arc to the superfinal state
  // when the result cannot be represented as a final weight.
  // The superfinal state will be added only if it is needed.  
  MAP_ALLOW_SUPERFINAL,

  // A final weight is mapped to an arc to the superfinal state
  // unless the result can be represented as a final weight of weight
  // Zero(). The superfinal state is always added (if the input is
  // not the empty Fst).  
  MAP_REQUIRE_SUPERFINAL
};

// This determines how symbol tables are mapped.  
enum MapSymbolsAction { 
  // Symbols should be cleared in the result by the map.  
  MAP_CLEAR_SYMBOLS,

  // Symbols should be copied from the input FST by the map. 
  MAP_COPY_SYMBOLS,

  // Symbols should not be modified in the result by the map itself.
  // (They may set by the mapper). 
  MAP_NOOP_SYMBOLS
};

class SomeArcMapper {
  public: 
   // Maps an arc type A to arc type B. 
   B operator()(const A &arc); 
   // Specifies final action the mapper requires (see above).
   // The mapper will be passed final weights as arcs of the
   // form A(0, 0, weight, kNoStateId). 
   MapFinalAction FinalAction() const; 
   // Specifies input symbol table action the mapper requires (see above). 
   MapSymbolsAction InputSymbolsAction() const;  
   // Specifies output symbol table action the mapper requires (see above). 
   MapSymbolsAction OutputSymbolsAction() const; 
   // This specifies the known properties of an Fst mapped by this
   // mapper. It takes as argument the input Fst's known properties   
   uint64 Properties(uint64 props) const;
};

The following arc mappers are defined in the OpenFst library:

Name Description
FromGallicMapper Extracts output label from gallic weight doc
IdentityArcMapper Maps to self doc
InvertWeightMapper Reciprocate all non-0 weights doc
PlusMapper Adds (⊕) a constant to all weights doc
QuantizeMapper Quantize all weights doc
ReverseWeightMapper Reverse all weights doc
RmWeightMapper Map all non-0 weights to 1 doc
SuperFinalMapper Redirects final states to new superfinal state doc
TimesMapper (Right) multiplies (⊗) a constant to all weights doc
ToGallicMapper Combines output label and weight into gallic weight doc
WeightConvertMapper Converts arc weight types (assuming appropriate WeightConvert class specialization), leaving labels and nextstates the same. doc

ToGallicMapper and FromGallicMapper are used, for example, to implement transducer determinization and minimization using weighted acceptor versions of these algorithms. Other specialized arc mappers are used to implement Decode, Encode, Invert, and Project.

 

Arcs

Line: 696 to 769
  The ilabel (olabel) lookahead matcher has some special properties. It currently requires that there are no input (output) epsilon cycles. Further, it may relabel the input (output) alphabet in order to efficiently look-ahead. The class LabelLookAheadRelabeler (in <fst/lookahead-matcher.h>) can be used to obtain the mapping between the old and new alphabet (LabelLookAheadRelabeler::RelabelPairs) and to relabel and sort other FSTs with the new labeling to make them suitable for composition (LabelLookAheadRelabeler::Relabel). Alternatively, the flag --save_relabel_ipairs (--save_relabel_opairs) can be used to send the relabeling information to a file when the lookahead matcher is constructed (useful when fstconvert is used to create a lookahead FST from the command line).
Deleted:
<
<

Mappers

Mappers are function objects used by the Map operation to transform arcs and/or final states. A mapper has the form:

// This determines how final weights are mapped.  
enum MapFinalAction { 
  // A final weight is mapped into a final weight. An error
  // is raised if this is not possible.  
  MAP_NO_SUPERFINAL,

  // A final weight is mapped to an arc to the superfinal state
  // when the result cannot be represented as a final weight.
  // The superfinal state will be added only if it is needed.  
  MAP_ALLOW_SUPERFINAL,

  // A final weight is mapped to an arc to the superfinal state
  // unless the result can be represented as a final weight of weight
  // Zero(). The superfinal state is always added (if the input is
  // not the empty Fst).  
  MAP_REQUIRE_SUPERFINAL
};

// This determines how symbol tables are mapped.  
enum MapSymbolsAction { 
  // Symbols should be cleared in the result by the map.  
  MAP_CLEAR_SYMBOLS,

  // Symbols should be copied from the input FST by the map. 
  MAP_COPY_SYMBOLS,

  // Symbols should not be modified in the result by the map itself.
  // (They may set by the mapper). 
  MAP_NOOP_SYMBOLS
};

class SomeMapper {
  public: 
   // Maps an arc type A to arc type B. 
   B operator()(const A &arc); 
   // Specifies final action the mapper requires (see above).
   // The mapper will be passed final weights as arcs of the
   // form A(0, 0, weight, kNoStateId). 
   MapFinalAction FinalAction() const; 
   // Specifies input symbol table action the mapper requires (see above). 
   MapSymbolsAction InputSymbolsAction() const;  
   // Specifies output symbol table action the mapper requires (see above). 
   MapSymbolsAction OutputSymbolsAction() const; 
   // This specifies the known properties of an Fst mapped by this
   // mapper. It takes as argument the input Fst's known properties   
   uint64 Properties(uint64 props) const;
};

The following mappers are defined in the OpenFst library:

Name Description
FromGallicMapper Extracts output label from gallic weight doc
IdentityMapper Maps to self doc [bad link?]
InvertWeightMapper Reciprocate all non-0 weights doc
PlusMapper Adds (⊕) a constant to all weights doc
QuantizeMapper Quantize all weights doc
ReverseWeightMapper Reverse all weights doc
RmWeightMapper Map all non-0 weights to 1 doc
SuperFinalMapper Redirects final states to new superfinal state doc
TimesMapper (Right) multiplies (⊗) a constant to all weights doc
ToGallicMapper Combines output label and weight into gallic weight doc

ToGallicMapper and FromGallicMapper are used, for example, to implement transducer determinization and minimization using weighted acceptor versions of these algorithms. Other specialized mappers are used to implement Decode, Encode, Invert, and Project.

 

Revision 502011-03-30 - AntoineAmarilli

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

Base Fsts

Changed:
<
<
Every Fst doc must specify an initial state, the final weights, arc and epsilon counts per states, an Fst type name, the Fst's properties, how to copy, read and write the Fst, and the input and output symbol tables (if any). In particular, the base Fst class has the interface:
>
>
Every Fst doc must specify an initial state, the final weights, arc and epsilon counts per states, an Fst type name, the Fst's properties, how to copy, read and write the Fst, and the input and output symbol tables (if any). In particular, the base Fst class has the interface:
 
template <class A>

Revision 492011-02-01 - MichaelRiley

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

fst::script

Changed:
<
<
The OpenFst library offers an additional abstraction layer that facilitates scripting with FSTs of different arc types. It allows users to load FSTs and perform various operations on them without specifying the underlying FST arc types. This higher-level layer, found in the fst::script namespace, is somewhat less efficient, due to indirection, and in general exposes fewer methods and options. It is used principally to implement the shell-level FST commands and future Python bindings. From C++, users are encouraged in most circumstances to use the lower-level templated classes and operations for their efficiency and completeness. However, for simple 'glue' code that will work seamlessly with different arc types (esp. I/O), this higher-level might be appropriate. To use the scripting layer, include <fst/fstscript.h> in the installation include directory and link to libfstscript.{a,so} in the installation library directory. The extension libraries work similarly; e.g. for the FAR extension, include <fst/extension/farscript.h> and link to lib/libfstfarscript.{a,so}.
>
>
The OpenFst library offers an additional abstraction layer that facilitates scripting with FSTs of different arc types. It allows users to load FSTs and perform various operations on them without specifying the underlying FST arc types. This higher-level layer, found in the fst::script namespace, is somewhat less efficient, due to indirection, and in general exposes fewer methods and options. It is used principally to implement the shell-level FST commands and future Python bindings. From C++, users are encouraged in most circumstances to use the lower-level templated classes and operations for their efficiency and completeness. However, for simple 'glue' code that will work seamlessly with different arc types (esp. I/O), this higher-level might be appropriate. To use the scripting layer, include <fst/fstscript.h> in the installation include directory and link to libfstscript.{a,so} in the installation library directory. The extension libraries work similarly; e.g. for the FAR extension, include <fst/extension/farscript.h> and link to lib/libfstfarscript.{a,so}.
  In the following, all classes and methods mentioned are in the namespace fst::script.

Class Overview

Changed:
<
<
At FST script level, the Fst class template hierarchy is partially mirrored with a template-free FstClass hierarchy. For example, these classes are defined:
>
>
At FST script level, the Fst<Arc> class template hierarchy is partially mirrored with a template-free FstClass hierarchy. For example, these classes are defined:
 

FstClass


Line: 555 to 555
 

Operations

In general, many of the operations that are implemented for the underlying templated FSTs are implemented for instances of

Changed:
<
<
FstClass, sometimes with modified option lists. Check <fst/fstscript.h>.
>
>
FstClass, sometimes with modified option lists. Check <fst/fstscript.h>.
 

Example

Line: 577 to 577
 ArcSort(input, OLABEL_COMPARE); ArcSort(model, ILABEL_COMPARE); // Container for composition result.
Changed:
<
<
VectorFstClass result(input->ArcType());
>
>
VectorFstClass result(input->ArcType());
 // Create the composed FST. Compose(*input, *model, &result); // Just keeps the output labels.
Line: 590 to 590
 The following non-abstract FST types with file representations are defined in the OpenFst library:

Name Usage Description Registered
Changed:
<
<
vector VectorFst General-purpose mutable FST libfst.{a,so} doc
const ConstFst General-purpose expanded, immutable FST (# arcs < 232) libfst.{a,so} doc
constN, N=8,16,64 ConstFst<A, uintN> General-purpose expanded, immutable FST (# arcs < 2N) fst/libfstconst.{a,so}, fst/constN-fst.so doc
compact_string CompactFst<A, StringCompactor> Compact, immutable, unweighted, string FST (# arcs < 232) libfst.{a,so} doc
compactN_string, N=8,16,64 CompactFst<A, StringCompactor, uintN> Compact, immutable, unweighted string FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN-fst.{a,so} doc
compact_weighted_string CompactFst<A, WeightedStringCompactor> Compact, immutable, weighted, string FST (# arcs < 232) libfst.{a,so} doc
compactN_weighted_string, N=8,16,64 CompactFst<A, WeightedStringCompactor, uintN> Compact, immutable, weighted, string FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_weighted-fst.{a,so} doc
compact_acceptor CompactFst<A, AcceptorCompactor> Compact, immutable, weighted FSA (# arcs < 232) libfst.{a,so} doc
compactN_acceptor, N=8,16,64 CompactFst<A, AcceptorCompactor, uintN> Compact, immutable, weighted FSA (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_acceptor-fst.{a,so} doc
compact_unweighted CompactFst<A, UnweightedCompactor> Compact, immutable, unweighted FST (# arcs < 232) libfst.{a,so} doc
compactN_unweighted N=8,16,64 CompactFst<A, UnweightedCompactor, uintN> Compact, immutable, unweighted FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted-fst.{a,so} doc
compact_unweighted_acceptor CompactFst<A, UnweightedAcceptorCompactor> Compact, immutable, unweighted FSA (# arcs < 232) libfst.{a,so} doc
compactN_unweighted_acceptor, N=8,16,64 CompactFst<A, UnweightedAcceptorCompactor, uintN> Compact, immutable, unweighted FSA (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted_acceptor-fst.{a,so} doc
>
>
vector VectorFst<A> General-purpose mutable FST libfst.{a,so} doc
const ConstFst<A> General-purpose expanded, immutable FST (# arcs < 232) libfst.{a,so} doc
constN, N=8,16,64 ConstFst<A, uintN> General-purpose expanded, immutable FST (# arcs < 2N) fst/libfstconst.{a,so}, fst/constN-fst.so doc
compact_string CompactFst<A, StringCompactor<A>> Compact, immutable, unweighted, string FST (# arcs < 232) libfst.{a,so} doc
compactN_string, N=8,16,64 CompactFst<A, StringCompactor<A>, uintN> Compact, immutable, unweighted string FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN-fst.{a,so} doc
compact_weighted_string CompactFst<A, WeightedStringCompactor<A>> Compact, immutable, weighted, string FST (# arcs < 232) libfst.{a,so} doc
compactN_weighted_string, N=8,16,64 CompactFst<A, WeightedStringCompactor<A>, uintN> Compact, immutable, weighted, string FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_weighted-fst.{a,so} doc
compact_acceptor CompactFst<A, AcceptorCompactor<A>> Compact, immutable, weighted FSA (# arcs < 232) libfst.{a,so} doc
compactN_acceptor, N=8,16,64 CompactFst<A, AcceptorCompactor<A>, uintN> Compact, immutable, weighted FSA (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_acceptor-fst.{a,so} doc
compact_unweighted CompactFst<A, UnweightedCompactor<A>> Compact, immutable, unweighted FST (# arcs < 232) libfst.{a,so} doc
compactN_unweighted N=8,16,64 CompactFst<A, UnweightedCompactor<A>, uintN> Compact, immutable, unweighted FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted-fst.{a,so} doc
compact_unweighted_acceptor CompactFst<A, UnweightedAcceptorCompactor<A>> Compact, immutable, unweighted FSA (# arcs < 232) libfst.{a,so} doc
compactN_unweighted_acceptor, N=8,16,64 CompactFst<A, UnweightedAcceptorCompactor<A>, uintN> Compact, immutable, unweighted FSA (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted_acceptor-fst.{a,so} doc
 
ilabel_lookahead {Std,Log}ILabelLookAheadFst Immutable FST with input label lookahead matcher fst/libfstlookahead.{a,so}, fst/ilabel_lookahead-fst.{a,so} doc [bad link?]
olabel_lookahead {Std,Log}OLabelLookAheadFst Immutable FST with output label lookahead matcher fst/libfstllookahead.{a,so}, fst/olabel_lookahead-fst.{a,so} doc [bad link?]
arc_lookahead {Std,Log}ArcLookAheadFst Immutable FST with arc lookahead matcher fst/libfstllookahead.{a,so}, fst/arc_lookahead-fst.{a,so} doc [bad link?]
Line: 619 to 619
 Non-abstract FST types without file representations include the on-the-fly Fst operations and the following:

Name Description
Changed:
<
<
EditFst Wraps an ExpandedFst as a MutableFst, sharing non-mutated components. doc
>
>
EditFst<A> Wraps an ExpandedFst as a MutableFst, sharing non-mutated components. doc
  You can convert to a non-abstract FST Type F<A> by calling its F<A>(const Fst<A> &) constructor from C++ or the fstconvert -fst_type=Fname shell-level command (when there is a file representation).
Line: 1176 to 1176
 
// Various ways to reading symbol tables 
StdFst *fst = StdFst::Read("some.fst");

Changed:
<
<
SymbolTable *isyms = fst->InputSymbolTable(); SymbolTable *osyms = fst->OutputSymbolTable();
>
>
SymbolTable *isyms = fst->InputSymbolTable(); SymbolTable *osyms = fst->OutputSymbolTable();
  SymbolTable *syms = SymbolTable::ReadText("some.syms"); // Adding and accessing symbols and keys
Changed:
<
<
syms->AddSymbol("kumquat", 7); int64 key = syms->Find("kumquat"); string symbol = syms->Find(7);
>
>
syms->AddSymbol("kumquat", 7); int64 key = syms->Find("kumquat"); string symbol = syms->Find(7);
  // Various ways of writing symbol tables
Changed:
<
<
fst->SetInputSymbols(isyms); fst->SetOutputSymbols(osyms); fst->Write("some.fst"):
>
>
fst->SetInputSymbols(isyms); fst->SetOutputSymbols(osyms); fst->Write("some.fst"):
 
Changed:
<
<
syms->WriteText("some.syms");
>
>
syms->WriteText("some.syms");
 

Line: 1229 to 1229
  SomeVisitor(T *return_data); // Invoked before visit
Changed:
<
<
void InitVisit(const Fst &fst);
>
>
void InitVisit(const Fst<Arc> &fst);
  // Invoked when state discovered (2nd arg is visitation root) bool InitState(StateId s, StateId root); // Invoked when arc to white/undiscovered state examined

Revision 482010-12-01 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 1097 to 1097
 
AutoQueue Automatically-selected from Fst properties doc
FifoQueue First-In, first-Out doc
LifoQueue Last-In, first-Out doc
Changed:
<
<
NaturalAStarQueue A* (under natural order with provided estimate) Recent changes
NaturalPruneQueue Pruning meta-queue (within provided threshold under natural order) Recent changes
>
>
NaturalAStarQueue A* (under natural order with provided estimate) doc
NaturalPruneQueue Pruning meta-queue (within provided threshold under natural order) doc
 
NaturalShortestFirstQueue Priority (least weight under natural order) doc
SccQueue Component graph top-ordered meta-queue doc
StateOrderQueue State-ID ordered doc

Revision 472010-11-24 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 1097 to 1097
 
AutoQueue Automatically-selected from Fst properties doc
FifoQueue First-In, first-Out doc
LifoQueue Last-In, first-Out doc
Added:
>
>
NaturalAStarQueue A* (under natural order with provided estimate) Recent changes
NaturalPruneQueue Pruning meta-queue (within provided threshold under natural order) Recent changes
NaturalShortestFirstQueue Priority (least weight under natural order) doc
 
SccQueue Component graph top-ordered meta-queue doc
Deleted:
<
<
ShortestFirstQueue Priority (least weight) doc
 
StateOrderQueue State-ID ordered doc
TopOrderQueue Topologically ordered doc

Revision 462010-10-19 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 94 to 94
 The following arc types are defined in the OpenFst library:

Name Label Type State ID Type Weight Type Registered
Added:
>
>
ExpectationArc<A, W> int int ExpectationWeight<A::Weight, W>
 
GallicArc<A, S> A::Label A::StateId GallicWeight<A::Label, A::Weight, S>  
LexicographicArc<W1, W2> int int LexicographicWeight<W1, W2>  
LogArc int int LogWeight DONE
MinMaxArc int int MinMaxWeight  
Changed:
<
<
PowerArc<W, n> int int PowerWeight<W, n>
>
>
PowerArc<A, n> int int PowerWeight<A::Weight, n>
 
ProductArc<W1, W2> int int ProductWeight<W1, W2>  
Added:
>
>
SignedLogArc int int SignedLogWeight DONE
SparsePowerArc<A> int int SparsePowerWeight<A::Weight>
 
StdArc int int TropicalWeight DONE
StringArc<S> int int StringWeight<int, S>  
Line: 1261 to 1264
 The following basic weight templates are defined in the OpenFst library:

Semiring Name Set
(Plus)

(Times)
0
(Zero)
1
(One)
Notes
Added:
>
>
Expectation ExpectationWeight<W1, W2> W1 X W2 W1 X ⊕W2 expectation (0W1,0W2) (1W1,0W2)   doc
 
Lexicographic LexicographicWeight<W1, W2> W1 X W2 min W1 X ⊗W2 (0W1,0W2) (1W1,1W2) min: lexicographic order w.r.t.
W1 and W2 natural orders
doc
Log LogWeightTpl<T> [-∞, ∞] -log(e-x + e-y) + 0 T: floating point doc
MinMax MinMaxWeightTpl<T> [-∞, ∞] min max -∞ T: floating point doc
Power PowerWeight<W, n> Wn Wn Wn 0Wn 1Wn   doc
Product ProductWeight<W1, W2> W1 X W2 W1 X ⊕W2 W1 X ⊗W2 (0W1,0W2) (1W1,1W2)   doc
Added:
>
>
SignedLog SignedLogWeightTpl<T> {-1,1} X [-∞, ∞] signed_log (*,+) (1, ∞) (1, 0) T: floating point doc
SparsePower SparsePowerWeight<W> Wn Wn Wn 0Wn 1Wn n: arbitrary doc
 
String StringWeight<L, STRING_LEFT> L* ∪ {∞} longest com. prefix ε L: signed integral doc
  StringWeight<L, STRING_RIGHT> L* ∪ {∞} longest com. suffix ε L: signed integral doc
Tropical TropicalWeightTpl<T> [-∞, ∞] min + 0 T: floating point doc
Line: 1276 to 1282
 
GallicWeight<L, W, S> ProductWeight<StringWeight<L, S>, W>
LogWeight LogWeightTpl<float>
MinMaxWeight MinMaxWeightTpl<float>
Added:
>
>
SignedLogWeight SignedLogWeightTpl<float>
 
TropicalWeight TropicalWeightTpl<float>

Weight pairs, such as ProductWeight and LexicographicWeight, can use command line flags to control

Revision 452010-09-03 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 600 to 600
 
compactN_unweighted N=8,16,64 CompactFst<A, UnweightedCompactor, uintN> Compact, immutable, unweighted FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted-fst.{a,so} doc
compact_unweighted_acceptor CompactFst<A, UnweightedAcceptorCompactor> Compact, immutable, unweighted FSA (# arcs < 232) libfst.{a,so} doc
compactN_unweighted_acceptor, N=8,16,64 CompactFst<A, UnweightedAcceptorCompactor, uintN> Compact, immutable, unweighted FSA (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted_acceptor-fst.{a,so} doc
Changed:
<
<
ilabel_lookahead {Std,Log}ILabelLookAheadFst Immutable FST with input label lookahead matcher fst/libfstlookahead.{a,so}, fst/ilabel_lookahead-fst.{a,so} doc [bad link?]
olabel_lookahead {Std,Log}OLabelLookAheadFst Immutable FST with output label lookahead matcher fst/libfstllookahead.{a,so}, fst/olabel_lookahead-fst.{a,so} doc [bad link?]
arc_lookahead {Std,Log}ArcLookAheadFst Immutable FST with arc lookahead matcher fst/libfstllookahead.{a,so}, fst/arc_lookahead-fst.{a,so} doc [bad link?]
>
>
ilabel_lookahead {Std,Log}ILabelLookAheadFst Immutable FST with input label lookahead matcher fst/libfstlookahead.{a,so}, fst/ilabel_lookahead-fst.{a,so} doc [bad link?]
olabel_lookahead {Std,Log}OLabelLookAheadFst Immutable FST with output label lookahead matcher fst/libfstllookahead.{a,so}, fst/olabel_lookahead-fst.{a,so} doc [bad link?]
arc_lookahead {Std,Log}ArcLookAheadFst Immutable FST with arc lookahead matcher fst/libfstllookahead.{a,so}, fst/arc_lookahead-fst.{a,so} doc [bad link?]
  These FST types are registered for StdArc and LogArc in the indicated libraries. The user must register other types themselves for general FST I/O.

Revision 442010-09-03 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 600 to 600
 
compactN_unweighted N=8,16,64 CompactFst<A, UnweightedCompactor, uintN> Compact, immutable, unweighted FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted-fst.{a,so} doc
compact_unweighted_acceptor CompactFst<A, UnweightedAcceptorCompactor> Compact, immutable, unweighted FSA (# arcs < 232) libfst.{a,so} doc
compactN_unweighted_acceptor, N=8,16,64 CompactFst<A, UnweightedAcceptorCompactor, uintN> Compact, immutable, unweighted FSA (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted_acceptor-fst.{a,so} doc
Changed:
<
<
ilabel_lookahead {Std,Log}ILabelLookAheadFst Immutable FST with input label lookahead matcher fst/libfstlookahead.{a,so}, fst/ilabel_lookahead-fst.{a,so}  
olabel_lookahead {Std,Log}OLabelLookAheadFst Immutable FST with output label lookahead matcher fst/libfstllookahead.{a,so}, fst/olabel_lookahead-fst.{a,so}  
arc_lookahead {Std,Log}ArcLookAheadFst Immutable FST with arc lookahead matcher fst/libfstllookahead.{a,so}, fst/arc_lookahead-fst.{a,so}  
>
>
ilabel_lookahead {Std,Log}ILabelLookAheadFst Immutable FST with input label lookahead matcher fst/libfstlookahead.{a,so}, fst/ilabel_lookahead-fst.{a,so} doc [bad link?]
olabel_lookahead {Std,Log}OLabelLookAheadFst Immutable FST with output label lookahead matcher fst/libfstllookahead.{a,so}, fst/olabel_lookahead-fst.{a,so} doc [bad link?]
arc_lookahead {Std,Log}ArcLookAheadFst Immutable FST with arc lookahead matcher fst/libfstllookahead.{a,so}, fst/arc_lookahead-fst.{a,so} doc [bad link?]
  These FST types are registered for StdArc and LogArc in the indicated libraries. The user must register other types themselves for general FST I/O.

Revision 432010-09-03 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 98 to 98
 
LexicographicArc<W1, W2> int int LexicographicWeight<W1, W2>  
LogArc int int LogWeight DONE
MinMaxArc int int MinMaxWeight  
Changed:
<
<
PowerArc<W, n> Recent changes int int PowerWeight<W, n>
>
>
PowerArc<W, n> int int PowerWeight<W, n>
 
ProductArc<W1, W2> int int ProductWeight<W1, W2>  
StdArc int int TropicalWeight DONE
StringArc<S> int int StringWeight<int, S>  
Line: 196 to 196
 
FLAGS_fst_compat_symbols bool true Require symbol tables to match when appropriate
FLAGS_fst_default_cache_gc bool true Enable garbage collection of cached Fsts
FLAGS_fst_default_cache_gc_limit int64 1048576 Byte size that triggers garbage collection of cached Fsts
Changed:
<
<
FLAGS_fst_field_separator Recent changes string " \t" Set of characters used as a separator between printed fields
FLAGS_fst_weight_parentheses Recent changes string "" Characters enclosing the first weight of a printed composite weight (and derived classes) to ensure proper I/O of nested composite weights; must have size 0 (none) or 2 (open and close parenthesis)
FLAGS_fst_weight_separator Recent changes string "," Character separator between printed composite weights; must be a single character
>
>
FLAGS_fst_field_separator string " \t" Set of characters used as a separator between printed fields
FLAGS_fst_weight_parentheses string "" Characters enclosing the first weight of a printed composite weight (and derived classes) to ensure proper I/O of nested composite weights; must have size 0 (none) or 2 (open and close parenthesis)
FLAGS_fst_weight_separator string "," Character separator between printed composite weights; must be a single character
 
FLAGS_fst_verify_properties bool false Verify Fst properites are correctly set when queried

The first ensures the arguments of binary FST operations (e.g. composition) have compatible symbol tables (e..g output symbol table matches

Line: 224 to 224
 Alternatively, the user can process options in his own way and directly assign to any of the above global options if he wishes to modify their defaults.

Changed:
<
<

Composition Filters Recent changes

>
>

Composition Filters

  A composition filter determines which matches are allowed to proceed in composition. The basic filters handle correct epsilon matching. In particular, they ensure that redundant epsilon paths, which would be incorrect with non-idempotent weights, are not created. More generally, composition filters can be used to block or modify composition paths for efficiency or other purposes usually working in tandem with specialized matchers. Their interface is:
Line: 364 to 364
  To avoid code bloat in a given program, registering arc types, in particular, should be used sparingly.
Changed:
<
<

Script Registration Recent changes

>
>

Script Registration

  In the above examples, the user provided the arc type as a template parameter. However, the call:
Line: 402 to 402
  To avoid code bloat in a given program, registering arc types should be used sparingly.
Changed:
<
<

FST Dynamic Shared Objects Recent changes

>
>

FST Dynamic Shared Objects

  The examples above show how users can modify programs to be able to read new arc and Fst types. However, it would not be ideal to have to do so for all the distribution binaries or other existing programs. Instead, this can be done more easily with dynamic shared objects (DSOs).
Line: 434 to 434
 be able to read the new arc type with existing programs.

Changed:
<
<

fst::script Recent changes

>
>

fst::script

 The OpenFst library offers an additional abstraction layer that facilitates scripting with FSTs of different arc types. It allows users to load FSTs and perform various operations on them without specifying the underlying FST arc types. This higher-level layer, found in the fst::script namespace, is somewhat less efficient, due to indirection, and in general exposes fewer methods and options. It is used principally to implement the shell-level FST commands and future Python bindings. From C++, users are encouraged in most circumstances to use the lower-level templated classes and operations for their efficiency and completeness. However, for simple 'glue' code that will work seamlessly with different arc types (esp. I/O), this higher-level might be appropriate. To use the scripting layer, include <fst/fstscript.h> in the installation include directory and link to libfstscript.{a,so} in the installation library directory. The extension libraries work similarly; e.g. for the FAR extension, include <fst/extension/farscript.h> and link to lib/libfstfarscript.{a,so}.
Line: 587 to 587
 The following non-abstract FST types with file representations are defined in the OpenFst library:

Name Usage Description Registered
Changed:
<
<
vector VectorFst General-purpose mutable FST libfst.{a,so}  
const ConstFst General-purpose expanded, immutable FST (# arcs < 232) libfst.{a,so}  
constN, N=8,16,64 ConstFst<A, uintN> General-purpose expanded, immutable FST (# arcs < 2N) fst/libfstconst.{a,so}, fst/constN-fst.so Recent changes
compact_string CompactFst<A, StringCompactor> Compact, immutable, unweighted, string FST (# arcs < 232) libfst.{a,so}  
compactN_string, N=8,16,64 CompactFst<A, StringCompactor, uintN> Compact, immutable, unweighted string FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN-fst.{a,so} Recent changes
compact_weighted_string CompactFst<A, WeightedStringCompactor> Compact, immutable, weighted, string FST (# arcs < 232) libfst.{a,so}  
compactN_weighted_string, N=8,16,64 CompactFst<A, WeightedStringCompactor, uintN> Compact, immutable, weighted, string FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_weighted-fst.{a,so} Recent changes
compact_acceptor CompactFst<A, AcceptorCompactor> Compact, immutable, weighted FSA (# arcs < 232) libfst.{a,so}  
compactN_acceptor, N=8,16,64 CompactFst<A, AcceptorCompactor, uintN> Compact, immutable, weighted FSA (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_acceptor-fst.{a,so} Recent changes
compact_unweighted CompactFst<A, UnweightedCompactor> Compact, immutable, unweighted FST (# arcs < 232) libfst.{a,so}  
compactN_unweighted N=8,16,64 CompactFst<A, UnweightedCompactor, uintN> Compact, immutable, unweighted FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted-fst.{a,so} Recent changes
compact_unweighted_acceptor CompactFst<A, UnweightedAcceptorCompactor> Compact, immutable, unweighted FSA (# arcs < 232) libfst.{a,so}  
compactN_unweighted_acceptor, N=8,16,64 CompactFst<A, UnweightedAcceptorCompactor, uintN> Compact, immutable, unweighted FSA (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted_acceptor-fst.{a,so} Recent changes
ilabel_lookahead {Std,Log}ILabelLookAheadFst Immutable FST with input label lookahead matcher fst/libfstlookahead.{a,so}, fst/ilabel_lookahead-fst.{a,so} Recent changes
olabel_lookahead {Std,Log}OLabelLookAheadFst Immutable FST with output label lookahead matcher fst/libfstllookahead.{a,so}, fst/olabel_lookahead-fst.{a,so} Recent changes
arc_lookahead {Std,Log}ArcLookAheadFst Immutable FST with arc lookahead matcher fst/libfstllookahead.{a,so}, fst/arc_lookahead-fst.{a,so} Recent changes
>
>
vector VectorFst General-purpose mutable FST libfst.{a,so} doc
const ConstFst General-purpose expanded, immutable FST (# arcs < 232) libfst.{a,so} doc
constN, N=8,16,64 ConstFst<A, uintN> General-purpose expanded, immutable FST (# arcs < 2N) fst/libfstconst.{a,so}, fst/constN-fst.so doc
compact_string CompactFst<A, StringCompactor> Compact, immutable, unweighted, string FST (# arcs < 232) libfst.{a,so} doc
compactN_string, N=8,16,64 CompactFst<A, StringCompactor, uintN> Compact, immutable, unweighted string FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN-fst.{a,so} doc
compact_weighted_string CompactFst<A, WeightedStringCompactor> Compact, immutable, weighted, string FST (# arcs < 232) libfst.{a,so} doc
compactN_weighted_string, N=8,16,64 CompactFst<A, WeightedStringCompactor, uintN> Compact, immutable, weighted, string FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_weighted-fst.{a,so} doc
compact_acceptor CompactFst<A, AcceptorCompactor> Compact, immutable, weighted FSA (# arcs < 232) libfst.{a,so} doc
compactN_acceptor, N=8,16,64 CompactFst<A, AcceptorCompactor, uintN> Compact, immutable, weighted FSA (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_acceptor-fst.{a,so} doc
compact_unweighted CompactFst<A, UnweightedCompactor> Compact, immutable, unweighted FST (# arcs < 232) libfst.{a,so} doc
compactN_unweighted N=8,16,64 CompactFst<A, UnweightedCompactor, uintN> Compact, immutable, unweighted FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted-fst.{a,so} doc
compact_unweighted_acceptor CompactFst<A, UnweightedAcceptorCompactor> Compact, immutable, unweighted FSA (# arcs < 232) libfst.{a,so} doc
compactN_unweighted_acceptor, N=8,16,64 CompactFst<A, UnweightedAcceptorCompactor, uintN> Compact, immutable, unweighted FSA (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted_acceptor-fst.{a,so} doc
ilabel_lookahead {Std,Log}ILabelLookAheadFst Immutable FST with input label lookahead matcher fst/libfstlookahead.{a,so}, fst/ilabel_lookahead-fst.{a,so}  
olabel_lookahead {Std,Log}OLabelLookAheadFst Immutable FST with output label lookahead matcher fst/libfstllookahead.{a,so}, fst/olabel_lookahead-fst.{a,so}  
arc_lookahead {Std,Log}ArcLookAheadFst Immutable FST with arc lookahead matcher fst/libfstllookahead.{a,so}, fst/arc_lookahead-fst.{a,so}  
  These FST types are registered for StdArc and LogArc in the indicated libraries. The user must register other types themselves for general FST I/O.
Line: 610 to 610
 Note the libraries other than libfst.{a,so} are extensions that must be built and linked separately (to avoid code bloat). For each of these, there is a version that contains all variants of that extension (e.g., lib/libfstconst.{a,so}) that should be specified at compile time . Alternatively, there are per variant libraries (e.g. lib/constN-fst.so) that will be dynamically loaded into any binary compiled with OpenFst when the LD_LIBRARY_PATH (or equivalent) includes e.g. /usr/local/lib/fst.
Added:
>
>
Note Std{I,O}LabelLookAheadFst, despite its name, uses the LogWeight::Plus() during weight-pushing in composition (only). This choice was made for reasons of efficiency and convenience; it can circumvented by changing the accumulator doc used.
 Non-abstract FST types without file representations include the on-the-fly Fst operations and the following:

Name Description
Changed:
<
<
EditFst Wraps an ExpandedFst as a MutableFst, sharing non-mutated components. Recent changes
>
>
EditFst Wraps an ExpandedFst as a MutableFst, sharing non-mutated components. doc
  You can convert to a non-abstract FST Type F<A> by calling its F<A>(const Fst<A> &) constructor from C++ or the fstconvert -fst_type=Fname shell-level command (when there is a file representation).

Changed:
<
<

Look-Ahead Matchers Recent changes

>
>

Look-Ahead Matchers

  Lookahead matchers are matchers that implement additional functionality to allow looking-ahead along paths. When used in combination with a lookahead filter in composition, this can result in considerable efficiency improvements. See Cyril Allauzen, Michael Riley and Johan Schalkwyk,
Line: 823 to 825
  void Next(); // Return matcher FST.
Changed:
<
<
const F& GetFst() const; Recent changes
>
>
const F& GetFst() const;
  // This specifies the known Fst properties as viewed from this // matcher. It takes as argument the input Fst's known properties.

Revision 422010-09-02 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 296 to 296
 
SequenceComposeFilter Requires epsilons on FST1 to be read before epsilons on FST2 doc
AltSequenceComposeFilter Requires epsilons on FST2 to be read before epsilons on FST1 doc
MatchComposeFilter Requires epsilons on FST1 to be matched with epsilons on FST2 whenever possible doc
Changed:
<
<
LookAheadComposeFilter Used with a lookahead matcher to block non-coaccessible paths Recent changes
PushWeightsComposeFilter Adds weight-pushing to a lookahead composition filter Recent changes
PushLabelsComposeFilter Adds label-pushing to a lookahead composition filter Recent changes
>
>
LookAheadComposeFilter Used with a lookahead matcher to block non-coaccessible paths doc
PushWeightsComposeFilter Adds weight-pushing to a lookahead composition filter doc
PushLabelsComposeFilter Adds label-pushing to a lookahead composition filter doc
  SequenceComposeFilter is the default composition filter. It can be changed by using the version of ComposeFst that accepts ComposeFstOptions. doc [bad link?]
Line: 682 to 682
 The following lookahead matchers are defined in the OpenFst library:

Name Description
Changed:
<
<
ILabelLookAheadMatcher Look-ahead to first non-epsilon input label on a path Recent changes
OLabelLookAheadMatcher Look-ahead to first non-epsilon output label on a path Recent changes
ArcLookAheadmatcher Look-ahead to first transition on a path Recent changes
>
>
ILabelLookAheadMatcher Look-ahead to first non-epsilon input label on a path doc
OLabelLookAheadMatcher Look-ahead to first non-epsilon output label on a path doc
ArcLookAheadMatcher Look-ahead to first transition on a path doc
  There are FST types that are provided with these matchers. When these are used in composition, no special options need to be passed; the appropriate matcher and filter are selected automatically.
Line: 837 to 837
 
RhoMatcher<M> ρ symbol handling; templated on underlying matcher doc
SigmaMatcher<M> σ symbol handling; templated on underlying matcher doc
PhiMatcher<M> φ symbol handling; templated on underlying matcher doc
Changed:
<
<
MultiEpsMatcher<M> Treats specified non-0 labels as non-consuming labels (in addition to 0) Recent changes
>
>
MultiEpsMatcher<M> Treats specified non-0 labels as non-consuming labels (in addition to 0) doc
  SortedMatcher requires the underlying Fst be sorted on the appropriate side. Find(0) matches any epsilons on the underlying Fst explicitly (as if they were any other symbol) but also returns an
Line: 1262 to 1262
 
Lexicographic LexicographicWeight<W1, W2> W1 X W2 min W1 X ⊗W2 (0W1,0W2) (1W1,1W2) min: lexicographic order w.r.t.
W1 and W2 natural orders
doc
Log LogWeightTpl<T> [-∞, ∞] -log(e-x + e-y) + 0 T: floating point doc
MinMax MinMaxWeightTpl<T> [-∞, ∞] min max -∞ T: floating point doc
Changed:
<
<
Power PowerWeight<W, n> Wn Wn Wn 0Wn 1Wn   Recent changes
>
>
Power PowerWeight<W, n> Wn Wn Wn 0Wn 1Wn   doc
 
Product ProductWeight<W1, W2> W1 X W2 W1 X ⊕W2 W1 X ⊗W2 (0W1,0W2) (1W1,1W2)   doc
String StringWeight<L, STRING_LEFT> L* ∪ {∞} longest com. prefix ε L: signed integral doc
  StringWeight<L, STRING_RIGHT> L* ∪ {∞} longest com. suffix ε L: signed integral doc

Revision 412010-08-28 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 686 to 686
 
OLabelLookAheadMatcher Look-ahead to first non-epsilon output label on a path Recent changes
ArcLookAheadmatcher Look-ahead to first transition on a path Recent changes
Changed:
<
<
There are FST types that are provided with these matchers.

When used in composition, no special options need to be passed; the appropriate matcher and filter are

>
>
There are FST types that are provided with these matchers. When these are used in composition, no special options need to be passed; the appropriate matcher and filter are
 selected automatically.

The ilabel (olabel) lookahead matcher has some special properties. It currently requires that there are no input (output) epsilon cycles. Further, it may relabel the input (output) alphabet in order to efficiently look-ahead. The class LabelLookAheadRelabeler (in <fst/lookahead-matcher.h>) can be used to obtain the mapping between the old and new alphabet (LabelLookAheadRelabeler::RelabelPairs) and to relabel and sort other FSTs with the new labeling to make them suitable for composition (LabelLookAheadRelabeler::Relabel). Alternatively, the flag --save_relabel_ipairs (--save_relabel_opairs) can be used to send the relabeling information to a file when the lookahead matcher is constructed (useful when fstconvert is used to create a lookahead FST from the command line).

Revision 402010-08-27 - MichaelRiley

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

fst::script Recent changes

The OpenFst library offers an additional abstraction layer that facilitates scripting with FSTs of different arc types. It allows users to load FSTs and perform various operations on them without specifying the underlying FST arc types. This higher-level layer, found in the fst::script namespace, is somewhat less efficient, due to indirection, and in general exposes fewer methods and options. It is used principally to implement the shell-level FST commands and future Python bindings. From C++, users are encouraged in most circumstances to use the lower-level templated classes and operations for their efficiency and completeness. However, for simple 'glue' code that will work seamlessly with different arc types (esp. I/O), this higher-level might be appropriate. To use the scripting layer, include <fst/fstscript.h> in the installation include directory and link to libfstscript.{a,so} in the installation library directory. The extension libraries work similarly; e.g. for the FAR extension,
Changed:
<
<
include <fst/extension/farscript.h> and link to lib/libfarscript.{a,so}.
>
>
include <fst/extension/farscript.h> and link to lib/libfstfarscript.{a,so}.
  In the following, all classes and methods mentioned are in the namespace fst::script.

Revision 392010-08-12 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 615 to 615
 
Name Description
EditFst Wraps an ExpandedFst as a MutableFst, sharing non-mutated components. Recent changes
Added:
>
>
 You can convert to a non-abstract FST Type F<A> by calling its F<A>(const Fst<A> &) constructor from C++ or the fstconvert -fst_type=Fname shell-level command (when there is a file representation).

Line: 685 to 686
 
OLabelLookAheadMatcher Look-ahead to first non-epsilon output label on a path Recent changes
ArcLookAheadmatcher Look-ahead to first transition on a path Recent changes
Changed:
<
<
There are FST types that are provided with these matchers. When used in composition, no special options need to be passed; the appropriate matcher and filter are
>
>
There are FST types that are provided with these matchers.

When used in composition, no special options need to be passed; the appropriate matcher and filter are

 selected automatically.
Added:
>
>
The ilabel (olabel) lookahead matcher has some special properties. It currently requires that there are no input (output) epsilon cycles. Further, it may relabel the input (output) alphabet in order to efficiently look-ahead. The class LabelLookAheadRelabeler (in <fst/lookahead-matcher.h>) can be used to obtain the mapping between the old and new alphabet (LabelLookAheadRelabeler::RelabelPairs) and to relabel and sort other FSTs with the new labeling to make them suitable for composition (LabelLookAheadRelabeler::Relabel). Alternatively, the flag --save_relabel_ipairs (--save_relabel_opairs) can be used to send the relabeling information to a file when the lookahead matcher is constructed (useful when fstconvert is used to create a lookahead FST from the command line).
 

Mappers

Revision 382010-08-12 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 615 to 615
 
Name Description
EditFst Wraps an ExpandedFst as a MutableFst, sharing non-mutated components. Recent changes
Changed:
<
<
You can convert to a given FST Type F by calling its F(const &Fst) constructor from C++ or fstconvert -fst_type=F shell-level command.
>
>
You can convert to a non-abstract FST Type F<A> by calling its F<A>(const Fst<A> &) constructor from C++ or the fstconvert -fst_type=Fname shell-level command (when there is a file representation).
 

Look-Ahead Matchers Recent changes

Revision 362010-08-11 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 687 to 687
 
OLabelLookAheadMatcher Look-ahead to first non-epsilon output label on a path Recent changes
ArcLookAheadmatcher Look-ahead to first transition on a path Recent changes
Changed:
<
<
There are FST types that are provided with these matchers. If used in composition, no special options need be passed; the appropriate matcher and filter is used automatically.
>
>
There are FST types that are provided with these matchers. When used in composition, no special options need to be passed; the appropriate matcher and filter are selected automatically.
 

Mappers

Revision 352010-08-11 - MichaelRiley

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

Composition Filters Recent changes

A composition filter determines which matches are allowed to proceed in composition. The basic filters handle correct epsilon matching. In particular, they ensure

Changed:
<
<
that redundant epsilon paths, which would be incorrect with non-idempotent weights, are not created. More generally, composition filters can be used to block or modify composition paths for efficiency or other purposes usually working in tandem with specialized matchers. Their interface is:
>
>
that redundant epsilon paths, which would be incorrect with non-idempotent weights, are not created. More generally, composition filters can be used to block or modify composition paths for efficiency or other purposes usually working in tandem with specialized matchers. Their interface is:
 
template <class M1, M2>
class SomeComposeFilter {

Line: 437 to 437
 

fst::script Recent changes

Changed:
<
<
The OpenFst library offers an additional abstraction layer that facilitates scripting with FSTs of different arc types. It allows users to load FSTs and perform various operations on them without specifying the underlying FST arc types. This higher-level layer, found in the fst::script namespace, is somewhat less efficient, due to indirection, and in general exposes far fewer methods and options. It is used principally to implement the shell-level FST commands and future Python bindings. From C++, users are encouraged in most circumstances to use the lower-level templated classes and operations for their efficiency and completeness. However, for simple 'glue' code that will work seamlessly with different arc types (esp. I/O), this higher-level might be appropriate. To use the scripting layer, include <fst/fstscript.h> in the installation include directory and link to libfstscript.so in the installation library directory.
>
>
The OpenFst library offers an additional abstraction layer that facilitates scripting with FSTs of different arc types. It allows users to load FSTs and perform various operations on them without specifying the underlying FST arc types. This higher-level layer, found in the fst::script namespace, is somewhat less efficient, due to indirection, and in general exposes fewer methods and options. It is used principally to implement the shell-level FST commands and future Python bindings. From C++, users are encouraged in most circumstances to use the lower-level templated classes and operations for their efficiency and completeness. However, for simple 'glue' code that will work seamlessly with different arc types (esp. I/O), this higher-level might be appropriate. To use the scripting layer, include <fst/fstscript.h> in the installation include directory and link to libfstscript.{a,so} in the installation library directory. The extension libraries work similarly; e.g. for the FAR extension, include <fst/extension/farscript.h> and link to lib/libfarscript.{a,so}.
  In the following, all classes and methods mentioned are in the namespace fst::script.
Line: 590 to 591
 
Name Usage Description Registered
vector VectorFst General-purpose mutable FST libfst.{a,so}  
const ConstFst General-purpose expanded, immutable FST (# arcs < 232) libfst.{a,so}  
Changed:
<
<
constN, N=8,16,64 ConstFst<A, uintN> General-purpose expanded, immutable FST (# arcs < 2N) fst/constN-fst.{a,so} Recent changes
>
>
constN, N=8,16,64 ConstFst<A, uintN> General-purpose expanded, immutable FST (# arcs < 2N) fst/libfstconst.{a,so}, fst/constN-fst.so Recent changes
 
compact_string CompactFst<A, StringCompactor> Compact, immutable, unweighted, string FST (# arcs < 232) libfst.{a,so}  
Changed:
<
<
compactN_string, N=8,16,64 CompactFst<A, StringCompactor, uintN> Compact, immutable, unweighted string FST (# arcs < 2N) fst/compactN-fst.{a,so} Recent changes
>
>
compactN_string, N=8,16,64 CompactFst<A, StringCompactor, uintN> Compact, immutable, unweighted string FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN-fst.{a,so} Recent changes
 
compact_weighted_string CompactFst<A, WeightedStringCompactor> Compact, immutable, weighted, string FST (# arcs < 232) libfst.{a,so}  
Changed:
<
<
compactN_weighted_string, N=8,16,64 CompactFst<A, WeightedStringCompactor, uintN> Compact, immutable, weighted, string FST (# arcs < 2N) fst/compactN_weighted-fst.{a,so} Recent changes
>
>
compactN_weighted_string, N=8,16,64 CompactFst<A, WeightedStringCompactor, uintN> Compact, immutable, weighted, string FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_weighted-fst.{a,so} Recent changes
 
compact_acceptor CompactFst<A, AcceptorCompactor> Compact, immutable, weighted FSA (# arcs < 232) libfst.{a,so}  
Changed:
<
<
compactN_acceptor, N=8,16,64 CompactFst<A, AcceptorCompactor, uintN> Compact, immutable, weighted FSA (# arcs < 2N) fst/compactN_acceptor-fst.{a,so} Recent changes
>
>
compactN_acceptor, N=8,16,64 CompactFst<A, AcceptorCompactor, uintN> Compact, immutable, weighted FSA (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_acceptor-fst.{a,so} Recent changes
 
compact_unweighted CompactFst<A, UnweightedCompactor> Compact, immutable, unweighted FST (# arcs < 232) libfst.{a,so}  
Changed:
<
<
compactN_unweighted N=8,16,64 CompactFst<A, UnweightedCompactor, uintN> Compact, immutable, unweighted FST (# arcs < 2N) fst/compactN_unweighted-fst.{a,so} Recent changes
>
>
compactN_unweighted N=8,16,64 CompactFst<A, UnweightedCompactor, uintN> Compact, immutable, unweighted FST (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted-fst.{a,so} Recent changes
 
compact_unweighted_acceptor CompactFst<A, UnweightedAcceptorCompactor> Compact, immutable, unweighted FSA (# arcs < 232) libfst.{a,so}  
Changed:
<
<
compactN_unweighted_acceptor, N=8,16,64 CompactFst<A, UnweightedAcceptorCompactor, uintN> Compact, immutable, unweighted FSA (# arcs < 2N) fst/compactN_unweighted_acceptor-fst.{a,so} Recent changes
ilabel_lookahead {Std,Log}ILabelLookAheadFst Immutable FST with input label lookahead matcher fst/ilabel_lookahead-fst.{a,so} Recent changes
olabel_lookahead {Std,Log}OLabelLookAheadFst Immutable FST with output label lookahead matcher fst/olabel_lookahead-fst.{a,so} Recent changes
arc_lookahead {Std,Log}ArcLookAheadFst Immutable FST with arc lookahead matcher fst/arc_lookahead-fst.{a,so} Recent changes
>
>
compactN_unweighted_acceptor, N=8,16,64 CompactFst<A, UnweightedAcceptorCompactor, uintN> Compact, immutable, unweighted FSA (# arcs < 2N) fst/libfstcompact.{a,so}, fst/compactN_unweighted_acceptor-fst.{a,so} Recent changes
ilabel_lookahead {Std,Log}ILabelLookAheadFst Immutable FST with input label lookahead matcher fst/libfstlookahead.{a,so}, fst/ilabel_lookahead-fst.{a,so} Recent changes
olabel_lookahead {Std,Log}OLabelLookAheadFst Immutable FST with output label lookahead matcher fst/libfstllookahead.{a,so}, fst/olabel_lookahead-fst.{a,so} Recent changes
arc_lookahead {Std,Log}ArcLookAheadFst Immutable FST with arc lookahead matcher fst/libfstllookahead.{a,so}, fst/arc_lookahead-fst.{a,so} Recent changes
  These FST types are registered for StdArc and LogArc in the indicated libraries. The user must register other types themselves for general FST I/O.
Changed:
<
<
Note the libraries other than libfst.{a,so} are extensions that must be built separately (to avoid code bloat).
>
>
Note the libraries other than libfst.{a,so} are extensions that must be built and linked separately (to avoid code bloat). For each of these, there is a version that contains all variants of that extension (e.g., lib/libfstconst.{a,so}) that should be specified at compile time . Alternatively, there are per variant libraries (e.g. lib/constN-fst.so) that will be dynamically loaded into any binary compiled with OpenFst when the LD_LIBRARY_PATH (or equivalent) includes e.g. /usr/local/lib/fst.
  Non-abstract FST types without file representations include the on-the-fly Fst operations and the following:
Line: 617 to 620
 You can convert to a given FST Type F by calling its F(const &Fst) constructor from C++ or fstconvert -fst_type=F shell-level command.

Changed:
<
<

LookAhead Matchers Recent changes

>
>

Look-Ahead Matchers Recent changes

  Lookahead matchers are matchers that implement additional functionality to allow looking-ahead along paths. When used in combination with a lookahead filter in composition, this can result in considerable efficiency improvements. See Cyril Allauzen, Michael Riley and Johan Schalkwyk,
Line: 684 to 687
 
OLabelLookAheadMatcher Look-ahead to first non-epsilon output label on a path Recent changes
ArcLookAheadmatcher Look-ahead to first transition on a path Recent changes
Added:
>
>
There are FST types that are provided with these matchers. If used in composition, no special options need be passed; the appropriate matcher and filter is used automatically.
 

Mappers

Line: 823 to 829
  uint64 Properties(uint64 props) const; };
Changed:
<
<
The following matchers are defined in the OpenFst library (see also the lookahead matcher topic).
>
>
The following matchers are defined in the OpenFst library (see also the lookahead matcher topic).
 
Name Description
SortedMatcher Binary search on sorted input doc

Revision 342010-08-10 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 305 to 305
 SequenceComposeFilter is the default composition filter. It can be changed by using the version of ComposeFst that accepts ComposeFstOptions. doc [bad link?]
Added:
>
>
See lookahead matchers for more information about composition with lookahead.
 

Expanded Fsts

Line: 614 to 616
  You can convert to a given FST Type F by calling its F(const &Fst) constructor from C++ or fstconvert -fst_type=F shell-level command.
Added:
>
>
 

LookAhead Matchers Recent changes

Lookahead matchers are matchers that implement additional functionality to allow looking-ahead

Line: 1276 to 1279
 
Deleted:
<
<
-- MichaelRiley - 27 Feb 2009
  • ciaa10.pdf: CIAA 2010 paper on composition filters
 
Changed:
<
<
META FILEATTACHMENT attachment="ciaa10.pdf" attr="" comment="CIAA 2010 paper on composition filters" date="1280954866" name="ciaa10.pdf" path="ciaa10.pdf" size="189785" stream="ciaa10.pdf" tmpFilename="/var/tmp/CGItemp34564" user="CyrilAllauzen" version="1"
>
>
META FILEATTACHMENT attachment="ciaa10.pdf" attr="h" comment="CIAA 2010 paper on composition filters" date="1280954866" name="ciaa10.pdf" path="ciaa10.pdf" size="189785" stream="ciaa10.pdf" tmpFilename="/var/tmp/CGItemp34564" user="CyrilAllauzen" version="1"

Revision 332010-08-06 - MichaelRiley

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

OpenFst Advanced Usage

Below are a variety of topics covered in greater depth or of more specialized interest than found in the Quick Tour. Reading the

Changed:
<
<
Quick Tour first is recommended.//
>
>
Quick Tour first is recommended.
  Items marked with a Recent changes are changes in OpenFst-1.2 (as yet to be released).
Line: 616 to 616
 

LookAhead Matchers Recent changes

Changed:
<
<
Lookahead matchers are matchers that implement additional functionality to allow looking ahead along paths. When used in composition in combination with a lookahead filter, this can result in considerable efficiency improvements. See Cyril Allauzen, Michael Riley and Johan Schalkwyk,
>
>
Lookahead matchers are matchers that implement additional functionality to allow looking-ahead along paths. When used in combination with a lookahead filter in composition, this can result in considerable efficiency improvements. See Cyril Allauzen, Michael Riley and Johan Schalkwyk,
 "Filters for Efficient Composition of Weighted Finite-State Transducers", Proceedings of the Fifteenth International Conference on Implementation and Application of Automata, (CIAA 2010), Winnipeg, MB.

The matcher interface is augmented with the following methods:

Revision 322010-08-05 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 599 to 599
 
compactN_unweighted N=8,16,64 CompactFst<A, UnweightedCompactor, uintN> Compact, immutable, unweighted FST (# arcs < 2N) fst/compactN_unweighted-fst.{a,so} Recent changes
compact_unweighted_acceptor CompactFst<A, UnweightedAcceptorCompactor> Compact, immutable, unweighted FSA (# arcs < 232) libfst.{a,so}  
compactN_unweighted_acceptor, N=8,16,64 CompactFst<A, UnweightedAcceptorCompactor, uintN> Compact, immutable, unweighted FSA (# arcs < 2N) fst/compactN_unweighted_acceptor-fst.{a,so} Recent changes
Changed:
<
<
ilabel_lookahead ILabelLookAheadFst Has one (non-epsilon) input label lookahead matcher fst/ilabel_lookahead-fst.{a,so} Recent changes
olabel_lookahead OLabelLookAheadFst Has one (non-epsilon) output label lookahead matcher fst/olabel_lookahead-fst.{a,so} Recent changes
arc_lookahead ArcLookAheadFst Has one-transition lookahead matcher fst/arc_lookahead-fst.{a,so} Recent changes
>
>
ilabel_lookahead {Std,Log}ILabelLookAheadFst Immutable FST with input label lookahead matcher fst/ilabel_lookahead-fst.{a,so} Recent changes
olabel_lookahead {Std,Log}OLabelLookAheadFst Immutable FST with output label lookahead matcher fst/olabel_lookahead-fst.{a,so} Recent changes
arc_lookahead {Std,Log}ArcLookAheadFst Immutable FST with arc lookahead matcher fst/arc_lookahead-fst.{a,so} Recent changes
  These FST types are registered for StdArc and LogArc in the indicated libraries. The user must register other types themselves for general FST I/O.
Line: 612 to 612
 
Name Description
EditFst Wraps an ExpandedFst as a MutableFst, sharing non-mutated components. Recent changes
Changed:
<
<

LookAhead Matchers Work in progress, under construction

>
>
You can convert to a given FST Type F by calling its F(const &Fst) constructor from C++ or fstconvert -fst_type=F shell-level command.

LookAhead Matchers Recent changes

Lookahead matchers are matchers that implement additional functionality to allow looking ahead along paths. When used in composition in combination with a lookahead filter, this can result in considerable efficiency improvements. See Cyril Allauzen, Michael Riley and Johan Schalkwyk, "Filters for Efficient Composition of Weighted Finite-State Transducers", Proceedings of the Fifteenth International Conference on Implementation and Application of Automata, (CIAA 2010), Winnipeg, MB.

The matcher interface is augmented with the following methods:

template <class F>
class SomeLookAheadMatcher {                                                         
 public:
  typedef F FST;
  typedef F::Arc Arc;
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Label Label;
  typedef typename Arc::Weight Weight;

 // Required constructors.
 LookAheadMatcher(const F &fst, MatchType match_type);
 LookAheadMatcher(const LookAheadMatcher &matcher);
 
 Below are methods for looking ahead for a match to a label and
 more generally, to a rational set. Each returns false if there is
 definitely not a match and returns true if there possibly is a match

 // LABEL LOOKAHEAD: Can 'label' be read from the current matcher state
 // after possibly following epsilon transitions? 
 bool LookAheadLabel(Label label) const;

 // RATIONAL LOOKAHEAD: The next methods allow looking ahead for an
 // arbitrary rational set of strings, specified by an FST and a state
 // from which to begin the matching. If the lookahead FST is a
 // transducer, this looks on the side different from the matcher
 // 'match_type' (cf. composition).  

 // Are there paths P from 's' in the lookahead FST that can be read from
 // the cur. matcher state?  
 bool LookAheadFst(const Fst<Arc>& fst, StateId s);

 // Gives an estimate of the combined weight of the paths P in the
 // lookahead and matcher FSTs for the last call to LookAheadFst.
 // A trivial implementation returns Weight::One(). Non-trivial 
 // implementations are useful for weight-pushing in composition.  
 Weight LookAheadWeight() const;

 // Is there is a single non-epsilon arc found in the lookahead FST
 // that begins P (after possibly following any epsilons) in the last
 // call LookAheadFst? If so, return true and copy it to '*arc', o.w.
 // return false. A trivial implementation returns false. Non-trivial
 // implementations are useful for label-pushing in composition.  
 bool LookAheadPrefix(Arc *arc);

 // Optionally pre-specifies the lookahead FST that will be passed
 // to LookAheadFst() for possible precomputation. If copy is true,
 // then 'fst' is a copy of the FST used in the previous call to
 // this method (useful to avoid unnecessary updates).  
 void InitLookAheadFst(const Fst<Arc>& fst, bool copy = false);
};

The following lookahead matchers are defined in the OpenFst library:

Name Description
ILabelLookAheadMatcher Look-ahead to first non-epsilon input label on a path Recent changes
OLabelLookAheadMatcher Look-ahead to first non-epsilon output label on a path Recent changes
ArcLookAheadmatcher Look-ahead to first transition on a path Recent changes
 

Mappers

Revision 312010-08-05 - MichaelRiley

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

Base Fsts

Changed:
<
<
Every Fst doc must specify an initial state, the final weights, arc and epsilon counts per states, an Fst type name, the Fst's properties, how to copy, read and write the Fst, and the input and output symbol tables (if any). In particular, the base Fst class has the inteface:
>
>
Every Fst doc must specify an initial state, the final weights, arc and epsilon counts per states, an Fst type name, the Fst's properties, how to copy, read and write the Fst, and the input and output symbol tables (if any). In particular, the base Fst class has the interface:
 
template <class A>

Line: 225 to 225
  Alternatively, the user can process options in his own way and directly assign to any of the above global options if he wishes to modify their defaults.
Deleted:
<
<

Compact Fsts Work in progress, under construction

 

Composition Filters Recent changes

A composition filter determines which matches are allowed to proceed in composition. The basic filters handle correct epsilon matching. In particular, they ensure

Changed:
<
<
that redundant epsilon paths, which would be incorrect with non-idempotent weights, are not created. More generally, composition filters can be used to block or modify composition paths for efficiency or other purposes (see the lookahead topic) usually working in tandem with specialized matchers. Their interface is:
>
>
that redundant epsilon paths, which would be incorrect with non-idempotent weights, are not created. More generally, composition filters can be used to block or modify composition paths for efficiency or other purposes usually working in tandem with specialized matchers. Their interface is:
 
template <class M1, M2>
class SomeComposeFilter {

Line: 249 to 246
  typedef typename Arc::Weight Weight; // Required constructor. The filter is either passed composition matchers or constructs
Changed:
<
<
// them internally. This is done so the filter can possibly modify the result lookahead).
>
>
// them internally. This is done so the filter can possibly modify the result (useful e.g. with lookahead).
  SomeComposeFilter(const FST1 &fst1, const FST2 &fst2, M1 *matcher1 = 0, M2 *matcher2); // Return start state of filter. FilterState Start() const;
Line: 583 to 580
 Project(&result, PROJECT_OUTPUT);
Changed:
<
<

LookAhead Matchers and Fsts Work in progress, under construction

>
>

Fst Types

The following non-abstract FST types with file representations are defined in the OpenFst library:

Name Usage Description Registered
vector VectorFst General-purpose mutable FST libfst.{a,so}  
const ConstFst General-purpose expanded, immutable FST (# arcs < 232) libfst.{a,so}  
constN, N=8,16,64 ConstFst<A, uintN> General-purpose expanded, immutable FST (# arcs < 2N) fst/constN-fst.{a,so} Recent changes
compact_string CompactFst<A, StringCompactor> Compact, immutable, unweighted, string FST (# arcs < 232) libfst.{a,so}  
compactN_string, N=8,16,64 CompactFst<A, StringCompactor, uintN> Compact, immutable, unweighted string FST (# arcs < 2N) fst/compactN-fst.{a,so} Recent changes
compact_weighted_string CompactFst<A, WeightedStringCompactor> Compact, immutable, weighted, string FST (# arcs < 232) libfst.{a,so}  
compactN_weighted_string, N=8,16,64 CompactFst<A, WeightedStringCompactor, uintN> Compact, immutable, weighted, string FST (# arcs < 2N) fst/compactN_weighted-fst.{a,so} Recent changes
compact_acceptor CompactFst<A, AcceptorCompactor> Compact, immutable, weighted FSA (# arcs < 232) libfst.{a,so}  
compactN_acceptor, N=8,16,64 CompactFst<A, AcceptorCompactor, uintN> Compact, immutable, weighted FSA (# arcs < 2N) fst/compactN_acceptor-fst.{a,so} Recent changes
compact_unweighted CompactFst<A, UnweightedCompactor> Compact, immutable, unweighted FST (# arcs < 232) libfst.{a,so}  
compactN_unweighted N=8,16,64 CompactFst<A, UnweightedCompactor, uintN> Compact, immutable, unweighted FST (# arcs < 2N) fst/compactN_unweighted-fst.{a,so} Recent changes
compact_unweighted_acceptor CompactFst<A, UnweightedAcceptorCompactor> Compact, immutable, unweighted FSA (# arcs < 232) libfst.{a,so}  
compactN_unweighted_acceptor, N=8,16,64 CompactFst<A, UnweightedAcceptorCompactor, uintN> Compact, immutable, unweighted FSA (# arcs < 2N) fst/compactN_unweighted_acceptor-fst.{a,so} Recent changes
ilabel_lookahead ILabelLookAheadFst Has one (non-epsilon) input label lookahead matcher fst/ilabel_lookahead-fst.{a,so} Recent changes
olabel_lookahead OLabelLookAheadFst Has one (non-epsilon) output label lookahead matcher fst/olabel_lookahead-fst.{a,so} Recent changes
arc_lookahead ArcLookAheadFst Has one-transition lookahead matcher fst/arc_lookahead-fst.{a,so} Recent changes

These FST types are registered for StdArc and LogArc in the indicated libraries. The user must register other types themselves for general FST I/O. Note the libraries other than libfst.{a,so} are extensions that must be built separately (to avoid code bloat).

Non-abstract FST types without file representations include the on-the-fly Fst operations and the following:

Name Description
EditFst Wraps an ExpandedFst as a MutableFst, sharing non-mutated components. Recent changes

LookAhead Matchers Work in progress, under construction

 

Mappers

Line: 1157 to 1185
 
Lexicographic LexicographicWeight<W1, W2> W1 X W2 min W1 X ⊗W2 (0W1,0W2) (1W1,1W2) min: lexicographic order w.r.t.
W1 and W2 natural orders
doc
Log LogWeightTpl<T> [-∞, ∞] -log(e-x + e-y) + 0 T: floating point doc
MinMax MinMaxWeightTpl<T> [-∞, ∞] min max -∞ T: floating point doc
Changed:
<
<
Power Recent changes PowerWeight<W, n> Wn Wn Wn 0Wn 1Wn   doc
>
>
Power PowerWeight<W, n> Wn Wn Wn 0Wn 1Wn   Recent changes
 
Product ProductWeight<W1, W2> W1 X W2 W1 X ⊕W2 W1 X ⊗W2 (0W1,0W2) (1W1,1W2)   doc
String StringWeight<L, STRING_LEFT> L* ∪ {∞} longest com. prefix ε L: signed integral doc
  StringWeight<L, STRING_RIGHT> L* ∪ {∞} longest com. suffix ε L: signed integral doc

Revision 292010-08-04 - MichaelRiley

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

OpenFst Advanced Usage

Below are a variety of topics covered in greater depth or of more specialized interest than found in the Quick Tour. Reading the

Changed:
<
<
Quick Tour first is recommended.
>
>
Quick Tour first is recommended.//
  Items marked with a Recent changes are changes in OpenFst-1.2 (as yet to be released).
Line: 229 to 229
 

Compact Fsts Work in progress, under construction

Changed:
<
<

Composition Filters

>
>

Composition Filters Recent changes

  A composition filter determines which matches are allowed to proceed in composition. The basic filters handle correct epsilon matching. In particular, they ensure
Changed:
<
<
that redundant epsilon paths, which would be incorrect with non-idempotent weights, are not created. More generally, composition filters can be used to block or modify composition paths for efficiency or specialized purposes. Their interface is:
>
>
that redundant epsilon paths, which would be incorrect with non-idempotent weights, are not created. More generally, composition filters can be used to block or modify composition paths for efficiency or other purposes (see the lookahead topic) usually working in tandem with specialized matchers. Their interface is:
 
Changed:
<
<
template <class A>

>
>
template <class M1, M2>

 class SomeComposeFilter { public:
Changed:
<
<
typedef A Arc;
>
>
typedef typename M1::FST1 FST1; typedef typename M1::FST2 FST2; typedef typename FST1::Arc Arc; typedef ... FilterState; typedef ... Matcher1; typedef ... Matcher2;
  typedef ... FilterState;
Added:
>
>
typedef typename Arc::StateId StateId; typedef typename Arc::Weight Weight;
 
Changed:
<
<
// Required constructor. SomeComposeFilter(const Fst<A> &fst1, const Fst&ltA> &fst2);
>
>
// Required constructor. The filter is either passed composition matchers or constructs // them internally. This is done so the filter can possibly modify the result lookahead). SomeComposeFilter(const FST1 &fst1, const FST2 &fst2, M1 *matcher1 = 0, M2 *matcher2);
  // Return start state of filter. FilterState Start() const; // Specifies current composition state. void SetState(StateId s1, StateId s2, const FilterState &f);
Added:
>
>
Matcher2 *GetMatcher2();
  // Apply filter at current composition state to these transitions. // If an arc label to be matched is kNolabel, then that side does not consume a symbol.
Line: 257 to 267
  // (cf. superfinal transitions). The filter may modify its inputs, // e.g. for optimizations. void FilterFinal(Weight *final1, Weight *final2) const;
Added:
>
>
// Return resp matchers. Ownership stays with the filter. These // methods allow the filter to access and possibly modify // the composition matchers (useful e.g. with lookahead). Matcher1 *GetMatcher1();
 }; The filter's state is represented by the type SomeComposeFilter::FilterState and is stored in the composition
Line: 286 to 301
 
SequenceComposeFilter Requires epsilons on FST1 to be read before epsilons on FST2 doc
AltSequenceComposeFilter Requires epsilons on FST2 to be read before epsilons on FST1 doc
MatchComposeFilter Requires epsilons on FST1 to be matched with epsilons on FST2 whenever possible doc
Added:
>
>
LookAheadComposeFilter Used with a lookahead matcher to block non-coaccessible paths Recent changes
PushWeightsComposeFilter Adds weight-pushing to a lookahead composition filter Recent changes
PushLabelsComposeFilter Adds label-pushing to a lookahead composition filter Recent changes
  SequenceComposeFilter is the default composition filter. It can be changed by using the version of ComposeFst that accepts ComposeFstOptions. doc [bad link?]
Line: 699 to 717
  // Advance to next arc (when Done) void Next();
Added:
>
>
// Return matcher FST. const F& GetFst() const; Recent changes
  // This specifies the known Fst properties as viewed from this // matcher. It takes as argument the input Fst's known properties. uint64 Properties(uint64 props) const; };
Changed:
<
<
The following matchers are defined in the OpenFst library:
>
>
The following matchers are defined in the OpenFst library (see also the lookahead matcher topic).
 
Name Description
SortedMatcher Binary search on sorted input doc
RhoMatcher<M> ρ symbol handling; templated on underlying matcher doc
SigmaMatcher<M> σ symbol handling; templated on underlying matcher doc
PhiMatcher<M> φ symbol handling; templated on underlying matcher doc
Added:
>
>
MultiEpsMatcher<M> Treats specified non-0 labels as non-consuming labels (in addition to 0) Recent changes
  SortedMatcher requires the underlying Fst be sorted on the appropriate side. Find(0) matches any epsilons on the underlying Fst explicitly (as if they were any other symbol) but also returns an

Revision 282010-08-04 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 331 to 331
  writes and reads a defined Fst type (VectorFst) and arc type (Arc) to and from a file in a straight-forward way.
Changed:
<
<

Library Registration

>
>

Library Registration

  The call:
Line: 349 to 349
  To avoid code bloat in a given program, registering arc types, in particular, should be used sparingly.
Changed:
<
<

Script Registration Recent changes

>
>

Script Registration Recent changes

  In the above examples, the user provided the arc type as a template parameter. However, the call:
Line: 387 to 387
  To avoid code bloat in a given program, registering arc types should be used sparingly.
Changed:
<
<

FST Dynamic Shared Objects Recent changes

>
>

FST Dynamic Shared Objects Recent changes

  The examples above show how users can modify programs to be able to read new arc and Fst types. However, it would not be ideal to have to do so for all the distribution binaries or other existing programs. Instead, this can be done more easily with dynamic shared objects (DSOs).
Line: 419 to 419
 be able to read the new arc type with existing programs.

Changed:
<
<

fst::script Work in progress, under construction

The OpenFst library also includes some functionality to facilitate scripting with FSTs. These methods allow client programs to load FSTs and perform operations on them without specifying the underlying arc type of the FSTs. This higher level is somewhat less efficient, due to indirection, and in general exposes fewer options. Thus, its use should be restricted to simple scripting applications; more complicated code should use the lower-level operations templated on arc types. In the following, all classes and methods mentioned are in the namespace fst::script.
>
>

fst::script Recent changes

The OpenFst library offers an additional abstraction layer that facilitates scripting with FSTs of different arc types. It allows users to load FSTs and perform various operations on them without specifying the underlying FST arc types. This higher-level layer, found in the fst::script namespace, is somewhat less efficient, due to indirection, and in general exposes far fewer methods and options. It is used principally to implement the shell-level FST commands and future Python bindings. From C++, users are encouraged in most circumstances to use the lower-level templated classes and operations for their efficiency and completeness. However, for simple 'glue' code that will work seamlessly with different arc types (esp. I/O), this higher-level might be appropriate. To use the scripting layer, include <fst/fstscript.h> in the installation include directory and link to libfstscript.so in the installation library directory.

In the following, all classes and methods mentioned are in the namespace fst::script.

 

Class Overview

Changed:
<
<
FST scripting support is implemented by 3 high level classes: FstClass, MutableFstClass, and VectorFstClass. The following documents each class's methods.
>
>
At FST script level, the Fst class template hierarchy is partially mirrored with a template-free FstClass hierarchy. For example, these classes are defined:
 

FstClass


Line: 465 to 467
 

MutableFstClass

Deleted:
<
<
This is essentially a wrapper for MutableFst<Arc>. FstClass::Read returns a MutableFstClass when it reads an FST with its kMutable flag set; thus, it's safe to downcast such pointers to MutableFstClass. See some examples.
 
class MutableFstClass : public FstClass {
 public:

Line: 490 to 486
 

VectorFstClass

Deleted:
<
<
This class is chiefly useful in two cases:
  • You want a new, blank FST with the same arc type as an existing FST, perhaps to hold some result.
  • You want a mutable copy of a (perhaps non-mutable) FST.
 
Deleted:
<
<
See some examples.
 
class VectorFstClass : public MutableFstClass {

Line: 511 to 502
 

WeightClass

Changed:
<
<
This class hides the type of a weight in the same way that the classes
>
>
This class hides the weight type similar to how the classes
 above hide the arc type of an FST. It is useful for weight I/O and for passing weights into the operations that require them.
Line: 544 to 535
 

Operations

Changed:
<
<
In general, the same high-level operations that are implemented for the underlying FSTs are implemented for instances of FstClass, sometimes with modified option lists. Check script/operations.h.
>
>
In general, many of the operations that are implemented for the underlying templated FSTs are implemented for instances of FstClass, sometimes with modified option lists. Check <fst/fstscript.h>.
 
Changed:
<
<

Examples

>
>

Example

 The code in the quick tour could be reimplemented using the fst::script library as follows. This new version will work with FSTs of all arc types, not
Line: 576 to 565
 Project(&result, PROJECT_OUTPUT);
Deleted:
<
<
When an FST with the kMutable flag set is read from disk, even if it is read by FstClass::Read, it is read as a MutableFstClass. That means that such pointers can be safely cast, as follows:

FstClass *ifst = FstClass::Read(some_filename);

MutableFstClass *ofst = 0;
if (ifst->Properties(kMutable, false)) {
  ofst = static_cast<MutableFstClass *>(ifst);
} else {
  // Otherwise, make a copy
  ofst = new VectorFstClass(*ifst);
  delete ifst;
}
 

LookAhead Matchers and Fsts Work in progress, under construction

Line: 1067 to 1038
  Symbol tables store the bijective mapping between textual labels, used in reading and printing an FST textual file, and their integer assignment, used in the FST's internal representation. Symbol tables are usually read in with fstcompile, can
Changed:
<
<
be stored by the FST, and used to print out the FST with fstprint,. Here are some examples of manipulating symbol tables directly:
>
>
be stored by the FST, and used to print out the FST with fstprint,. Here are /amples of manipulating symbol tables directly:
 
// Various ways to reading symbol tables 
StdFst *fst = StdFst::Read("some.fst");

Revision 272010-08-03 - JacobRatkiewicz

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

fst::script Work in progress, under construction

Added:
>
>
The OpenFst library also includes some functionality to facilitate scripting with FSTs. These methods allow client programs to load FSTs and perform operations on them without specifying the underlying arc type of the FSTs. This higher level is somewhat less efficient, due to indirection, and in general exposes fewer options. Thus, its use should be restricted to simple scripting applications; more complicated code should use the lower-level operations templated on arc types. In the following, all classes and methods mentioned are in the namespace fst::script.

Class Overview

FST scripting support is implemented by 3 high level classes: FstClass, MutableFstClass, and VectorFstClass. The following documents each class's methods.

FstClass

class FstClass {
 public:
  // Construct an FstClass from a templated Fst, hiding its arc type. 
  template<class Arc>
  explicit FstClass(Fst<Arc> *fst);
  // Copy constructor 
  explicit FstClass(const FstClass &other);
  // Read an arc-templated Fst from disk, and return as an FstClass 
  static FstClass *Read(const string &fname);
  // String representation of the arc type 
  virtual const string &ArcType() const;
  // String representation of the underlying Fst type (e.g. 'vector') 
  virtual const string &FstType() const;
  // String representation of the arc's weight type 
  virtual const string &WeightType() const;
  // A pointer to this Fst's input symbol table 
  virtual const SymbolTable *InputSymbols() const;
  // A pointer to this Fst's output symbol table 
  virtual const SymbolTable *OutputSymbols() const;
  // Write the underlying arc-templated Fst to disk 
  virtual void Write(const string &fname);
  // Return an integer representing all the properties (see Fst::Properties) 
  virtual uint64 Properties(uint64 mask, bool test) const;
  // Call to get the underlying FST, if you know the concrete arc type
  // e.g. for an FstClass fc,
  // const Fst<StdArc> &f = *(fc.GetFst<StdArc>());
  // Returns NULL if the given arc type doesn't match the underlying FST. 
  template<class Arc>
  const Fst<Arc> *GetFst() const;

  virtual ~FstClass();
}

Unlike its lower-level analogue Fst<Arc>, FstClass is not abstract; it is a container which can be constructed from an arbitrary Fst<Arc>.

MutableFstClass

This is essentially a wrapper for MutableFst<Arc>. FstClass::Read returns a MutableFstClass when it reads an FST with its kMutable flag set; thus, it's safe to downcast such pointers to MutableFstClass. See some examples.

class MutableFstClass : public FstClass {
 public:
  // Construct a MutableFstClass from some kind of MutableFst<> 
  template<class Arc>
  explicit MutableFstClass(MutableFst<Arc> *fst);
  // If your code knows the arc type of the underlying MutableFst<>, it
  // can use this method to extract a pointer to it. This pointer can be used
  // to change the underlying MutableFst<> 
  template<class Arc>
  MutableFst<Arc> *GetMutableFst();
  // Set the input symbol table of the underlying MutableFst 
  virtual void SetInputSymbols(SymbolTable *is);
  // Set the output symbol table of the underlying MutableFst 
  virtual void SetOutputSymbols(SymbolTable *os);
};

VectorFstClass

This class is chiefly useful in two cases:
  • You want a new, blank FST with the same arc type as an existing FST, perhaps to hold some result.
  • You want a mutable copy of a (perhaps non-mutable) FST.

See some examples.

class VectorFstClass : public MutableFstClass {
public:
  // Construct a copy of "other" as a VectorFstClass 
  explicit VectorFstClass(const FstClass &other);
  // Construct a blank VectorFstClass with the given arc type 
  explicit VectorFstClass(const string &arc_type);
  // Wrap the given VectorFst<Arc> 
  template<class Arc>
  explicit VectorFstClass(VectorFst<Arc> *fst);
};

WeightClass

This class hides the type of a weight in the same way that the classes above hide the arc type of an FST. It is useful for weight I/O and for passing weights into the operations that require them.

class WeightClass {
 public:
  // Construct a Zero 
  WeightClass();
  // Wrap a weight of the given type 
  template<class W>
  explicit WeightClass(const W &weight);
  // Construct a weight given the string representation of its type
  // (e.g. "tropical") and a string representation of the weight
  // itself. 
  WeightClass(const string &weight_type, const string &weight_str);
  // Copy constructor and assign 
  WeightClass(const WeightClass &other);
  WeightClass &operator = (const WeightClass &other);
  // If you know the correct weight type, you can get it with this
  method. Will return NULL if an incorrect type is attempted.  
  template<class W>
  W *GetWeight() const;
  // Constants representing zero and one in all possible weight types 
  static const WeightClass &Zero();
  static const WeightClass &One();

  ~WeightClass();
};

Operations

In general, the same high-level operations that are implemented for the underlying FSTs are implemented for instances of FstClass, sometimes with modified option lists. Check script/operations.h.

Examples

The code in the quick tour could be reimplemented using the fst::script library as follows. This new version will work with FSTs of all arc types, not just StdArc (though the arc types in input.fst and model.fst must match).

// Reads in an input FST. 
FstClass *input = FstClass::Read("input.fst");
// Reads in the transduction model. 
FstClass *model = FstClass::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, OLABEL_COMPARE);
ArcSort(model, ILABEL_COMPARE);
// Container for composition result. 
VectorFstClass result(input->ArcType());
// Create the composed FST. 
Compose(*input, *model, &result);
// Just keeps the output labels. 
Project(&result,  PROJECT_OUTPUT);

When an FST with the kMutable flag set is read from disk, even if it is read by FstClass::Read, it is read as a MutableFstClass. That means that such pointers can be safely cast, as follows:

FstClass *ifst = FstClass::Read(some_filename);

MutableFstClass *ofst = 0;
if (ifst->Properties(kMutable, false)) {
  ofst = static_cast<MutableFstClass *>(ifst);
} else {
  // Otherwise, make a copy
  ofst = new VectorFstClass(*ifst);
  delete ifst;
}
 

LookAhead Matchers and Fsts Work in progress, under construction

Revision 262010-08-02 - JacobRatkiewicz

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 412 to 412
 // Register the fst::script operations with this arc type REGISTER_FST_OPERATIONS(MyArc); // Register some other operation with this arc type
Changed:
<
<
REGISTER_FST_OPERTION(Operations, MyArc, Args);
>
>
REGISTER_FST_OPERATION(Operations, MyArc, Args);
 

compiled into a dynamic shared object my_arc.so. If can be found in LD_LIBRARY_PATH (or equivalent), you should

Revision 252010-08-02 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 225 to 225
  Alternatively, the user can process options in his own way and directly assign to any of the above global options if he wishes to modify their defaults.
Added:
>
>

Compact Fsts Work in progress, under construction

 

Composition Filters

Line: 320 to 323
 The following code:
Changed:
<
<
VectorFst ifst;
>
>
VectorFst ifst;
 ... ifst.Write("a.fst");
Changed:
<
<
VectorFst *ofst = VectorFst::Read("a.fst");
>
>
VectorFst *ofst = VectorFst::Read("a.fst");
 
Changed:
<
<
writes and reads a defined Fst type (VectorFst) and arc type (A) to and from a file in a straight-forward way.
>
>
writes and reads a defined Fst type (VectorFst) and arc type (Arc) to and from a file in a straight-forward way.
 
Changed:
<
<

Library Registration

>
>

Library Registration

  The call:
Changed:
<
<
Fst *fst = Fst::Read("a.fst");
>
>
Fst *fst = Fst::Read("a.fst");
 

reads the same VectorFst from the file as above, but returns a base Fst. This form, useful for code that works generically for different Fst types,

Changed:
<
<
can not work unless the Fst and arc type are library-registered. Some arc types (see here) are already registered for all the Fst types defined in the OpenFst library. Other arc type A and Fst type F pairs can be registered with the following call:
>
>
can not work unless the Fst and arc type are appropriately registered. Some arc types (see here) are already registered for common Fst types defined in the OpenFst library. Other arc type Arc and Fst type F pairs can be registered with the following call:
 
Changed:
<
<
REGISTER_FST(F, A);
>
>
REGISTER_FST(F, Arc);
 

To avoid code bloat in a given program, registering arc types, in particular, should be used sparingly.

Changed:
<
<

Main Registration

>
>

Script Registration Recent changes

  In the above examples, the user provided the arc type as a template parameter. However, the call:
Changed:
<
<
$ fstinfo a.fst
>
>
$ fstdeterminize in.fst >out.fst
 

works e.g. for both StdArc and LogArc arcs. This is accomplished by calling in main(argc, argv):

Changed:
<
<
return CALL_FST_MAIN(InfoMain, argc, argv);
>
>
namespace script { FstClass *ifst = FstClass::Read(in_name); VectorFstClass ofst(ifst->ArcType()); Determinize(*ifst, &ofst); ofst.Write(out_name); }
 

where:

Changed:
<
<
template int InfoMain(int argc; char **argv, istream &strm, const FstReadOptions &opts) { Fst *fst = Fst::Read(strm, opts); ... return 0; }
>
>
class VectorFstClass; void Determinize(const FstClass &ifst, MutableFstClass *ofst);
 
Changed:
<
<
is a templated `main' function that does the arc-specific work. CALL_FST_MAIN passes to InfoMain the command line arguments and an opened stream to an Fst (opened from the first argument or standard input if no arguments). CALL_FST_MAIN does the type dispatch by examining the Fst's header and then passing on the (partially-read) input stream, which can be used by InfoMain to read in the actual Fst. This dispatch works only with arc and main function pairs that have been main-registered. Each OpenFst distribution binary registers its templated main function with the arc types marked registered here. An arc type A and main function M pair can be registered with the following call:
>
>
are a class and function in the fst:script namespace that do not depend on the Arc template parameter. These forms, useful for code that works generically for different Arc types, can not work unless the arc type is appropriately registered. Some arc types (see here) are already registered. Other arc types Arc can be registered with the following calls:
 
Changed:
<
<
REGISTER_FST_MAIN(M, A);
>
>
REGISTER_FST_CLASS(VectorFstClass, Arc); REGISTER_FST_OPERATION(Determinize, Arc, DeterminizeArgs);
 

To avoid code bloat in a given program, registering arc types should be used sparingly.

Changed:
<
<
To use main registration in your own program, you need to include additionally <fst/main.h> and link additionally to libfstmain.so.

FST Dynamic Shared Objects

>
>

FST Dynamic Shared Objects Recent changes

  The examples above show how users can modify programs to be able to read new arc and Fst types. However, it would not be ideal to have to do so for all the distribution binaries or other existing programs. Instead, this can be done more easily with dynamic shared objects (DSOs).
Line: 387 to 393
 for all the distribution binaries or other existing programs. Instead, this can be done more easily with dynamic shared objects (DSOs).

To add a new Fst type, MyFst with MyFst::Type() = "my_fst", use the code:

Deleted:
<
<
 

Deleted:
<
<
extern "C" { void my_fst_init() {
  // Register some arc types with this Fst type REGISTER_FST(MyFst, StdArc); REGISTER_FST(MyFst, LogArc);
Deleted:
<
<
} }
 

compiled into a dynamic shared object my_fst.so. If my_fst.so can be found in the LD_LIBRARY_PATH (or equivalent), you should

Line: 402 to 403
 be able to read the new Fst type with existing programs.

To add a new arc type, MyArc with MyArc::Type() = "my_arc", use the code:

Deleted:
<
<
 

Changed:
<
<
extern "C" { void my_arc_init() {
>
>
  // Register some Fst types with this arc type REGISTER_FST(VectorFst, MyArc); REGISTER_FST(ConstFst, MyArc);
Changed:
<
<
// Register the OpenFst binaries with this arc type REGISTER_FST_MAINS(MyArc); // Register some other main with this arc type REGISTER_FST_MAIN(SomeMain, MyArc); } }
>
>
// Register the fst::script operations with this arc type REGISTER_FST_OPERATIONS(MyArc); // Register some other operation with this arc type REGISTER_FST_OPERTION(Operations, MyArc, Args);
 

compiled into a dynamic shared object my_arc.so. If can be found in LD_LIBRARY_PATH (or equivalent), you should be able to read the new arc type with existing programs.

Added:
>
>

fst::script Work in progress, under construction

LookAhead Matchers and Fsts Work in progress, under construction

 

Mappers

Line: 922 to 926
 

User-defined Fst Classes Work in progress, under construction

Deleted:
<
<
TBA
 

Visitors

Revision 242010-07-31 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 100 to 100
 
LexicographicArc<W1, W2> int int LexicographicWeight<W1, W2>  
LogArc int int LogWeight DONE
MinMaxArc int int MinMaxWeight  
Added:
>
>
PowerArc<W, n> Recent changes int int PowerWeight<W, n>
 
ProductArc<W1, W2> int int ProductWeight<W1, W2>  
StdArc int int TropicalWeight DONE
StringArc<S> int int StringWeight<int, S>  
Line: 197 to 198
 
FLAGS_fst_compat_symbols bool true Require symbol tables to match when appropriate
FLAGS_fst_default_cache_gc bool true Enable garbage collection of cached Fsts
FLAGS_fst_default_cache_gc_limit int64 1048576 Byte size that triggers garbage collection of cached Fsts
Changed:
<
<
FLAGS_fst_pair_parentheses string "" Characters enclosing the first weight of a printed pair weight (and derived classes) to ensure proper I/O of nested pair weights; must have size 0 (none) or 2 (open and close parenthesis)
FLAGS_fst_pair_separator string "," Character separator between printed pair weights; must be a single character
>
>
FLAGS_fst_field_separator Recent changes string " \t" Set of characters used as a separator between printed fields
FLAGS_fst_weight_parentheses Recent changes string "" Characters enclosing the first weight of a printed composite weight (and derived classes) to ensure proper I/O of nested composite weights; must have size 0 (none) or 2 (open and close parenthesis)
FLAGS_fst_weight_separator Recent changes string "," Character separator between printed composite weights; must be a single character
 
FLAGS_fst_verify_properties bool false Verify Fst properites are correctly set when queried

The first ensures the arguments of binary FST operations (e.g. composition) have compatible symbol tables (e..g output symbol table matches input symbol table for composition). The second two are used to control the caching of expanded state and arc information found in most

Changed:
<
<
delayed Fst classes; the default values should normally be satisfactory. The next two are used to control the text formating of ProductWeight and other weight pairs. The last is used to ensure that the
>
>
delayed Fst classes; the default values should normally be satisfactory. The next is used in the textual representation of FSTs and symbol tables. The next two are used to control the text formating of ProductWeight and other weight tuples. The last is used to ensure that the
 properties of an FST have been correctly set; it is used for debugging only since it incurs considerable computational cost.

In each of the Fst distribution installed binaries, the above options, as well as any of those defined specific to the binary, can be set from the command line using e.g.

Changed:
<
<
--fst_default_cache_gc=false or --fst_pair_parenthesis="(" . Additionally, the option --help and --v=N (where N = 0,1,2,..) will print out usage information and
>
>
--fst_default_cache_gc=false or --fst_weight_parenthesis="(" . Additionally, the option --help and --v=N (where N = 0,1,2,..) will print out usage information and
 set the verbosity level of logging, respectively. The flag processing is modeled after the Google gflags package.

In a user-defined binary, the command line options processing will all also work if the user calls:

Line: 986 to 989
 
Lexicographic LexicographicWeight<W1, W2> W1 X W2 min W1 X ⊗W2 (0W1,0W2) (1W1,1W2) min: lexicographic order w.r.t.
W1 and W2 natural orders
doc
Log LogWeightTpl<T> [-∞, ∞] -log(e-x + e-y) + 0 T: floating point doc
MinMax MinMaxWeightTpl<T> [-∞, ∞] min max -∞ T: floating point doc
Added:
>
>
Power Recent changes PowerWeight<W, n> Wn Wn Wn 0Wn 1Wn   doc
 
Product ProductWeight<W1, W2> W1 X W2 W1 X ⊕W2 W1 X ⊗W2 (0W1,0W2) (1W1,1W2)   doc
String StringWeight<L, STRING_LEFT> L* ∪ {∞} longest com. prefix ε L: signed integral doc
  StringWeight<L, STRING_RIGHT> L* ∪ {∞} longest com. suffix ε L: signed integral doc

Revision 222009-03-22 - MichaelRiley

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

Composition Filters

A composition filter determines which matches are allowed to proceed in composition. The basic filters handle correct epsilon matching. In particular, they ensure

Changed:
<
<
that redundant epsilon paths, which would be incorrect with non-idempotent weights, are not created. More generally, they can be used to block or modify composition paths for particular purposes. Their interface is:
>
>
that redundant epsilon paths, which would be incorrect with non-idempotent weights, are not created. More generally, composition filters can be used to block or modify composition paths for efficiency or specialized purposes. Their interface is:
 
template <class A>                            
class SomeComposeFilter {

Line: 253 to 251
  void FilterFinal(Weight *final1, Weight *final2) const; };
Changed:
<
<
The filter's state is represented by the type SomeComposeFilter::FilterState, specified by the filter and stored in the composition
>
>
The filter's state is represented by the type SomeComposeFilter::FilterState and is stored in the composition
 state table tuple. It has the form:

class SomeFilterState {                                                          

Revision 212009-03-21 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 562 to 562
 
PhiMatcher<M> φ symbol handling; templated on underlying matcher doc

SortedMatcher requires the underlying Fst be sorted on the appropriate side. Find(0)

Changed:
<
<
matches any epsilons on the underlying Fst explicitly (as if it were any other symbol) but also returns an
>
>
matches any epsilons on the underlying Fst explicitly (as if they were any other symbol) but also returns an
 implicit self-loop
Changed:
<
<
(Arc(kNoLabel, 0, Weight::One(), current_state) if the match_type is MATCH_INPUT and
>
>
(namely Arc(kNoLabel, 0, Weight::One(), current_state) if the match_type is MATCH_INPUT and
 Arc(0, kNoLabel, Weight::One(), current_state) if the match_type is MATCH_OUTPUT). This loop implements a 'non-consuming' match in composition
Changed:
<
<
with kNoLabel informing composition that this is the case. A
>
>
(with kNoLabel informing composition that this is the case). A
 composition filter determines which of these epsilon transitions are ultimately accepted.
Line: 578 to 578
  The ε symbol is assigned label 0 by convention. The numeric label of the other special symbols is determined by a constructor argument to their respective matchers.
Changed:
<
<
The ρ, σ and φ matchers add their functionality to their template argument matcher. In this way,
>
>
The ρ, σ and φ matchers augment the functionality of their underlying template argument matcher. In this way,
 matchers can be cascaded (with special symbol precedence determined by the order).

A design choice for these matchers is whether to remove the special symbol in the result

Line: 587 to 587
 applying special-symbol removal prior to composition (c.f., epsilon removal). This case requires that only one of the FSTs in composition contain such symbols. The second case requires well-defined semantics and that composition proper identify and handle any non-consuming
Changed:
<
<
symbols on each FST. The result of Find(kNoLabel) identifies on one FST, while the matcher's returning a kNolabel loop handles the other (both described above).
>
>
symbols on each FST. (The result of Find(kNoLabel) identifies on one FST, while the matcher's returning a kNolabel loop handles the other, both described above.)
  The template Matcher<F> selects the pre-designated matcher for Fst type F; it is typically SortedMatcher. Composition uses this matcher by default. It can be changed by using the version of ComposeFst that accepts
Line: 684 to 684
 options that control caching behavior.

Here is an example that selects minimal caching and

Changed:
<
<
the rho matcher (for fst2 ρ's) for composition::
>
>
the rho matcher (for fst2 ρ's) in composition::
 
Changed:
<
<
typedef RhoMatcher<SortedMatcher< Fst > > RM;
>
>
typedef RhoMatcher< SortedMatcher > RM;
 
Changed:
<
<
ComposeFstOptions<LogArc, RM> opts;
>
>
ComposeFstOptions<StdArc, RM> opts;
 opts.gc_limit = 0; opts.matcher1 = new RM(fst1, MATCH_NONE, kNoLabel); opts.matcher2 = new RM(fst2, MATCH_INPUT, SomeRhoLabel);
Changed:
<
<
ComposeFst cfst(fst1, fst2, opts);
>
>
StdComposeFst cfst(fst1, fst2, opts);
 

Follow the links to the code under each operation's documentation

Revision 202009-03-18 - MichaelRiley

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

Composition Filters

Changed:
<
<
A composition filter determines which matches are allowed to proceed in composition. The basic filters handle correct epsilon matching. Their interface is:
>
>
A composition filter determines which matches are allowed to proceed in composition. The basic filters handle correct epsilon matching. In particular, they ensure that redundant epsilon paths, which would be incorrect with non-idempotent weights, are not created. More generally, they can be used to block or modify composition paths for particular purposes. Their interface is:
 
template <class A>                            
class SomeComposeFilter {

Line: 490 to 493
 

Matchers

Matchers can find and iterate through requested labels at

Changed:
<
<
FST states. In the simplest form, these are just some associative map or search keyed on labels. More generally, they may implement matching special labels that represent sets of labels such as ρ (rest), σ (all) or φ (fail).
>
>
FST states; their principal use is in composition matching. In the simplest form, these are just a search or hash keyed on labels. More generally, they may implement matching special symbols that represent sets of labels such as ρ (rest), σ (all) or φ (fail), which can be used for more compact automata representations and faster matching.
  The Matcher interface is:
Line: 559 to 562
 
PhiMatcher<M> φ symbol handling; templated on underlying matcher doc

SortedMatcher requires the underlying Fst be sorted on the appropriate side. Find(0)

Changed:
<
<
matches any epsilons explicitly (as if it were any other symbol) but also returns the self-loop Arc(kNoLabel, 0, Weight::One(), current_state) if the match_type is MATCH_INPUT and Arc(0, kNoLabel, Weight::One(), current_state) if the match_type is MATCH_OUTPUT. The kNoLabel informs composition that no symbol was consumed in that case. A
>
>
matches any epsilons on the underlying Fst explicitly (as if it were any other symbol) but also returns an implicit self-loop (Arc(kNoLabel, 0, Weight::One(), current_state) if the match_type is MATCH_INPUT and Arc(0, kNoLabel, Weight::One(), current_state) if the match_type is MATCH_OUTPUT). This loop implements a 'non-consuming' match in composition with kNoLabel informing composition that this is the case. A
 composition filter determines which of these epsilon transitions are ultimately accepted.
Line: 574 to 578
  The ε symbol is assigned label 0 by convention. The numeric label of the other special symbols is determined by a constructor argument to their respective matchers.
Added:
>
>
The ρ, σ and φ matchers add their functionality to their template argument matcher. In this way, matchers can be cascaded (with special symbol precedence determined by the order).
  A design choice for these matchers is whether to remove the special symbol in the result (used for the ρ, σ, and φ matchers) or return it (used for epsilon-handling). The first case is equivalent to (but more efficient than)
Changed:
<
<
applying special-symbol removal prior to composition (c.f., epsilon removal).
>
>
applying special-symbol removal prior to composition (c.f., epsilon removal). This case requires that only one of the FSTs in composition contain such symbols.
 The second case requires well-defined semantics and that composition proper identify and handle any non-consuming
Changed:
<
<
symbols on each FST. The result of Find(kNoLabel) identifies for one FST, while the matcher's returning a kNolabel loop permits handling the other (both described above).
>
>
symbols on each FST. The result of Find(kNoLabel) identifies on one FST, while the matcher's returning a kNolabel loop handles the other (both described above).
  The template Matcher<F> selects the pre-designated matcher for Fst type F; it is typically SortedMatcher. Composition uses this matcher by default. It can be changed by using the version of ComposeFst that accepts
Changed:
<
<
ComposeFstOptions. doc [bad link?]. Note two matchers (of the same C++ type but different MatchType) are used in composition -- one for each FST. Whether actual matching is done on one or both sides depends on the capabilities of the matchers (queried by Type()) and composition.
>
>
ComposeFstOptions doc [bad link?]. Note two matchers (of the same C++ type but different MatchType) are used in composition -- one for each FST. Whether actual match queries are performed on one or both FSTs depends on the matcher constructor arguments, the matcher capabilities (queried by Type()) and composition itself.
 
Changed:
<
<
An example use of a matcher is here.
>
>
An example use of a matcher is here and an example use of a ρ matcher in composition is here.
 

Mutable Fsts

Line: 676 to 684
 options that control caching behavior.

Here is an example that selects minimal caching and

Changed:
<
<
the epsilon-matching composition filter in composition:
>
>
the rho matcher (for fst2 ρ's) for composition::
 
Changed:
<
<
ComposeFstOptions opts;
>
>
typedef RhoMatcher<SortedMatcher< Fst > > RM;

ComposeFstOptions<LogArc, RM> opts;

 opts.gc_limit = 0;
Changed:
<
<
opts.filter = new MatchComposeFilter(fst1, fst2);
>
>
opts.matcher1 = new RM(fst1, MATCH_NONE, kNoLabel); opts.matcher2 = new RM(fst2, MATCH_INPUT, SomeRhoLabel);
 ComposeFst cfst(fst1, fst2, opts);

Revision 192009-03-14 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 204 to 204
 The second two are used to control the caching of expanded state and arc information found in most delayed Fst classes; the default values should normally be satisfactory. The next two are used to control the text formating of ProductWeight and other weight pairs. The last is used to ensure that the
Changed:
<
<
properties of an FST have been correctly set; is is used for debugging only, since it incurs considerable computational cost.
>
>
properties of an FST have been correctly set; it is used for debugging only since it incurs considerable computational cost.
  In each of the Fst distribution installed binaries, the above options, as well as any of those defined specific to the binary, can be set from the command line using e.g. --fst_default_cache_gc=false or --fst_pair_parenthesis="(" . Additionally, the option --help and --v=N (where N = 0,1,2,..) will print out usage information and
Line: 278 to 278
 
AltSequenceComposeFilter Requires epsilons on FST2 to be read before epsilons on FST1 doc
MatchComposeFilter Requires epsilons on FST1 to be matched with epsilons on FST2 whenever possible doc
Changed:
<
<
SequenceComposeFilter is the default composition filter. It can be changed by using the version of ComposeFst that accepts
>
>
SequenceComposeFilter is the default composition filter. It can be changed by using the version of ComposeFst that accepts
 ComposeFstOptions. doc [bad link?]

Line: 563 to 563
 Arc(kNoLabel, 0, Weight::One(), current_state) if the match_type is MATCH_INPUT and Arc(0, kNoLabel, Weight::One(), current_state) if the match_type is MATCH_OUTPUT. The kNoLabel informs composition that no symbol was consumed in that case. A
Changed:
<
<
composition filter determines which of these epsilon transitions are ultimately
>
>
composition filter determines which of these epsilon transitions are ultimately
 accepted.
Changed:
<
<
The special symbols referenced above are explained by this table:
>
>
The special symbols referenced above behave as described in this table:
 
  Consumes no symbol Consumes symbol
Matches all ε σ
Matches rest φ ρ
Added:
>
>
The ε symbol is assigned label 0 by convention. The numeric label of the other special symbols is determined by a constructor argument to their respective matchers.
  A design choice for these matchers is whether to remove the special symbol in the result (used for the ρ, σ, and φ matchers) or return it (used for epsilon-handling). The first case is equivalent to (but more efficient than)
Changed:
<
<
applying special-symbol removal prior to composition (c.f., epsilon removal),
>
>
applying special-symbol removal prior to composition (c.f., epsilon removal).
 The second case requires well-defined semantics and that composition proper identify and handle any non-consuming symbols on each FST. The result of Find(kNoLabel) identifies for one FST, while the matcher's returning a kNolabel loop permits handling the other (both described above).

The template Matcher<F> selects the pre-designated matcher for Fst type F; it is typically SortedMatcher.

Changed:
<
<
Composition uses this matcher by default. It can be changed by using the version of ComposeFst that accepts
>
>
Composition uses this matcher by default. It can be changed by using the version of ComposeFst that accepts
 ComposeFstOptions. doc [bad link?]. Note two matchers (of the same C++ type but different
Changed:
<
<
MatchType) are used in composition -- one for each FST. Whether actual matching is done on one or both sides depends on the capabilities of the matchers and composition.
>
>
MatchType) are used in composition -- one for each FST. Whether actual matching is done on one or both sides depends on the capabilities of the matchers (queried by Type()) and composition.
  An example use of a matcher is here.
Line: 670 to 672
 

Operation Options

Many FST operations have versions that accept options, especially option structures, that have not

Changed:
<
<
been documented in this Wiki for brevity, other than to mention some of the parameters that can be changed. For example, most of the delayed Fsts have constructors that accept options that control caching behavior. Follow the links to the code under each operation's documentation for the details.
>
>
been documented in this Wiki for brevity other than to mention some of the parameters that can be changed. For example, most of the delayed Fsts have constructors that accept options that control caching behavior.

Here is an example that selects minimal caching and the epsilon-matching composition filter in composition:

ComposeFstOptions<LogArc> opts;
opts.gc_limit = 0;
opts.filter = new MatchComposeFilter<LogArc>(fst1, fst2);
ComposeFst<LogArc> cfst(fst1, fst2, opts);

Follow the links to the code under each operation's documentation for the specific details.

 

Properties

Line: 720 to 734
 
  kNotWeighted Only trivial arc and final weights

The call fst.Properties(mask, false) returns the stored property bits set in the mask bits; some properties

Changed:
<
<
may be unknown.
>
>
may be unknown. it is a constant-time operation.
 The call fst.Properties(mask, true) returns the stored property bits set in the mask bits after
Changed:
<
<
computing and updating any of those set in the mask that are unknown.
>
>
computing and updating any of those set in the mask that are unknown. It is a linear-time (O(V + E)) operation if any of the requested bits were unknown.
 

State Iterators

Line: 853 to 867
 
DetStringComposeStateTable VectorStateTable Efficient when FST1 is deterministic and FST2 is a string doc
EraseableComposeStateTable ErasableStateTable Allows composition state tuple erasure doc
Changed:
<
<
GenericComposeStateTable is the default composition state table. It can be changed by using the version of ComposeFst that accepts
>
>
GenericComposeStateTable is the default composition state table. It can be changed by using the version of ComposeFst that accepts
 ComposeFstOptions. doc [bad link?]

Line: 974 to 988
 
TropicalWeight TropicalWeightTpl<float>

Weight pairs, such as ProductWeight and LexicographicWeight, can use command line flags to control

Changed:
<
<
their textual formatting. FLAGS_fst_pair_weight_separator is printed between the weights (default: ","). FLAGS_fst_piar_parentheses (default: "") brackets the pair; if you create complex nested pairs (i.e., tuples), they may need to be printed with non-empty brackets (e.g. "()") to ensure correct parsing if read back in.
>
>
their textual formatting. FLAGS_fst_pair_weight_separator is printed between the weights (default: ","). FLAGS_fst_pair_parentheses (default: "") brackets the pair; if you create complex nested pairs (i.e., tuples), they may need to be printed with non-empty brackets (e.g. "()") to ensure correct parsing if read back in. These affect only textual (not binary) I/O.
  Additional weight information:

Revision 182009-03-12 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 184 to 184
 
  • Bounded caching: If gc is true, then the cache will be garbage-collected when it grows past gc_limit. This case is useful when states are revisited and memory is a concern. This is the default case (based on the global flags).
Changed:
<
<
  • Minimal caching: It is not possible to completely avoid caching in such an FST since the cache is used to implement the arc iterators efficiently (creating an iterator fills the cache, iterating reads from the cache). However, if gc is true, gc_limit is set to 0, and arcs iterators for only one state at a time have been in existence for an FST, then only the information for that state is cached and this case is especially optimized. This case is useful when states are not revisited (e.g. when a cached FST is simply being copied to a mutable FST).
>
>
  • Minimal caching: It is generally not possible to avoid all caching in such an FST since the cache is used to implement the arc iterators efficiently (creating an iterator computes and writes the state's arcs to the cache, iterating reads from the cache). However, if (1) gc is true, (2) gc_limit is 0, and (3) arcs iterators have been created (and then destroyed) only one state at a time, then only information for that state is cached and this case is especially optimized. This case is useful when states are not revisited (e.g. when a cached FST is simply being copied to a mutable FST).
 

Command Line Flags

Revision 172009-03-12 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 178 to 178
 };

All OpenFst cached Fsts have constructors that accept this (or a class derived from it) as an argument. The member defaults are controlled by

Changed:
<
<
global flags. If gc is true, then Fst cache will be garbage-collected once it grows past gc_limit. If gc_limit is set to 0, there is special caching behavior: so long as only one arc iterator is opened at a time for the FST, it uses space O(d), where d = maximum out-degree.
>
>
global flags. These options can be used for:

  • Maximal caching: If gc is false, then any expanded state will be cached for the extent of the FST. This case is useful when states are revisited and memory is not a concern.

  • Bounded caching: If gc is true, then the cache will be garbage-collected when it grows past gc_limit. This case is useful when states are revisited and memory is a concern. This is the default case (based on the global flags).

  • Minimal caching: It is not possible to completely avoid caching in such an FST since the cache is used to implement the arc iterators efficiently (creating an iterator fills the cache, iterating reads from the cache). However, if gc is true, gc_limit is set to 0, and arcs iterators for only one state at a time have been in existence for an FST, then only the information for that state is cached and this case is especially optimized. This case is useful when states are not revisited (e.g. when a cached FST is simply being copied to a mutable FST).
 

Command Line Flags

Revision 162009-03-06 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 542 to 542
  void Next(); // This specifies the known Fst properties as viewed from this
Changed:
<
<
// mapper. It takes as argument the input Fst's known properties.
>
>
// matcher. It takes as argument the input Fst's known properties.
  uint64 Properties(uint64 props) const; };
Line: 554 to 554
 
SigmaMatcher<M> σ symbol handling; templated on underlying matcher doc
PhiMatcher<M> φ symbol handling; templated on underlying matcher doc
Changed:
<
<
SortedMatcher requires the underlying Fst be sorted on the appropriate side. It matches epsilons explicitly (as if it were any other symbol) and as if the current FST state had a self-loop
>
>
SortedMatcher requires the underlying Fst be sorted on the appropriate side. Find(0) matches any epsilons explicitly (as if it were any other symbol) but also returns the self-loop
 Arc(kNoLabel, 0, Weight::One(), current_state) if the match_type is MATCH_INPUT and
Changed:
<
<
Arc(0, kNoLabel, Weight::One(), current_state) if the match_type is MATCH_OUTPUT. This and composition filter implement composition epsilon handling.
>
>
Arc(0, kNoLabel, Weight::One(), current_state) if the match_type is MATCH_OUTPUT. The kNoLabel informs composition that no symbol was consumed in that case. A composition filter determines which of these epsilon transitions are ultimately accepted.
  The special symbols referenced above are explained by this table:
Line: 566 to 568
 
Matches all ε σ
Matches rest φ ρ
Added:
>
>
A design choice for these matchers is whether to remove the special symbol in the result (used for the ρ, σ, and φ matchers) or return it (used for epsilon-handling). The first case is equivalent to (but more efficient than) applying special-symbol removal prior to composition (c.f., epsilon removal), The second case requires well-defined semantics and that composition proper identify and handle any non-consuming symbols on each FST. The result of Find(kNoLabel) identifies for one FST, while the matcher's returning a kNolabel loop permits handling the other (both described above).

 The template Matcher<F> selects the pre-designated matcher for Fst type F; it is typically SortedMatcher. Composition uses this matcher by default. It can be changed by using the version of ComposeFst that accepts
Changed:
<
<
ComposeFstOptions. doc [bad link?]
>
>
ComposeFstOptions. doc [bad link?]. Note two matchers (of the same C++ type but different MatchType) are used in composition -- one for each FST. Whether actual matching is done on one or both sides depends on the capabilities of the matchers and composition.
  An example use of a matcher is here.

Revision 152009-03-06 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 412 to 412
 be able to read the new arc type with existing programs.

Changed:
<
<

Mappers Work in progress, under construction

>
>

Mappers

Mappers are function objects used by the Map operation to transform arcs and/or final states. A mapper has the form:

// This determines how final weights are mapped.  
enum MapFinalAction { 
  // A final weight is mapped into a final weight. An error
  // is raised if this is not possible.  
  MAP_NO_SUPERFINAL,

  // A final weight is mapped to an arc to the superfinal state                 
  // when the result cannot be represented as a final weight.                   
  // The superfinal state will be added only if it is needed.                   
  MAP_ALLOW_SUPERFINAL,

  // A final weight is mapped to an arc to the superfinal state                 
  // unless the result can be represented as a final weight of weight           
  // Zero(). The superfinal state is always added (if the input is              
  // not the empty Fst).                                                        
  MAP_REQUIRE_SUPERFINAL
};

// This determines how symbol tables are mapped.                                
enum MapSymbolsAction { 
  // Symbols should be cleared in the result by the map.                        
  MAP_CLEAR_SYMBOLS,

  // Symbols should be copied from the input FST by the map.                    
  MAP_COPY_SYMBOLS,

  // Symbols should not be modified in the result by the map itself.            
  // (They may set by the mapper).                                              
  MAP_NOOP_SYMBOLS
};

class SomeMapper {                                                               
  public:                                                                     
   // Maps an arc type A to arc type B.                                       
   B operator()(const A &arc);                                                
   // Specifies final action the mapper requires (see above).                 
   // The mapper will be passed final weights as arcs of the                  
   // form A(0, 0, weight, kNoStateId).                                       
   MapFinalAction FinalAction() const;                                        
   // Specifies input symbol table action the mapper requires (see above).    
   MapSymbolsAction InputSymbolsAction() const;                              
   // Specifies output symbol table action the mapper requires (see above).   
   MapSymbolsAction OutputSymbolsAction() const;                              
   // This specifies the known properties of an Fst mapped by this            
   // mapper. It takes as argument the input Fst's known properties             
   uint64 Properties(uint64 props) const;                                  
};

The following mappers are defined in the OpenFst library:

Name Description
FromGallicMapper Extracts output label from gallic weight doc
IdentityMapper Maps to self doc [bad link?]
InvertWeightMapper Reciprocate all non-0 weights doc
PlusMapper Adds (⊕) a constant to all weights doc
QuantizeMapper Quantize all weights doc
ReverseWeightMapper Reverse all weights doc
RmWeightMapper Map all non-0 weights to 1 doc
SuperFinalMapper Redirects final states to new superfinal state doc
TimesMapper (Right) multiplies (⊗) a constant to all weights doc
ToGallicMapper Combines output label and weight into gallic weight doc

ToGallicMapper and FromGallicMapper are used, for example, to implement transducer determinization and minimization using weighted acceptor versions of these algorithms. Other specialized mappers are used to implement Decode, Encode, Invert, and Project.

 

Matchers

Line: 810 to 878
 

User-defined Fst Classes Work in progress, under construction

Added:
>
>
TBA
 

Visitors

Revision 142009-03-06 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 161 to 161
 provide access to the states and transitions of the FST.

Changed:
<
<

Caching Work in progress, under construction

>
>

Caching

Most of the delayed Fst classes use internal caching to save expanded states and arcs. This caching is controlled by this struct:

struct CacheOptions { 
  // enable GC 
  bool gc; 
  // # of bytes allowed before GC               
  size_t gc_limit;                          

  CacheOptions(bool g, size_t l) : gc(g), gc_limit(l) {}
  CacheOptions()
      : gc(FLAGS_fst_default_cache_gc),
        gc_limit(FLAGS_fst_default_cache_gc_limit) {}
};

All OpenFst cached Fsts have constructors that accept this (or a class derived from it) as an argument. The member defaults are controlled by global flags. If gc is true, then Fst cache will be garbage-collected once it grows past gc_limit. If gc_limit is set to 0, there is special caching behavior: so long as only one arc iterator is opened at a time for the FST, it uses space O(d), where d = maximum out-degree.

 

Command Line Flags

Line: 178 to 197
  The first ensures the arguments of binary FST operations (e.g. composition) have compatible symbol tables (e..g output symbol table matches input symbol table for composition).
Changed:
<
<
The second two are used to control the caching of expanded state and arc information found in most of the on-the-fly Fst classes; the default values should normally be satisfactory. The next two are used
>
>
The second two are used to control the caching of expanded state and arc information found in most delayed Fst classes; the default values should normally be satisfactory. The next two are used
 to control the text formating of ProductWeight and other weight pairs. The last is used to ensure that the properties of an FST have been correctly set; is is used for debugging only, since it incurs considerable computational cost.
Line: 226 to 246
  void FilterFinal(Weight *final1, Weight *final2) const; };
Changed:
<
<
The filter's state is represented by the type SomeComposeFilter::FilterState, defined by the filter and stored in the composition
>
>
The filter's state is represented by the type SomeComposeFilter::FilterState, specified by the filter and stored in the composition
 state table tuple. It has the form:

class SomeFilterState {                                                          

Line: 566 to 586
 

Operation Options

Changed:
<
<
>
>
Many FST operations have versions that accept options, especially option structures, that have not been documented in this Wiki for brevity, other than to mention some of the parameters that can be changed. For example, most of the delayed Fsts have constructors that accept options that control caching behavior. Follow the links to the code under each operation's documentation for the details.
 

Properties

Each Fst has associated with it a set of stored properties that assert facts about it. These are queried in an FST with the Properties() method and set in a MutableFst with the SetProperties() method. OpenFst library operations use these properties to optimize their performance. OpenFst library operations and mutable FSTs attempt to preserve as much

Line: 750 to 774
 ComposeFstOptions. doc [bad link?]

Changed:
<
<

Symbol Tables Work in progress, under construction

>
>

Symbol Tables

Symbol tables store the bijective mapping between textual labels, used in reading and printing an FST textual file, and their integer assignment, used in the FST's internal representation. Symbol tables are usually read in with fstcompile, can be stored by the FST, and used to print out the FST with fstprint,. Here are some examples of manipulating symbol tables directly:

// Various ways to reading symbol tables 
StdFst *fst = StdFst::Read("some.fst");
SymbolTable *isyms = fst->InputSymbolTable();
SymbolTable *osyms = fst->OutputSymbolTable();

SymbolTable *syms = SymbolTable::ReadText("some.syms");

// Adding and accessing symbols and keys 
syms->AddSymbol("kumquat", 7);
int64 key = syms->Find("kumquat");
string symbol = syms->Find(7);

// Various ways of writing symbol tables 
fst->SetInputSymbols(isyms);
fst->SetOutputSymbols(osyms);
fst->Write("some.fst"):

syms->WriteText("some.syms");
 

User-defined Fst Arcs and Weights

Revision 132009-03-05 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 562 to 562
 This is the default total order (under the requirements above) that we use for the shortest path and pruning algorithms. This order is the natural one to use given that it generally needs to be total, monotonic and. negative: total so that all weights can be compared, monotonic so there is a practical algorithm, and negative so that the "free" weight 1 is preferred to the "disallowed" weight 0.
Added:
>
>

Operation Options

 

Properties

Revision 122009-03-05 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 176 to 176
 
FLAGS_fst_pair_separator string "," Character separator between printed pair weights; must be a single character
FLAGS_fst_verify_properties bool false Verify Fst properites are correctly set when queried
Changed:
<
<
The first ensures the arguments of binary FST operations (e.g. ComposeDoc) have compatible symbol tables (e..g output symbol table matches
>
>
The first ensures the arguments of binary FST operations (e.g. composition) have compatible symbol tables (e..g output symbol table matches
 input symbol table for composition). The second two are used to control the caching of expanded state and arc information found in most of the on-the-fly Fst classes; the default values should normally be satisfactory. The next two are used to control the text formating of ProductWeight and other weight pairs. The last is used to ensure that the
Line: 688 to 688
 

State Tables

State tables determine the bijective mapping between state tuples (e.g. in composition triples of two FST states and a
Changed:
<
<
composition filter state) and their corresponding state IDs.
>
>
composition filter state) and their corresponding state IDs.
 They are classes, templated on state tuples, of the form:

template <class T>                                                          

Line: 815 to 815
 

Weights

Changed:
<
<
A Weight is a type that represents an FST transition's cost.
>
>
A Weight is a type that is used to represent the cost of taking transitions in an FST.
  The following basic weight templates are defined in the OpenFst library:

Revision 112009-03-05 - MichaelRiley

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

OpenFst Advanced Usage

Changed:
<
<
natBelow are a variety of topics covered in greater depth or of more specialized interest than found in the Quick Tour. Reading the
>
>
Below are a variety of topics covered in greater depth or of more specialized interest than found in the Quick Tour. Reading the
 Quick Tour first is recommended.
Changed:
<
<
/p
>
>
 

Arc Iterators

Line: 54 to 54
 
template <class Arc>

Changed:
<
<
class ArcFilter {
>
>
class SomeArcFilter {
 public: // Return true iff arc is to be transitioned. bool operator()(const Arc &arc) const;
Line: 74 to 74
  An Arc is a type that represents an FST transition from a given source state. It specifies an input label, an output label, a weight, and a destination state ID and it has a type name. In particular, it has the following form:
Changed:
<
<
struct Arc {
>
>
struct SomeArc {

  typedef W Weight; typedef L Label; typedef S StateId;
Line: 87 to 87
  Weight weight; StateId nextstate; };
Changed:
<
<
>
>
  where W is a valid weight type, and L and S are signed integral types.
Line: 202 to 202
 A composition filter determines which matches are allowed to proceed in composition. The basic filters handle correct epsilon matching. Their interface is:

template <class A>                            

Changed:
<
<
class ComposeFilter {
>
>
class SomeComposeFilter {
  public: typedef A Arc; typedef ... FilterState; // Required constructor.
Changed:
<
<
ComposeFilter(const Fst<A> &fst1, const Fst&ltA> &fst2);
>
>
SomeComposeFilter(const Fst<A> &fst1, const Fst&ltA> &fst2);
  // Return start state of filter. FilterState Start() const; // Specifies current composition state.
Line: 226 to 226
  void FilterFinal(Weight *final1, Weight *final2) const; };
Changed:
<
<
The filter's state is represented by the type ComposeFilter::FilterState, defined by the filter and stored in the composition state table tuple.
>
>
The filter's state is represented by the type SomeComposeFilter::FilterState, defined by the filter and stored in the composition state table tuple. It has the form:

class SomeFilterState {                                                          
  public:                                                             
   // Required constructors 
   SomeFilterState(); 
   SomeFilterState(const SomeFilterState &f);       
   // An invalid filter state.  
   static const SomeFilterState NoState();        
   // Maps state to integer for hashing.    
   size_t Hash() const;                   
   // Equality of filter states. 
   bool operator==(const SomeFilterState &f) const;       
   // Inequality of filter states.  
   bool operator!=(const SomeFilterState &f) const;   
   // Assignment to filter states. 
   SomeFilterState& operator=(const SomeFilterState& f);
}; 
  The following composition filters are defined in the OpenFst library:
Line: 236 to 254
 
AltSequenceComposeFilter Requires epsilons on FST2 to be read before epsilons on FST1 doc
MatchComposeFilter Requires epsilons on FST1 to be matched with epsilons on FST2 whenever possible doc
Changed:
<
<
SequenceComposeFilter is the default composition filter. It can be changed by using the version of CompseFst that accepts
>
>
SequenceComposeFilter is the default composition filter. It can be changed by using the version of ComposeFst that accepts
 ComposeFstOptions. doc [bad link?]

Line: 377 to 395
 

Mappers Work in progress, under construction

Changed:
<
<

Matchers Work in progress, under construction

>
>

Matchers

Matchers can find and iterate through requested labels at FST states. In the simplest form, these are just some associative map or search keyed on labels. More generally, they may implement matching special labels that represent sets of labels such as ρ (rest), σ (all) or φ (fail).

The Matcher interface is:

// Specifies matcher action. 
enum MatchType {
   MATCH_INPUT, // Match input label.                        
   MATCH_OUTPUT, // Match output label.                           
   MATCH_NONE, // Match nothing.                             
   MATCH_UNKNOWN, // Match type unknown.                        
};

template <class F>
class SomeMatcher {  
  public:          
   typedef F FST; 
   typedef F::Arc Arc; 
   typedef typename Arc::StateId StateId;           
   typedef typename Arc::Label Label;      
   typedef typename Arc::Weight Weight;   
  
   // Required constructors.                   
   SomeMatcher(const F &fst, MatchType type); 
   SomeMatcher(const SomeMatcher &matcher); 
  
   // Returns the match type that can be provided (depending on   
   // compatibility of the input FST). It is either  
   // the requested match type, MATCH_NONE, or MATCH_UNKNOWN. 
   // If 'test' is false, a constant time test is performed, but 
   // MATCH_UNKNOWN may be returned. If 'test' is true,  
   // a definite answer is returned, but may involve more costly 
   // computation (e.g., visiting the Fst).  
   MatchType Type(bool test) const; 

   // Specifies the current state.        
   void SetState(StateId s); 
 
   // This finds matches to a label at the current state.
   // Returns true if a match found. kNoLabel matches any
   // 'non-consuming' transitions, e.g., epsilon transitions, 
   // which do not require a matching symbol.          
   bool Find(Label label);

   // These iterate through any matches found: 
   // No more matches.   
   bool Done() const; 
   // Current arc (when !Done)    
   const A& Value() const; 
   // Advance to next arc (when !Done) 
   void Next();  
  
   // This specifies the known Fst properties as viewed from this 
   // mapper. It takes as argument the input Fst's known properties.  
   uint64 Properties(uint64 props) const; 
};
 
Added:
>
>
The following matchers are defined in the OpenFst library:

Name Description
SortedMatcher Binary search on sorted input doc
RhoMatcher<M> ρ symbol handling; templated on underlying matcher doc
SigmaMatcher<M> σ symbol handling; templated on underlying matcher doc
PhiMatcher<M> φ symbol handling; templated on underlying matcher doc

SortedMatcher requires the underlying Fst be sorted on the appropriate side. It matches epsilons explicitly (as if it were any other symbol) and as if the current FST state had a self-loop Arc(kNoLabel, 0, Weight::One(), current_state) if the match_type is MATCH_INPUT and Arc(0, kNoLabel, Weight::One(), current_state) if the match_type is MATCH_OUTPUT. This and composition filter implement composition epsilon handling.

The special symbols referenced above are explained by this table:

  Consumes no symbol Consumes symbol
Matches all ε σ
Matches rest φ ρ

The template Matcher<F> selects the pre-designated matcher for Fst type F; it is typically SortedMatcher. Composition uses this matcher by default. It can be changed by using the version of ComposeFst that accepts ComposeFstOptions. doc [bad link?]

An example use of a matcher is here.

 

Mutable Fsts

Line: 548 to 652
 
template <class StateId>                                                      

Changed:
<
<
class Queue {
>
>
class SomeQueue {
  public: // Ctr: may need args (e.g., Fst, comparator) for some queues
Changed:
<
<
Queue(...);
>
>
SomeQueue(...);
  // Returns the head of the queue StateId Head() const; // Inserts a state
Line: 581 to 685
 Some queues accept arc filters to control which transitions are explored.

Changed:
<
<

State Tables Work in progress, under construction

>
>

State Tables

State tables determine the bijective mapping between state tuples (e.g. in composition triples of two FST states and a composition filter state) and their corresponding state IDs. They are classes, templated on state tuples, of the form:

template <class T>                                                          
class SomeStateTable { 
   typedef typename T StateTuple;

   // Required constructors.                                                  
   SomeStateTable(); 
   // Lookup state ID by tuple. If it doesn't exist, then add it.             
   StateId FindState(const StateTuple &);   
   // Lookup state tuple by state ID.     
   const StateTuple<StateId> &Tuple(StateId) const;    
 };

A state tuple has the form:

template <class S>
struct SomeStateTuple {
   typedef typename S StateId; 

   // Required constructor. 
   SomeStateTuple(); 
   // Data 
   ...                    
};

A specific state tuple is a ComposeStateTuple doc [bad link?] that has data members StateId state_id1, StateId state_id2, and FilterState filter_state.

The following state tables are defined in the OpenFst library:

Name Description
HashStateTable Hash map implementation doc
CompactHashStateTable Hash set implementation doc
VectorStateTable Vector implementation doc
VectorHashStateTable Vector and hash set implementation doc
ErasableStateTable Deque implementation - permits erasures doc

Different state tables provide different time and space tradeoffs for applications.

Composition state tables are defined using state tables with ComposeStateTuple. They are the principal data structure used by composition other than the result cache.

The following composition state tables are defined in the OpenFst library:

Name State Table Description
GenericComposeStateTable CompactHashStateTable General-purpose choice doc
ProductComposeStateTable VectorStateTable Efficient when the composition state space is densely populated doc
StringDetComposeStateTable VectorStateTable Efficient when FST1 is a string and FST2 is deterministic doc
DetStringComposeStateTable VectorStateTable Efficient when FST1 is deterministic and FST2 is a string doc
EraseableComposeStateTable ErasableStateTable Allows composition state tuple erasure doc

GenericComposeStateTable is the default composition state table. It can be changed by using the version of ComposeFst that accepts ComposeFstOptions. doc [bad link?]

 

Symbol Tables Work in progress, under construction

Line: 615 to 777
 // states and then calling FinishVisit().

template <class Arc>

Changed:
<
<
class Visitor {
>
>
class SomeVisitor {
 public: typedef typename Arc::StateId StateId;
Changed:
<
<
Visitor(T *return_data);
>
>
SomeVisitor(T *return_data);
  // Invoked before visit void InitVisit(const Fst &fst); // Invoked when state discovered (2nd arg is visitation root)
Line: 676 to 837
 
TropicalWeight TropicalWeightTpl<float>

Weight pairs, such as ProductWeight and LexicographicWeight, can use command line flags to control

Changed:
<
<
their textual formatting. FLAGS_fst_product_weight_separator is printed between the weights (default: ","). FLAGS_fst_parentheses (default: "")
>
>
their textual formatting. FLAGS_fst_pair_weight_separator is printed between the weights (default: ","). FLAGS_fst_piar_parentheses (default: "")
 brackets the pair; if you create complex nested pairs (i.e., tuples), they may need to be printed with non-empty brackets (e.g. "()") to ensure correct parsing if read back in.

Additional weight information:

Revision 102009-03-05 - MichaelRiley

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

OpenFst Advanced Usage

Changed:
<
<
Below are a variety of topics covered in greater depth or of more specialized interest than found in the Quick Tour. Reading the
>
>
natBelow are a variety of topics covered in greater depth or of more specialized interest than found in the Quick Tour. Reading the
 Quick Tour first is recommended.
Changed:
<
<
>
>
/p
 

Arc Iterators

Line: 197 to 197
 Alternatively, the user can process options in his own way and directly assign to any of the above global options if he wishes to modify their defaults.

Changed:
<
<

Composition Filters Work in progress, under construction

>
>

Composition Filters

A composition filter determines which matches are allowed to proceed in composition. The basic filters handle correct epsilon matching. Their interface is:

template <class A>                            
class ComposeFilter {
 public:
   typedef A Arc;
   typedef ... FilterState; 
  
   // Required constructor. 
   ComposeFilter(const Fst<A> &fst1, const Fst<A> &fst2);                       
   // Return start state of filter. 
   FilterState Start() const; 
   // Specifies current composition state. 
   void SetState(StateId s1, StateId s2, const FilterState &f);               
                                                                               
   // Apply filter at current composition state to these transitions.
   // If an arc label to be matched is kNolabel, then that side does not consume a symbol.  
   // Returns the new filter state or, if disallowed, FilterState::NoState().
   // The filter is permitted to modify its inputs, e.g. for optimizations. 
   FilterState FilterArc(A *arc1, A *arc2) const;
 
   // Apply filter at current composition state to these final weights 
   // (cf. superfinal transitions). The filter may modify its inputs,
   // e.g. for optimizations. 
   void FilterFinal(Weight *final1, Weight *final2) const;
}; 
The filter's state is represented by the type ComposeFilter::FilterState, defined by the filter and stored in the composition state table tuple.

The following composition filters are defined in the OpenFst library:

Name Description
SequenceComposeFilter Requires epsilons on FST1 to be read before epsilons on FST2 doc
AltSequenceComposeFilter Requires epsilons on FST2 to be read before epsilons on FST1 doc
MatchComposeFilter Requires epsilons on FST1 to be matched with epsilons on FST2 whenever possible doc

SequenceComposeFilter is the default composition filter. It can be changed by using the version of CompseFst that accepts ComposeFstOptions. doc [bad link?]

 

Expanded Fsts

Revision 92009-03-04 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 169 to 169
 OpenFst has several global options in the library proper that most users can ignore, leaving them with their default values:

Option Type Default Description
Added:
>
>
FLAGS_fst_compat_symbols bool true Require symbol tables to match when appropriate
 
FLAGS_fst_default_cache_gc bool true Enable garbage collection of cached Fsts
FLAGS_fst_default_cache_gc_limit int64 1048576 Byte size that triggers garbage collection of cached Fsts
FLAGS_fst_pair_parentheses string "" Characters enclosing the first weight of a printed pair weight (and derived classes) to ensure proper I/O of nested pair weights; must have size 0 (none) or 2 (open and close parenthesis)
FLAGS_fst_pair_separator string "," Character separator between printed pair weights; must be a single character
FLAGS_fst_verify_properties bool false Verify Fst properites are correctly set when queried
Changed:
<
<
The first two are used to control the caching of expanded state and arc information found in most of the on-the-fly Fst classes; the default values should normally be satisfactory. The second two are used to control the text formating of ProductWeight doc and other weight pairs. The last is used to ensure that the
>
>
The first ensures the arguments of binary FST operations (e.g. ComposeDoc) have compatible symbol tables (e..g output symbol table matches input symbol table for composition). The second two are used to control the caching of expanded state and arc information found in most of the on-the-fly Fst classes; the default values should normally be satisfactory. The next two are used to control the text formating of ProductWeight and other weight pairs. The last is used to ensure that the
 properties of an FST have been correctly set; is is used for debugging only, since it incurs considerable computational cost.

In each of the Fst distribution installed binaries, the above options, as well as any of those defined specific to the binary, can be set from the command line using e.g.

Line: 632 to 635
 
MinMaxWeight MinMaxWeightTpl<float>
TropicalWeight TropicalWeightTpl<float>
Added:
>
>
Weight pairs, such as ProductWeight and LexicographicWeight, can use command line flags to control their textual formatting. FLAGS_fst_product_weight_separator is printed between the weights (default: ","). FLAGS_fst_parentheses (default: "") brackets the pair; if you create complex nested pairs (i.e., tuples), they may need to be printed with non-empty brackets (e.g. "()") to ensure correct parsing if read back in.
 Additional weight information:

Revision 72009-03-04 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="WebHome"
Line: 63 to 63
  Pre-defined arc filters include:
Changed:
<
<
Name Description  
>
>
Name Description
 
AnyArcFilter Accept all arcs doc
EpsilonArcFilter Accept only arcs with input and output epsilons doc
InputEpsilonArcFilter Accept only arcs with input epsilons doc
OutputEpsilonArcFilter Accept only arcs with output epsilons doc
Added:
>
>

Arcs

An Arc is a type that represents an FST transition from a given source state. It specifies an input label, an output label, a weight, and a destination state ID and it has a type name. In particular, it has the following form:

struct Arc {
   typedef W Weight;
   typedef L Label;
   typedef S StateId;

   static const string &Type();

   Label ilabel;
   Label olabel;
   Weight weight;
   StateId nextstate;
};

where W is a valid weight type, and L and S are signed integral types.

The following arc types are defined in the OpenFst library:

Name Label Type State ID Type Weight Type Registered
GallicArc<A, S> A::Label A::StateId GallicWeight<A::Label, A::Weight, S>  
LexicographicArc<W1, W2> int int LexicographicWeight<W1, W2>  
LogArc int int LogWeight DONE
MinMaxArc int int MinMaxWeight  
ProductArc<W1, W2> int int ProductWeight<W1, W2>  
StdArc int int TropicalWeight DONE
StringArc<S> int int StringWeight<int, S>  

Additional arc information:

 

Base Fsts

Line: 188 to 224
 ConstFst doc

Changed:
<
<

FST Input/Output Work in progress, under construction

>
>

FST Input/Output

The following code:

VectorFst<A> ifst;
...
ifst.Write("a.fst");
VectorFst<A> *ofst = VectorFst<A>::Read("a.fst");

writes and reads a defined Fst type (VectorFst) and arc type (A) to and from a file in a straight-forward way.

Library Registration

The call:

 
Added:
>
>
Fst<Arc> *fst = Fst<A>::Read("a.fst");

reads the same VectorFst from the file as above, but returns a base Fst. This form, useful for code that works generically for different Fst types, can not work unless the Fst and arc type are library-registered. Some arc types (see here) are already registered for all the Fst types defined in the OpenFst library. Other arc type A and Fst type F pairs can be registered with the following call:

REGISTER_FST(F, A);

To avoid code bloat in a given program, registering arc types, in particular, should be used sparingly.

Main Registration

In the above examples, the user provided the arc type as a template parameter. However, the call:

$ fstinfo a.fst

works e.g. for both StdArc and LogArc arcs. This is accomplished by calling in main(argc, argv):

return CALL_FST_MAIN(InfoMain, argc, argv);

where:

template <class Arc>
int InfoMain(int argc; char **argv, istream &strm, const FstReadOptions &opts) {
    Fst<Arc> *fst = Fst<Arc>::Read(strm, opts);
    ...
    return 0;
}

is a templated `main' function that does the arc-specific work. CALL_FST_MAIN passes to InfoMain the command line arguments and an opened stream to an Fst (opened from the first argument or standard input if no arguments). CALL_FST_MAIN does the type dispatch by examining the Fst's header and then passing on the (partially-read) input stream, which can be used by InfoMain to read in the actual Fst. This dispatch works only with arc and main function pairs that have been main-registered. Each OpenFst distribution binary registers its templated main function with the arc types marked registered here. An arc type A and main function M pair can be registered with the following call:

REGISTER_FST_MAIN(M, A);

To avoid code bloat in a given program, registering arc types should be used sparingly.

To use main registration in your own program, you need to include additionally <fst/main.h> and link additionally to libfstmain.so.

FST Dynamic Shared Objects

The examples above show how users can modify programs to be able to read new arc and Fst types. However, it would not be ideal to have to do so for all the distribution binaries or other existing programs. Instead, this can be done more easily with dynamic shared objects (DSOs).

To add a new Fst type, MyFst with MyFst::Type() = "my_fst", use the code:

extern "C" {
void my_fst_init() { 
  // Register some arc types with this Fst type 
  REGISTER_FST(MyFst, StdArc);
  REGISTER_FST(MyFst, LogArc);
}
}

compiled into a dynamic shared object my_fst.so. If my_fst.so can be found in the LD_LIBRARY_PATH (or equivalent), you should be able to read the new Fst type with existing programs.

To add a new arc type, MyArc with MyArc::Type() = "my_arc", use the code:

extern "C" {
void my_arc_init() { 
  // Register some Fst types with this arc type 
  REGISTER_FST(VectorFst, MyArc);
  REGISTER_FST(ConstFst, MyArc);

  // Register the OpenFst binaries with this arc type 
  REGISTER_FST_MAINS(MyArc); 
  // Register some other main with this arc type 
  REGISTER_FST_MAIN(SomeMain, MyArc);
}
}

compiled into a dynamic shared object my_arc.so. If can be found in LD_LIBRARY_PATH (or equivalent), you should be able to read the new arc type with existing programs.

Mappers Work in progress, under construction

 

Matchers Work in progress, under construction

Line: 245 to 387
  The companion mutable arc iterator class provides access to and modification of the transitions of the FST
Added:
>
>

Natural Orders

The natural order ≤ associated with a semiring is defined as a ≤ b iff a ⊕ b = a. In the OpenFst library, we define the strict version of this order as:

template <class W>
NaturalLess() {
  bool operator()(const W &w1, const W &w2) const {
    return (Plus(w1, w2) == w1) && w1 != w2;
  }
};

An order is left monotonic w.r.t a semring iff a ≤ b ⇒ ∀c, c ⊕ a ≤ c ⊕ b and c ⊗ a ≤ c ⊗ b; right monotonic is defined similarly. An order is negative iff 10.

The natural order is a left (right) monotonic and negative partial order iff the semiring is idempotent and left (right) distributive. It is a total order iff the semiring has the path property. See Mohri, "Semiring Framework and Algorithms for Shortest-Distance Problems", Journal of Automata, Languages and Combinatorics 7(3):321-350, 2002.

This is the default total order (under the requirements above) that we use for the shortest path and pruning algorithms. This order is the natural one to use given that it generally needs to be total, monotonic and. negative: total so that all weights can be compared, monotonic so there is a practical algorithm, and negative so that the "free" weight 1 is preferred to the "disallowed" weight 0.

 

Properties

Line: 356 to 526
  Pre-defined state queues include:
Changed:
<
<
Queue Description  
>
>
Queue Description
 
AutoQueue Automatically-selected from Fst properties doc
FifoQueue First-In, first-Out doc
LifoQueue Last-In, first-Out doc
Line: 372 to 542
 

Changed:
<
<

User-defined Fst Arcs and Weights Work in progress, under construction

>
>

User-defined Fst Arcs and Weights

 
Added:
>
>
A user may define his own weight type so long as it meets the necessary requirements.

A user may define his own arc type so long as has the right form. Some Fst I/O with new arc types requires registration.

 

User-defined Fst Classes Work in progress, under construction

Line: 427 to 600
  Pre-defined FST visitors include:
Changed:
<
<
Visitor Type Description  
>
>
Visitor Type Description
 
CopyVisitor Visit Copies in a queue-specified order doc
SccVisitor DfsVisit Finds strongly-connected components, accessibility and coaccessibility doc
TopOrderVisitor DfsVisit Finds topological order doc

The visit operations optionally accept arc filters to control which transitions are explored.

Added:
>
>

Weights

A Weight is a type that represents an FST transition's cost.

The following basic weight templates are defined in the OpenFst library:

Semiring Name Set
(Plus)

(Times)
0
(Zero)
1
(One)
Notes
Lexicographic LexicographicWeight<W1, W2> W1 X W2 min W1 X ⊗W2 (0W1,0W2) (1W1,1W2) min: lexicographic order w.r.t.
W1 and W2 natural orders
doc
Log LogWeightTpl<T> [-∞, ∞] -log(e-x + e-y) + 0 T: floating point doc
MinMax MinMaxWeightTpl<T> [-∞, ∞] min max -∞ T: floating point doc
Product ProductWeight<W1, W2> W1 X W2 W1 X ⊕W2 W1 X ⊗W2 (0W1,0W2) (1W1,1W2)   doc
String StringWeight<L, STRING_LEFT> L* ∪ {∞} longest com. prefix ε L: signed integral doc
  StringWeight<L, STRING_RIGHT> L* ∪ {∞} longest com. suffix ε L: signed integral doc
Tropical TropicalWeightTpl<T> [-∞, ∞] min + 0 T: floating point doc

The following weight types have been defined in the OpenFst library in terms of the above:

Name Type
GallicWeight<L, W, S> ProductWeight<StringWeight<L, S>, W>
LogWeight LogWeightTpl<float>
MinMaxWeight MinMaxWeightTpl<float>
TropicalWeight TropicalWeightTpl<float>

Additional weight information:

 -- MichaelRiley - 27 Feb 2009

Revision 62009-03-03 - MichaelRiley

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

Arc Iterators

Changed:
<
<
An arc iterator doc has the form:
>
>
An arc iterator doc is used to access the transitions leaving an FST state. It has the form:
 
Changed:
<
<
template <class F>
>
>
template <class F>

 class ArcIterator { typedef typename F::Arc Arc; typedef typename Arc::StateId StateId;

public:

Changed:
<
<
ArcIterator(const &F fst, StateId s); // End of iterator? bool Done() const; // Current arc (when Done) const Arc& Value() const; // Advance to next arc (when Done) void Next(); // Return to initial condition void Reset(); // Arc access by position void Seek(size_t posi);
>
>
ArcIterator(const &F fst, StateId s); // End of iterator? bool Done() const; // Current arc (when Done) const Arc& Value() const; // Advance to next arc (when Done) void Next(); // Return current position size_t Position(); // Return to initial position void Reset(); // Arc access by position void Seek(size_t pos);
 };
Changed:
<
<
>
>

It is templated on the Fst class F to allow efficient specializations but defaults to a generic version on the abstract base Fst class.

See here for conventions that arc iterator use must respect.

  All current OpenFst library Seek() methods are constant time.
Line: 45 to 52
  Arc filters are accepted by various operations to control which arcs are transitioned. An arc filter has the form:
Changed:
<
<
template <class Arc>