FST  openfst-1.8.4
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>> {
138 
139  public:
140  using Arc = A;
141  using Label = typename Arc::Label;
142  using StateId = typename Arc::StateId;
143  using typename Base::Impl;
144 
146  friend class ArcIterator<ComplementFst<Arc>>;
147 
148  explicit ComplementFst(const Fst<Arc> &fst)
149  : Base(std::make_shared<Impl>(fst)) {
150  static constexpr auto props =
152  if (fst.Properties(props, true) != props) {
153  FSTERROR() << "ComplementFst: Argument not an unweighted "
154  << "epsilon-free deterministic acceptor";
155  GetImpl()->SetProperties(kError, kError);
156  }
157  }
158 
159  // See Fst<>::Copy() for doc.
160  ComplementFst(const ComplementFst &fst, bool safe = false)
161  : Base(fst, safe) {}
162 
163  // Gets a copy of this FST. See Fst<>::Copy() for further doc.
164  ComplementFst *Copy(bool safe = false) const override {
165  return new ComplementFst(*this, safe);
166  }
167 
168  inline void InitStateIterator(StateIteratorData<Arc> *data) const override;
169 
170  inline void InitArcIterator(StateId s,
171  ArcIteratorData<Arc> *data) const override;
172 
173  // Label that represents the ρ-transition; we use a negative value private to
174  // the library and which will preserve FST label sort order.
175  static constexpr Label kRhoLabel = -2;
176 
177  private:
178  using Base::GetImpl;
179 
180  ComplementFst &operator=(const ComplementFst &) = delete;
181 };
182 
183 // Specialization for ComplementFst.
184 template <class Arc>
186  public:
187  using StateId = typename Arc::StateId;
188 
190  : siter_(*fst.GetImpl()->fst_), s_(0) {}
191 
192  bool Done() const final { return s_ > 0 && siter_.Done(); }
193 
194  StateId Value() const final { return s_; }
195 
196  void Next() final {
197  if (s_ != 0) siter_.Next();
198  ++s_;
199  }
200 
201  void Reset() final {
202  siter_.Reset();
203  s_ = 0;
204  }
205 
206  private:
207  StateIterator<Fst<Arc>> siter_;
208  StateId s_;
209 };
210 
211 // Specialization for ComplementFst.
212 template <class Arc>
214  public:
215  using StateId = typename Arc::StateId;
216  using Weight = typename Arc::Weight;
217 
218  ArcIterator(const ComplementFst<Arc> &fst, StateId s) : s_(s), pos_(0) {
219  if (s_ != 0) {
220  aiter_ =
221  std::make_unique<ArcIterator<Fst<Arc>>>(*fst.GetImpl()->fst_, s - 1);
222  }
223  }
224 
225  bool Done() const final {
226  if (s_ != 0) {
227  return pos_ > 0 && aiter_->Done();
228  } else {
229  return pos_ > 0;
230  }
231  }
232 
233  // Adds the ρ-label to the ρ destination state.
234  const Arc &Value() const final {
235  if (pos_ == 0) {
236  arc_.ilabel = arc_.olabel = ComplementFst<Arc>::kRhoLabel;
237  arc_.weight = Weight::One();
238  arc_.nextstate = 0;
239  } else {
240  arc_ = aiter_->Value();
241  ++arc_.nextstate;
242  }
243  return arc_;
244  }
245 
246  void Next() final {
247  if (s_ != 0 && pos_ > 0) aiter_->Next();
248  ++pos_;
249  }
250 
251  size_t Position() const final { return pos_; }
252 
253  void Reset() final {
254  if (s_ != 0) aiter_->Reset();
255  pos_ = 0;
256  }
257 
258  void Seek(size_t a) final {
259  if (s_ != 0) {
260  if (a == 0) {
261  aiter_->Reset();
262  } else {
263  aiter_->Seek(a - 1);
264  }
265  }
266  pos_ = a;
267  }
268 
269  uint8_t Flags() const final { return kArcValueFlags; }
270 
271  void SetFlags(uint8_t, uint8_t) final {}
272 
273  private:
274  std::unique_ptr<ArcIterator<Fst<Arc>>> aiter_;
275  StateId s_;
276  size_t pos_;
277  mutable Arc arc_;
278 };
279 
280 template <class Arc>
282  StateIteratorData<Arc> *data) const {
283  data->base = std::make_unique<StateIterator<ComplementFst<Arc>>>(*this);
284 }
285 
286 template <class Arc>
288  StateId s, ArcIteratorData<Arc> *data) const {
289  data->base = std::make_unique<ArcIterator<ComplementFst<Arc>>>(*this, s);
290 }
291 
292 // Useful alias when using StdArc.
294 
295 } // namespace fst
296 
297 #endif // FST_COMPLEMENT_H_
typename Arc::Label Label
Definition: complement.h:141
void SetProperties(uint64_t props)
Definition: fst.h:710
uint64_t Properties() const override
Definition: complement.h:113
constexpr uint8_t kArcValueFlags
Definition: fst.h:452
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:234
typename Arc::Label Label
Definition: complement.h:58
typename Arc::StateId StateId
Definition: complement.h:142
const SymbolTable * OutputSymbols() const
Definition: fst.h:762
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:772
ComplementFst(const Fst< Arc > &fst)
Definition: complement.h:148
ComplementFstImpl(const Fst< Arc > &fst)
Definition: complement.h:70
ComplementFstImpl(const ComplementFstImpl< Arc > &impl)
Definition: complement.h:78
constexpr int kNoStateId
Definition: fst.h:195
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:57
virtual uint64_t Properties() const
Definition: fst.h:702
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:218
ComplementFst(const ComplementFst &fst, bool safe=false)
Definition: complement.h:160
constexpr uint64_t kNoEpsilons
Definition: properties.h:81
std::unique_ptr< StateIteratorBase< Arc > > base
Definition: fst.h:381
constexpr uint64_t kIDeterministic
Definition: properties.h:69
void SetFlags(uint8_t, uint8_t) final
Definition: complement.h:271
std::unique_ptr< ArcIteratorBase< Arc > > base
Definition: fst.h:493
uint64_t ComplementProperties(uint64_t inprops)
Definition: properties.cc:60
void SetInputSymbols(const SymbolTable *isyms)
Definition: fst.h:768
StateIterator(const ComplementFst< Arc > &fst)
Definition: complement.h:189
constexpr uint64_t kILabelSorted
Definition: properties.h:94
void InitStateIterator(StateIteratorData< Arc > *data) const override
Definition: complement.h:281
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:164
virtual const SymbolTable * InputSymbols() const =0
const SymbolTable * InputSymbols() const
Definition: fst.h:760
void SetType(std::string_view type)
Definition: fst.h:700
size_t NumInputEpsilons(StateId s) const
Definition: complement.h:105
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const override
Definition: complement.h:287
FstImpl & operator=(const FstImpl &impl)
Definition: fst.h:685
constexpr uint64_t kAcceptor
Definition: properties.h:64
virtual const SymbolTable * OutputSymbols() const =0