All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
SimpleDecoder Class Reference

Simplest possible decoder, included largely for didactic purposes and as a means to debug more highly optimized decoders. More...

#include <simple-decoder.h>

Collaboration diagram for SimpleDecoder:

Classes

class  Token
 

Public Types

typedef fst::StdArc StdArc
 
typedef StdArc::Weight StdWeight
 
typedef StdArc::Label Label
 
typedef StdArc::StateId StateId
 

Public Member Functions

 SimpleDecoder (const fst::Fst< fst::StdArc > &fst, BaseFloat beam)
 
 ~SimpleDecoder ()
 
bool Decode (DecodableInterface *decodable)
 Decode this utterance. More...
 
bool ReachedFinal () const
 
bool GetBestPath (Lattice *fst_out, bool use_final_probs=true) const
 
BaseFloat FinalRelativeCost () const
 *** The next functions are from the "new interface". *** More...
 
void InitDecoding ()
 InitDecoding initializes the decoding, and should only be used if you intend to call AdvanceDecoding(). More...
 
void AdvanceDecoding (DecodableInterface *decodable, int32 max_num_frames=-1)
 This will decode until there are no more frames ready in the decodable object, but if max_num_frames is >= 0 it will decode no more than that many frames. More...
 
int32 NumFramesDecoded () const
 Returns the number of frames already decoded. More...
 

Private Member Functions

void ProcessEmitting (DecodableInterface *decodable)
 
void ProcessNonemitting ()
 
 KALDI_DISALLOW_COPY_AND_ASSIGN (SimpleDecoder)
 

Static Private Member Functions

static void ClearToks (unordered_map< StateId, Token * > &toks)
 
static void PruneToks (BaseFloat beam, unordered_map< StateId, Token * > *toks)
 

Private Attributes

unordered_map< StateId, Token * > cur_toks_
 
unordered_map< StateId, Token * > prev_toks_
 
const fst::Fst< fst::StdArc > & fst_
 
BaseFloat beam_
 
int32 num_frames_decoded_
 

Detailed Description

Simplest possible decoder, included largely for didactic purposes and as a means to debug more highly optimized decoders.

See SimpleDecoder: the simplest possible decoder for more information.

Definition at line 37 of file simple-decoder.h.

Member Typedef Documentation

typedef StdArc::Label Label

Definition at line 41 of file simple-decoder.h.

typedef StdArc::StateId StateId

Definition at line 42 of file simple-decoder.h.

Definition at line 39 of file simple-decoder.h.

typedef StdArc::Weight StdWeight

Definition at line 40 of file simple-decoder.h.

Constructor & Destructor Documentation

SimpleDecoder ( const fst::Fst< fst::StdArc > &  fst,
BaseFloat  beam 
)
inline

Definition at line 44 of file simple-decoder.h.

44 : fst_(fst), beam_(beam) { }
Definition: graph.dox:21
const fst::Fst< fst::StdArc > & fst_

Definition at line 27 of file simple-decoder.cc.

References SimpleDecoder::ClearToks(), SimpleDecoder::cur_toks_, and SimpleDecoder::prev_toks_.

27  {
30 }
unordered_map< StateId, Token * > cur_toks_
unordered_map< StateId, Token * > prev_toks_
static void ClearToks(unordered_map< StateId, Token * > &toks)

Member Function Documentation

void AdvanceDecoding ( DecodableInterface decodable,
int32  max_num_frames = -1 
)

This will decode until there are no more frames ready in the decodable object, but if max_num_frames is >= 0 it will decode no more than that many frames.

If it returns false, then no tokens are alive, which is a kind of error state.

Definition at line 58 of file simple-decoder.cc.

References SimpleDecoder::beam_, SimpleDecoder::ClearToks(), SimpleDecoder::cur_toks_, KALDI_ASSERT, SimpleDecoder::num_frames_decoded_, DecodableInterface::NumFramesReady(), SimpleDecoder::prev_toks_, SimpleDecoder::ProcessEmitting(), SimpleDecoder::ProcessNonemitting(), and SimpleDecoder::PruneToks().

59  {
61  "You must call InitDecoding() before AdvanceDecoding()");
62  int32 num_frames_ready = decodable->NumFramesReady();
63  // num_frames_ready must be >= num_frames_decoded, or else
64  // the number of frames ready must have decreased (which doesn't
65  // make sense) or the decodable object changed between calls
66  // (which isn't allowed).
67  KALDI_ASSERT(num_frames_ready >= num_frames_decoded_);
68  int32 target_frames_decoded = num_frames_ready;
69  if (max_num_frames >= 0)
70  target_frames_decoded = std::min(target_frames_decoded,
71  num_frames_decoded_ + max_num_frames);
72  while (num_frames_decoded_ < target_frames_decoded) {
73  // note: ProcessEmitting() increments num_frames_decoded_
75  cur_toks_.swap(prev_toks_);
76  ProcessEmitting(decodable);
79  }
80 }
void ProcessEmitting(DecodableInterface *decodable)
unordered_map< StateId, Token * > cur_toks_
unordered_map< StateId, Token * > prev_toks_
static void PruneToks(BaseFloat beam, unordered_map< StateId, Token * > *toks)
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
static void ClearToks(unordered_map< StateId, Token * > &toks)
void ClearToks ( unordered_map< StateId, Token * > &  toks)
staticprivate

Definition at line 264 of file simple-decoder.cc.

References SimpleDecoder::Token::TokenDelete().

Referenced by SimpleDecoder::AdvanceDecoding(), SimpleDecoder::Decode(), SimpleDecoder::InitDecoding(), and SimpleDecoder::~SimpleDecoder().

264  {
265  for (unordered_map<StateId, Token*>::iterator iter = toks.begin();
266  iter != toks.end(); ++iter) {
267  Token::TokenDelete(iter->second);
268  }
269  toks.clear();
270 }
static void TokenDelete(Token *tok)
bool Decode ( DecodableInterface decodable)

Decode this utterance.

Returns true if any tokens reached the end of the file (regardless of whether they are in a final state); query ReachedFinal() after Decode() to see whether we reached a final state.

Definition at line 33 of file simple-decoder.cc.

References SimpleDecoder::beam_, SimpleDecoder::ClearToks(), SimpleDecoder::cur_toks_, SimpleDecoder::InitDecoding(), DecodableInterface::IsLastFrame(), SimpleDecoder::num_frames_decoded_, SimpleDecoder::prev_toks_, SimpleDecoder::ProcessEmitting(), SimpleDecoder::ProcessNonemitting(), and SimpleDecoder::PruneToks().

Referenced by main().

