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