FST  openfst-1.8.2.post1
OpenFst Library
rational.h
Go to the documentation of this file.
1 // Copyright 2005-2020 Google LLC
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 // See www.openfst.org for extensive documentation on this weighted
16 // finite-state transducer library.
17 //
18 // An FST implementation and base interface for delayed unions, concatenations,
19 // and closures.
20 
21 #ifndef FST_RATIONAL_H_
22 #define FST_RATIONAL_H_
23 
24 #include <algorithm>
25 #include <cstdint>
26 #include <string>
27 #include <vector>
28 
29 
30 #include <fst/mutable-fst.h>
31 #include <fst/replace.h>
32 #include <fst/test-properties.h>
33 
34 namespace fst {
35 
37 
38 // This specifies whether to add the empty string.
40  CLOSURE_STAR = 0, // Add the empty string.
41  CLOSURE_PLUS = 1 // Don't add the empty string.
42 };
43 
44 template <class Arc>
46 
47 template <class Arc>
48 void Union(RationalFst<Arc> *fst1, const Fst<Arc> &fst2);
49 
50 template <class Arc>
51 void Concat(RationalFst<Arc> *fst1, const Fst<Arc> &fst2);
52 
53 template <class Arc>
54 void Concat(const Fst<Arc> &fst1, RationalFst<Arc> *fst2);
55 
56 template <class Arc>
57 void Closure(RationalFst<Arc> *fst, ClosureType closure_type);
58 
59 namespace internal {
60 
61 // Implementation class for delayed unions, concatenations and closures.
62 template <class A>
63 class RationalFstImpl : public FstImpl<A> {
64  public:
65  using Arc = A;
66  using Label = typename Arc::Label;
67  using StateId = typename Arc::StateId;
68  using Weight = typename Arc::Weight;
69 
75 
76  explicit RationalFstImpl(const RationalFstOptions &opts)
77  : nonterminals_(0), replace_options_(opts, 0) {
78  SetType("rational");
79  fst_tuples_.emplace_back(0, nullptr);
80  }
81 
83  : rfst_(impl.rfst_),
84  nonterminals_(impl.nonterminals_),
85  replace_(impl.replace_ ? impl.replace_->Copy(true) : nullptr),
86  replace_options_(impl.replace_options_) {
87  SetType("rational");
88  fst_tuples_.reserve(impl.fst_tuples_.size());
89  for (const auto &pair : impl.fst_tuples_) {
90  fst_tuples_.emplace_back(pair.first,
91  pair.second ? pair.second->Copy(true) : nullptr);
92  }
93  }
94 
95  ~RationalFstImpl() override {
96  for (auto &tuple : fst_tuples_) delete tuple.second;
97  }
98 
99  StateId Start() { return Replace()->Start(); }
100 
101  Weight Final(StateId s) { return Replace()->Final(s); }
102 
103  size_t NumArcs(StateId s) { return Replace()->NumArcs(s); }
104 
105  size_t NumInputEpsilons(StateId s) { return Replace()->NumInputEpsilons(s); }
106 
108  return Replace()->NumOutputEpsilons(s);
109  }
110 
111  uint64_t Properties() const override { return Properties(kFstProperties); }
112 
113  // Sets error if found, and returns other FST impl properties.
114  uint64_t Properties(uint64_t mask) const override {
115  if ((mask & kError) && Replace()->Properties(kError, false)) {
116  SetProperties(kError, kError);
117  }
118  return FstImpl<Arc>::Properties(mask);
119  }
120 
121  // Implementation of UnionFst(fst1, fst2).
122  void InitUnion(const Fst<Arc> &fst1, const Fst<Arc> &fst2) {
123  replace_.reset();
124  const auto props1 = fst1.Properties(kFstProperties, false);
125  const auto props2 = fst2.Properties(kFstProperties, false);
128  rfst_.AddState();
129  rfst_.AddState();
130  rfst_.SetStart(0);
131  rfst_.SetFinal(1);
132  rfst_.SetInputSymbols(fst1.InputSymbols());
133  rfst_.SetOutputSymbols(fst1.OutputSymbols());
134  nonterminals_ = 2;
135  rfst_.EmplaceArc(0, 0, -1, Weight::One(), 1);
136  rfst_.EmplaceArc(0, 0, -2, Weight::One(), 1);
137  fst_tuples_.emplace_back(-1, fst1.Copy());
138  fst_tuples_.emplace_back(-2, fst2.Copy());
139  SetProperties(UnionProperties(props1, props2, true), kCopyProperties);
140  }
141 
142  // Implementation of ConcatFst(fst1, fst2).
143  void InitConcat(const Fst<Arc> &fst1, const Fst<Arc> &fst2) {
144  replace_.reset();
145  const auto props1 = fst1.Properties(kFstProperties, false);
146  const auto props2 = fst2.Properties(kFstProperties, false);
149  rfst_.AddState();
150  rfst_.AddState();
151  rfst_.AddState();
152  rfst_.SetStart(0);
153  rfst_.SetFinal(2);
154  rfst_.SetInputSymbols(fst1.InputSymbols());
155  rfst_.SetOutputSymbols(fst1.OutputSymbols());
156  nonterminals_ = 2;
157  rfst_.EmplaceArc(0, 0, -1, Weight::One(), 1);
158  rfst_.EmplaceArc(1, 0, -2, Weight::One(), 2);
159  fst_tuples_.emplace_back(-1, fst1.Copy());
160  fst_tuples_.emplace_back(-2, fst2.Copy());
161  SetProperties(ConcatProperties(props1, props2, true), kCopyProperties);
162  }
163 
164  // Implementation of ClosureFst(fst, closure_type).
165  void InitClosure(const Fst<Arc> &fst, ClosureType closure_type) {
166  replace_.reset();
167  const auto props = fst.Properties(kFstProperties, false);
170  if (closure_type == CLOSURE_STAR) {
171  rfst_.AddState();
172  rfst_.SetStart(0);
173  rfst_.SetFinal(0);
174  rfst_.EmplaceArc(0, 0, -1, Weight::One(), 0);
175  } else {
176  rfst_.AddState();
177  rfst_.AddState();
178  rfst_.SetStart(0);
179  rfst_.SetFinal(1);
180  rfst_.EmplaceArc(0, 0, -1, Weight::One(), 1);
181  rfst_.EmplaceArc(1, 0, 0, Weight::One(), 0);
182  }
183  rfst_.SetInputSymbols(fst.InputSymbols());
184  rfst_.SetOutputSymbols(fst.OutputSymbols());
185  fst_tuples_.emplace_back(-1, fst.Copy());
186  nonterminals_ = 1;
187  SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR, true),
189  }
190 
191  // Implementation of Union(Fst &, RationalFst *).
192  void AddUnion(const Fst<Arc> &fst) {
193  replace_.reset();
194  const auto props1 = FstImpl<A>::Properties();
195  const auto props2 = fst.Properties(kFstProperties, false);
196  VectorFst<Arc> afst;
197  afst.AddState();
198  afst.AddState();
199  afst.SetStart(0);
200  afst.SetFinal(1);
201  ++nonterminals_;
202  afst.EmplaceArc(0, 0, -nonterminals_, Weight::One(), 1);
203  Union(&rfst_, afst);
204  fst_tuples_.emplace_back(-nonterminals_, fst.Copy());
205  SetProperties(UnionProperties(props1, props2, true), kCopyProperties);
206  }
207 
208  // Implementation of Concat(Fst &, RationalFst *).
209  void AddConcat(const Fst<Arc> &fst, bool append) {
210  replace_.reset();
211  const auto props1 = FstImpl<A>::Properties();
212  const auto props2 = fst.Properties(kFstProperties, false);
213  VectorFst<Arc> afst;
214  afst.AddState();
215  afst.AddState();
216  afst.SetStart(0);
217  afst.SetFinal(1);
218  ++nonterminals_;
219  afst.EmplaceArc(0, 0, -nonterminals_, Weight::One(), 1);
220  if (append) {
221  Concat(&rfst_, afst);
222  } else {
223  Concat(afst, &rfst_);
224  }
225  fst_tuples_.emplace_back(-nonterminals_, fst.Copy());
226  SetProperties(ConcatProperties(props1, props2, true), kCopyProperties);
227  }
228 
229  // Implementation of Closure(RationalFst *, closure_type).
230  void AddClosure(ClosureType closure_type) {
231  replace_.reset();
232  const auto props = FstImpl<A>::Properties();
233  Closure(&rfst_, closure_type);
234  SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR, true),
236  }
237 
238  // Returns the underlying ReplaceFst, preserving ownership of the underlying
239  // object.
241  if (!replace_) {
242  fst_tuples_[0].second = rfst_.Copy();
243  replace_ =
244  std::make_unique<ReplaceFst<Arc>>(fst_tuples_, replace_options_);
245  }
246  return replace_.get();
247  }
248 
249  private:
250  // Rational topology machine, using negative non-terminals.
251  VectorFst<Arc> rfst_;
252  // Number of nonterminals used.
253  Label nonterminals_;
254  // Contains the nonterminals and their corresponding FSTs.
255  mutable std::vector<std::pair<Label, const Fst<Arc> *>> fst_tuples_;
256  // Underlying ReplaceFst.
257  mutable std::unique_ptr<ReplaceFst<Arc>> replace_;
258  const ReplaceFstOptions<Arc> replace_options_;
259 };
260 
261 } // namespace internal
262 
263 // Parent class for the delayed rational operations (union, concatenation, and
264 // closure). This class attaches interface to implementation and handles
265 // reference counting, delegating most methods to ImplToFst.
266 template <class A>
267 class RationalFst : public ImplToFst<internal::RationalFstImpl<A>> {
268  public:
269  using Arc = A;
270  using StateId = typename Arc::StateId;
271 
273 
274  friend class StateIterator<RationalFst<Arc>>;
275  friend class ArcIterator<RationalFst<Arc>>;
276  friend void Union<>(RationalFst<Arc> *fst1, const Fst<Arc> &fst2);
277  friend void Concat<>(RationalFst<Arc> *fst1, const Fst<Arc> &fst2);
278  friend void Concat<>(const Fst<Arc> &fst1, RationalFst<Arc> *fst2);
279  friend void Closure<>(RationalFst<Arc> *fst, ClosureType closure_type);
280 
281  void InitStateIterator(StateIteratorData<Arc> *data) const override {
282  GetImpl()->Replace()->InitStateIterator(data);
283  }
284 
285  void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const override {
286  GetImpl()->Replace()->InitArcIterator(s, data);
287  }
288 
289  protected:
291 
293  : ImplToFst<Impl>(std::make_shared<Impl>(opts)) {}
294 
295  // See Fst<>::Copy() for doc.
296  RationalFst(const RationalFst &fst, bool safe = false)
297  : ImplToFst<Impl>(fst, safe) {}
298 
299  private:
300  RationalFst &operator=(const RationalFst &) = delete;
301 };
302 
303 // Specialization for RationalFst.
304 template <class Arc>
305 class StateIterator<RationalFst<Arc>> : public StateIterator<ReplaceFst<Arc>> {
306  public:
307  explicit StateIterator(const RationalFst<Arc> &fst)
308  : StateIterator<ReplaceFst<Arc>>(*(fst.GetImpl()->Replace())) {}
309 };
310 
311 // Specialization for RationalFst.
312 template <class Arc>
313 class ArcIterator<RationalFst<Arc>> : public CacheArcIterator<ReplaceFst<Arc>> {
314  public:
315  using StateId = typename Arc::StateId;
316 
318  : ArcIterator<ReplaceFst<Arc>>(*(fst.GetImpl()->Replace()), s) {}
319 };
320 
321 } // namespace fst
322 
323 #endif // FST_RATIONAL_H_
uint64_t ConcatProperties(uint64_t inprops1, uint64_t inprops2, bool delayed=false)
Definition: properties.cc:96
size_t NumOutputEpsilons(StateId s)
Definition: rational.h:107
void SetProperties(uint64_t props)
Definition: fst.h:710
void InitStateIterator(StateIteratorData< Arc > *data) const override
Definition: rational.h:281
void AddConcat(const Fst< Arc > &fst, bool append)
Definition: rational.h:209
void SetStart(StateId s) override
Definition: mutable-fst.h:298
RationalFst(const RationalFstOptions &opts=RationalFstOptions())
Definition: rational.h:292
virtual uint64_t Properties(uint64_t mask, bool test) const =0
void SetFinal(StateId s, Weight weight=Weight::One()) override
Definition: mutable-fst.h:303
void Closure(MutableFst< Arc > *fst, ClosureType closure_type)
Definition: closure.h:47
RationalFst(const RationalFst &fst, bool safe=false)
Definition: rational.h:296
ReplaceFst< Arc > * Replace() const
Definition: rational.h:240
void AddClosure(ClosureType closure_type)
Definition: rational.h:230
constexpr uint64_t kError
Definition: properties.h:51
uint64_t Properties() const override
Definition: rational.h:111
ArcIterator(const RationalFst< Arc > &fst, StateId s)
Definition: rational.h:317
void SetOutputSymbols(const SymbolTable *osyms)
Definition: fst.h:772
typename Arc::Weight Weight
Definition: rational.h:68
typename ReplaceFst< Arc >::Arc Arc
Definition: fst.h:408
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const override
Definition: rational.h:285
CacheOptions RationalFstOptions
Definition: rational.h:36
size_t NumArcs(StateId s)
Definition: rational.h:103
void InitConcat(const Fst< Arc > &fst1, const Fst< Arc > &fst2)
Definition: rational.h:143
StateId AddState() override
Definition: mutable-fst.h:316
void SetOutputSymbols(const SymbolTable *osyms) override
Definition: mutable-fst.h:396
Weight Final(StateId s)
Definition: rational.h:101
typename Arc::StateId StateId
Definition: rational.h:270
uint64_t ClosureProperties(uint64_t inprops, bool star, bool delayed=false)
Definition: properties.cc:39
virtual uint64_t Properties() const
Definition: fst.h:702
uint64_t UnionProperties(uint64_t inprops1, uint64_t inprops2, bool delayed=false)
Definition: properties.cc:394
void Union(RationalFst< Arc > *fst1, const Fst< Arc > &fst2)
Definition: union.h:110
constexpr uint64_t kCopyProperties
Definition: properties.h:162
void SetInputSymbols(const SymbolTable *isyms) override
Definition: mutable-fst.h:391
virtual Fst * Copy(bool safe=false) const =0
typename Arc::StateId StateId
Definition: rational.h:315
VectorFst * Copy(bool safe=false) const override
Definition: vector-fst.h:546
void InitClosure(const Fst< Arc > &fst, ClosureType closure_type)
Definition: rational.h:165
RationalFstImpl(const RationalFstImpl< Arc > &impl)
Definition: rational.h:82
StateIterator(const RationalFst< Arc > &fst)
Definition: rational.h:307
void EmplaceArc(StateId state, T &&...ctor_args)
Definition: vector-fst.h:560
void SetInputSymbols(const SymbolTable *isyms)
Definition: fst.h:768
void Concat(MutableFst< Arc > *fst1, const Fst< Arc > &fst2)
Definition: concat.h:48
constexpr uint64_t kFstProperties
Definition: properties.h:325
void InitUnion(const Fst< Arc > &fst1, const Fst< Arc > &fst2)
Definition: rational.h:122
typename Arc::Label Label
Definition: rational.h:66
typename ReplaceFst< Arc >::Arc Arc
Definition: cache.h:1195
virtual const SymbolTable * InputSymbols() const =0
ClosureType
Definition: rational.h:39
void AddUnion(const Fst< Arc > &fst)
Definition: rational.h:192
size_t NumInputEpsilons(StateId s)
Definition: rational.h:105
void SetType(std::string_view type)
Definition: fst.h:700
RationalFstImpl(const RationalFstOptions &opts)
Definition: rational.h:76
uint64_t Properties(uint64_t mask) const override
Definition: rational.h:114
FstImpl & operator=(const FstImpl &impl)
Definition: fst.h:687
typename Arc::StateId StateId
Definition: rational.h:67
virtual const SymbolTable * OutputSymbols() const =0