/usr/include/fst/push.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 | // See www.openfst.org for extensive documentation on this weighted
// finite-state transducer library.
//
// Class to reweight/push an FST, and utility functions to weigh and reweight
// an FST.
#ifndef FST_LIB_PUSH_H_
#define FST_LIB_PUSH_H_
#include <vector>
#include <fst/arc-map.h>
#include <fst/factor-weight.h>
#include <fst/fst.h>
#include <fst/reweight.h>
#include <fst/shortest-distance.h>
namespace fst {
// Compute the total weight (sum of the weights of all accepting paths) from
// the output of ShortestDistance. 'distance' is the shortest distance from the
// initial state when 'reverse == false' and to the final states when
// 'reverse == true'.
template <class Arc>
typename Arc::Weight ComputeTotalWeight(
const Fst<Arc> &fst, const std::vector<typename Arc::Weight> &distance,
bool reverse) {
if (reverse)
return fst.Start() < distance.size() ? distance[fst.Start()]
: Arc::Weight::Zero();
typename Arc::Weight sum = Arc::Weight::Zero();
for (typename Arc::StateId s = 0; s < distance.size(); ++s)
sum = Plus(sum, Times(distance[s], fst.Final(s)));
return sum;
}
// Divide the weight of every accepting path by 'w'. The weight 'w' is
// divided at the final states if 'at_final == true' and at the
// initial state otherwise.
template <class Arc>
void RemoveWeight(MutableFst<Arc> *fst, typename Arc::Weight w, bool at_final) {
if ((w == Arc::Weight::One()) || (w == Arc::Weight::Zero())) return;
if (at_final) {
// Remove 'w' from the final states
for (StateIterator<MutableFst<Arc>> sit(*fst); !sit.Done(); sit.Next())
fst->SetFinal(sit.Value(),
Divide(fst->Final(sit.Value()), w, DIVIDE_RIGHT));
} else { // at_final == false
// Remove 'w' from the initial state
typename Arc::StateId start = fst->Start();
for (MutableArcIterator<MutableFst<Arc>> ait(fst, start); !ait.Done();
ait.Next()) {
Arc arc = ait.Value();
arc.weight = Divide(arc.weight, w, DIVIDE_LEFT);
ait.SetValue(arc);
}
fst->SetFinal(start, Divide(fst->Final(start), w, DIVIDE_LEFT));
}
}
// Pushes the weights in FST in the direction defined by TYPE. If
// pushing towards the initial state, the sum of the weight of the
// outgoing transitions and final weight at a non-initial state is
// equal to One() in the resulting machine. If pushing towards the
// final state, the same property holds on the reverse machine.
//
// Weight needs to be left distributive when pushing towards the
// initial state and right distributive when pushing towards the final
// states.
template <class Arc>
void Push(MutableFst<Arc> *fst, ReweightType type, float delta = kDelta,
bool remove_total_weight = false) {
std::vector<typename Arc::Weight> distance;
ShortestDistance(*fst, &distance, type == REWEIGHT_TO_INITIAL, delta);
typename Arc::Weight total_weight = Arc::Weight::One();
if (remove_total_weight)
total_weight =
ComputeTotalWeight(*fst, distance, type == REWEIGHT_TO_INITIAL);
Reweight(fst, distance, type);
if (remove_total_weight)
RemoveWeight(fst, total_weight, type == REWEIGHT_TO_FINAL);
}
const uint32 kPushWeights = 0x0001;
const uint32 kPushLabels = 0x0002;
const uint32 kPushRemoveTotalWeight = 0x0004;
const uint32 kPushRemoveCommonAffix = 0x0008;
// OFST obtained from IFST by pushing weights and/or labels according
// to PTYPE in the direction defined by RTYPE. Weight needs to be
// left distributive when pushing weights towards the initial state
// and right distributive when pushing weights towards the final
// states.
template <class Arc, ReweightType rtype>
void Push(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, uint32 ptype,
float delta = kDelta) {
if ((ptype & (kPushWeights | kPushLabels)) == kPushWeights) {
*ofst = ifst;
Push(ofst, rtype, delta, ptype & kPushRemoveTotalWeight);
} else if (ptype & kPushLabels) {
const GallicType gtype =
rtype == REWEIGHT_TO_INITIAL ? GALLIC_LEFT : GALLIC_RIGHT;
std::vector<typename GallicArc<Arc, gtype>::Weight> gdistance;
VectorFst<GallicArc<Arc, gtype>> gfst;
ArcMap(ifst, &gfst, ToGallicMapper<Arc, gtype>());
if (ptype & kPushWeights) {
ShortestDistance(gfst, &gdistance, rtype == REWEIGHT_TO_INITIAL, delta);
} else {
ArcMapFst<Arc, Arc, RmWeightMapper<Arc>> uwfst(ifst,
RmWeightMapper<Arc>());
ArcMapFst<Arc, GallicArc<Arc, gtype>, ToGallicMapper<Arc, gtype>> guwfst(
uwfst, ToGallicMapper<Arc, gtype>());
ShortestDistance(guwfst, &gdistance, rtype == REWEIGHT_TO_INITIAL, delta);
}
typename GallicArc<Arc, gtype>::Weight total_weight =
GallicArc<Arc, gtype>::Weight::One();
if (ptype & (kPushRemoveTotalWeight | kPushRemoveCommonAffix)) {
total_weight =
ComputeTotalWeight(gfst, gdistance, rtype == REWEIGHT_TO_INITIAL);
total_weight = typename GallicArc<Arc, gtype>::Weight(
ptype & kPushRemoveCommonAffix
? total_weight.Value1()
: StringWeight<typename Arc::Label,
GALLIC_STRING_TYPE(gtype)>::One(),
ptype & kPushRemoveTotalWeight ? total_weight.Value2()
: Arc::Weight::One());
}
Reweight(&gfst, gdistance, rtype);
if (ptype & (kPushRemoveTotalWeight | kPushRemoveCommonAffix))
RemoveWeight(&gfst, total_weight, rtype == REWEIGHT_TO_FINAL);
FactorWeightFst<GallicArc<Arc, gtype>,
GallicFactor<typename Arc::Label, typename Arc::Weight,
gtype>> fwfst(gfst);
ArcMap(fwfst, ofst, FromGallicMapper<Arc, gtype>());
ofst->SetOutputSymbols(ifst.OutputSymbols());
} else {
LOG(WARNING) << "Push: pushing type is set to 0: "
<< "pushing neither labels nor weights.";
*ofst = ifst;
}
}
} // namespace fst
#endif /* FST_LIB_PUSH_H_ */
|