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);	[bad link?]
template <class Arc> ComposeFst<Arc>:: ComposeFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2);
fstcompose a.fst b.fst out.fst -connect: Trim output (def: true)

Examples

A:

B:

A o B:

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

Complexity

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

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