FST  openfst-1.8.4
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  using Base = ComposeFst<A>;
73 
74  public:
75  using Arc = A;
76  using StateId = typename Arc::StateId;
77  using Weight = typename Arc::Weight;
78 
79  using Base::CreateBase;
80  using Base::CreateBase1;
81  using Base::Properties;
82 
83  IntersectFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
84  const CacheOptions &opts = CacheOptions())
85  : Base(CreateBase(fst1, fst2, opts)) {
86  const bool acceptors =
87  fst1.Properties(kAcceptor, true) && fst2.Properties(kAcceptor, true);
88  if (!acceptors) {
89  FSTERROR() << "IntersectFst: Input FSTs are not acceptors";
90  GetMutableImpl()->SetProperties(kError);
91  }
92  }
93 
94  template <class M, class Filter, class StateTable>
95  IntersectFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
97  : Base(CreateBase1(fst1, fst2, opts)) {
98  const bool acceptors =
99  fst1.Properties(kAcceptor, true) && fst2.Properties(kAcceptor, true);
100  if (!acceptors) {
101  FSTERROR() << "IntersectFst: input FSTs are not acceptors";
102  GetMutableImpl()->SetProperties(kError);
103  }
104  }
105 
106  // See Fst<>::Copy() for doc.
107  IntersectFst(const IntersectFst &fst, bool safe = false) : Base(fst, safe) {}
108 
109  // Get a copy of this IntersectFst. See Fst<>::Copy() for further doc.
110  IntersectFst *Copy(bool safe = false) const override {
111  return new IntersectFst(*this, safe);
112  }
113 
114  private:
115  using Base::GetImpl;
116  using Base::GetMutableImpl;
117 };
118 
119 // Specialization for IntersectFst.
120 template <class Arc>
121 class StateIterator<IntersectFst<Arc>> : public StateIterator<ComposeFst<Arc>> {
122  public:
124  : StateIterator<ComposeFst<Arc>>(fst) {}
125 };
126 
127 // Specialization for IntersectFst.
128 template <class Arc>
129 class ArcIterator<IntersectFst<Arc>> : public ArcIterator<ComposeFst<Arc>> {
130  public:
131  using StateId = typename Arc::StateId;
132 
134  : ArcIterator<ComposeFst<Arc>>(fst, s) {}
135 };
136 
137 // Useful alias when using StdArc.
139 
140 // Computes the intersection (Hadamard product) of two FSAs. This version
141 // writes the intersection to an output MurableFst. Only strings that are in
142 // both automata are retained in the result.
143 //
144 // The two arguments must be acceptors. One of the arguments must be
145 // label-sorted.
146 //
147 // Complexity: same as Compose.
148 //
149 // Caveats: same as Compose.
150 template <class Arc>
151 void Intersect(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
152  MutableFst<Arc> *ofst,
153  const IntersectOptions &opts = IntersectOptions()) {
154  using M = Matcher<Fst<Arc>>;
155  // In each case, we cache only the last state for fastest copy.
156  switch (opts.filter_type) {
157  case AUTO_FILTER: {
158  CacheOptions nopts;
159  nopts.gc_limit = 0;
160  *ofst = IntersectFst<Arc>(ifst1, ifst2, nopts);
161  break;
162  }
163  case SEQUENCE_FILTER: {
165  iopts.gc_limit = 0;
166  *ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
167  break;
168  }
169  case ALT_SEQUENCE_FILTER: {
171  iopts.gc_limit = 0;
172  *ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
173  break;
174  }
175  case MATCH_FILTER: {
177  iopts.gc_limit = 0;
178  *ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
179  break;
180  }
181  case NO_MATCH_FILTER: {
183  iopts.gc_limit = 0;
184  *ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
185  break;
186  }
187  case NULL_FILTER: {
189  iopts.gc_limit = 0;
190  *ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
191  break;
192  }
193  case TRIVIAL_FILTER: {
195  iopts.gc_limit = 0;
196  *ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
197  break;
198  }
199  }
200  if (opts.connect) Connect(ofst);
201 }
202 
203 } // namespace fst
204 
205 #endif // FST_INTERSECT_H_
ArcIterator(const IntersectFst< Arc > &fst, StateId s)
Definition: intersect.h:133
typename ComposeFst< Arc >::Arc Arc
Definition: fst.h:516
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:95
IntersectFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const CacheOptions &opts=CacheOptions())
Definition: intersect.h:83
StateIterator(const IntersectFst< Arc > &fst)
Definition: intersect.h:123
constexpr uint64_t kError
Definition: properties.h:52
IntersectFst * Copy(bool safe=false) const override
Definition: intersect.h:110
void Intersect(const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, const IntersectOptions &opts=IntersectOptions())
Definition: intersect.h:151
void Connect(MutableFst< Arc > *fst)
Definition: connect.h:47
typename ComposeFst< Arc >::Arc Arc
Definition: fst.h:407
#define FSTERROR()
Definition: util.h:57
typename Arc::Weight Weight
Definition: intersect.h:77
IntersectFst(const IntersectFst &fst, bool safe=false)
Definition: intersect.h:107
typename Arc::StateId StateId
Definition: intersect.h:76
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