/usr/include/fst/closure.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 | // 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 FST transduces string x to y with weight a,
// then the 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 = # of states.
template <class Arc>
void Closure(MutableFst<Arc> *fst, ClosureType closure_type) {
typedef typename Arc::StateId StateId;
typedef typename Arc::Label Label;
typedef typename Arc::Weight Weight;
uint64 props = fst->Properties(kFstProperties, false);
StateId start = fst->Start();
for (StateIterator<MutableFst<Arc>> siter(*fst); !siter.Done();
siter.Next()) {
StateId s = siter.Value();
Weight final = fst->Final(s);
if (final != Weight::Zero()) fst->AddArc(s, Arc(0, 0, final, start));
}
if (closure_type == CLOSURE_STAR) {
fst->ReserveStates(fst->NumStates() + 1);
StateId 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 t)
: RationalFstOptions(opts), type(t) {}
explicit ClosureFstOptions(ClosureType t) : type(t) {}
ClosureFstOptions() : type(CLOSURE_STAR) {}
};
// Computes the concatenative closure. This version is a delayed
// Fst. If FST transduces string x to y with weight a, then the
// 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 = # 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:
typedef A Arc;
ClosureFst(const Fst<A> &fst, ClosureType closure_type) {
GetMutableImpl()->InitClosure(fst, closure_type);
}
ClosureFst(const Fst<A> &fst, const ClosureFstOptions &opts)
: RationalFst<A>(opts) {
GetMutableImpl()->InitClosure(fst, opts.type);
}
// See Fst<>::Copy() for doc.
ClosureFst(const ClosureFst<A> &fst, bool safe = false)
: RationalFst<A>(fst, safe) {}
// Get 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<RationalFstImpl<A>>::GetImpl;
using ImplToFst<RationalFstImpl<A>>::GetMutableImpl;
};
// Specialization for ClosureFst.
template <class A>
class StateIterator<ClosureFst<A>> : public StateIterator<RationalFst<A>> {
public:
explicit StateIterator(const ClosureFst<A> &fst)
: StateIterator<RationalFst<A>>(fst) {}
};
// Specialization for ClosureFst.
template <class A>
class ArcIterator<ClosureFst<A>> : public ArcIterator<RationalFst<A>> {
public:
typedef typename A::StateId StateId;
ArcIterator(const ClosureFst<A> &fst, StateId s)
: ArcIterator<RationalFst<A>>(fst, s) {}
};
// Useful alias when using StdArc.
typedef ClosureFst<StdArc> StdClosureFst;
} // namespace fst
#endif // FST_LIB_CLOSURE_H_
|