Closure
Description
This operation computes the concatenative closure. If
A
transduces string
x
to
y
with weight
a
, then the
closure transduces
x
to
y
with weight
a
,
xx
to
yy
with weight
a ⊗ a
,
xxx
to
yyy
with weight
a ⊗ a ⊗ a
,
etc. If
closure_type
is
CLOSURE_STAR
, then the empty string is
transduced to itself with weight
1
as well.
Usage
enum ClosureType { CLOSURE_STAR, CLOSURE_PLUS };
template<class Arc>
void Closure(MutableFst<Arc> *fst, ClosureType type);
|
|
template <class Arc> ClosureFst<Arc>::
ClosureFst(const Fst<Arc> &fst, ClosureType type);
|
|
fstclosure [--opts] a.fst out.fst
--closure_type: closure_star (def) | closure_plus
|
|
Examples
A
:
A*
:
Closure(&A, CLOSURE_STAR);
ClosureFst<Arc>(A, CLOSURE_STAR);
fstclosure a.fst out.fst
A+
:
Closure(&A, CLOSURE_PLUS);
ClosureFst<Arc>(A, CLOSURE_PLUS);
fstclosure --closure_plus a.fst out.fst
Complexity
Closure
:
where
V = # of states and
E = # of arcs.
ClosureFst:
where
v = # of states visited,
e = # of arcs visited.
Constant time to visit an input state or arc is assumed and exclusive of
caching.
--
MichaelRiley - 13 Jun 2007