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 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
:
B
:
A o B
:
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