FST  openfst-1.7.1
OpenFst Library
intersect.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 intersection of two FSAs.
5 
6 #ifndef FST_INTERSECT_H_
7 #define FST_INTERSECT_H_
8 
9 #include <algorithm>
10 #include <vector>
11 
12 #include <fst/log.h>
13 
14 #include <fst/cache.h>
15 #include <fst/compose.h>
16 
17 
18 namespace fst {
19 
21 
22 template <class Arc, class M = Matcher<Fst<Arc>>,
23  class Filter = SequenceComposeFilter<M>,
24  class StateTable =
25  GenericComposeStateTable<Arc, typename Filter::FilterState>>
27  : public ComposeFstOptions<Arc, M, Filter, StateTable> {
29 
30  explicit IntersectFstOptions(const CacheOptions &opts, M *matcher1 = nullptr,
31  M *matcher2 = nullptr, Filter *filter = nullptr,
32  StateTable *state_table = nullptr)
33  : ComposeFstOptions<Arc, M, Filter, StateTable>(opts, matcher1, matcher2,
34  filter, state_table) {}
35 };
36 
37 // Computes the intersection (Hadamard product) of two FSAs. This version is a
38 // delayed FST. Only strings that are in both automata are retained in the
39 // result.
40 //
41 // The two arguments must be acceptors. One of the arguments must be
42 // label-sorted.
43 //
44 // Complexity: same as ComposeFst.
45 //
46 // Caveats: same as ComposeFst.
47 template <class A>
48 class IntersectFst : public ComposeFst<A> {
49  public:
50  using Arc = A;
51  using StateId = typename Arc::StateId;
52  using Weight = typename Arc::Weight;
53 
57 
58  IntersectFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
59  const CacheOptions &opts = CacheOptions())
60  : ComposeFst<Arc>(CreateBase(fst1, fst2, opts)) {
61  const bool acceptors =
62  fst1.Properties(kAcceptor, true) && fst2.Properties(kAcceptor, true);
63  if (!acceptors) {
64  FSTERROR() << "IntersectFst: Input FSTs are not acceptors";
65  GetMutableImpl()->SetProperties(kError);
66  }
67  }
68 
69  template <class M, class Filter, class StateTable>
70  IntersectFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
72  : ComposeFst<Arc>(CreateBase1(fst1, fst2, opts)) {
73  const bool acceptors =
74  fst1.Properties(kAcceptor, true) && fst2.Properties(kAcceptor, true);
75  if (!acceptors) {
76  FSTERROR() << "IntersectFst: input FSTs are not acceptors";
77  GetMutableImpl()->SetProperties(kError);
78  }
79  }
80 
81  // See Fst<>::Copy() for doc.
82  IntersectFst(const IntersectFst<Arc> &fst, bool safe = false)
83  : ComposeFst<Arc>(fst, safe) {}
84 
85  // Get a copy of this IntersectFst. See Fst<>::Copy() for further doc.
86  IntersectFst<Arc> *Copy(bool safe = false) const override {
87  return new IntersectFst<Arc>(*this, safe);
88  }
89 
90  private:
92  using ImplToFst<internal::ComposeFstImplBase<A>>::GetMutableImpl;
93 };
94 
95 // Specialization for IntersectFst.
96 template <class Arc>
97 class StateIterator<IntersectFst<Arc>> : public StateIterator<ComposeFst<Arc>> {
98  public:
100  : StateIterator<ComposeFst<Arc>>(fst) {}
101 };
102 
103 // Specialization for IntersectFst.
104 template <class Arc>
105 class ArcIterator<IntersectFst<Arc>> : public ArcIterator<ComposeFst<Arc>> {
106  public:
107  using StateId = typename Arc::StateId;
108 
110  : ArcIterator<ComposeFst<Arc>>(fst, s) {}
111 };
112 
113 // Useful alias when using StdArc.
115 
116 // Computes the intersection (Hadamard product) of two FSAs. This version
117 // writes the intersection to an output MurableFst. Only strings that are in
118 // both automata are retained in the result.
119 //
120 // The two arguments must be acceptors. One of the arguments must be
121 // label-sorted.
122 //
123 // Complexity: same as Compose.
124 //
125 // Caveats: same as Compose.
126 template <class Arc>
127 void Intersect(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
128  MutableFst<Arc> *ofst,
129  const IntersectOptions &opts = IntersectOptions()) {
130  using M = Matcher<Fst<Arc>>;
131  if (opts.filter_type == AUTO_FILTER) {
132  CacheOptions nopts;
133  nopts.gc_limit = 0; // Cache only the last state for fastest copy.
134  *ofst = IntersectFst<Arc>(ifst1, ifst2, nopts);
135  } else if (opts.filter_type == SEQUENCE_FILTER) {
137  iopts.gc_limit = 0; // Cache only the last state for fastest copy.
138  *ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
139  } else if (opts.filter_type == ALT_SEQUENCE_FILTER) {
141  iopts.gc_limit = 0; // Cache only the last state for fastest copy.
142  *ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
143  } else if (opts.filter_type == MATCH_FILTER) {
145  iopts.gc_limit = 0; // Cache only the last state for fastest copy.
146  *ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
147  }
148  if (opts.connect) Connect(ofst);
149 }
150 
151 } // namespace fst
152 
153 #endif // FST_INTERSECT_H_
IntersectFst< Arc > * Copy(bool safe=false) const override
Definition: intersect.h:86
ArcIterator(const IntersectFst< Arc > &fst, StateId s)
Definition: intersect.h:109
typename ComposeFst< Arc >::Arc Arc
Definition: fst.h:480
IntersectFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const IntersectFstOptions< Arc, M, Filter, StateTable > &opts)
Definition: intersect.h:70
IntersectFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const CacheOptions &opts=CacheOptions())
Definition: intersect.h:58
StateIterator(const IntersectFst< Arc > &fst)
Definition: intersect.h:99
void Intersect(const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, const IntersectOptions &opts=IntersectOptions())
Definition: intersect.h:127
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
#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::Weight Weight
Definition: intersect.h:52
constexpr uint64 kAcceptor
Definition: properties.h:45
constexpr uint64 kError
Definition: properties.h:33
IntersectFst(const IntersectFst< Arc > &fst, bool safe=false)
Definition: intersect.h:82
typename Arc::StateId StateId
Definition: intersect.h:51
size_t gc_limit
Definition: cache.h:29
ComposeOptions IntersectOptions
Definition: intersect.h:20
IntersectFstOptions(const CacheOptions &opts, M *matcher1=nullptr, M *matcher2=nullptr, Filter *filter=nullptr, StateTable *state_table=nullptr)
Definition: intersect.h:30
StateTable * state_table
Definition: compose.h:43