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 // Copyright 2005-2010 Google, Inc.
16 // Author: riley@google.com (Michael Riley)
17 //
18 // \file
19 // Functions and classes to compute the concatenative closure of an Fst.
20
21 #ifndef FST_LIB_CLOSURE_H__
22 #define FST_LIB_CLOSURE_H__
23
24 #include <vector>
25 using std::vector;
26 #include <algorithm>
27
28 #include <fst/mutable-fst.h>
29 #include <fst/rational.h>
30
31
32 namespace fst {
33
34 // Computes the concatenative closure. This version modifies its
35 // MutableFst input. If FST transduces string x to y with weight a,
36 // then the closure transduces x to y with weight a, xx to yy with
37 // weight Times(a, a), xxx to yyy with with Times(Times(a, a), a),
38 // etc. If closure_type == CLOSURE_STAR, then the empty string is
39 // transduced to itself with weight Weight::One() as well.
40 //
41 // Complexity:
42 // - Time: O(V)
43 // - Space: O(V)
44 // where V = # of states.
45 template<class Arc>
Closure(MutableFst<Arc> * fst,ClosureType closure_type)46 void Closure(MutableFst<Arc> *fst, ClosureType closure_type) {
47 typedef typename Arc::StateId StateId;
48 typedef typename Arc::Label Label;
49 typedef typename Arc::Weight Weight;
50
51 uint64 props = fst->Properties(kFstProperties, false);
52 StateId start = fst->Start();
53 for (StateIterator< MutableFst<Arc> > siter(*fst);
54 !siter.Done();
55 siter.Next()) {
56 StateId s = siter.Value();
57 Weight final = fst->Final(s);
58 if (final != Weight::Zero())
59 fst->AddArc(s, Arc(0, 0, final, start));
60 }
61 if (closure_type == CLOSURE_STAR) {
62 fst->ReserveStates(fst->NumStates() + 1);
63 StateId nstart = fst->AddState();
64 fst->SetStart(nstart);
65 fst->SetFinal(nstart, Weight::One());
66 if (start != kNoLabel)
67 fst->AddArc(nstart, Arc(0, 0, Weight::One(), start));
68 }
69 fst->SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR),
70 kFstProperties);
71 }
72
73 // Computes the concatenative closure. This version modifies its
74 // RationalFst input.
75 template<class Arc>
Closure(RationalFst<Arc> * fst,ClosureType closure_type)76 void Closure(RationalFst<Arc> *fst, ClosureType closure_type) {
77 fst->GetImpl()->AddClosure(closure_type);
78 }
79
80
81 struct ClosureFstOptions : RationalFstOptions {
82 ClosureType type;
83
ClosureFstOptionsClosureFstOptions84 ClosureFstOptions(const RationalFstOptions &opts, ClosureType t)
85 : RationalFstOptions(opts), type(t) {}
ClosureFstOptionsClosureFstOptions86 explicit ClosureFstOptions(ClosureType t) : type(t) {}
ClosureFstOptionsClosureFstOptions87 ClosureFstOptions() : type(CLOSURE_STAR) {}
88 };
89
90
91 // Computes the concatenative closure. This version is a delayed
92 // Fst. If FST transduces string x to y with weight a, then the
93 // closure transduces x to y with weight a, xx to yy with weight
94 // Times(a, a), xxx to yyy with weight Times(Times(a, a), a), etc. If
95 // closure_type == CLOSURE_STAR, then The empty string is transduced
96 // to itself with weight Weight::One() as well.
97 //
98 // Complexity:
99 // - Time: O(v)
100 // - Space: O(v)
101 // where v = # of states visited. Constant time and space to visit an
102 // input state or arc is assumed and exclusive of caching.
103 template <class A>
104 class ClosureFst : public RationalFst<A> {
105 public:
106 using ImplToFst< RationalFstImpl<A> >::GetImpl;
107
108 typedef A Arc;
109
ClosureFst(const Fst<A> & fst,ClosureType closure_type)110 ClosureFst(const Fst<A> &fst, ClosureType closure_type) {
111 GetImpl()->InitClosure(fst, closure_type);
112 }
113
ClosureFst(const Fst<A> & fst,const ClosureFstOptions & opts)114 ClosureFst(const Fst<A> &fst, const ClosureFstOptions &opts)
115 : RationalFst<A>(opts) {
116 GetImpl()->InitClosure(fst, opts.type);
117 }
118
119 // See Fst<>::Copy() for doc.
120 ClosureFst(const ClosureFst<A> &fst, bool safe = false)
121 : RationalFst<A>(fst, safe) {}
122
123 // Get a copy of this ClosureFst. See Fst<>::Copy() for further doc.
124 virtual ClosureFst<A> *Copy(bool safe = false) const {
125 return new ClosureFst<A>(*this, safe);
126 }
127 };
128
129
130 // Specialization for ClosureFst.
131 template <class A>
132 class StateIterator< ClosureFst<A> > : public StateIterator< RationalFst<A> > {
133 public:
StateIterator(const ClosureFst<A> & fst)134 explicit StateIterator(const ClosureFst<A> &fst)
135 : StateIterator< RationalFst<A> >(fst) {}
136 };
137
138
139 // Specialization for ClosureFst.
140 template <class A>
141 class ArcIterator< ClosureFst<A> > : public ArcIterator< RationalFst<A> > {
142 public:
143 typedef typename A::StateId StateId;
144
ArcIterator(const ClosureFst<A> & fst,StateId s)145 ArcIterator(const ClosureFst<A> &fst, StateId s)
146 : ArcIterator< RationalFst<A> >(fst, s) {}
147 };
148
149
150 // Useful alias when using StdArc.
151 typedef ClosureFst<StdArc> StdClosureFst;
152
153 } // namespace fst
154
155 #endif // FST_LIB_CLOSURE_H__
156