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