hmm-topology.cc
Go to the documentation of this file.
1 // hmm/hmm-topology.cc
2 
3 // Copyright 2009-2011 Microsoft Corporation
4 // 2014 Johns Hopkins University (author: Daniel Povey)
5 
6 // See ../../COPYING for clarification regarding multiple authors
7 //
8 // Licensed under the Apache License, Version 2.0 (the "License");
9 // you may not use this file except in compliance with the License.
10 // You may obtain a copy of the License at
11 //
12 // http://www.apache.org/licenses/LICENSE-2.0
13 //
14 // THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 // KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
16 // WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
17 // MERCHANTABLITY OR NON-INFRINGEMENT.
18 // See the Apache 2 License for the specific language governing permissions and
19 // limitations under the License.
20 
21 #include <vector>
22 
23 #include "hmm/hmm-topology.h"
24 #include "util/text-utils.h"
25 
26 
27 namespace kaldi {
28 
29 
30 
31 void HmmTopology::GetPhoneToNumPdfClasses(std::vector<int32> *phone2num_pdf_classes) const {
32  KALDI_ASSERT(!phones_.empty());
33  phone2num_pdf_classes->clear();
34  phone2num_pdf_classes->resize(phones_.back() + 1, -1);
35  for (size_t i = 0; i < phones_.size(); i++)
36  (*phone2num_pdf_classes)[phones_[i]] = NumPdfClasses(phones_[i]);
37 }
38 
39 void HmmTopology::Read(std::istream &is, bool binary) {
40  ExpectToken(is, binary, "<Topology>");
41  if (!binary) { // Text-mode read, different "human-readable" format.
42  phones_.clear();
43  phone2idx_.clear();
44  entries_.clear();
45  std::string token;
46  while ( ! (is >> token).fail() ) {
47  if (token == "</Topology>") { break; } // finished parsing.
48  else if (token != "<TopologyEntry>") {
49  KALDI_ERR << "Reading HmmTopology object, expected </Topology> or <TopologyEntry>, got "<<token;
50  } else {
51  ExpectToken(is, binary, "<ForPhones>");
52  std::vector<int32> phones;
53  std::string s;
54  while (1) {
55  is >> s;
56  if (is.fail()) KALDI_ERR << "Reading HmmTopology object, unexpected end of file while expecting phones.";
57  if (s == "</ForPhones>") break;
58  else {
59  int32 phone;
60  if (!ConvertStringToInteger(s, &phone))
61  KALDI_ERR << "Reading HmmTopology object, expected "
62  << "integer, got instead " << s;
63  phones.push_back(phone);
64  }
65  }
66 
67  std::vector<HmmState> this_entry;
68  std::string token;
69  ReadToken(is, binary, &token);
70  while (token != "</TopologyEntry>") {
71  if (token != "<State>")
72  KALDI_ERR << "Expected </TopologyEntry> or <State>, got instead " << token;
73  int32 state;
74  ReadBasicType(is, binary, &state);
75  if (state != static_cast<int32>(this_entry.size()))
76  KALDI_ERR << "States are expected to be in order from zero, expected "
77  << this_entry.size() << ", got " << state;
78  ReadToken(is, binary, &token);
79  int32 forward_pdf_class = kNoPdf; // -1 by default, means no pdf.
80  if (token == "<PdfClass>") {
81  ReadBasicType(is, binary, &forward_pdf_class);
82  this_entry.push_back(HmmState(forward_pdf_class));
83  ReadToken(is, binary, &token);
84  if (token == "<SelfLoopPdfClass>")
85  KALDI_ERR << "pdf classes should be defined using <PdfClass> "
86  << "or <ForwardPdfClass>/<SelfLoopPdfClass> pair";
87  } else if (token == "<ForwardPdfClass>") {
88  int32 self_loop_pdf_class = kNoPdf;
89  ReadBasicType(is, binary, &forward_pdf_class);
90  ReadToken(is, binary, &token);
91  if (token != "<SelfLoopPdfClass>")
92  KALDI_ERR << "Expected <SelfLoopPdfClass>, got instead " << token;
93  ReadBasicType(is, binary, &self_loop_pdf_class);
94  this_entry.push_back(HmmState(forward_pdf_class, self_loop_pdf_class));
95  ReadToken(is, binary, &token);
96  } else
97  this_entry.push_back(HmmState(forward_pdf_class));
98  while (token == "<Transition>") {
99  int32 dst_state;
100  BaseFloat trans_prob;
101  ReadBasicType(is, binary, &dst_state);
102  ReadBasicType(is, binary, &trans_prob);
103  this_entry.back().transitions.push_back(std::make_pair(dst_state, trans_prob));
104  ReadToken(is, binary, &token);
105  }
106  if (token == "<Final>") // TODO: remove this clause after a while.
107  KALDI_ERR << "You are trying to read old-format topology with new Kaldi.";
108  if (token != "</State>")
109  KALDI_ERR << "Expected </State>, got instead " << token;
110  ReadToken(is, binary, &token);
111  }
112  int32 my_index = entries_.size();
113  entries_.push_back(this_entry);
114 
115  for (size_t i = 0; i < phones.size(); i++) {
116  int32 phone = phones[i];
117  if (static_cast<int32>(phone2idx_.size()) <= phone)
118  phone2idx_.resize(phone+1, -1); // -1 is invalid index.
119  KALDI_ASSERT(phone > 0);
120  if (phone2idx_[phone] != -1)
121  KALDI_ERR << "Phone with index "<<(i)<<" appears in multiple topology entries.";
122  phone2idx_[phone] = my_index;
123  phones_.push_back(phone);
124  }
125  }
126  }
127  std::sort(phones_.begin(), phones_.end());
129  } else { // binary I/O, just read member objects directly from disk.
130  ReadIntegerVector(is, binary, &phones_);
131  ReadIntegerVector(is, binary, &phone2idx_);
132  int32 sz;
133  ReadBasicType(is, binary, &sz);
134  bool is_hmm = true;
135  if (sz == -1) {
136  is_hmm = false;
137  ReadBasicType(is, binary, &sz);
138  }
139  entries_.resize(sz);
140  for (int32 i = 0; i < sz; i++) {
141  int32 thist_sz;
142  ReadBasicType(is, binary, &thist_sz);
143  entries_[i].resize(thist_sz);
144  for (int32 j = 0 ; j < thist_sz; j++) {
145  ReadBasicType(is, binary, &(entries_[i][j].forward_pdf_class));
146  if (is_hmm)
147  entries_[i][j].self_loop_pdf_class = entries_[i][j].forward_pdf_class;
148  else
149  ReadBasicType(is, binary, &(entries_[i][j].self_loop_pdf_class));
150  int32 thiss_sz;
151  ReadBasicType(is, binary, &thiss_sz);
152  entries_[i][j].transitions.resize(thiss_sz);
153  for (int32 k = 0; k < thiss_sz; k++) {
154  ReadBasicType(is, binary, &(entries_[i][j].transitions[k].first));
155  ReadBasicType(is, binary, &(entries_[i][j].transitions[k].second));
156  }
157  }
158  }
159  ExpectToken(is, binary, "</Topology>");
160  }
161  Check(); // Will throw if not ok.
162 }
163 
164 
165 void HmmTopology::Write(std::ostream &os, bool binary) const {
166  bool is_hmm = IsHmm();
167  WriteToken(os, binary, "<Topology>");
168  if (!binary) { // Text-mode write.
169  os << "\n";
170  for (int32 i = 0; i < static_cast<int32> (entries_.size()); i++) {
171  WriteToken(os, binary, "<TopologyEntry>");
172  os << "\n";
173  WriteToken(os, binary, "<ForPhones>");
174  os << "\n";
175  for (size_t j = 0; j < phone2idx_.size(); j++) {
176  if (phone2idx_[j] == i)
177  os << j << " ";
178  }
179  os << "\n";
180  WriteToken(os, binary, "</ForPhones>");
181  os << "\n";
182  for (size_t j = 0; j < entries_[i].size(); j++) {
183  WriteToken(os, binary, "<State>");
184  WriteBasicType(os, binary, static_cast<int32>(j));
185  if (entries_[i][j].forward_pdf_class != kNoPdf) {
186  if (is_hmm) {
187  WriteToken(os, binary, "<PdfClass>");
188  WriteBasicType(os, binary, entries_[i][j].forward_pdf_class);
189  } else {
190  WriteToken(os, binary, "<ForwardPdfClass>");
191  WriteBasicType(os, binary, entries_[i][j].forward_pdf_class);
192  KALDI_ASSERT(entries_[i][j].self_loop_pdf_class != kNoPdf);
193  WriteToken(os, binary, "<SelfLoopPdfClass>");
194  WriteBasicType(os, binary, entries_[i][j].self_loop_pdf_class);
195  }
196  }
197  for (size_t k = 0; k < entries_[i][j].transitions.size(); k++) {
198  WriteToken(os, binary, "<Transition>");
199  WriteBasicType(os, binary, entries_[i][j].transitions[k].first);
200  WriteBasicType(os, binary, entries_[i][j].transitions[k].second);
201  }
202  WriteToken(os, binary, "</State>");
203  os << "\n";
204  }
205  WriteToken(os, binary, "</TopologyEntry>");
206  os << "\n";
207  }
208  } else {
209  WriteIntegerVector(os, binary, phones_);
210  WriteIntegerVector(os, binary, phone2idx_);
211  // -1 is put here as a signal that the object has the new,
212  // extended format with SelfLoopPdfClass
213  if (!is_hmm) WriteBasicType(os, binary, static_cast<int32>(-1));
214  WriteBasicType(os, binary, static_cast<int32>(entries_.size()));
215  for (size_t i = 0; i < entries_.size(); i++) {
216  WriteBasicType(os, binary, static_cast<int32>(entries_[i].size()));
217  for (size_t j = 0; j < entries_[i].size(); j++) {
218  WriteBasicType(os, binary, entries_[i][j].forward_pdf_class);
219  if (!is_hmm) WriteBasicType(os, binary, entries_[i][j].self_loop_pdf_class);
220  WriteBasicType(os, binary, static_cast<int32>(entries_[i][j].transitions.size()));
221  for (size_t k = 0; k < entries_[i][j].transitions.size(); k++) {
222  WriteBasicType(os, binary, entries_[i][j].transitions[k].first);
223  WriteBasicType(os, binary, entries_[i][j].transitions[k].second);
224  }
225  }
226  }
227  }
228  WriteToken(os, binary, "</Topology>");
229  if (!binary) os << "\n";
230 }
231 
233  if (entries_.empty() || phones_.empty() || phone2idx_.empty())
234  KALDI_ERR << "HmmTopology::Check(), empty object.";
235  std::vector<bool> is_seen(entries_.size(), false);
236  for (size_t i = 0; i < phones_.size(); i++) {
237  int32 phone = phones_[i];
238  if (static_cast<size_t>(phone) >= phone2idx_.size() ||
239  static_cast<size_t>(phone2idx_[phone]) >= entries_.size())
240  KALDI_ERR << "HmmTopology::Check(), phone has no valid index.";
241  is_seen[phone2idx_[phone]] = true;
242  }
243  for (size_t i = 0; i < entries_.size(); i++) {
244  if (!is_seen[i])
245  KALDI_ERR << "HmmTopoloy::Check(), entry with no corresponding phones.";
246  int32 num_states = static_cast<int32>(entries_[i].size());
247  if (num_states <= 1)
248  KALDI_ERR << "HmmTopology::Check(), cannot only have one state (i.e., must "
249  "have at least one emitting state).";
250  if (!entries_[i][num_states-1].transitions.empty())
251  KALDI_ERR << "HmmTopology::Check(), last state must have no transitions.";
252  // not sure how necessary this next stipulation is.
253  if (entries_[i][num_states-1].forward_pdf_class != kNoPdf)
254  KALDI_ERR << "HmmTopology::Check(), last state must not be emitting.";
255 
256  std::vector<bool> has_trans_in(num_states, false);
257  std::vector<int32> seen_pdf_classes;
258 
259  for (int32 j = 0; j < num_states; j++) { // j is the state-id.
260  BaseFloat tot_prob = 0.0;
261  if (entries_[i][j].forward_pdf_class != kNoPdf) {
262  seen_pdf_classes.push_back(entries_[i][j].forward_pdf_class);
263  seen_pdf_classes.push_back(entries_[i][j].self_loop_pdf_class);
264  }
265  std::set<int32> seen_transition;
266  for (int32 k = 0;
267  static_cast<size_t>(k) < entries_[i][j].transitions.size();
268  k++) {
269  tot_prob += entries_[i][j].transitions[k].second;
270  if (entries_[i][j].transitions[k].second <= 0.0)
271  KALDI_ERR << "HmmTopology::Check(), negative or zero transition prob.";
272  int32 dst_state = entries_[i][j].transitions[k].first;
273  // The commented code in the next few lines disallows a completely
274  // skippable phone, as this would cause to stop working some mechanisms
275  // that are being built, which enable the creation of phone-level lattices
276  // and rescoring these with a different lexicon and LM.
277  if (dst_state == num_states-1 // && j != 0
278  && entries_[i][j].forward_pdf_class == kNoPdf)
279  KALDI_ERR << "We do not allow any state to be "
280  "nonemitting and have a transition to the final-state (this would "
281  "stop the SplitToPhones function from identifying the last state "
282  "of a phone.";
283  if (dst_state < 0 || dst_state >= num_states)
284  KALDI_ERR << "HmmTopology::Check(), invalid dest state " << (dst_state);
285  if (seen_transition.count(dst_state) != 0)
286  KALDI_ERR << "HmmTopology::Check(), duplicate transition found.";
287  if (dst_state == k) { // self_loop...
288  KALDI_ASSERT(entries_[i][j].self_loop_pdf_class != kNoPdf &&
289  "Nonemitting states cannot have self-loops.");
290  }
291  seen_transition.insert(dst_state);
292  has_trans_in[dst_state] = true;
293  }
294  if (j+1 < num_states) {
295  KALDI_ASSERT(tot_prob > 0.0 && "Non-final state must have transitions out."
296  "(with nonzero probability)");
297  if (fabs(tot_prob - 1.0) > 0.01)
298  KALDI_WARN << "Total probability for state " << j <<
299  " in topology entry is " << tot_prob;
300  } else
301  KALDI_ASSERT(tot_prob == 0.0);
302  }
303  // make sure all but start state have input transitions.
304  for (int32 j = 1; j < num_states; j++)
305  if (!has_trans_in[j])
306  KALDI_ERR << "HmmTopology::Check, state "<<(j)<<" has no input transitions.";
307  SortAndUniq(&seen_pdf_classes);
308  if (seen_pdf_classes.front() != 0 ||
309  seen_pdf_classes.back() != static_cast<int32>(seen_pdf_classes.size()) - 1) {
310  KALDI_ERR << "HmmTopology::Check(), pdf_classes are expected to be "
311  "contiguous and start from zero.";
312  }
313  }
314 }
315 
316 bool HmmTopology::IsHmm() const {
317  const std::vector<int32> &phones = GetPhones();
318  KALDI_ASSERT(!phones.empty());
319  for (size_t i = 0; i < phones.size(); i++) {
320  int32 phone = phones[i];
321  const TopologyEntry &entry = TopologyForPhone(phone);
322  for (int32 j = 0; j < static_cast<int32>(entry.size()); j++) { // for each state...
323  int32 forward_pdf_class = entry[j].forward_pdf_class,
324  self_loop_pdf_class = entry[j].self_loop_pdf_class;
325  if (forward_pdf_class != self_loop_pdf_class)
326  return false;
327  }
328  }
329  return true;
330 }
331 
332 const HmmTopology::TopologyEntry& HmmTopology::TopologyForPhone(int32 phone) const { // Will throw if phone not covered.
333  if (static_cast<size_t>(phone) >= phone2idx_.size() || phone2idx_[phone] == -1) {
334  KALDI_ERR << "TopologyForPhone(), phone "<<(phone)<<" not covered.";
335  }
336  return entries_[phone2idx_[phone]];
337 }
338 
340  // will throw if phone not covered.
341  const TopologyEntry &entry = TopologyForPhone(phone);
342  int32 max_pdf_class = 0;
343  for (size_t i = 0; i < entry.size(); i++) {
344  max_pdf_class = std::max(max_pdf_class, entry[i].forward_pdf_class);
345  max_pdf_class = std::max(max_pdf_class, entry[i].self_loop_pdf_class);
346  }
347  return max_pdf_class+1;
348 }
349 
351  const TopologyEntry &entry = TopologyForPhone(phone);
352  // min_length[state] gives the minimum length for sequences up to and
353  // including that state.
354  std::vector<int32> min_length(entry.size(),
355  std::numeric_limits<int32>::max());
356  KALDI_ASSERT(!entry.empty());
357 
358  min_length[0] = (entry[0].forward_pdf_class == -1 ? 0 : 1);
359  int32 num_states = min_length.size();
360  bool changed = true;
361  while (changed) {
362  changed = false;
363  for (int32 s = 0; s < num_states; s++) {
364  const HmmState &this_state = entry[s];
365  std::vector<std::pair<int32, BaseFloat> >::const_iterator
366  iter = this_state.transitions.begin(),
367  end = this_state.transitions.end();
368  for (; iter != end; ++iter) {
369  int32 next_state = iter->first;
370  KALDI_ASSERT(next_state < num_states);
371  int32 next_state_min_length = min_length[s] +
372  (entry[next_state].forward_pdf_class == -1 ? 0 : 1);
373  if (next_state_min_length < min_length[next_state]) {
374  min_length[next_state] = next_state_min_length;
375  if (next_state < s)
376  changed = true;
377  // the test of 'next_state < s' is an optimization for speed.
378  }
379  }
380  }
381  }
382  KALDI_ASSERT(min_length.back() != std::numeric_limits<int32>::max());
383  // the last state is the final-state.
384  return min_length.back();
385 }
386 
387 } // End namespace kaldi
This code computes Goodness of Pronunciation (GOP) and extracts phone-level pronunciation feature for...
Definition: chain.dox:20
bool ConvertStringToInteger(const std::string &str, Int *out)
Converts a string into an integer via strtoll and returns false if there was any kind of problem (i...
Definition: text-utils.h:118
A structure defined inside HmmTopology to represent a HMM state.
Definition: hmm-topology.h:96
bool IsHmm() const
Returns true if this HmmTopology is really &#39;hmm-like&#39;, i.e.
void ReadBasicType(std::istream &is, bool binary, T *t)
ReadBasicType is the name of the read function for bool, integer types, and floating-point types...
Definition: io-funcs-inl.h:55
kaldi::int32 int32
void ReadToken(std::istream &is, bool binary, std::string *str)
ReadToken gets the next token and puts it in str (exception on failure).
Definition: io-funcs.cc:154
void Read(std::istream &is, bool binary)
Definition: hmm-topology.cc:39
std::vector< HmmState > TopologyEntry
TopologyEntry is a typedef that represents the topology of a single (prototype) state.
Definition: hmm-topology.h:133
void SortAndUniq(std::vector< T > *vec)
Sorts and uniq&#39;s (removes duplicates) from a vector.
Definition: stl-utils.h:39
static const int32 kNoPdf
A constant used in the HmmTopology class as the pdf-class kNoPdf, which is used when a HMM-state is n...
Definition: hmm-topology.h:86
std::vector< int32 > phones_
Definition: hmm-topology.h:182
int32 NumPdfClasses(int32 phone) const
Returns the number of pdf-classes for this phone; throws exception if phone not covered by this topol...
void Write(std::ostream &os, bool binary) const
void ReadIntegerVector(std::istream &is, bool binary, std::vector< T > *v)
Function for reading STL vector of integer types.
Definition: io-funcs-inl.h:232
void ExpectToken(std::istream &is, bool binary, const char *token)
ExpectToken tries to read in the given token, and throws an exception on failure. ...
Definition: io-funcs.cc:191
const TopologyEntry & TopologyForPhone(int32 phone) const
Returns the topology entry (i.e.
std::vector< std::pair< int32, BaseFloat > > transitions
A list of transitions, indexed by what we call a &#39;transition-index&#39;.
Definition: hmm-topology.h:109
#define KALDI_ERR
Definition: kaldi-error.h:147
std::vector< TopologyEntry > entries_
Definition: hmm-topology.h:184
#define KALDI_WARN
Definition: kaldi-error.h:150
void WriteToken(std::ostream &os, bool binary, const char *token)
The WriteToken functions are for writing nonempty sequences of non-space characters.
Definition: io-funcs.cc:134
const std::vector< int32 > & GetPhones() const
Returns a reference to a sorted, unique list of phones covered by the topology (these phones will be ...
Definition: hmm-topology.h:163
std::vector< int32 > phone2idx_
Definition: hmm-topology.h:183
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:185
void WriteIntegerVector(std::ostream &os, bool binary, const std::vector< T > &v)
Function for writing STL vectors of integer types.
Definition: io-funcs-inl.h:198
void WriteBasicType(std::ostream &os, bool binary, T t)
WriteBasicType is the name of the write function for bool, integer types, and floating-point types...
Definition: io-funcs-inl.h:34
int32 MinLength(int32 phone) const
void GetPhoneToNumPdfClasses(std::vector< int32 > *phone2num_pdf_classes) const
Outputs a vector of int32, indexed by phone, that gives the number of Pdf-classes pdf-classes for the...
Definition: hmm-topology.cc:31
bool IsSortedAndUniq(const std::vector< T > &vec)
Returns true if the vector is sorted and contains each element only once.
Definition: stl-utils.h:63