Blame view
src/fstext/epsilon-property-inl.h
4.63 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 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
|