Difference: ComposeDoc (1 vs. 24)

Revision 242018-04-27 - MichaelRiley

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

Compose

Line: 20 to 20
 |
template <class Arc> 
void Compose(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2, MutableFst<Arc> *ofst);
Changed:
<
<
| doc [bad link?] |
>
>
| |
 |
template <class Arc> ComposeFst<Arc>::
ComposeFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2);

Revision 232014-04-23 - MichaelRiley

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

Compose

Line: 86 to 86
  See here for more discussion on efficient usage.
Changed:
<
<
-- MichaelRiley - 15 Jun 2007
>
>

See Also

Composition Filters, Matchers, State Tables

 
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183240047" name="compose2.jpg" path="compose2.jpg" size="11516" user="Main.MichaelRiley" version="7"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183240022" name="compose1.jpg" path="compose1.jpg" size="12003" user="Main.MichaelRiley" version="2"

Revision 222012-05-13 - MichaelRiley

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

Compose

Line: 84 to 84
  or the input side of the second transducer or prefer placing them later in a path since they delay matching and can introduce non-coaccessible states and transitions
Added:
>
>
See here for more discussion on efficient usage.
 -- MichaelRiley - 15 Jun 2007

META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183240047" name="compose2.jpg" path="compose2.jpg" size="11516" user="Main.MichaelRiley" version="7"

Revision 212012-01-19 - MichaelRiley

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

Compose

Line: 74 to 74
 Compose and fstcompose trim their output, ComposeFst does not (since it is a delayed operation).

The efficiency of composition can be strongly affected by several factors:

Changed:
<
<
  • the choice of which transducer is sorted - prefer sorting the FST that has the greater average out-degree;
  • the amount of non-determinism;
>
>
  • the choice of which transducer is sorted
    • prefer sorting the FST that has the greater average out-degree
    • sorting both transducers allows composition to automatically select the best transducer to match against (per state pair)
    • note stored sort properties of the FSTs are first checked in constant time followed by the minimum number of linear-time sort tests necessary to discover one sorted FST; thus composition may be unaware that both FSTs are sorted when those properties are not stored.
  • the amount of non-determinism
 
  • the presence and location of epsilon transitions - avoid epsilon transitions on the output side of the first transducer or the input side of the second transducer or prefer placing them later in a path since they
Changed:
<
<
delay matching and can introduce non-coaccessible states and transitions.
>
>
delay matching and can introduce non-coaccessible states and transitions
  -- MichaelRiley - 15 Jun 2007

Revision 202011-12-06 - MichaelRiley

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

Compose

Revision 192009-03-06 - MichaelRiley

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

Compose

Line: 12 to 12
  matchers). The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight for instance).
Changed:
<
<
Versions of this operation (not all shown here) accept options that allow choosing the matcher, composition filter, state table and, when delayed, the caching behaviour used by composition.
>
>
Versions of this operation (not all shown here) accept options that allow choosing the matcher, composition filter, state table and, when delayed, the caching behavior used by composition.
 

Usage

Revision 182009-03-06 - CyrilAllauzen

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

Compose

Line: 10 to 10
  The output labels of the first transducer or the input labels of the second transducer must be sorted (or the FSTs otherwise support appropriate matchers).
Changed:
<
<
The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight).
>
>
The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight for instance).

Versions of this operation (not all shown here) accept options that allow choosing the matcher, composition filter, state table and, when delayed, the caching behaviour used by composition.

 

Usage

Line: 63 to 66
 
  • Space: O(v1 v2)
where vi = # of states visited, di = maximum out-degree, and mi = maximum multiplicity of the states visited.for the ith FST.
Changed:
<
<
Constant time and space to visit an input state or arc is assumed and exclusive of caching.
>
>
Constant time and space to visit an input state or arc is assumed and exclusive of caching.
 

Caveats

Revision 172009-03-03 - MichaelRiley

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

Compose

Line: 10 to 10
  The output labels of the first transducer or the input labels of the second transducer must be sorted (or the FSTs otherwise support appropriate matchers).
Changed:
<
<
The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight).
>
>
The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight).
 

Usage

Revision 162009-02-26 - MichaelRiley

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

Compose

Line: 8 to 8
 transduces y to z with weight b, then their composition transduces string x to z with weight a ⊗ b.
