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