/usr/include/fst/difference.h is in libfst-dev 1.5.3+r3-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 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 | // See www.openfst.org for extensive documentation on this weighted
// finite-state transducer library.
//
// Class to compute the difference between two FSAs.
#ifndef FST_LIB_DIFFERENCE_H_
#define FST_LIB_DIFFERENCE_H_
#include <algorithm>
#include <vector>
#include <fst/cache.h>
#include <fst/complement.h>
#include <fst/compose.h>
namespace fst {
template <class A, class M = Matcher<Fst<A>>,
class F = SequenceComposeFilter<M>,
class T = GenericComposeStateTable<A, typename F::FilterState>>
struct DifferenceFstOptions : public ComposeFstOptions<A, M, F, T> {
explicit DifferenceFstOptions(const CacheOptions &opts, M *mat1 = 0,
M *mat2 = 0, F *filt = 0, T *sttable = 0)
: ComposeFstOptions<A, M, F, T>(mat1, mat2, filt, sttable) {}
DifferenceFstOptions() {}
};
// Computes the difference between two FSAs. This version is a delayed
// Fst. Only strings that are in the first automaton but not in second
// are retained in the result.
//
// The first argument must be an acceptor; the second argument must be
// an unweighted, epsilon-free, deterministic acceptor. One of the
// arguments must be label-sorted.
//
// Complexity: same as ComposeFst.
//
// Caveats: same as ComposeFst.
template <class A>
class DifferenceFst : public ComposeFst<A> {
public:
using ComposeFst<A>::CreateBase1;
typedef A Arc;
typedef typename A::Weight Weight;
typedef typename A::StateId StateId;
// A - B = A ^ B'.
DifferenceFst(const Fst<A> &fst1, const Fst<A> &fst2,
const CacheOptions &opts = CacheOptions())
: ComposeFst<A>(CreateDifferenceImplWithCacheOpts(fst1, fst2, opts)) {
if (!fst1.Properties(kAcceptor, true)) {
FSTERROR() << "DifferenceFst: 1st argument not an acceptor";
GetImpl()->SetProperties(kError, kError);
}
}
template <class M, class F, class T>
DifferenceFst(const Fst<A> &fst1, const Fst<A> &fst2,
const DifferenceFstOptions<A, M, F, T> &opts)
: ComposeFst<A>(
CreateDifferenceImplWithDifferenceOpts(fst1, fst2, opts)) {
if (!fst1.Properties(kAcceptor, true)) {
FSTERROR() << "DifferenceFst: 1st argument not an acceptor";
GetImpl()->SetProperties(kError, kError);
}
}
// See Fst<>::Copy() for doc.
DifferenceFst(const DifferenceFst<A> &fst, bool safe = false)
: ComposeFst<A>(fst, safe) {}
// Get a copy of this DifferenceFst. See Fst<>::Copy() for further doc.
DifferenceFst<A> *Copy(bool safe = false) const override {
return new DifferenceFst<A>(*this, safe);
}
private:
using Impl = ComposeFstImplBase<A>;
using ImplToFst<Impl>::GetImpl;
static std::shared_ptr<Impl> CreateDifferenceImplWithCacheOpts(
const Fst<A> &fst1, const Fst<A> &fst2, const CacheOptions &opts) {
typedef RhoMatcher<Matcher<Fst<A>>> R;
ComplementFst<A> cfst(fst2);
ComposeFstOptions<A, R> copts(
CacheOptions(), new R(fst1, MATCH_NONE),
new R(cfst, MATCH_INPUT, ComplementFst<A>::kRhoLabel));
return CreateBase1(fst1, cfst, copts);
}
template <class M, class F, class T>
static std::shared_ptr<Impl> CreateDifferenceImplWithDifferenceOpts(
const Fst<A> &fst1, const Fst<A> &fst2,
const DifferenceFstOptions<A, M, F, T> &opts) {
typedef RhoMatcher<M> R;
ComplementFst<A> cfst(fst2);
ComposeFstOptions<A, R> copts(opts);
copts.matcher1 = new R(fst1, MATCH_NONE, kNoLabel, MATCHER_REWRITE_ALWAYS,
opts.matcher1);
copts.matcher2 = new R(cfst, MATCH_INPUT, ComplementFst<A>::kRhoLabel,
MATCHER_REWRITE_ALWAYS, opts.matcher2);
return CreateBase1(fst1, cfst, copts);
}
};
// Specialization for DifferenceFst.
template <class A>
class StateIterator<DifferenceFst<A>> : public StateIterator<ComposeFst<A>> {
public:
explicit StateIterator(const DifferenceFst<A> &fst)
: StateIterator<ComposeFst<A>>(fst) {}
};
// Specialization for DifferenceFst.
template <class A>
class ArcIterator<DifferenceFst<A>> : public ArcIterator<ComposeFst<A>> {
public:
typedef typename A::StateId StateId;
ArcIterator(const DifferenceFst<A> &fst, StateId s)
: ArcIterator<ComposeFst<A>>(fst, s) {}
};
// Useful alias when using StdArc.
typedef DifferenceFst<StdArc> StdDifferenceFst;
typedef ComposeOptions DifferenceOptions;
// Computes the difference between two FSAs. This version is writes
// the difference to an output MutableFst. Only strings that are in
// the first automaton but not in second are retained in the result.
//
// The first argument must be an acceptor; the second argument must be
// an unweighted, epsilon-free, deterministic acceptor. One of the
// arguments must be label-sorted.
//
// Complexity: same as Compose.
//
// Caveats: same as Compose.
template <class Arc>
void Difference(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
MutableFst<Arc> *ofst,
const DifferenceOptions &opts = DifferenceOptions()) {
typedef Matcher<Fst<Arc>> M;
if (opts.filter_type == AUTO_FILTER) {
CacheOptions nopts;
nopts.gc_limit = 0; // Cache only the last state for fastest copy.
*ofst = DifferenceFst<Arc>(ifst1, ifst2, nopts);
} else if (opts.filter_type == SEQUENCE_FILTER) {
DifferenceFstOptions<Arc> dopts;
dopts.gc_limit = 0; // Cache only the last state for fastest copy.
*ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
} else if (opts.filter_type == ALT_SEQUENCE_FILTER) {
DifferenceFstOptions<Arc, M, AltSequenceComposeFilter<M>> dopts;
dopts.gc_limit = 0; // Cache only the last state for fastest copy.
*ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
} else if (opts.filter_type == MATCH_FILTER) {
DifferenceFstOptions<Arc, M, MatchComposeFilter<M>> dopts;
dopts.gc_limit = 0; // Cache only the last state for fastest copy.
*ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
}
if (opts.connect) Connect(ofst);
}
} // namespace fst
#endif // FST_LIB_DIFFERENCE_H_
|