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