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
|
void Compose(const Fst &ifst1, const Fst &ifst2, MutableFst *ofst);
| [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)
|
|
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(V1 V2 D1 log D2),
where Vi = # of states and Di = maximum out-degree
for the ith FST.
ComposeFst
:
- Constructor: O(1)
- Traversal: O(v1 v2 d1 log d2),
where vi = # of states visited and di = maximum out-degree of the states visited.for the ith FST and 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