FST  openfst-1.8.3
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>> {
274  public:
275  using Arc = A;
276  using StateId = typename Arc::StateId;
277 
279 
280  friend class StateIterator<RationalFst<Arc>>;
281  friend class ArcIterator<RationalFst<Arc>>;
282  friend void Union<>(RationalFst<Arc> *fst1, const Fst<Arc> &fst2);
283  friend void Concat<>(RationalFst<Arc> *fst1, const Fst<Arc> &fst2);
284  friend void Concat<>(const Fst<Arc> &fst1, RationalFst<Arc> *fst2);
285  friend void Closure<>(RationalFst<Arc> *fst, ClosureType closure_type);
286 
287  void InitStateIterator(StateIteratorData<Arc> *data) const override {
288  GetImpl()->Replace()->InitStateIterator(data);
289  }
290 
291  void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const override {
292  GetImpl()->Replace()->InitArcIterator(s, data);
293  }
294 
295  protected:
297 
299  : ImplToFst<Impl>(std::make_shared<Impl>(opts)) {}
300 
301  // See Fst<>::Copy() for doc.
302  RationalFst(const RationalFst &fst, bool safe = false)
303  : ImplToFst<Impl>(fst, safe) {}
304 
305  private:
306  RationalFst &operator=(const RationalFst &) = delete;
307 };
308 
309 // Specialization for RationalFst.
310 template <class Arc>
311 class StateIterator<RationalFst<Arc>> : public StateIterator<ReplaceFst<Arc>> {
312  public:
313  explicit StateIterator(const RationalFst<Arc> &fst)
314  : StateIterator<ReplaceFst<Arc>>(*(fst.GetImpl()->Replace())) {}
315 };
316 
317 // Specialization for RationalFst.
318 template <class Arc>
319 class ArcIterator<RationalFst<Arc>> : public CacheArcIterator<ReplaceFst<Arc>> {
320  public:
321  using StateId = typename Arc::StateId;
322 
324  : ArcIterator<ReplaceFst<Arc>>(*(fst.GetImpl()->Replace()), s) {}
325 };
326 
327 } // namespace fst
328 
329 #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:709
void InitStateIterator(StateIteratorData< Arc > *data) const override
Definition: rational.h:287
void AddConcat(const Fst< Arc > &fst, bool append)
Definition: rational.h:215
void SetStart(StateId s) override
Definition: mutable-fst.h:303
RationalFst(const RationalFstOptions &opts=RationalFstOptions())
Definition: rational.h:298
virtual uint64_t Properties(uint64_t mask, bool test) const =0
void SetFinal(StateId s, Weight weight=Weight::One()) override
Definition: mutable-fst.h:308
void Closure(MutableFst< Arc > *fst, ClosureType closure_type)
Definition: closure.h:51
RationalFst(const RationalFst &fst, bool safe=false)
Definition: rational.h:302
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:323
void SetOutputSymbols(const SymbolTable *osyms)
Definition: fst.h:771
typename Arc::Weight Weight
Definition: rational.h:74
typename ReplaceFst< Arc >::Arc Arc
Definition: fst.h:408
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const override
Definition: rational.h:291
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
StateId AddState() override
Definition: mutable-fst.h:321
void SetOutputSymbols(const SymbolTable *osyms) override
Definition: mutable-fst.h:401
Weight Final(StateId s)
Definition: rational.h:107
typename Arc::StateId StateId
Definition: rational.h:276
uint64_t ClosureProperties(uint64_t inprops, bool star, bool delayed=false)
Definition: properties.cc:38
virtual uint64_t Properties() const
Definition: fst.h:701
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
void SetInputSymbols(const SymbolTable *isyms) override
Definition: mutable-fst.h:396
virtual Fst * Copy(bool safe=false) const =0
typename Arc::StateId StateId
Definition: rational.h:321
VectorFst * Copy(bool safe=false) const override
Definition: vector-fst.h:553
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:313
void EmplaceArc(StateId state, T &&...ctor_args)
Definition: vector-fst.h:567
void SetInputSymbols(const SymbolTable *isyms)
Definition: fst.h:767
void Concat(MutableFst< Arc > *fst1, const Fst< Arc > &fst2)
Definition: concat.h:55
constexpr uint64_t kFstProperties
Definition: properties.h:326
void InitUnion(const Fst< Arc > &fst1, const Fst< Arc > &fst2)
Definition: rational.h:128
typename Arc::Label Label
Definition: rational.h:72
typename ReplaceFst< Arc >::Arc Arc
Definition: cache.h:1202
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:699
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:686
typename Arc::StateId StateId
Definition: rational.h:73
virtual const SymbolTable * OutputSymbols() const =0