Changed:
<
<
The output labels of the first transducer or the input labels of the second transducer must be sorted.
>
>
The output labels of the first transducer or the input labels of the second transducer must be sorted (or the FSTs otherwise support appropriate matchers).
 The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight).

Usage

Revision 152007-07-11 - MichaelRiley

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

Compose

Line: 6 to 6
  This operation computes the composition of two transducers. If A transduces string x to y with weight a and B transduces y to z with weight b, then their composition transduces
Changed:
<
<
string x to z with weight Times(x, z).
>
>
string x to z with weight a ⊗ b.
  The output labels of the first transducer or the input labels of the second transducer must be sorted. The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight).

Revision 142007-07-04 - CyrilAllauzen

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

Compose

Line: 70 to 70
 Compose and fstcompose trim their output, ComposeFst does not (since it is a delayed operation).

The efficiency of composition can be strongly affected by several factors:

Changed:
<
<
  • the choice of which tnansducer is sorted - prefer sorting the FST that has the greater average out-degree.
  • the amount of non-determinism
>
>
  • the choice of which transducer is sorted - prefer sorting the FST that has the greater average out-degree;
  • the amount of non-determinism;
 
  • the presence and location of epsilon transitions - avoid epsilon transitions on the output side of the first transducer or the input side of the second transducer or prefer placing them later in a path since they delay matching and can introduce non-coaccessible states and transitions.

Revision 132007-07-02 - MichaelRiley

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

Compose

Line: 52 to 52
 Assuming the first FST is unsorted and the second is sorted:

Compose:

Changed:
<
<
  • Time: O(V1 V2 D1 log D2)
  • Space: O(V1 V2 D1 D2)
where Vi = # of states and Di = maximum out-degree for the ith FST.
>
>
  • Time: O(V1 V2 D1 (log D2 + M2))
  • Space: O(V1 V2 D1 M2)
where Vi = # of states, Di = maximum out-degree and Mi = maximum multiplicity for the ith FST.
  ComposeFst:
Changed:
<
<
  • TIme: O(v1 v2 d1 log d2),
>
>
  • TIme: O(v1 v2 d1 (log d2 + m2)),
 
  • Space: O(v1 v2)
Changed:
<
<
where vi = # of states visited and di = maximum out-degree of the states visited.for the ith FST.
>
>
where vi = # of states visited, di = maximum out-degree, and mi = maximum multiplicity of the states visited.for the ith FST.
 Constant time and space to visit an input state or arc is assumed and exclusive of caching.

Line: 72 to 72
 The efficiency of composition can be strongly affected by several factors:
  • the choice of which tnansducer is sorted - prefer sorting the FST that has the greater average out-degree.
Added:
>
>
  • the amount of non-determinism
 
  • the presence and location of epsilon transitions - avoid epsilon transitions on the output side of the first transducer or the input side of the second transducer or prefer placing them later in a path since they delay matching and can introduce non-coaccessible states and transitions.

Revision 122007-07-02 - MichaelRiley

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

Compose

Line: 51 to 51
  Assuming the first FST is unsorted and the second is sorted:
Changed:
<
<
Compose: O(V1 V2 D1 log D2),
>
>
Compose:
  • Time: O(V1 V2 D1 log D2)
  • Space: O(V1 V2 D1 D2)
 where Vi = # of states and Di = maximum out-degree for the ith FST.

ComposeFst:

Changed:
<
<
  • Constructor: O(1)
  • Traversal: O(v1 v2 d1 log d2),
>
>
  • TIme: O(v1 v2 d1 log d2),
  • Space: O(v1 v2)
  where vi = # of states visited and di = maximum out-degree of the
Changed:
<
<
states visited.for the ith FST and constant time to visit an input state or arc is assumed.
>
>
states visited.for the ith FST. Constant time and space to visit an input state or arc is assumed and exclusive of caching.
 

Caveats

Revision 112007-07-01 - MichaelRiley

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

Compose

Line: 13 to 13
 

Usage

Changed:
<
<
|
>
>
|
template <class Arc> 
 void Compose(const Fst &ifst1, const Fst &ifst2, MutableFst *ofst); | doc [bad link?] | |
Line: 58 to 59
 
  • Constructor: O(1)
  • Traversal: O(v1 v2 d1 log d2),
    where vi = # of states visited and di = maximum out-degree of the
Changed:
<
<
states visited.for the ith FST and assuming constant time to visit an input state or arc.
>
>
states visited.for the ith FST and constant time to visit an input state or arc is assumed.
 

Caveats

