epsilon-property-inl.h
Go to the documentation of this file.
1 // fstext/epsilon-property-inl.h
2 
3 // Copyright 2014 Johns Hopkins University (Author: Daniel Povey)
4 
5 // See ../../COPYING for clarification regarding multiple authors
6 //
7 // Licensed under the Apache License, Version 2.0 (the "License");
8 // you may not use this file except in compliance with the License.
9 // You may obtain a copy of the License at
10 //
11 // http://www.apache.org/licenses/LICENSE-2.0
12 //
13 // THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14 // KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
15 // WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
16 // MERCHANTABLITY OR NON-INFRINGEMENT.
17 // See the Apache 2 License for the specific language governing permissions and
18 // limitations under the License.
19 
20 #ifndef KALDI_FSTEXT_EPSILON_PROPERTY_INL_H_
21 #define KALDI_FSTEXT_EPSILON_PROPERTY_INL_H_
22 
23 namespace fst {
24 
25 
26 
27 template<class Arc>
28 void ComputeStateInfo(const VectorFst<Arc> &fst,
29  std::vector<char> *epsilon_info) {
30  typedef typename Arc::StateId StateId;
31  typedef VectorFst<Arc> Fst;
32  epsilon_info->clear();
33  epsilon_info->resize(fst.NumStates(), static_cast<char>(0));
34  for (StateId s = 0; s < fst.NumStates(); s++) {
35  for (ArcIterator<Fst> aiter(fst, s); !aiter.Done(); aiter.Next()) {
36  const Arc &arc = aiter.Value();
37  if (arc.ilabel == 0 && arc.olabel == 0) {
38  (*epsilon_info)[arc.nextstate] |= static_cast<char>(kStateHasEpsilonArcsEntering);
39  (*epsilon_info)[s] |= static_cast<char>(kStateHasEpsilonArcsLeaving);
40  } else {
41  (*epsilon_info)[arc.nextstate] |= static_cast<char>(kStateHasNonEpsilonArcsEntering);
42  (*epsilon_info)[s] |= static_cast<char>(kStateHasNonEpsilonArcsLeaving);
43  }
44  }
45  }
46 }
47 
48 template<class Arc>
49 void EnsureEpsilonProperty(VectorFst<Arc> *fst) {
50 
51  typedef typename Arc::StateId StateId;
52  typedef typename Arc::Weight Weight;
53  typedef VectorFst<Arc> Fst;
54  std::vector<char> epsilon_info;
55  ComputeStateInfo(*fst, &epsilon_info);
56 
57 
58  StateId num_states_old = fst->NumStates();
59  StateId non_coaccessible_state = fst->AddState();
60 
65  std::vector<StateId> new_state_vec(num_states_old, kNoStateId);
66  for (StateId s = 0; s < num_states_old; s++) {
67  if ((epsilon_info[s] & kStateHasEpsilonArcsEntering) != 0 &&
68  (epsilon_info[s] & kStateHasNonEpsilonArcsEntering) != 0) {
69  assert(s != fst->Start()); // a type of cyclic FST we can't handle
70  // easily.
71  StateId new_state = fst->AddState();
72  new_state_vec[s] = new_state;
73  fst->AddArc(new_state, Arc(0, 0, Weight::One(), s));
74  }
75  }
76 
79  for (StateId s = 0; s < num_states_old; s++) {
80  for (MutableArcIterator<Fst> aiter(fst, s);
81  !aiter.Done(); aiter.Next()) {
82  Arc arc = aiter.Value();
83  if (arc.ilabel != 0 || arc.olabel != 0) { // non-epsilon arc
84  StateId replacement_state;
85  if (arc.nextstate >= 0 && arc.nextstate < num_states_old &&
86  (replacement_state = new_state_vec[arc.nextstate]) !=
87  kNoStateId) {
88  arc.nextstate = replacement_state;
89  aiter.SetValue(arc);
90  }
91  }
92  }
93  }
94 
97  for (StateId s = 0; s < num_states_old; s++) {
98  if ((epsilon_info[s] & kStateHasEpsilonArcsLeaving) != 0 &&
99  (epsilon_info[s] & kStateHasNonEpsilonArcsLeaving) != 0) {
100  // state has non-epsilon and epsilon arcs leaving.
101  // create a new state and move the non-epsilon arcs to leave
102  // from there instead.
103  StateId new_state = fst->AddState();
104  for (MutableArcIterator<Fst> aiter(fst, s); !aiter.Done();
105  aiter.Next()) {
106  Arc arc = aiter.Value();
107  if (arc.ilabel != 0 || arc.olabel != 0) { // non-epsilon arc.
108  assert(arc.nextstate != s); // we don't handle cyclic FSTs.
109  // move this arc to leave from the new state:
110  fst->AddArc(new_state, arc);
111  arc.nextstate = non_coaccessible_state;
112  aiter.SetValue(arc); // invalidate the arc, Connect() will remove it.
113  }
114  }
115  // Create an epsilon arc to the new state.
116  fst->AddArc(s, Arc(0, 0, Weight::One(), new_state));
117  }
118  }
119  Connect(fst); // Removes arcs to the non-coaccessible state.
120 }
121 
122 
123 
124 } // namespace fst.
125 
126 #endif
fst::StdArc::StateId StateId
void EnsureEpsilonProperty(VectorFst< Arc > *fst)
This function modifies the fst (while maintaining equivalence) in such a way that, after the modification, all states of the FST which have epsilon-arcs entering them, have no non-epsilon arcs entering them, and all states which have epsilon-arcs leaving them, have no non-epsilon arcs leaving them.
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
void ComputeStateInfo(const VectorFst< Arc > &fst, std::vector< char > *epsilon_info)
This function will set epsilon_info to have size equal to the NumStates() of the FST, containing a logical-or of the enum values kStateHasEpsilonArcsEntering, kStateHasNonEpsilonArcsEntering, kStateHasEpsilonArcsLeaving, and kStateHasNonEpsilonArcsLeaving.
fst::StdArc::Weight Weight