epsilon-property-inl.h
4.63 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
117
118
119
120
121
122
123
124
125
126
// fstext/epsilon-property-inl.h
// Copyright 2014 Johns Hopkins University (Author: Daniel Povey)
// See ../../COPYING for clarification regarding multiple authors
//
// 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
//
// THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
// WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
// MERCHANTABLITY OR NON-INFRINGEMENT.
// See the Apache 2 License for the specific language governing permissions and
// limitations under the License.
#ifndef KALDI_FSTEXT_EPSILON_PROPERTY_INL_H_
#define KALDI_FSTEXT_EPSILON_PROPERTY_INL_H_
namespace fst {
template<class Arc>
void ComputeStateInfo(const VectorFst<Arc> &fst,
std::vector<char> *epsilon_info) {
typedef typename Arc::StateId StateId;
typedef VectorFst<Arc> Fst;
epsilon_info->clear();
epsilon_info->resize(fst.NumStates(), static_cast<char>(0));
for (StateId s = 0; s < fst.NumStates(); s++) {
for (ArcIterator<Fst> aiter(fst, s); !aiter.Done(); aiter.Next()) {
const Arc &arc = aiter.Value();
if (arc.ilabel == 0 && arc.olabel == 0) {
(*epsilon_info)[arc.nextstate] |= static_cast<char>(kStateHasEpsilonArcsEntering);
(*epsilon_info)[s] |= static_cast<char>(kStateHasEpsilonArcsLeaving);
} else {
(*epsilon_info)[arc.nextstate] |= static_cast<char>(kStateHasNonEpsilonArcsEntering);
(*epsilon_info)[s] |= static_cast<char>(kStateHasNonEpsilonArcsLeaving);
}
}
}
}
template<class Arc>
void EnsureEpsilonProperty(VectorFst<Arc> *fst) {
typedef typename Arc::StateId StateId;
typedef typename Arc::Weight Weight;
typedef VectorFst<Arc> Fst;
std::vector<char> epsilon_info;
ComputeStateInfo(*fst, &epsilon_info);
StateId num_states_old = fst->NumStates();
StateId non_coaccessible_state = fst->AddState();
/// new_state_vec is for those states that have both epsilon and
/// non-epsilon arcs entering. For these states, we'll create a new
/// state for the non-epsilon arcs to enter and put it in this array,
/// and we'll put an epsilon transition from the new state to the old state.
std::vector<StateId> new_state_vec(num_states_old, kNoStateId);
for (StateId s = 0; s < num_states_old; s++) {
if ((epsilon_info[s] & kStateHasEpsilonArcsEntering) != 0 &&
(epsilon_info[s] & kStateHasNonEpsilonArcsEntering) != 0) {
assert(s != fst->Start()); // a type of cyclic FST we can't handle
// easily.
StateId new_state = fst->AddState();
new_state_vec[s] = new_state;
fst->AddArc(new_state, Arc(0, 0, Weight::One(), s));
}
}
/// First modify arcs to point to states in new_state_vec when
/// necessary.
for (StateId s = 0; s < num_states_old; s++) {
for (MutableArcIterator<Fst> aiter(fst, s);
!aiter.Done(); aiter.Next()) {
Arc arc = aiter.Value();
if (arc.ilabel != 0 || arc.olabel != 0) { // non-epsilon arc
StateId replacement_state;
if (arc.nextstate >= 0 && arc.nextstate < num_states_old &&
(replacement_state = new_state_vec[arc.nextstate]) !=
kNoStateId) {
arc.nextstate = replacement_state;
aiter.SetValue(arc);
}
}
}
}
/// Now handle the situation where states have both epsilon and non-epsilon
/// arcs leaving.
for (StateId s = 0; s < num_states_old; s++) {
if ((epsilon_info[s] & kStateHasEpsilonArcsLeaving) != 0 &&
(epsilon_info[s] & kStateHasNonEpsilonArcsLeaving) != 0) {
// state has non-epsilon and epsilon arcs leaving.
// create a new state and move the non-epsilon arcs to leave
// from there instead.
StateId new_state = fst->AddState();
for (MutableArcIterator<Fst> aiter(fst, s); !aiter.Done();
aiter.Next()) {
Arc arc = aiter.Value();
if (arc.ilabel != 0 || arc.olabel != 0) { // non-epsilon arc.
assert(arc.nextstate != s); // we don't handle cyclic FSTs.
// move this arc to leave from the new state:
fst->AddArc(new_state, arc);
arc.nextstate = non_coaccessible_state;
aiter.SetValue(arc); // invalidate the arc, Connect() will remove it.
}
}
// Create an epsilon arc to the new state.
fst->AddArc(s, Arc(0, 0, Weight::One(), new_state));
}
}
Connect(fst); // Removes arcs to the non-coaccessible state.
}
} // namespace fst.
#endif