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