FST  openfst-1.7.1
OpenFst Library
difference.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 compute the difference between two FSAs.
5 
6 #ifndef FST_DIFFERENCE_H_
7 #define FST_DIFFERENCE_H_
8 
9 #include <memory>
10 
11 
12 #include <fst/cache.h>
13 #include <fst/complement.h>
14 #include <fst/compose.h>
15 
16 
17 namespace fst {
18 
19 template <class Arc, class M = Matcher<Fst<Arc>>,
20  class Filter = SequenceComposeFilter<M>,
21  class StateTable =
22  GenericComposeStateTable<Arc, typename Filter::FilterState>>
24  : public ComposeFstOptions<Arc, M, Filter, StateTable> {
26  M *matcher1 = nullptr, M *matcher2 = nullptr,
27  Filter *filter = nullptr,
28  StateTable *state_table = nullptr)
29  : ComposeFstOptions<Arc, M, Filter, StateTable>(opts, matcher1, matcher2,
30  filter, state_table) {}
31 };
32 
33 // Computes the difference between two FSAs. This version is a delayed FST.
34 // Only strings that are in the first automaton but not in second are retained
35 // in the result.
36 //
37 // The first argument must be an acceptor; the second argument must be an
38 // unweighted, epsilon-free, deterministic acceptor. One of the arguments must
39 // be label-sorted.
40 //
41 // Complexity: same as ComposeFst.
42 //
43 // Caveats: same as ComposeFst.
44 template <class A>
45 class DifferenceFst : public ComposeFst<A> {
46  public:
47  using Arc = A;
48  using Weight = typename Arc::Weight;
49  using StateId = typename Arc::StateId;
50 
52 
53  // A - B = A ^ B'.
54  DifferenceFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
55  const CacheOptions &opts = CacheOptions())
56  : ComposeFst<Arc>(CreateDifferenceImplWithCacheOpts(fst1, fst2, opts)) {
57  if (!fst1.Properties(kAcceptor, true)) {
58  FSTERROR() << "DifferenceFst: 1st argument not an acceptor";
59  GetImpl()->SetProperties(kError, kError);
60  }
61  }
62 
63  template <class Matcher, class Filter, class StateTable>
65  const Fst<Arc> &fst1, const Fst<Arc> &fst2,
67  : ComposeFst<Arc>(
68  CreateDifferenceImplWithDifferenceOpts(fst1, fst2, opts)) {
69  if (!fst1.Properties(kAcceptor, true)) {
70  FSTERROR() << "DifferenceFst: 1st argument not an acceptor";
71  GetImpl()->SetProperties(kError, kError);
72  }
73  }
74 
75  // See Fst<>::Copy() for doc.
76  DifferenceFst(const DifferenceFst<Arc> &fst, bool safe = false)
77  : ComposeFst<Arc>(fst, safe) {}
78 
79  // Get a copy of this DifferenceFst. See Fst<>::Copy() for further doc.
80  DifferenceFst<Arc> *Copy(bool safe = false) const override {
81  return new DifferenceFst<Arc>(*this, safe);
82  }
83 
84  private:
87 
88  static std::shared_ptr<Impl> CreateDifferenceImplWithCacheOpts(
89  const Fst<Arc> &fst1, const Fst<Arc> &fst2, const CacheOptions &opts) {
90  using RM = RhoMatcher<Matcher<Fst<A>>>;
91  ComplementFst<Arc> cfst(fst2);
93  CacheOptions(), new RM(fst1, MATCH_NONE),
95  return CreateBase1(fst1, cfst, copts);
96  }
97 
98  template <class Matcher, class Filter, class StateTable>
99  static std::shared_ptr<Impl> CreateDifferenceImplWithDifferenceOpts(
100  const Fst<Arc> &fst1, const Fst<Arc> &fst2,
102  using RM = RhoMatcher<Matcher>;
103  ComplementFst<Arc> cfst(fst2);
104  ComposeFstOptions<Arc, RM> copts(opts);
105  copts.matcher1 = new RM(fst1, MATCH_NONE, kNoLabel, MATCHER_REWRITE_ALWAYS,
106  opts.matcher1);
107  copts.matcher2 = new RM(cfst, MATCH_INPUT, ComplementFst<Arc>::kRhoLabel,
109  return CreateBase1(fst1, cfst, copts);
110  }
111 };
112 
113 // Specialization for DifferenceFst.
114 template <class Arc>
116  : public StateIterator<ComposeFst<Arc>> {
117  public:
119  : StateIterator<ComposeFst<Arc>>(fst) {}
120 };
121 
122 // Specialization for DifferenceFst.
123 template <class Arc>
124 class ArcIterator<DifferenceFst<Arc>> : public ArcIterator<ComposeFst<Arc>> {
125  public:
126  using StateId = typename Arc::StateId;
127 
129  : ArcIterator<ComposeFst<Arc>>(fst, s) {}
130 };
131 
133 
134 // Useful alias when using StdArc.
136 
138 
139 // Computes the difference between two FSAs. This version writes the difference
140 // to an output MutableFst. Only strings that are in the first automaton but not
141 // in the second are retained in the result.
142 //
143 // The first argument must be an acceptor; the second argument must be an
144 // unweighted, epsilon-free, deterministic acceptor. One of the arguments must
145 // be label-sorted.
146 //
147 // Complexity: same as Compose.
148 //
149 // Caveats: same as Compose.
150 template <class Arc>
151 void Difference(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
152  MutableFst<Arc> *ofst,
153  const DifferenceOptions &opts = DifferenceOptions()) {
154  using M = Matcher<Fst<Arc>>;
155  if (opts.filter_type == AUTO_FILTER) {
156  CacheOptions nopts;
157  nopts.gc_limit = 0; // Cache only the last state for fastest copy.
158  *ofst = DifferenceFst<Arc>(ifst1, ifst2, nopts);
159  } else if (opts.filter_type == SEQUENCE_FILTER) {
161  dopts.gc_limit = 0; // Cache only the last state for fastest copy.
162  *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
163  } else if (opts.filter_type == ALT_SEQUENCE_FILTER) {
165  dopts.gc_limit = 0; // Cache only the last state for fastest copy.
166  *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
167  } else if (opts.filter_type == MATCH_FILTER) {
169  dopts.gc_limit = 0; // Cache only the last state for fastest copy.
170  *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
171  }
172  if (opts.connect) Connect(ofst);
173 }
174 
175 } // namespace fst
176 
177 #endif // FST_DIFFERENCE_H_
typename Arc::Weight Weight
Definition: difference.h:48
StateIterator(const DifferenceFst< Arc > &fst)
Definition: difference.h:118
typename ComposeFst< Arc >::Arc Arc
Definition: fst.h:480
constexpr int kNoLabel
Definition: fst.h:179
DifferenceFst< Arc > * Copy(bool safe=false) const override
Definition: difference.h:80
DifferenceFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const DifferenceFstOptions< Arc, Matcher, Filter, StateTable > &opts)
Definition: difference.h:64
void Connect(MutableFst< Arc > *fst)
Definition: connect.h:268
typename ComposeFst< Arc >::Arc Arc
Definition: fst.h:374
virtual uint64 Properties(uint64 mask, bool test) const =0
void Difference(const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, const DifferenceOptions &opts=DifferenceOptions())
Definition: difference.h:151
#define FSTERROR()
Definition: util.h:35
CacheOptions(bool gc=FLAGS_fst_default_cache_gc, size_t gc_limit=FLAGS_fst_default_cache_gc_limit)
Definition: cache.h:31
typename Arc::StateId StateId
Definition: difference.h:49
ComposeOptions DifferenceOptions
Definition: difference.h:132
constexpr uint64 kAcceptor
Definition: properties.h:45
DifferenceFstOptions(const CacheOptions &opts=CacheOptions(), M *matcher1=nullptr, M *matcher2=nullptr, Filter *filter=nullptr, StateTable *state_table=nullptr)
Definition: difference.h:25
constexpr uint64 kError
Definition: properties.h:33
DifferenceFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const CacheOptions &opts=CacheOptions())
Definition: difference.h:54
size_t gc_limit
Definition: cache.h:29
DifferenceFst(const DifferenceFst< Arc > &fst, bool safe=false)
Definition: difference.h:76
ArcIterator(const DifferenceFst< Arc > &fst, StateId s)
Definition: difference.h:128
StateTable * state_table
Definition: compose.h:43