TWiki> FST Web>FstQuickTour>ComposeDoc (revision 3)EditAttach

Compose

Description

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).

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

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.

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

Topic attachments
I Attachment History Action Size Date Who Comment
JPEGjpg compose1.jpg r1 manage 7.7 K 2007-06-16 - 02:55 MichaelRiley  
JPEGjpg compose2.jpg r6 r5 r4 r3 r2 manage 8.6 K 2007-06-16 - 03:22 MichaelRiley  
JPEGjpg compose3.jpg r5 r4 r3 r2 r1 manage 9.9 K 2007-06-16 - 03:22 MichaelRiley  
Edit | Attach | Watch | Print version | History: r24 | r5 < r4 < r3 < r2 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r3 - 2007-06-16 - MichaelRiley
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback