/usr/include/fst/reverse.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 | // See www.openfst.org for extensive documentation on this weighted
// finite-state transducer library.
//
// Functions and classes to sort arcs in an FST.
#ifndef FST_LIB_REVERSE_H_
#define FST_LIB_REVERSE_H_
#include <algorithm>
#include <vector>
#include <fst/cache.h>
namespace fst {
// Reverses an FST. The reversed result is written to an output mutable FST.
// If A transduces string x to y with weight a, then the reverse of A
// transduces the reverse of x to the reverse of y with weight a.Reverse().
//
// Typically, a = a.Reverse() and an arc is its own reverse (e.g., for
// TropicalWeight or LogWeight). In general, e.g., when the weights only form a
// left or right semiring, the output arc type must match the input arc type
// except having the reversed Weight type.
//
// When require_superinitial is false, a superinitial state is not created in
// the reversed FST iff the input FST has exactly one final state (which becomes
// the initial state of the reversed FST) with a final weight of semiring One,
// or if it does not belong to any cycle. When require_superinitial is true, a
// superinitial state is always created.
template <class FromArc, class ToArc>
void Reverse(const Fst<FromArc> &ifst, MutableFst<ToArc> *ofst,
bool require_superinitial = true) {
using StateId = typename FromArc::StateId;
using FromWeight = typename FromArc::Weight;
using ToWeight = typename ToArc::Weight;
ofst->DeleteStates();
ofst->SetInputSymbols(ifst.InputSymbols());
ofst->SetOutputSymbols(ifst.OutputSymbols());
if (ifst.Properties(kExpanded, false)) {
ofst->ReserveStates(CountStates(ifst) + 1);
}
StateId istart = ifst.Start();
StateId ostart = kNoStateId;
StateId offset = 0;
uint64 dfs_iprops = 0;
uint64 dfs_oprops = 0;
if (!require_superinitial) {
for (StateIterator<Fst<FromArc>> siter(ifst); !siter.Done(); siter.Next()) {
const auto s = siter.Value();
if (ifst.Final(s) == FromWeight::Zero()) continue;
if (ostart != kNoStateId) {
ostart = kNoStateId;
break;
} else {
ostart = s;
}
}
if (ostart != kNoStateId && ifst.Final(ostart) != FromWeight::One()) {
std::vector<StateId> scc;
SccVisitor<FromArc> scc_visitor(&scc, nullptr, nullptr, &dfs_iprops);
DfsVisit(ifst, &scc_visitor);
if (count(scc.begin(), scc.end(), scc[ostart]) > 1) {
ostart = kNoStateId;
} else {
for (ArcIterator<Fst<FromArc>> aiter(ifst, ostart); !aiter.Done();
aiter.Next()) {
if (aiter.Value().nextstate == ostart) {
ostart = kNoStateId;
break;
}
}
}
if (ostart != kNoStateId) dfs_oprops = kInitialAcyclic;
}
}
if (ostart == kNoStateId) { // Super-initial requested or needed.
ostart = ofst->AddState();
offset = 1;
}
for (StateIterator<Fst<FromArc>> siter(ifst); !siter.Done(); siter.Next()) {
const auto is = siter.Value();
const auto os = is + offset;
while (ofst->NumStates() <= os) ofst->AddState();
if (is == istart) ofst->SetFinal(os, ToWeight::One());
const auto weight = ifst.Final(is);
if ((weight != FromWeight::Zero()) && (offset == 1)) {
const ToArc oarc(0, 0, weight.Reverse(), os);
ofst->AddArc(0, oarc);
}
for (ArcIterator<Fst<FromArc>> aiter(ifst, is); !aiter.Done();
aiter.Next()) {
const auto &iarc = aiter.Value();
const auto nos = iarc.nextstate + offset;
auto weight = iarc.weight.Reverse();
if (!offset && (nos == ostart)) {
weight = Times(ifst.Final(ostart).Reverse(), weight);
}
const ToArc oarc(iarc.ilabel, iarc.olabel, weight, os);
while (ofst->NumStates() <= nos) ofst->AddState();
ofst->AddArc(nos, oarc);
}
}
ofst->SetStart(ostart);
if (offset == 0 && ostart == istart) {
ofst->SetFinal(ostart, ifst.Final(ostart).Reverse());
}
const auto iprops = ifst.Properties(kCopyProperties, false) | dfs_iprops;
const auto oprops = ofst->Properties(kFstProperties, false) | dfs_oprops;
ofst->SetProperties(ReverseProperties(iprops, offset == 1) | oprops,
kFstProperties);
}
} // namespace fst
#endif // FST_LIB_REVERSE_H_
|