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



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 a ⊗ b.

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 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 behavior used by composition.


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






A o B:


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


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


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


  • TIme: O(v1 v2 d1 (log d2 + m2)),
  • 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. Constant time and space to visit an input state or arc is assumed and exclusive of caching.


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

-- MichaelRiley - 15 Jun 2007

Topic attachments
I Attachment History Action Size Date Who Comment
JPEGjpg compose1.jpg r2 r1 manage 11.7 K 2007-06-30 - 21:47 MichaelRiley  
JPEGjpg compose2.jpg r7 r6 r5 r4 r3 manage 11.2 K 2007-06-30 - 21:47 MichaelRiley  
JPEGjpg compose3.jpg r6 r5 r4 r3 r2 manage 14.8 K 2007-06-30 - 21:47 MichaelRiley  
Edit | Attach | Watch | Print version | History: r24 | r22 < r21 < r20 < r19 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r20 - 2011-12-06 - MichaelRiley
Ideas, requests, problems regarding TWiki? Send feedback