FST  openfst-1.8.2.post1
OpenFst Library
intersect.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 intersection of two FSAs.
19 
20 #ifndef FST_INTERSECT_H_
21 #define FST_INTERSECT_H_
22 
23 #include <algorithm>
24 #include <vector>
25 
26 #include <fst/log.h>
27 
28 #include <fst/cache.h>
29 #include <fst/compose.h>
30 
31 
32 namespace fst {
33 
35 
36 template <class Arc, class M = Matcher<Fst<Arc>>,
37  class Filter = SequenceComposeFilter<M>,
38  class StateTable =
39  GenericComposeStateTable<Arc, typename Filter::FilterState>>
41  : public ComposeFstOptions<Arc, M, Filter, StateTable> {
43 
44  explicit IntersectFstOptions(const CacheOptions &opts, M *matcher1 = nullptr,
45  M *matcher2 = nullptr, Filter *filter = nullptr,
46  StateTable *state_table = nullptr)
47  : ComposeFstOptions<Arc, M, Filter, StateTable>(opts, matcher1, matcher2,
48  filter, state_table) {}
49 };
50 
51 // Computes the intersection (Hadamard product) of two FSAs. This version is a
52 // delayed FST. Only strings that are in both automata are retained in the
53 // result.
54 //
55 // The two arguments must be acceptors. One of the arguments must be
56 // label-sorted.
57 //
58 // Complexity: same as ComposeFst.
59 //
60 // Caveats: same as ComposeFst.
61 template <class A>
62 class IntersectFst : public ComposeFst<A> {
63  public:
64  using Arc = A;
65  using StateId = typename Arc::StateId;
66  using Weight = typename Arc::Weight;
67 
71 
72  IntersectFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
73  const CacheOptions &opts = CacheOptions())
74  : ComposeFst<Arc>(CreateBase(fst1, fst2, opts)) {
75  const bool acceptors =
76  fst1.Properties(kAcceptor, true) && fst2.Properties(kAcceptor, true);
77  if (!acceptors) {
78  FSTERROR() << "IntersectFst: Input FSTs are not acceptors";
79  GetMutableImpl()->SetProperties(kError);
80  }
81  }
82 
83  template <class M, class Filter, class StateTable>
84  IntersectFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
86  : ComposeFst<Arc>(CreateBase1(fst1, fst2, opts)) {
87  const bool acceptors =
88  fst1.Properties(kAcceptor, true) && fst2.Properties(kAcceptor, true);
89  if (!acceptors) {
90  FSTERROR() << "IntersectFst: input FSTs are not acceptors";
91  GetMutableImpl()->SetProperties(kError);
92  }
93  }
94 
95  // See Fst<>::Copy() for doc.
96  IntersectFst(const IntersectFst &fst, bool safe = false)
97  : ComposeFst<Arc>(fst, safe) {}
98 
99  // Get a copy of this IntersectFst. See Fst<>::Copy() for further doc.
100  IntersectFst *Copy(bool safe = false) const override {
101  return new IntersectFst(*this, safe);
102  }
103 
104  private:
106  using ImplToFst<internal::ComposeFstImplBase<A>>::GetMutableImpl;
107 };
108 
109 // Specialization for IntersectFst.
110 template <class Arc>
111 class StateIterator<IntersectFst<Arc>> : public StateIterator<ComposeFst<Arc>> {
112  public:
114  : StateIterator<ComposeFst<Arc>>(fst) {}
115 };
116 
117 // Specialization for IntersectFst.
118 template <class Arc>
119 class ArcIterator<IntersectFst<Arc>> : public ArcIterator<ComposeFst<Arc>> {
120  public:
121  using StateId = typename Arc::StateId;
122 
124  : ArcIterator<ComposeFst<Arc>>(fst, s) {}
125 };
126 
127 // Useful alias when using StdArc.
129 
130 // Computes the intersection (Hadamard product) of two FSAs. This version
131 // writes the intersection to an output MurableFst. Only strings that are in
132 // both automata are retained in the result.
133 //
134 // The two arguments must be acceptors. One of the arguments must be
135 // label-sorted.
136 //
137 // Complexity: same as Compose.
138 //
139 // Caveats: same as Compose.
140 template <class Arc>
141 void Intersect(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
142  MutableFst<Arc> *ofst,
143  const IntersectOptions &opts = IntersectOptions()) {
144  using M = Matcher<Fst<Arc>>;
145  // In each case, we cache only the last state for fastest copy.
146  switch (opts.filter_type) {
147  case AUTO_FILTER: {
148  CacheOptions nopts;
149  nopts.gc_limit = 0;
150  *ofst = IntersectFst<Arc>(ifst1, ifst2, nopts);
151  break;
152  }
153  case SEQUENCE_FILTER: {
155  iopts.gc_limit = 0;
156  *ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
157  break;
158  }
159  case ALT_SEQUENCE_FILTER: {
161  iopts.gc_limit = 0;
162  *ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
163  break;
164  }
165  case MATCH_FILTER: {
167  iopts.gc_limit = 0;
168  *ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
169  break;
170  }
171  case NO_MATCH_FILTER: {
173  iopts.gc_limit = 0;
174  *ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
175  break;
176  }
177  case NULL_FILTER: {
179  iopts.gc_limit = 0;
180  *ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
181  break;
182  }
183  case TRIVIAL_FILTER: {
185  iopts.gc_limit = 0;
186  *ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
187  break;
188  }
189  }
190  if (opts.connect) Connect(ofst);
191 }
192 
193 } // namespace fst
194 
195 #endif // FST_INTERSECT_H_
ArcIterator(const IntersectFst< Arc > &fst, StateId s)
Definition: intersect.h:123
typename ComposeFst< Arc >::Arc Arc
Definition: fst.h:518
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
IntersectFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const IntersectFstOptions< Arc, M, Filter, StateTable > &opts)
Definition: intersect.h:84
IntersectFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const CacheOptions &opts=CacheOptions())
Definition: intersect.h:72
StateIterator(const IntersectFst< Arc > &fst)
Definition: intersect.h:113
constexpr uint64_t kError
Definition: properties.h:51
IntersectFst * Copy(bool safe=false) const override
Definition: intersect.h:100
void Intersect(const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, const IntersectOptions &opts=IntersectOptions())
Definition: intersect.h:141
void Connect(MutableFst< Arc > *fst)
Definition: connect.h:278
typename ComposeFst< Arc >::Arc Arc
Definition: fst.h:408
#define FSTERROR()
Definition: util.h:53
typename Arc::Weight Weight
Definition: intersect.h:66
IntersectFst(const IntersectFst &fst, bool safe=false)
Definition: intersect.h:96
typename Arc::StateId StateId
Definition: intersect.h:65
size_t gc_limit
Definition: cache.h:45
ComposeOptions IntersectOptions
Definition: intersect.h:34
IntersectFstOptions(const CacheOptions &opts, M *matcher1=nullptr, M *matcher2=nullptr, Filter *filter=nullptr, StateTable *state_table=nullptr)
Definition: intersect.h:44
constexpr uint64_t kAcceptor
Definition: properties.h:63
StateTable * state_table
Definition: compose.h:58