/usr/include/fst/closure.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 | // See www.openfst.org for extensive documentation on this weighted
// finite-state transducer library.
//
// Functions and classes to compute the concatenative closure of an FST.
#ifndef FST_LIB_CLOSURE_H_
#define FST_LIB_CLOSURE_H_
#include <algorithm>
#include <vector>
#include <fst/mutable-fst.h>
#include <fst/rational.h>
namespace fst {
// Computes the concatenative closure. This version modifies its
// MutableFst input. If an FST transduces string x to y with weight a,
// then its closure transduces x to y with weight a, xx to yy with
// weight Times(a, a), xxx to yyy with with Times(Times(a, a), a),
// etc. If closure_type == CLOSURE_STAR, then the empty string is
// transduced to itself with weight Weight::One() as well.
//
// Complexity:
//
// Time: O(V)
// Space: O(V)
//
// where V is the number of states.
template <class Arc>
void Closure(MutableFst<Arc> *fst, ClosureType closure_type) {
using Label = typename Arc::Label;
using StateId = typename Arc::StateId;
using Weight = typename Arc::Weight;
const auto props = fst->Properties(kFstProperties, false);
const auto start = fst->Start();
for (StateIterator<MutableFst<Arc>> siter(*fst); !siter.Done();
siter.Next()) {
const auto s = siter.Value();
const auto weight = fst->Final(s);
if (weight != Weight::Zero()) fst->AddArc(s, Arc(0, 0, weight, start));
}
if (closure_type == CLOSURE_STAR) {
fst->ReserveStates(fst->NumStates() + 1);
const auto nstart = fst->AddState();
fst->SetStart(nstart);
fst->SetFinal(nstart, Weight::One());
if (start != kNoLabel) fst->AddArc(nstart, Arc(0, 0, Weight::One(), start));
}
fst->SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR),
kFstProperties);
}
// Computes the concatenative closure. This version modifies its
// RationalFst input.
template <class Arc>
void Closure(RationalFst<Arc> *fst, ClosureType closure_type) {
fst->GetMutableImpl()->AddClosure(closure_type);
}
struct ClosureFstOptions : RationalFstOptions {
ClosureType type;
ClosureFstOptions(const RationalFstOptions &opts,
ClosureType type = CLOSURE_STAR)
: RationalFstOptions(opts), type(type) {}
explicit ClosureFstOptions(ClosureType type = CLOSURE_STAR) : type(type) {}
};
// Computes the concatenative closure. This version is a delayed FST. If an FST
// transduces string x to y with weight a, then its closure transduces x to y
// with weight a, xx to yy with weight Times(a, a), xxx to yyy with weight
// Times(Times(a, a), a), etc. If closure_type == CLOSURE_STAR, then the empty
// string is transduced to itself with weight Weight::One() as well.
//
// Complexity:
//
// Time: O(v)
// Space: O(v)
//
// where v is the number of states visited. Constant time and space to visit an
// input state or arc is assumed and exclusive of caching.
template <class A>
class ClosureFst : public RationalFst<A> {
public:
using Arc = A;
ClosureFst(const Fst<Arc> &fst, ClosureType closure_type) {
GetMutableImpl()->InitClosure(fst, closure_type);
}
ClosureFst(const Fst<Arc> &fst, const ClosureFstOptions &opts)
: RationalFst<A>(opts) {
GetMutableImpl()->InitClosure(fst, opts.type);
}
// See Fst<>::Copy() for doc.
ClosureFst(const ClosureFst<Arc> &fst, bool safe = false)
: RationalFst<A>(fst, safe) {}
// Gets a copy of this ClosureFst. See Fst<>::Copy() for further doc.
ClosureFst<A> *Copy(bool safe = false) const override {
return new ClosureFst<A>(*this, safe);
}
private:
using ImplToFst<internal::RationalFstImpl<Arc>>::GetImpl;
using ImplToFst<internal::RationalFstImpl<Arc>>::GetMutableImpl;
};
// Specialization for ClosureFst.
template <class Arc>
class StateIterator<ClosureFst<Arc>> : public StateIterator<RationalFst<Arc>> {
public:
explicit StateIterator(const ClosureFst<Arc> &fst)
: StateIterator<RationalFst<Arc>>(fst) {}
};
// Specialization for ClosureFst.
template <class Arc>
class ArcIterator<ClosureFst<Arc>> : public ArcIterator<RationalFst<Arc>> {
public:
using StateId = typename Arc::StateId;
ArcIterator(const ClosureFst<Arc> &fst, StateId s)
: ArcIterator<RationalFst<Arc>>(fst, s) {}
};
// Useful alias when using StdArc.
using StdClosureFst = ClosureFst<StdArc>;
} // namespace fst
#endif // FST_LIB_CLOSURE_H_
|