/usr/include/fst/intersect.h is in libfst-dev 1.6.3-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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_LIB_INTERSECT_H_
#define FST_LIB_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_LIB_INTERSECT_H_
|