statesort.h
2.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
// See www.openfst.org for extensive documentation on this weighted
// finite-state transducer library.
//
// Function to sort states of an FST.
#ifndef FST_STATESORT_H_
#define FST_STATESORT_H_
#include <algorithm>
#include <vector>
#include <fst/log.h>
#include <fst/mutable-fst.h>
namespace fst {
// Sorts the input states of an FST. order[i] gives the the state ID after
// sorting that corresponds to the state ID i before sorting; it must
// therefore be a permutation of the input FST's states ID sequence.
template <class Arc>
void StateSort(MutableFst<Arc> *fst,
const std::vector<typename Arc::StateId> &order) {
using StateId = typename Arc::StateId;
using Weight = typename Arc::Weight;
if (order.size() != fst->NumStates()) {
FSTERROR() << "StateSort: Bad order vector size: " << order.size();
fst->SetProperties(kError, kError);
return;
}
if (fst->Start() == kNoStateId) return;
const auto props = fst->Properties(kStateSortProperties, false);
std::vector<bool> done(order.size(), false);
std::vector<Arc> arcsa;
std::vector<Arc> arcsb;
fst->SetStart(order[fst->Start()]);
for (StateIterator<MutableFst<Arc>> siter(*fst); !siter.Done();
siter.Next()) {
auto s1 = siter.Value();
StateId s2;
if (done[s1]) continue;
auto final1 = fst->Final(s1);
auto final2 = Weight::Zero();
arcsa.clear();
for (ArcIterator<MutableFst<Arc>> aiter(*fst, s1); !aiter.Done();
aiter.Next()) {
arcsa.push_back(aiter.Value());
}
for (; !done[s1]; s1 = s2, final1 = final2, std::swap(arcsa, arcsb)) {
s2 = order[s1];
if (!done[s2]) {
final2 = fst->Final(s2);
arcsb.clear();
for (ArcIterator<MutableFst<Arc>> aiter(*fst, s2); !aiter.Done();
aiter.Next()) {
arcsb.push_back(aiter.Value());
}
}
fst->SetFinal(s2, final1);
fst->DeleteArcs(s2);
for (auto arc : arcsa) { // Copy intended.
arc.nextstate = order[arc.nextstate];
fst->AddArc(s2, arc);
}
done[s1] = true;
}
}
fst->SetProperties(props, kFstProperties);
}
} // namespace fst
#endif // FST_STATESORT_H_