33  {
34  InitDecoding();
35  while( !decodable->IsLastFrame(num_frames_decoded_ - 1)) {
37  cur_toks_.swap(prev_toks_);
38  ProcessEmitting(decodable);
41  }
42  return (!cur_toks_.empty());
43 }
void ProcessEmitting(DecodableInterface *decodable)
unordered_map< StateId, Token * > cur_toks_
unordered_map< StateId, Token * > prev_toks_
static void PruneToks(BaseFloat beam, unordered_map< StateId, Token * > *toks)
static void ClearToks(unordered_map< StateId, Token * > &toks)
void InitDecoding()
InitDecoding initializes the decoding, and should only be used if you intend to call AdvanceDecoding(...
BaseFloat FinalRelativeCost ( ) const

*** The next functions are from the "new interface". ***

FinalRelativeCost() serves the same function as ReachedFinal(), but gives more information. It returns the difference between the best (final-cost plus cost) of any token on the final frame, and the best cost of any token on the final frame. If it is infinity it means no final-states were present on the final frame. It will usually be nonnegative.

Definition at line 93 of file simple-decoder.cc.

References SimpleDecoder::cur_toks_, SimpleDecoder::fst_, and KALDI_WARN.

93  {
94  // as a special case, if there are no active tokens at all (e.g. some kind of
95  // pruning failure), return infinity.
96  double infinity = std::numeric_limits<double>::infinity();
97  if (cur_toks_.empty())
98  return infinity;
99  double best_cost = infinity,
100  best_cost_with_final = infinity;
101  for (unordered_map<StateId, Token*>::const_iterator iter = cur_toks_.begin();
102  iter != cur_toks_.end();
103  ++iter) {
104  // Note: Plus is taking the minimum cost, since we're in the tropical
105  // semiring.
106  best_cost = std::min(best_cost, iter->second->cost_);
107  best_cost_with_final = std::min(best_cost_with_final,
108  iter->second->cost_ +
109  fst_.Final(iter->first).Value());
110  }
111  BaseFloat extra_cost = best_cost_with_final - best_cost;
112  if (extra_cost != extra_cost) { // NaN. This shouldn't happen; it indicates some
113  // kind of error, most likely.
114  KALDI_WARN << "Found NaN (likely search failure in decoding)";
115  return infinity;
116  }
117  // Note: extra_cost will be infinity if no states were final.
118  return extra_cost;
119 }
unordered_map< StateId, Token * > cur_toks_
float BaseFloat
Definition: kaldi-types.h:29
const fst::Fst< fst::StdArc > & fst_
#define KALDI_WARN
Definition: kaldi-error.h:130
bool GetBestPath ( Lattice fst_out,
bool  use_final_probs = true 
) const

Definition at line 123 of file simple-decoder.cc.

References SimpleDecoder::Token::arc_, SimpleDecoder::Token::cost_, SimpleDecoder::cur_toks_, SimpleDecoder::fst_, rnnlm::i, KALDI_ASSERT, LatticeWeightTpl< BaseFloat >::One(), SimpleDecoder::Token::prev_, SimpleDecoder::ReachedFinal(), and fst::RemoveEpsLocal().

Referenced by main().

123  {
124  fst_out->DeleteStates();
125  Token *best_tok = NULL;
126  bool is_final = ReachedFinal();
127  if (!is_final) {
128  for (unordered_map<StateId, Token*>::const_iterator iter = cur_toks_.begin();
129  iter != cur_toks_.end();
130  ++iter)
131  if (best_tok == NULL || *best_tok < *(iter->second) )
132  best_tok = iter->second;
133  } else {
134  double infinity =std::numeric_limits<double>::infinity(),
135  best_cost = infinity;
136  for (unordered_map<StateId, Token*>::const_iterator iter = cur_toks_.begin();
137  iter != cur_toks_.end();
138  ++iter) {
139  double this_cost = iter->second->cost_ + fst_.Final(iter->first).Value();
140  if (this_cost != infinity && this_cost < best_cost) {
141  best_cost = this_cost;
142  best_tok = iter->second;
143  }
144  }
145  }
146  if (best_tok == NULL) return false; // No output.
147 
148  std::vector<LatticeArc> arcs_reverse; // arcs in reverse order.
149  for (Token *tok = best_tok; tok != NULL; tok = tok->prev_)
150  arcs_reverse.push_back(tok->arc_);
151  KALDI_ASSERT(arcs_reverse.back().nextstate == fst_.Start());
152  arcs_reverse.pop_back(); // that was a "fake" token... gives no info.
153 
154  StateId cur_state = fst_out->AddState();
155  fst_out->SetStart(cur_state);
156  for (ssize_t i = static_cast<ssize_t>(arcs_reverse.size())-1; i >= 0; i--) {
157  LatticeArc arc = arcs_reverse[i];
158  arc.nextstate = fst_out->AddState();
159  fst_out->AddArc(cur_state, arc);
160  cur_state = arc.nextstate;
161  }
162  if (is_final && use_final_probs)
163  fst_out->SetFinal(cur_state,
164  LatticeWeight(fst_.Final(best_tok->arc_.nextstate).Value(),
165  0.0));
166  else
167  fst_out->SetFinal(cur_state, LatticeWeight::One());
168  fst::RemoveEpsLocal(fst_out);
169  return true;
170 }
fst::ArcTpl< LatticeWeight > LatticeArc
Definition: kaldi-lattice.h:40
unordered_map< StateId, Token * > cur_toks_
StdArc::StateId StateId
void RemoveEpsLocal(MutableFst< Arc > *fst)
RemoveEpsLocal remove some (but not necessarily all) epsilons in an FST, using an algorithm that is g...
fst::LatticeWeightTpl< BaseFloat > LatticeWeight
Definition: kaldi-lattice.h:32
bool ReachedFinal() const
static const LatticeWeightTpl One()
const fst::Fst< fst::StdArc > & fst_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void InitDecoding ( )

InitDecoding initializes the decoding, and should only be used if you intend to call AdvanceDecoding().

If you call Decode(), you don't need to call this. You can call InitDecoding if you have already decoded an utterance and want to start with a new utterance.

Definition at line 45 of file simple-decoder.cc.

References SimpleDecoder::ClearToks(), SimpleDecoder::cur_toks_, SimpleDecoder::fst_, KALDI_ASSERT, SimpleDecoder::num_frames_decoded_, SimpleDecoder::prev_toks_, and SimpleDecoder::ProcessNonemitting().

Referenced by SimpleDecoder::Decode().

45  {
46  // clean up from last time:
49  // initialize decoding:
50  StateId start_state = fst_.Start();
51  KALDI_ASSERT(start_state != fst::kNoStateId);
52  StdArc dummy_arc(0, 0, StdWeight::One(), start_state);
53  cur_toks_[start_state] = new Token(dummy_arc, 0.0, NULL);
56 }
unordered_map< StateId, Token * > cur_toks_
StdArc::StateId StateId
unordered_map< StateId, Token * > prev_toks_
const fst::Fst< fst::StdArc > & fst_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
static void ClearToks(unordered_map< StateId, Token * > &toks)
KALDI_DISALLOW_COPY_AND_ASSIGN ( SimpleDecoder  )
private
int32 NumFramesDecoded ( ) const
inline

Returns the number of frames already decoded.

Definition at line 89 of file simple-decoder.h.

References SimpleDecoder::num_frames_decoded_.

89 { return num_frames_decoded_; }
void ProcessEmitting ( DecodableInterface decodable)
private

Definition at line 173 of file simple-decoder.cc.

References SimpleDecoder::Token::arc_, SimpleDecoder::beam_, SimpleDecoder::Token::cost_, SimpleDecoder::cur_toks_, SimpleDecoder::fst_, KALDI_ASSERT, DecodableInterface::LogLikelihood(), SimpleDecoder::num_frames_decoded_, SimpleDecoder::prev_toks_, and SimpleDecoder::Token::TokenDelete().

Referenced by SimpleDecoder::AdvanceDecoding(), and SimpleDecoder::Decode().

173  {
174  int32 frame = num_frames_decoded_;
175  // Processes emitting arcs for one frame. Propagates from
176  // prev_toks_ to cur_toks_.
177  double cutoff = std::numeric_limits<BaseFloat>::infinity();
178  for (unordered_map<StateId, Token*>::iterator iter = prev_toks_.begin();
179  iter != prev_toks_.end();
180  ++iter) {
181  StateId state = iter->first;
182  Token *tok = iter->second;
183  KALDI_ASSERT(state == tok->arc_.nextstate);
184  for (fst::ArcIterator<fst::Fst<StdArc> > aiter(fst_, state);
185  !aiter.Done();
186  aiter.Next()) {
187  const StdArc &arc = aiter.Value();
188  if (arc.ilabel != 0) { // propagate..
189  BaseFloat acoustic_cost = -decodable->LogLikelihood(frame, arc.ilabel);
190  double total_cost = tok->cost_ + arc.weight.Value() + acoustic_cost;
191 
192  if (total_cost > cutoff) continue;
193  if (total_cost + beam_ < cutoff)
194  cutoff = total_cost + beam_;
195  Token *new_tok = new Token(arc, acoustic_cost, tok);
196  unordered_map<StateId, Token*>::iterator find_iter
197  = cur_toks_.find(arc.nextstate);
198  if (find_iter == cur_toks_.end()) {
199  cur_toks_[arc.nextstate] = new_tok;
200  } else {
201  if ( *(find_iter->second) < *new_tok ) {
202  Token::TokenDelete(find_iter->second);
203  find_iter->second = new_tok;
204  } else {
205  Token::TokenDelete(new_tok);
206  }
207  }
208  }
209  }
210  }
212 }
unordered_map< StateId, Token * > cur_toks_
StdArc::StateId StateId
unordered_map< StateId, Token * > prev_toks_
float BaseFloat
Definition: kaldi-types.h:29
const fst::Fst< fst::StdArc > & fst_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
static void TokenDelete(Token *tok)
void ProcessNonemitting ( )
private

Definition at line 214 of file simple-decoder.cc.

References SimpleDecoder::Token::arc_, SimpleDecoder::beam_, SimpleDecoder::Token::cost_, SimpleDecoder::cur_toks_, SimpleDecoder::fst_, KALDI_ASSERT, and SimpleDecoder::Token::TokenDelete().

Referenced by SimpleDecoder::AdvanceDecoding(), SimpleDecoder::Decode(), and SimpleDecoder::InitDecoding().

214  {
215  // Processes nonemitting arcs for one frame. Propagates within
216  // cur_toks_.
217  std::vector<StateId> queue_;
218  double infinity = std::numeric_limits<double>::infinity();
219  double best_cost = infinity;
220  for (unordered_map<StateId, Token*>::iterator iter = cur_toks_.begin();
221  iter != cur_toks_.end();
222  ++iter) {
223  queue_.push_back(iter->first);
224  best_cost = std::min(best_cost, iter->second->cost_);
225  }
226  double cutoff = best_cost + beam_;
227 
228  while (!queue_.empty()) {
229  StateId state = queue_.back();
230  queue_.pop_back();
231  Token *tok = cur_toks_[state];
232  KALDI_ASSERT(tok != NULL && state == tok->arc_.nextstate);
233  for (fst::ArcIterator<fst::Fst<StdArc> > aiter(fst_, state);
234  !aiter.Done();
235  aiter.Next()) {
236  const StdArc &arc = aiter.Value();
237  if (arc.ilabel == 0) { // propagate nonemitting only...
238  const BaseFloat acoustic_cost = 0.0;
239  Token *new_tok = new Token(arc, acoustic_cost, tok);
240  if (new_tok->cost_ > cutoff) {
241  Token::TokenDelete(new_tok);
242  } else {
243  unordered_map<StateId, Token*>::iterator find_iter
244  = cur_toks_.find(arc.nextstate);
245  if (find_iter == cur_toks_.end()) {
246  cur_toks_[arc.nextstate] = new_tok;
247  queue_.push_back(arc.nextstate);
248  } else {
249  if ( *(find_iter->second) < *new_tok ) {
250  Token::TokenDelete(find_iter->second);
251  find_iter->second = new_tok;
252  queue_.push_back(arc.nextstate);
253  } else {
254  Token::TokenDelete(new_tok);
255  }
256  }
257  }
258  }
259  }
260  }
261 }
unordered_map< StateId, Token * > cur_toks_
StdArc::StateId StateId
float BaseFloat
Definition: kaldi-types.h:29
const fst::Fst< fst::StdArc > & fst_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
static void TokenDelete(Token *tok)
void PruneToks ( BaseFloat  beam,
unordered_map< StateId, Token * > *  toks 
)
staticprivate

Definition at line 273 of file simple-decoder.cc.

References rnnlm::i, KALDI_VLOG, and SimpleDecoder::Token::TokenDelete().

Referenced by SimpleDecoder::AdvanceDecoding(), and SimpleDecoder::Decode().

273  {
274  if (toks->empty()) {
275  KALDI_VLOG(2) << "No tokens to prune.\n";
276  return;
277  }
278  double best_cost = std::numeric_limits<double>::infinity();
279  for (unordered_map<StateId, Token*>::iterator iter = toks->begin();
280  iter != toks->end(); ++iter)
281  best_cost = std::min(best_cost, iter->second->cost_);
282  std::vector<StateId> retained;
283  double cutoff = best_cost + beam;
284  for (unordered_map<StateId, Token*>::iterator iter = toks->begin();
285  iter != toks->end(); ++iter) {
286  if (iter->second->cost_ < cutoff)
287  retained.push_back(iter->first);
288  else
289  Token::TokenDelete(iter->second);
290  }
291  unordered_map<StateId, Token*> tmp;
292  for (size_t i = 0; i < retained.size(); i++) {
293  tmp[retained[i]] = (*toks)[retained[i]];
294  }
295  KALDI_VLOG(2) << "Pruned to " << (retained.size()) << " toks.\n";
296  tmp.swap(*toks);
297 }
#define KALDI_VLOG(v)
Definition: kaldi-error.h:136
static void TokenDelete(Token *tok)
bool ReachedFinal ( ) const

Definition at line 82 of file simple-decoder.cc.

References SimpleDecoder::cur_toks_, and SimpleDecoder::fst_.

Referenced by SimpleDecoder::GetBestPath(), and main().

82  {
83  for (unordered_map<StateId, Token*>::const_iterator iter = cur_toks_.begin();
84  iter != cur_toks_.end();
85  ++iter) {
86  if (iter->second->cost_ != std::numeric_limits<BaseFloat>::infinity() &&
87  fst_.Final(iter->first) != StdWeight::Zero())
88  return true;
89  }
90  return false;
91 }
unordered_map< StateId, Token * > cur_toks_
const fst::Fst< fst::StdArc > & fst_

Member Data Documentation


The documentation for this class was generated from the following files: