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
|
// statesort.h
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
//
// \file
// Function to sort states of an Fst.
#ifndef FST_LIB_STATESORT_H__
#define FST_LIB_STATESORT_H__
#include <algorithm>
#include "fst/lib/mutable-fst.h"
namespace fst {
// Sorts the input states of an FST, modifying it. ORDER[i] gives the
// the state Id after sorting that corresponds to state Id i before
// sorting. ORDER must be a permutation of FST's states ID sequence:
// (1, 2, ..., fst->NumStates() - 1).
template <class Arc>
void StateSort(MutableFst<Arc> *fst,
const vector<typename Arc::StateId> &order) {
typedef typename Arc::StateId StateId;
typedef typename Arc::Weight Weight;
CHECK_EQ(order.size(), fst->NumStates());
if (fst->Start() == kNoStateId)
return;
uint64 props = fst->Properties(kStateSortProperties, false);
vector<bool> done(order.size(), false);
vector<Arc> arcsa, arcsb;
vector<Arc> *arcs1 = &arcsa, *arcs2 = &arcsb;
fst->SetStart(order[fst->Start()]);
for (StateIterator< MutableFst<Arc> > siter(*fst);
!siter.Done();
siter.Next()) {
StateId s1 = siter.Value(), s2;
if (done[s1])
continue;
Weight final1 = fst->Final(s1), final2 = Weight::Zero();
arcs1->clear();
for (ArcIterator< MutableFst<Arc> > aiter(*fst, s1);
!aiter.Done();
aiter.Next())
arcs1->push_back(aiter.Value());
for (; !done[s1]; s1 = s2, final1 = final2, swap(arcs1, arcs2)) {
s2 = order[s1];
if (!done[s2]) {
final2 = fst->Final(s2);
arcs2->clear();
for (ArcIterator< MutableFst<Arc> > aiter(*fst, s2);
!aiter.Done();
aiter.Next())
arcs2->push_back(aiter.Value());
}
fst->SetFinal(s2, final1);
fst->DeleteArcs(s2);
for (size_t i = 0; i < arcs1->size(); ++i) {
Arc arc = (*arcs1)[i];
arc.nextstate = order[arc.nextstate];
fst->AddArc(s2, arc);
}
done[s1] = true;
}
}
fst->SetProperties(props, kFstProperties);
}
} // namespace fst
#endif // FST_LIB_STATESORT_H__
|
