Blame view
tools/openfst-1.6.7/src/include/fst/statesort.h
2.14 KB
8dcb6dfcb
first commit
|
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_
|