Revision 102007-06-30 - MichaelRiley

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

Compose

Line: 13 to 13
 

Usage

Changed:
<
<
|
template <class Arc> 
>
>
|
 void Compose(const Fst &ifst1, const Fst &ifst2, MutableFst *ofst); | doc [bad link?] | |
Line: 51 to 50
  Assuming the first FST is unsorted and the second is sorted:
Changed:
<
<
Compose: O((nstates1 * nstates2 * max_out_degree1 log(max_out_degree2))
ComposeFst:
>
>
Compose: O(V1 V2 D1 log D2), where Vi = # of states and Di = maximum out-degree for the ith FST.

ComposeFst:

 
  • Constructor: O(1)
Changed:
<
<
  • Traversal: O((nstates1_visited * nstates2_visited * max_out_degree1_visited * log(max_out_degree2_visited)),
    assuming constant time to visit an input state or arc.
>
>
  • Traversal: O(v1 v2 d1 log d2),
    where vi = # of states visited and di = maximum out-degree of the states visited.for the ith FST and assuming constant time to visit an input state or arc.
 

Caveats

Line: 71 to 74
  -- MichaelRiley - 15 Jun 2007
Changed:
<
<
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462230" name="compose2.jpg" path="compose2.jpg" size="8826" user="Main.MichaelRiley" version="6"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462230" name="compose1.jpg" path="compose1.jpg" size="7902" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462230" name="compose3.jpg" path="compose3.jpg" size="10184" user="Main.MichaelRiley" version="5"
>
>
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183240047" name="compose2.jpg" path="compose2.jpg" size="11516" user="Main.MichaelRiley" version="7"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183240022" name="compose1.jpg" path="compose1.jpg" size="12003" user="Main.MichaelRiley" version="2"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183240071" name="compose3.jpg" path="compose3.jpg" size="15164" user="Main.MichaelRiley" version="6"

Revision 92007-06-30 - MichaelRiley

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

Compose

Line: 46 to 46
 fstcompose a.fst b.fst out.fst
Added:
>
>
 

Complexity

Assuming the first FST is unsorted and the second is sorted:

Line: 56 to 57
 
  • Traversal: O((nstates1_visited * nstates2_visited * max_out_degree1_visited * log(max_out_degree2_visited)),
    assuming constant time to visit an input state or arc.
Added:
>
>
 

Caveats

Compose and fstcompose trim their output, ComposeFst does not (since it is a delayed operation).

Line: 63 to 65
 The efficiency of composition can be strongly affected by several factors:
  • the choice of which tnansducer is sorted - prefer sorting the FST that has the greater average out-degree.
Changed:
<
<
  • the presence and location of epsilon transitions - avoid epsilon transitions on the output side of the first transducer
>
>
  • the presence and location of epsilon transitions - avoid epsilon transitions on the output side of the first transducer
  or the input side of the second transducer or prefer placing them later in a path since they delay matching and can introduce non-coaccessible states and transitions.

Revision 82007-06-30 - MichaelRiley

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

Compose

Line: 22 to 22
 ComposeFst(const Fst &fst1, const Fst &fst2); | doc | |
Changed:
<
<
fstcompose a.fst b.fst out.fst -connect: Trim output (def: true)
>
>
fstcompose [--opts] a.fst b.fst out.fst --connect: Trim output (def: true)
  | |

Examples

Revision 72007-06-26 - MichaelRiley

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

Compose

Line: 13 to 13
 

Usage

Changed:
<
<
>
>
|
 template void Compose(const Fst &ifst1, const Fst &ifst2, MutableFst *ofst);
Changed:
<
<
>
>
| doc [bad link?] | |
 template ComposeFst:: ComposeFst(const Fst &fst1, const Fst &fst2);
Changed:
<
<
>
>
| doc | |
 fstcompose a.fst b.fst out.fst -connect: Trim output (def: true)
Changed:
<
<
>
>
| |
 

Examples

Revision 62007-06-23 - MichaelRiley

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

Compose

Line: 21 to 21
 ComposeFst(const Fst &fst1, const Fst &fst2);

fstcompose a.fst b.fst out.fst

Added:
>
>
-connect: Trim output (def: true)
 

Examples

Line: 66 to 67
  -- MichaelRiley - 15 Jun 2007
Changed:
<
<
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1181964136" name="compose2.jpg" path="compose2.jpg" size="8826" user="Main.MichaelRiley" version="6"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1181962547" name="compose1.jpg" path="compose1.jpg" size="7902" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1181964162" name="compose3.jpg" path="compose3.jpg" size="10184" user="Main.MichaelRiley" version="5"
>
>
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462230" name="compose2.jpg" path="compose2.jpg" size="8826" user="Main.MichaelRiley" version="6"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462230" name="compose1.jpg" path="compose1.jpg" size="7902" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462230" name="compose3.jpg" path="compose3.jpg" size="10184" user="Main.MichaelRiley" version="5"

Revision 52007-06-20 - MichaelRiley

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

Compose

Revision 42007-06-17 - MichaelRiley

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

Compose

Line: 46 to 46
 

Complexity

Changed:
<
<
Compose: O((nstates1 + narcs1) * (nstates2 + narcs2))
>
>
Assuming the first FST is unsorted and the second is sorted:

Compose: O((nstates1 * nstates2 * max_out_degree1 log(max_out_degree2))

 ComposeFst:
  • Constructor: O(1)
Changed:
<
<
  • Traversal: O((nstates1_visited + narcs1_visited) * (nstates2_visited + narcs2_visited)), assuming constant time to visit an input state or arc.
>
>
  • Traversal: O((nstates1_visited * nstates2_visited * max_out_degree1_visited * log(max_out_degree2_visited)),
    assuming constant time to visit an input state or arc.
 

Caveats

Revision 32007-06-16 - MichaelRiley

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

Compose

Description

Changed:
<
<
This operation omputes the composition of two transducers. If A transduces string x to y with weight a and B
>
>
This operation computes the composition of two transducers. If A transduces string x to y with weight a and B
 transduces y to z with weight b, then their composition transduces string x to z with weight Times(x, z).
Line: 51 to 51
 
  • Constructor: O(1)
  • Traversal: O((nstates1_visited + narcs1_visited) * (nstates2_visited + narcs2_visited)), assuming constant time to visit an input state or arc.
Added:
>
>

Caveats

Compose and fstcompose trim their output, ComposeFst does not (since it is a delayed operation).

The efficiency of composition can be strongly affected by several factors:

  • the choice of which tnansducer is sorted - prefer sorting the FST that has the greater average out-degree.
  • the presence and location of epsilon transitions - avoid epsilon transitions on the output side of the first transducer or the input side of the second transducer or prefer placing them later in a path since they delay matching and can introduce non-coaccessible states and transitions.
 -- MichaelRiley - 15 Jun 2007

META FILEATTACHMENT attr="" autoattached="1" comment="" date="1181964136" name="compose2.jpg" path="compose2.jpg" size="8826" user="Main.MichaelRiley" version="6"

Revision 22007-06-16 - MichaelRiley

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

Compose

Line: 8 to 8
 transduces y to z with weight b, then their composition transduces string x to z with weight Times(x, z).
Changed:
<
<
The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight).
>
>
The output labels of the first transducer or the input labels of the second transducer must be sorted.

The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight).

Usage

template <class Arc> 
void Compose(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2, MutableFst<Arc> *ofst);

template <class Arc> ComposeFst<Arc>::
ComposeFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2);

fstcompose a.fst b.fst out.fst
 

Examples

Revision 12007-06-16 - MichaelRiley

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

Compose

Description

This operation omputes the composition of two transducers. If A transduces string x to y with weight a and B transduces y to z with weight b, then their composition transduces string x to z with weight Times(x, z).

The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight).

Examples

A:

compose1.jpg

B:

compose2.jpg

A o B:

compose3.jpg

Compose(A, B, &C);
ComposeFst<Arc>(A, B);
fstcompose a.fst b.fst out.fst

Complexity

Compose: O((nstates1 + narcs1) * (nstates2 + narcs2))
ComposeFst:

  • Constructor: O(1)
  • Traversal: O((nstates1_visited + narcs1_visited) * (nstates2_visited + narcs2_visited)), assuming constant time to visit an input state or arc.

-- MichaelRiley - 15 Jun 2007

META FILEATTACHMENT attr="" autoattached="1" comment="" date="1181964136" name="compose2.jpg" path="compose2.jpg" size="8826" user="Main.MichaelRiley" version="6"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1181962547" name="compose1.jpg" path="compose1.jpg" size="7902" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1181964162" name="compose3.jpg" path="compose3.jpg" size="10184" user="Main.MichaelRiley" version="5"
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback