FST  openfst-1.8.3
OpenFst Library
complement.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 // Class to complement an FST.
19 
20 #ifndef FST_COMPLEMENT_H_
21 #define FST_COMPLEMENT_H_
22 
23 #include <algorithm>
24 #include <cstddef>
25 #include <cstdint>
26 #include <memory>
27 #include <string>
28 #include <vector>
29 
30 #include <fst/log.h>
31 #include <fst/arc.h>
32 #include <fst/float-weight.h>
33 #include <fst/fst.h>
34 #include <fst/impl-to-fst.h>
35 #include <fst/properties.h>
36 #include <fst/util.h>
37 
38 namespace fst {
39 
40 template <class Arc>
42 
43 namespace internal {
44 
45 // Implementation of delayed ComplementFst. The algorithm used completes the
46 // (deterministic) FSA and then exchanges final and non-final states.
47 // Completion, i.e. ensuring that all labels can be read from every state, is
48 // accomplished by using ρ-labels, which match all labels that are otherwise
49 // not found leaving a state. The first state in the output is reserved to be a
50 // new state that is the destination of all ρ-labels. Each remaining output
51 // state s corresponds to input state s - 1. The first arc in the output at
52 // these states is the ρ-label, the remaining arcs correspond to the input
53 // arcs.
54 template <class A>
55 class ComplementFstImpl : public FstImpl<A> {
56  public:
57  using Arc = A;
58  using Label = typename Arc::Label;
59  using StateId = typename Arc::StateId;
60  using Weight = typename Arc::Weight;
61 
62  using FstImpl<A>::SetType;
66 
68  friend class ArcIterator<ComplementFst<Arc>>;
69 
70  explicit ComplementFstImpl(const Fst<Arc> &fst) : fst_(fst.Copy()) {
71  SetType("complement");
72  const auto props = fst.Properties(kILabelSorted, false);
76  }
77 
79  : fst_(impl.fst_->Copy()) {
80  SetType("complement");
84  }
85 
86  StateId Start() const {
87  if (Properties(kError)) return kNoStateId;
88  const auto start = fst_->Start();
89  return start != kNoStateId ? start + 1 : 0;
90  }
91 
92  // Exchange final and non-final states; makes ρ-destination state final.
93  Weight Final(StateId s) const {
94  if (s == 0 || fst_->Final(s - 1) == Weight::Zero()) {
95  return Weight::One();
96  } else {
97  return Weight::Zero();
98  }
99  }
100 
101  size_t NumArcs(StateId s) const {
102  return s == 0 ? 1 : fst_->NumArcs(s - 1) + 1;
103  }
104 
105  size_t NumInputEpsilons(StateId s) const {
106  return s == 0 ? 0 : fst_->NumInputEpsilons(s - 1);
107  }
108 
109  size_t NumOutputEpsilons(StateId s) const {
110  return s == 0 ? 0 : fst_->NumOutputEpsilons(s - 1);
111  }
112 
113  uint64_t Properties() const override { return Properties(kFstProperties); }
114 
115  // Sets error if found, and returns other FST impl properties.
116  uint64_t Properties(uint64_t mask) const override {
117  if ((mask & kError) && fst_->Properties(kError, false)) {
118  SetProperties(kError, kError);
119  }
120  return FstImpl<Arc>::Properties(mask);
121  }
122 
123  private:
124  std::unique_ptr<const Fst<Arc>> fst_;
125 };
126 
127 } // namespace internal
128 
129 // Complements an automaton. This is a library-internal operation that
130 // introduces a (negative) ρ-label; use Difference/DifferenceFst in user code,
131 // which will not see this label. This version is a delayed FST.
132 //
133 // This class attaches interface to implementation and handles
134 // reference counting, delegating most methods to ImplToFst.
135 template <class A>
136 class ComplementFst : public ImplToFst<internal::ComplementFstImpl<A>> {
137  public:
138  using Arc = A;
139  using Label = typename Arc::Label;
140  using StateId = typename Arc::StateId;
142 
144  friend class ArcIterator<ComplementFst<Arc>>;
145 
146  explicit ComplementFst(const Fst<Arc> &fst)
147  : ImplToFst<Impl>(std::make_shared<Impl>(fst)) {
148  static constexpr auto props =
150  if (fst.Properties(props, true) != props) {
151  FSTERROR() << "ComplementFst: Argument not an unweighted "
152  << "epsilon-free deterministic acceptor";
153  GetImpl()->SetProperties(kError, kError);
154  }
155  }
156 
157  // See Fst<>::Copy() for doc.
158  ComplementFst(const ComplementFst &fst, bool safe = false)
159  : ImplToFst<Impl>(fst, safe) {}
160 
161  // Gets a copy of this FST. See Fst<>::Copy() for further doc.
162  ComplementFst *Copy(bool safe = false) const override {
163  return new ComplementFst(*this, safe);
164  }
165 
166  inline void InitStateIterator(StateIteratorData<Arc> *data) const override;
167 
168  inline void InitArcIterator(StateId s,
169  ArcIteratorData<Arc> *data) const override;
170 
171  // Label that represents the ρ-transition; we use a negative value private to
172  // the library and which will preserve FST label sort order.
173  static constexpr Label kRhoLabel = -2;
174 
175  private:
177 
178  ComplementFst &operator=(const ComplementFst &) = delete;
179 };
180 
181 // Specialization for ComplementFst.
182 template <class Arc>
184  public:
185  using StateId = typename Arc::StateId;
186 
188  : siter_(*fst.GetImpl()->fst_), s_(0) {}
189 
190  bool Done() const final { return s_ > 0 && siter_.Done(); }
191 
192  StateId Value() const final { return s_; }
193 
194  void Next() final {
195  if (s_ != 0) siter_.Next();
196  ++s_;
197  }
198 
199  void Reset() final {
200  siter_.Reset();
201  s_ = 0;
202  }
203 
204  private:
205  StateIterator<Fst<Arc>> siter_;
206  StateId s_;
207 };
208 
209 // Specialization for ComplementFst.
210 template <class Arc>
212  public:
213  using StateId = typename Arc::StateId;
214  using Weight = typename Arc::Weight;
215 
216  ArcIterator(const ComplementFst<Arc> &fst, StateId s) : s_(s), pos_(0) {
217  if (s_ != 0) {
218  aiter_ =
219  std::make_unique<ArcIterator<Fst<Arc>>>(*fst.GetImpl()->fst_, s - 1);
220  }
221  }
222 
223  bool Done() const final {
224  if (s_ != 0) {
225  return pos_ > 0 && aiter_->Done();
226  } else {
227  return pos_ > 0;
228  }
229  }
230 
231  // Adds the ρ-label to the ρ destination state.
232  const Arc &Value() const final {
233  if (pos_ == 0) {
234  arc_.ilabel = arc_.olabel = ComplementFst<Arc>::kRhoLabel;
235  arc_.weight = Weight::One();
236  arc_.nextstate = 0;
237  } else {
238  arc_ = aiter_->Value();
239  ++arc_.nextstate;
240  }
241  return arc_;
242  }
243 
244  void Next() final {
245  if (s_ != 0 && pos_ > 0) aiter_->Next();
246  ++pos_;
247  }
248 
249  size_t Position() const final { return pos_; }
250 
251  void Reset() final {
252  if (s_ != 0) aiter_->Reset();
253  pos_ = 0;
254  }
255 
256  void Seek(size_t a) final {
257  if (s_ != 0) {
258  if (a == 0) {
259  aiter_->Reset();
260  } else {
261  aiter_->Seek(a - 1);
262  }
263  }
264  pos_ = a;
265  }
266 
267  uint8_t Flags() const final { return kArcValueFlags; }
268 
269  void SetFlags(uint8_t, uint8_t) final {}
270 
271  private:
272  std::unique_ptr<ArcIterator<Fst<Arc>>> aiter_;
273  StateId s_;
274  size_t pos_;
275  mutable Arc arc_;
276 };
277 
278 template <class Arc>
280  StateIteratorData<Arc> *data) const {
281  data->base = std::make_unique<StateIterator<ComplementFst<Arc>>>(*this);
282 }
283 
284 template <class Arc>
286  StateId s, ArcIteratorData<Arc> *data) const {
287  data->base = std::make_unique<ArcIterator<ComplementFst<Arc>>>(*this, s);
288 }
289 
290 // Useful alias when using StdArc.
292 
293 } // namespace fst
294 
295 #endif // FST_COMPLEMENT_H_
typename Arc::Label Label
Definition: complement.h:139
void SetProperties(uint64_t props)
Definition: fst.h:709
uint64_t Properties() const override
Definition: complement.h:113
constexpr uint8_t kArcValueFlags
Definition: fst.h:453
virtual uint64_t Properties(uint64_t mask, bool test) const =0
size_t NumOutputEpsilons(StateId s) const
Definition: complement.h:109
Weight Final(StateId s) const
Definition: complement.h:93
const Arc & Value() const final
Definition: complement.h:232
typename Arc::Label Label
Definition: complement.h:58
typename Arc::StateId StateId
Definition: complement.h:140
const SymbolTable * OutputSymbols() const
Definition: fst.h:761
constexpr uint64_t kError
Definition: properties.h:52
size_t NumArcs(StateId s) const
Definition: complement.h:101
void SetOutputSymbols(const SymbolTable *osyms)
Definition: fst.h:771
ComplementFst(const Fst< Arc > &fst)
Definition: complement.h:146
ComplementFstImpl(const Fst< Arc > &fst)
Definition: complement.h:70
ComplementFstImpl(const ComplementFstImpl< Arc > &impl)
Definition: complement.h:78
constexpr int kNoStateId
Definition: fst.h:196
typename Arc::StateId StateId
Definition: complement.h:59
uint64_t Properties(uint64_t mask) const override
Definition: complement.h:116
#define FSTERROR()
Definition: util.h:56
virtual uint64_t Properties() const
Definition: fst.h:701
typename Arc::Weight Weight
Definition: complement.h:60
constexpr uint64_t kCopyProperties
Definition: properties.h:163
ArcIterator(const ComplementFst< Arc > &fst, StateId s)
Definition: complement.h:216
ComplementFst(const ComplementFst &fst, bool safe=false)
Definition: complement.h:158
constexpr uint64_t kNoEpsilons
Definition: properties.h:81
std::unique_ptr< StateIteratorBase< Arc > > base
Definition: fst.h:382
constexpr uint64_t kIDeterministic
Definition: properties.h:69
void SetFlags(uint8_t, uint8_t) final
Definition: complement.h:269
std::unique_ptr< ArcIteratorBase< Arc > > base
Definition: fst.h:494
uint64_t ComplementProperties(uint64_t inprops)
Definition: properties.cc:60
void SetInputSymbols(const SymbolTable *isyms)
Definition: fst.h:767
StateIterator(const ComplementFst< Arc > &fst)
Definition: complement.h:187
constexpr uint64_t kILabelSorted
Definition: properties.h:94
void InitStateIterator(StateIteratorData< Arc > *data) const override
Definition: complement.h:279
constexpr uint64_t kFstProperties
Definition: properties.h:326
constexpr uint64_t kUnweighted
Definition: properties.h:106
ComplementFst * Copy(bool safe=false) const override
Definition: complement.h:162
virtual const SymbolTable * InputSymbols() const =0
const SymbolTable * InputSymbols() const
Definition: fst.h:759
void SetType(std::string_view type)
Definition: fst.h:699
size_t NumInputEpsilons(StateId s) const
Definition: complement.h:105
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const override
Definition: complement.h:285
FstImpl & operator=(const FstImpl &impl)
Definition: fst.h:686
const internal::ComplementFstImpl< A > * GetImpl() const
Definition: impl-to-fst.h:123
constexpr uint64_t kAcceptor
Definition: properties.h:64
virtual const SymbolTable * OutputSymbols() const =0