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
Times(a, a)
,
xxx
to
yyy
with weight
Times(Times(a, a), a)
,
etc. If
closure_type
is
CLOSURE_STAR
, then the empty string is
transduced to itself with weight
Weight::One()
as well.
Usage
enum ClosureType { CLOSURE_STAR, CLOSURE_PLUS };
template<class Arc>
void Closure(MutableFst<Arc> *fst, ClosureType type);
|
[bad link?] |
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
:
O(nstates + narcs)
ClosureFst:
- Constructor: O(1)
- Traversal: O(nstates_visited + narcs_visited),
assuming constant time to visit an input state or arc.
--
MichaelRiley - 13 Jun 2007