FST  openfst-1.8.2.post1
OpenFst Library
difference.h
Go to the documentation of this file.
1 // Copyright 2005-2020 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 compute the difference between two FSAs.
19 
20 #ifndef FST_DIFFERENCE_H_
21 #define FST_DIFFERENCE_H_
22 
23 #include <memory>
24 
25 
26 #include <fst/cache.h>
27 #include <fst/complement.h>
28 #include <fst/compose.h>
29 
30 
31 namespace fst {
32 
33 template <class Arc, class M = Matcher<Fst<Arc>>,
34  class Filter = SequenceComposeFilter<M>,
35  class StateTable =
36  GenericComposeStateTable<Arc, typename Filter::FilterState>>
38  : public ComposeFstOptions<Arc, M, Filter, StateTable> {
40  M *matcher1 = nullptr, M *matcher2 = nullptr,
41  Filter *filter = nullptr,
42  StateTable *state_table = nullptr)
43  : ComposeFstOptions<Arc, M, Filter, StateTable>(opts, matcher1, matcher2,
44  filter, state_table) {}
45 };
46 
47 // Computes the difference between two FSAs. This version is a delayed FST.
48 // Only strings that are in the first automaton but not in second are retained
49 // in the result.
50 //
51 // The first argument must be an acceptor; the second argument must be an
52 // unweighted, epsilon-free, deterministic acceptor. One of the arguments must
53 // be label-sorted.
54 //
55 // Complexity: same as ComposeFst.
56 //
57 // Caveats: same as ComposeFst.
58 template <class A>
59 class DifferenceFst : public ComposeFst<A> {
60  public:
61  using Arc = A;
62  using Weight = typename Arc::Weight;
63  using StateId = typename Arc::StateId;
64 
66 
67  // A - B = A ^ B'.
68  DifferenceFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
69  const CacheOptions &opts = CacheOptions())
70  : ComposeFst<Arc>(CreateDifferenceImplWithCacheOpts(fst1, fst2, opts)) {
71  if (!fst1.Properties(kAcceptor, true)) {
72  FSTERROR() << "DifferenceFst: 1st argument not an acceptor";
73  GetImpl()->SetProperties(kError, kError);
74  }
75  }
76 
77  template <class Matcher, class Filter, class StateTable>
79  const Fst<Arc> &fst1, const Fst<Arc> &fst2,
81  : ComposeFst<Arc>(
82  CreateDifferenceImplWithDifferenceOpts(fst1, fst2, opts)) {
83  if (!fst1.Properties(kAcceptor, true)) {
84  FSTERROR() << "DifferenceFst: 1st argument not an acceptor";
85  GetImpl()->SetProperties(kError, kError);
86  }
87  }
88 
89  // See Fst<>::Copy() for doc.
90  DifferenceFst(const DifferenceFst &fst, bool safe = false)
91  : ComposeFst<Arc>(fst, safe) {}
92 
93  // Get a copy of this DifferenceFst. See Fst<>::Copy() for further doc.
94  DifferenceFst *Copy(bool safe = false) const override {
95  return new DifferenceFst(*this, safe);
96  }
97 
98  private:
101 
102  static std::shared_ptr<Impl> CreateDifferenceImplWithCacheOpts(
103  const Fst<Arc> &fst1, const Fst<Arc> &fst2, const CacheOptions &opts) {
104  using RM = RhoMatcher<Matcher<Fst<A>>>;
105  ComplementFst<Arc> cfst(fst2);
107  CacheOptions(), new RM(fst1, MATCH_NONE),
109  return CreateBase1(fst1, cfst, copts);
110  }
111 
112  template <class Matcher, class Filter, class StateTable>
113  static std::shared_ptr<Impl> CreateDifferenceImplWithDifferenceOpts(
114  const Fst<Arc> &fst1, const Fst<Arc> &fst2,
116  using RM = RhoMatcher<Matcher>;
117  ComplementFst<Arc> cfst(fst2);
118  ComposeFstOptions<Arc, RM> copts(opts);
119  copts.matcher1 = new RM(fst1, MATCH_NONE, kNoLabel, MATCHER_REWRITE_ALWAYS,
120  opts.matcher1);
121  copts.matcher2 = new RM(cfst, MATCH_INPUT, ComplementFst<Arc>::kRhoLabel,
123  return CreateBase1(fst1, cfst, copts);
124  }
125 };
126 
127 // Specialization for DifferenceFst.
128 template <class Arc>
130  : public StateIterator<ComposeFst<Arc>> {
131  public:
133  : StateIterator<ComposeFst<Arc>>(fst) {}
134 };
135 
136 // Specialization for DifferenceFst.
137 template <class Arc>
138 class ArcIterator<DifferenceFst<Arc>> : public ArcIterator<ComposeFst<Arc>> {
139  public:
140  using StateId = typename Arc::StateId;
141 
143  : ArcIterator<ComposeFst<Arc>>(fst, s) {}
144 };
145 
147 
148 // Useful alias when using StdArc.
150 
152 
153 // Computes the difference between two FSAs. This version writes the difference
154 // to an output MutableFst. Only strings that are in the first automaton but not
155 // in the second are retained in the result.
156 //
157 // The first argument must be an acceptor; the second argument must be an
158 // unweighted, epsilon-free, deterministic acceptor. One of the arguments must
159 // be label-sorted.
160 //
161 // Complexity: same as Compose.
162 //
163 // Caveats: same as Compose.
164 template <class Arc>
165 void Difference(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
166  MutableFst<Arc> *ofst,
167  const DifferenceOptions &opts = DifferenceOptions()) {
168  using M = Matcher<Fst<Arc>>;
169  // In each case, we cache only the last state for fastest copy.
170  switch (opts.filter_type) {
171  case AUTO_FILTER: {
172  CacheOptions nopts;
173  nopts.gc_limit = 0;
174  *ofst = DifferenceFst<Arc>(ifst1, ifst2, nopts);
175  break;
176  }
177  case SEQUENCE_FILTER: {
179  dopts.gc_limit = 0;
180  *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
181  break;
182  }
183  case ALT_SEQUENCE_FILTER: {
185  dopts.gc_limit = 0;
186  *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
187  break;
188  }
189  case MATCH_FILTER: {
191  dopts.gc_limit = 0;
192  *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
193  break;
194  }
195  case NO_MATCH_FILTER: {
197  dopts.gc_limit = 0;
198  *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
199  break;
200  }
201  case NULL_FILTER: {
203  dopts.gc_limit = 0;
204  *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
205  break;
206  }
207  case TRIVIAL_FILTER: {
209  dopts.gc_limit = 0;
210  *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
211  break;
212  }
213  }
214  if (opts.connect) Connect(ofst);
215 }
216 
217 } // namespace fst
218 
219 #endif // FST_DIFFERENCE_H_
typename Arc::Weight Weight
Definition: difference.h:62
DifferenceFst(const DifferenceFst &fst, bool safe=false)
Definition: difference.h:90
StateIterator(const DifferenceFst< Arc > &fst)
Definition: difference.h:132
typename ComposeFst< Arc >::Arc Arc
Definition: fst.h:518
constexpr int kNoLabel
Definition: fst.h:201
CacheOptions(bool gc=FST_FLAGS_fst_default_cache_gc, size_t gc_limit=FST_FLAGS_fst_default_cache_gc_limit)
Definition: cache.h:47
virtual uint64_t Properties(uint64_t mask, bool test) const =0
DifferenceFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const DifferenceFstOptions< Arc, Matcher, Filter, StateTable > &opts)
Definition: difference.h:78
constexpr uint64_t kError
Definition: properties.h:51
void Connect(MutableFst< Arc > *fst)
Definition: connect.h:278
typename ComposeFst< Arc >::Arc Arc
Definition: fst.h:408
void Difference(const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, const DifferenceOptions &opts=DifferenceOptions())
Definition: difference.h:165
#define FSTERROR()
Definition: util.h:53
typename Arc::StateId StateId
Definition: difference.h:63
ComposeOptions DifferenceOptions
Definition: difference.h:146
DifferenceFstOptions(const CacheOptions &opts=CacheOptions(), M *matcher1=nullptr, M *matcher2=nullptr, Filter *filter=nullptr, StateTable *state_table=nullptr)
Definition: difference.h:39
DifferenceFst * Copy(bool safe=false) const override
Definition: difference.h:94
DifferenceFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const CacheOptions &opts=CacheOptions())
Definition: difference.h:68
size_t gc_limit
Definition: cache.h:45
ArcIterator(const DifferenceFst< Arc > &fst, StateId s)
Definition: difference.h:142
constexpr uint64_t kAcceptor
Definition: properties.h:63
StateTable * state_table
Definition: compose.h:58