reverse.h
4.14 KB
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_REVERSE_H_
#define FST_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_REVERSE_H_