1 // closure.h
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 //
16 // \file
17 // Functions and classes to compute the concatenative closure of an Fst.
18
19 #ifndef FST_LIB_CLOSURE_H__
20 #define FST_LIB_CLOSURE_H__
21
22 #include "fst/lib/mutable-fst.h"
23 #include "fst/lib/rational.h"
24
25 namespace fst {
26
27 // Computes the concatenative closure. This version modifies its
28 // MutableFst input. If FST transduces string x to y with weight a,
29 // then the closure transduces x to y with weight a, xx to yy with
30 // weight Times(a, a), xxx to yyy with with Times(Times(a, a), a),
31 // etc. If closure_type == CLOSURE_STAR, then the empty string is
32 // transduced to itself with weight Weight::One() as well.
33 //
34 // Complexity:
35 // - Time: O(V)
36 // - Space: O(V)
37 // where V = # of states.
38 template<class Arc>
Closure(MutableFst<Arc> * fst,ClosureType closure_type)39 void Closure(MutableFst<Arc> *fst, ClosureType closure_type) {
40 typedef typename Arc::StateId StateId;
41 typedef typename Arc::Label Label;
42 typedef typename Arc::Weight Weight;
43
44 uint64 props = fst->Properties(kFstProperties, false);
45 StateId start = fst->Start();
46 for (StateIterator< MutableFst<Arc> > siter(*fst);
47 !siter.Done();
48 siter.Next()) {
49 StateId s = siter.Value();
50 Weight final = fst->Final(s);
51 if (final != Weight::Zero())
52 fst->AddArc(s, Arc(0, 0, final, start));
53 }
54 if (closure_type == CLOSURE_STAR) {
55 StateId nstart = fst->AddState();
56 fst->SetStart(nstart);
57 fst->SetFinal(nstart, Weight::One());
58 if (start != kNoLabel)
59 fst->AddArc(nstart, Arc(0, 0, Weight::One(), start));
60 }
61 fst->SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR),
62 kFstProperties);
63 }
64
65 // Computes the concatenative closure. This version modifies its
66 // RationalFst input.
67 template<class Arc>
Closure(RationalFst<Arc> * fst,ClosureType closure_type)68 void Closure(RationalFst<Arc> *fst, ClosureType closure_type) {
69 fst->Impl()->AddClosure(closure_type);
70 }
71
72
73 struct ClosureFstOptions : RationalFstOptions {
74 ClosureType type;
75
ClosureFstOptionsClosureFstOptions76 ClosureFstOptions(const RationalFstOptions &opts, ClosureType t)
77 : RationalFstOptions(opts), type(t) {}
ClosureFstOptionsClosureFstOptions78 explicit ClosureFstOptions(ClosureType t) : type(t) {}
ClosureFstOptionsClosureFstOptions79 ClosureFstOptions() : type(CLOSURE_STAR) {}
80 };
81
82
83 // Computes the concatenative closure. This version is a delayed
84 // Fst. If FST transduces string x to y with weight a, then the
85 // closure transduces x to y with weight a, xx to yy with weight
86 // Times(a, a), xxx to yyy with weight Times(Times(a, a), a), etc. If
87 // closure_type == CLOSURE_STAR, then The empty string is transduced
88 // to itself with weight Weight::One() as well.
89 //
90 // Complexity:
91 // - Time: O(v)
92 // - Space: O(v)
93 // where v = # of states visited. Constant time and space to visit an
94 // input state or arc is assumed and exclusive of caching.
95 template <class A>
96 class ClosureFst : public RationalFst<A> {
97 public:
98 using RationalFst<A>::Impl;
99
100 typedef A Arc;
101
ClosureFst(const Fst<A> & fst,ClosureType closure_type)102 ClosureFst(const Fst<A> &fst, ClosureType closure_type) {
103 Impl()->InitClosure(fst, closure_type);
104 }
105
ClosureFst(const Fst<A> & fst,const ClosureFstOptions & opts)106 ClosureFst(const Fst<A> &fst, const ClosureFstOptions &opts)
107 : RationalFst<A>(opts) {
108 Impl()->InitClosure(fst, opts.type);
109 }
110
ClosureFst(const ClosureFst<A> & fst)111 ClosureFst(const ClosureFst<A> &fst) : RationalFst<A>(fst) {}
112
Copy()113 virtual ClosureFst<A> *Copy() const { return new ClosureFst<A>(*this); }
114 };
115
116
117 // Specialization for ClosureFst.
118 template <class A>
119 class StateIterator< ClosureFst<A> > : public StateIterator< RationalFst<A> > {
120 public:
StateIterator(const ClosureFst<A> & fst)121 explicit StateIterator(const ClosureFst<A> &fst)
122 : StateIterator< RationalFst<A> >(fst) {}
123 };
124
125
126 // Specialization for ClosureFst.
127 template <class A>
128 class ArcIterator< ClosureFst<A> > : public ArcIterator< RationalFst<A> > {
129 public:
130 typedef typename A::StateId StateId;
131
ArcIterator(const ClosureFst<A> & fst,StateId s)132 ArcIterator(const ClosureFst<A> &fst, StateId s)
133 : ArcIterator< RationalFst<A> >(fst, s) {}
134 };
135
136
137 // Useful alias when using StdArc.
138 typedef ClosureFst<StdArc> StdClosureFst;
139
140 } // namespace fst
141
142 #endif // FST_LIB_CLOSURE_H__
143