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