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

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

#include <lattice-simple-decoder.h>

Collaboration diagram for LatticeSimpleDecoder:

Classes

struct  ForwardLink
 
struct  Token
 
struct  TokenList
 

Public Types

typedef fst::StdArc Arc
 
typedef Arc::Label Label
 
typedef Arc::StateId StateId
 
typedef Arc::Weight Weight
 

Public Member Functions

 LatticeSimpleDecoder (const fst::Fst< fst::StdArc > &fst, const LatticeSimpleDecoderConfig &config)
 
 ~LatticeSimpleDecoder ()
 
const LatticeSimpleDecoderConfigGetOptions () const
 
bool Decode (DecodableInterface *decodable)
 
bool ReachedFinal () const
 says whether a final-state was active on the last frame. More...
 
void InitDecoding ()
 InitDecoding initializes the decoding, and should only be used if you intend to call AdvanceDecoding(). More...
 
void FinalizeDecoding ()
 This function may be optionally called after AdvanceDecoding(), when you do not plan to decode any further. More...
 
BaseFloat FinalRelativeCost () const
 FinalRelativeCost() serves the same purpose as ReachedFinal(), but gives more information. More...
 
bool GetBestPath (Lattice *lat, bool use_final_probs=true) const
 
bool GetRawLattice (Lattice *lat, bool use_final_probs=true) const
 
bool GetLattice (CompactLattice *clat, bool use_final_probs=true) const
 
int32 NumFramesDecoded () const
 

Private Member Functions

TokenFindOrAddToken (StateId state, int32 frame_plus_one, BaseFloat tot_cost, bool emitting, bool *changed)
 
void PruneForwardLinks (int32 frame, bool *extra_costs_changed, bool *links_pruned, BaseFloat delta)
 
void PruneForwardLinksFinal ()
 
void PruneTokensForFrame (int32 frame)
 
void PruneActiveTokens (BaseFloat delta)
 
void ProcessEmitting (DecodableInterface *decodable)
 
void ProcessNonemitting ()
 
void ClearActiveTokens ()
 
void ComputeFinalCosts (unordered_map< Token *, BaseFloat > *final_costs, BaseFloat *final_relative_cost, BaseFloat *final_best_cost) const
 
void PruneCurrentTokens (BaseFloat beam, unordered_map< StateId, Token * > *toks)
 

Private Attributes

unordered_map< StateId, Token * > cur_toks_
 
unordered_map< StateId, Token * > prev_toks_
 
std::vector< TokenListactive_toks_
 
const fst::Fst< fst::StdArc > & fst_
 
LatticeSimpleDecoderConfig config_
 
int32 num_toks_
 
bool warned_
 
bool decoding_finalized_
 decoding_finalized_ is true if someone called FinalizeDecoding(). More...
 
unordered_map< Token *, BaseFloatfinal_costs_
 For the meaning of the next 3 variables, see the comment for decoding_finalized_ above., and ComputeFinalCosts(). More...
 
BaseFloat final_relative_cost_
 
BaseFloat final_best_cost_
 

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 76 of file lattice-simple-decoder.h.

Member Typedef Documentation

typedef fst::StdArc Arc

Definition at line 78 of file lattice-simple-decoder.h.

typedef Arc::Label Label

Definition at line 79 of file lattice-simple-decoder.h.

typedef Arc::StateId StateId

Definition at line 80 of file lattice-simple-decoder.h.

typedef Arc::Weight Weight

Definition at line 81 of file lattice-simple-decoder.h.

Constructor & Destructor Documentation

LatticeSimpleDecoder ( const fst::Fst< fst::StdArc > &  fst,
const LatticeSimpleDecoderConfig config 
)
inline

Definition at line 83 of file lattice-simple-decoder.h.

References LatticeSimpleDecoderConfig::Check().

84  :
85  fst_(fst), config_(config), num_toks_(0) { config.Check(); }
LatticeSimpleDecoderConfig config_
Definition: graph.dox:21
const fst::Fst< fst::StdArc > & fst_

Member Function Documentation

void ClearActiveTokens ( )
private

Definition at line 615 of file lattice-simple-decoder.cc.

References LatticeSimpleDecoder::active_toks_, rnnlm::i, KALDI_ASSERT, LatticeSimpleDecoder::Token::next, and LatticeSimpleDecoder::num_toks_.

Referenced by LatticeSimpleDecoder::InitDecoding(), and LatticeSimpleDecoder::~LatticeSimpleDecoder().

615  { // a cleanup routine, at utt end/begin
616  for (size_t i = 0; i < active_toks_.size(); i++) {
617  // Delete all tokens alive on this frame, and any forward
618  // links they may have.
619  for (Token *tok = active_toks_[i].toks; tok != NULL; ) {
620  tok->DeleteForwardLinks();
621  Token *next_tok = tok->next;
622  delete tok;
623  num_toks_--;
624  tok = next_tok;
625  }
626  }
627  active_toks_.clear();
628  KALDI_ASSERT(num_toks_ == 0);
629 }
std::vector< TokenList > active_toks_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void ComputeFinalCosts ( unordered_map< Token *, BaseFloat > *  final_costs,
BaseFloat final_relative_cost,
BaseFloat final_best_cost 
) const
private

Definition at line 292 of file lattice-simple-decoder.cc.

References LatticeSimpleDecoder::cur_toks_, LatticeSimpleDecoder::decoding_finalized_, LatticeSimpleDecoder::fst_, KALDI_ASSERT, and LatticeSimpleDecoder::Token::tot_cost.

Referenced by LatticeSimpleDecoder::FinalRelativeCost(), LatticeSimpleDecoder::GetRawLattice(), and LatticeSimpleDecoder::PruneForwardLinksFinal().

295  {
297  if (final_costs != NULL)
298  final_costs->clear();
299 
300  BaseFloat infinity = std::numeric_limits<BaseFloat>::infinity();
301  BaseFloat best_cost = infinity,
302  best_cost_with_final = infinity;
303 
304  for (unordered_map<StateId, Token*>::const_iterator iter = cur_toks_.begin();
305  iter != cur_toks_.end(); ++iter) {
306  StateId state = iter->first;
307  Token *tok = iter->second;
308  BaseFloat final_cost = fst_.Final(state).Value();
309  BaseFloat cost = tok->tot_cost,
310  cost_with_final = cost + final_cost;
311  best_cost = std::min(cost, best_cost);
312  best_cost_with_final = std::min(cost_with_final, best_cost_with_final);
313  if (final_costs != NULL && final_cost != infinity)
314  (*final_costs)[tok] = final_cost;
315  }
316  if (final_relative_cost != NULL) {
317  if (best_cost == infinity && best_cost_with_final == infinity) {
318  // Likely this will only happen if there are no tokens surviving.
319  // This seems the least bad way to handle it.
320  *final_relative_cost = infinity;
321  } else {
322  *final_relative_cost = best_cost_with_final - best_cost;
323  }
324  }
325  if (final_best_cost != NULL) {
326  if (best_cost_with_final != infinity) { // final-state exists.
327  *final_best_cost = best_cost_with_final;
328  } else { // no final-state exists.
329  *final_best_cost = best_cost;
330  }
331  }
332 }
bool decoding_finalized_
decoding_finalized_ is true if someone called FinalizeDecoding().
float BaseFloat
Definition: kaldi-types.h:29
const fst::Fst< fst::StdArc > & fst_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
unordered_map< StateId, Token * > cur_toks_
bool Decode ( DecodableInterface decodable)

Definition at line 46 of file lattice-simple-decoder.cc.

References LatticeSimpleDecoderConfig::beam, LatticeSimpleDecoder::config_, LatticeSimpleDecoder::cur_toks_, LatticeSimpleDecoder::final_costs_, LatticeSimpleDecoder::FinalizeDecoding(), LatticeSimpleDecoder::InitDecoding(), DecodableInterface::IsLastFrame(), LatticeSimpleDecoderConfig::lattice_beam, LatticeSimpleDecoder::NumFramesDecoded(), LatticeSimpleDecoder::ProcessEmitting(), LatticeSimpleDecoder::ProcessNonemitting(), LatticeSimpleDecoderConfig::prune_interval, LatticeSimpleDecoderConfig::prune_scale, LatticeSimpleDecoder::PruneActiveTokens(), and LatticeSimpleDecoder::PruneCurrentTokens().

Referenced by kaldi::DecodeUtteranceLatticeSimple().

46  {
47  InitDecoding();
48 
49  while (!decodable->IsLastFrame(NumFramesDecoded() - 1)) {
52  ProcessEmitting(decodable);
53  // Important to call PruneCurrentTokens before ProcessNonemitting, or we
54  // would get dangling forward pointers. Anyway, ProcessNonemitting uses the
55  // beam.
58  }
60 
61  // Returns true if we have any kind of traceback available (not necessarily
62  // to the end state; query ReachedFinal() for that).
63  return !final_costs_.empty();
64 }
void InitDecoding()
InitDecoding initializes the decoding, and should only be used if you intend to call AdvanceDecoding(...
LatticeSimpleDecoderConfig config_
unordered_map< Token *, BaseFloat > final_costs_
For the meaning of the next 3 variables, see the comment for decoding_finalized_ above., and ComputeFinalCosts().
void FinalizeDecoding()
This function may be optionally called after AdvanceDecoding(), when you do not plan to decode any fu...
void PruneActiveTokens(BaseFloat delta)
void PruneCurrentTokens(BaseFloat beam, unordered_map< StateId, Token * > *toks)
void ProcessEmitting(DecodableInterface *decodable)
unordered_map< StateId, Token * > cur_toks_
void FinalizeDecoding ( )

This function may be optionally called after AdvanceDecoding(), when you do not plan to decode any further.

It does an extra pruning step that will help to prune the lattices output by GetLattice and (particularly) GetRawLattice more accurately, particularly toward the end of the utterance. It does this by using the final-probs in pruning (if any final-state survived); it also does a final pruning step that visits all states (the pruning that is done during decoding may fail to prune states that are within kPruningScale = 0.1 outside of the beam). If you call this, you cannot call AdvanceDecoding again (it will fail), and you cannot call GetLattice() and related functions with use_final_probs = false. Used to be called PruneActiveTokensFinal().

Definition at line 495 of file lattice-simple-decoder.cc.

References KALDI_VLOG, LatticeSimpleDecoder::num_toks_, LatticeSimpleDecoder::NumFramesDecoded(), LatticeSimpleDecoder::PruneForwardLinks(), LatticeSimpleDecoder::PruneForwardLinksFinal(), and LatticeSimpleDecoder::PruneTokensForFrame().

Referenced by LatticeSimpleDecoder::Decode().

495  {
496  int32 final_frame_plus_one = NumFramesDecoded();
497  int32 num_toks_begin = num_toks_;
499  for (int32 f = final_frame_plus_one - 1; f >= 0; f--) {
500  bool b1, b2; // values not used.
501  BaseFloat dontcare = 0.0;
502  PruneForwardLinks(f, &b1, &b2, dontcare);
503  PruneTokensForFrame(f + 1);
504  }
506  KALDI_VLOG(3) << "pruned tokens from " << num_toks_begin
507  << " to " << num_toks_;
508 }
float BaseFloat
Definition: kaldi-types.h:29
void PruneForwardLinks(int32 frame, bool *extra_costs_changed, bool *links_pruned, BaseFloat delta)
#define KALDI_VLOG(v)
Definition: kaldi-error.h:136
BaseFloat FinalRelativeCost ( ) const

FinalRelativeCost() serves the same purpose 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. If it not too positive (e.g. < 5 is my first guess, but this is not tested) you can take it as a good indication that we reached the final-state with reasonable likelihood.

Definition at line 421 of file lattice-simple-decoder.cc.

References LatticeSimpleDecoder::ComputeFinalCosts(), LatticeSimpleDecoder::decoding_finalized_, and LatticeSimpleDecoder::final_relative_cost_.

Referenced by LatticeSimpleDecoder::ReachedFinal().

421  {
422  if (!decoding_finalized_) {
423  BaseFloat relative_cost;
424  ComputeFinalCosts(NULL, &relative_cost, NULL);
425  return relative_cost;
426  } else {
427  // we're not allowed to call that function if FinalizeDecoding() has
428  // been called; return a cached value.
429  return final_relative_cost_;
430  }
431 }
bool decoding_finalized_
decoding_finalized_ is true if someone called FinalizeDecoding().
void ComputeFinalCosts(unordered_map< Token *, BaseFloat > *final_costs, BaseFloat *final_relative_cost, BaseFloat *final_best_cost) const
float BaseFloat
Definition: kaldi-types.h:29
LatticeSimpleDecoder::Token * FindOrAddToken ( StateId  state,
int32  frame_plus_one,
BaseFloat  tot_cost,
bool  emitting,
bool *  changed 
)
inlineprivate

Definition at line 194 of file lattice-simple-decoder.cc.

References LatticeSimpleDecoder::active_toks_, LatticeSimpleDecoder::cur_toks_, KALDI_ASSERT, LatticeSimpleDecoder::num_toks_, and LatticeSimpleDecoder::Token::tot_cost.

Referenced by LatticeSimpleDecoder::ProcessEmitting(), and LatticeSimpleDecoder::ProcessNonemitting().

196  {
197  KALDI_ASSERT(frame < active_toks_.size());
198  Token *&toks = active_toks_[frame].toks;
199 
200  unordered_map<StateId, Token*>::iterator find_iter = cur_toks_.find(state);
201  if (find_iter == cur_toks_.end()) { // no such token presently.
202  // Create one.
203  const BaseFloat extra_cost = 0.0;
204  // tokens on the currently final frame have zero extra_cost
205  // as any of them could end up
206  // on the winning path.
207  Token *new_tok = new Token (tot_cost, extra_cost, NULL, toks);
208  toks = new_tok;
209  num_toks_++;
210  cur_toks_[state] = new_tok;
211  if (changed) *changed = true;
212  return new_tok;
213  } else {
214  Token *tok = find_iter->second; // There is an existing Token for this state.
215  if (tok->tot_cost > tot_cost) {
216  tok->tot_cost = tot_cost;
217  if (changed) *changed = true;
218  } else {
219  if (changed) *changed = false;
220  }
221  return tok;
222  }
223 }
std::vector< TokenList > active_toks_
float BaseFloat
Definition: kaldi-types.h:29
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
unordered_map< StateId, Token * > cur_toks_
bool GetBestPath ( Lattice lat,
bool  use_final_probs = true 
) const

Definition at line 68 of file lattice-simple-decoder.cc.

References LatticeSimpleDecoder::GetRawLattice().

Referenced by kaldi::DecodeUtteranceLatticeSimple().

69  {
70  fst::VectorFst<LatticeArc> fst;
71  GetRawLattice(&fst, use_final_probs);
72  ShortestPath(fst, ofst);
73  return (ofst->NumStates() > 0);
74 }
Definition: graph.dox:21
bool GetRawLattice(Lattice *lat, bool use_final_probs=true) const
bool GetLattice ( CompactLattice clat,
bool  use_final_probs = true 
) const

Definition at line 158 of file lattice-simple-decoder.cc.

References LatticeSimpleDecoder::config_, LatticeSimpleDecoderConfig::det_opts, fst::DeterminizeLatticePruned(), LatticeSimpleDecoder::GetRawLattice(), KALDI_WARN, LatticeSimpleDecoderConfig::lattice_beam, DeterminizeLatticePrunedOptions::max_mem, and DeterminizeLatticePhonePrunedOptions::max_mem.

160  {
161  Lattice raw_fst;
162  GetRawLattice(&raw_fst, use_final_probs);
163  Invert(&raw_fst); // make it so word labels are on the input.
164  if (!TopSort(&raw_fst)) // topological sort makes lattice-determinization more efficient
165  KALDI_WARN << "Topological sorting of state-level lattice failed "
166  "(probably your lexicon has empty words or your LM has epsilon cycles; this "
167  " is a bad idea.)";
168  // (in phase where we get backward-costs).
169  fst::ILabelCompare<LatticeArc> ilabel_comp;
170  ArcSort(&raw_fst, ilabel_comp); // sort on ilabel; makes
171  // lattice-determinization more efficient.
172 
174  lat_opts.max_mem = config_.det_opts.max_mem;
175 
176  DeterminizeLatticePruned(raw_fst, config_.lattice_beam, ofst, lat_opts);
177  raw_fst.DeleteStates(); // Free memory-- raw_fst no longer needed.
178  Connect(ofst); // Remove unreachable states... there might be
179  // a small number of these, in some cases.
180  // Note: if something went wrong and the raw lattice was empty,
181  // we should still get to this point in the code without warnings or failures.
182  return (ofst->NumStates() != 0);
183 }
LatticeSimpleDecoderConfig config_
bool DeterminizeLatticePruned(const ExpandedFst< ArcTpl< Weight > > &ifst, double beam, MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > *ofst, DeterminizeLatticePrunedOptions opts)
bool GetRawLattice(Lattice *lat, bool use_final_probs=true) const
fst::VectorFst< LatticeArc > Lattice
Definition: kaldi-lattice.h:44
#define KALDI_WARN
Definition: kaldi-error.h:130
fst::DeterminizeLatticePhonePrunedOptions det_opts
const LatticeSimpleDecoderConfig& GetOptions ( ) const
inline

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

References LatticeSimpleDecoder::config_.

Referenced by kaldi::DecodeUtteranceLatticeSimple().

89  {
90  return config_;
91  }
LatticeSimpleDecoderConfig config_
bool GetRawLattice ( Lattice lat,
bool  use_final_probs = true 
) const

Definition at line 78 of file lattice-simple-decoder.cc.

References LatticeSimpleDecoder::active_toks_, LatticeSimpleDecoder::ComputeFinalCosts(), LatticeSimpleDecoder::decoding_finalized_, LatticeSimpleDecoder::final_costs_, KALDI_ASSERT, KALDI_ERR, KALDI_WARN, LatticeSimpleDecoder::ForwardLink::next, LatticeSimpleDecoder::num_toks_, LatticeSimpleDecoder::NumFramesDecoded(), and LatticeWeightTpl< BaseFloat >::One().

Referenced by kaldi::DecodeUtteranceLatticeSimple(), LatticeSimpleDecoder::GetBestPath(), and LatticeSimpleDecoder::GetLattice().

79  {
80  typedef LatticeArc Arc;
81  typedef Arc::StateId StateId;
82  typedef Arc::Weight Weight;
83  typedef Arc::Label Label;
84 
85  // Note: you can't use the old interface (Decode()) if you want to
86  // get the lattice with use_final_probs = false. You'd have to do
87  // InitDecoding() and then AdvanceDecoding().
88  if (decoding_finalized_ && !use_final_probs)
89  KALDI_ERR << "You cannot call FinalizeDecoding() and then call "
90  << "GetRawLattice() with use_final_probs == false";
91 
92  unordered_map<Token*, BaseFloat> final_costs_local;
93 
94  const unordered_map<Token*, BaseFloat> &final_costs =
95  (decoding_finalized_ ? final_costs_ : final_costs_local);
96 
97  if (!decoding_finalized_ && use_final_probs)
98  ComputeFinalCosts(&final_costs_local, NULL, NULL);
99 
100  ofst->DeleteStates();
101  int32 num_frames = NumFramesDecoded();
102  KALDI_ASSERT(num_frames > 0);
103  const int32 bucket_count = num_toks_/2 + 3;
104  unordered_map<Token*, StateId> tok_map(bucket_count);
105  // First create all states.
106  for (int32 f = 0; f <= num_frames; f++) {
107  if (active_toks_[f].toks == NULL) {
108  KALDI_WARN << "GetRawLattice: no tokens active on frame " << f
109  << ": not producing lattice.\n";
110  return false;
111  }
112  for (Token *tok = active_toks_[f].toks; tok != NULL; tok = tok->next)
113  tok_map[tok] = ofst->AddState();
114  // The next statement sets the start state of the output FST.
115  // Because we always add new states to the head of the list
116  // active_toks_[f].toks, and the start state was the first one
117  // added, it will be the last one added to ofst.
118  if (f == 0 && ofst->NumStates() > 0)
119  ofst->SetStart(ofst->NumStates()-1);
120  }
121  StateId cur_state = 0; // we rely on the fact that we numbered these
122  // consecutively (AddState() returns the numbers in order..)
123  for (int32 f = 0; f <= num_frames; f++) {
124  for (Token *tok = active_toks_[f].toks; tok != NULL; tok = tok->next,
125  cur_state++) {
126  for (ForwardLink *l = tok->links;
127  l != NULL;
128  l = l->next) {
129  unordered_map<Token*, StateId>::const_iterator iter =
130  tok_map.find(l->next_tok);
131  StateId nextstate = iter->second;
132  KALDI_ASSERT(iter != tok_map.end());
133  Arc arc(l->ilabel, l->olabel,
134  Weight(l->graph_cost, l->acoustic_cost),
135  nextstate);
136  ofst->AddArc(cur_state, arc);
137  }
138  if (f == num_frames) {
139  if (use_final_probs && !final_costs.empty()) {
140  unordered_map<Token*, BaseFloat>::const_iterator iter =
141  final_costs.find(tok);
142  if (iter != final_costs.end())
143  ofst->SetFinal(cur_state, LatticeWeight(iter->second, 0));
144  } else {
145  ofst->SetFinal(cur_state, LatticeWeight::One());
146  }
147  }
148  }
149  }
150  KALDI_ASSERT(cur_state == ofst->NumStates());
151  return (cur_state != 0);
152 }
fst::StdArc::StateId StateId
fst::ArcTpl< LatticeWeight > LatticeArc
Definition: kaldi-lattice.h:40
std::vector< TokenList > active_toks_
bool decoding_finalized_
decoding_finalized_ is true if someone called FinalizeDecoding().
unordered_map< Token *, BaseFloat > final_costs_
For the meaning of the next 3 variables, see the comment for decoding_finalized_ above., and ComputeFinalCosts().
fst::LatticeWeightTpl< BaseFloat > LatticeWeight
Definition: kaldi-lattice.h:32
void ComputeFinalCosts(unordered_map< Token *, BaseFloat > *final_costs, BaseFloat *final_relative_cost, BaseFloat *final_best_cost) const
static const LatticeWeightTpl One()
#define KALDI_ERR
Definition: kaldi-error.h:127
#define KALDI_WARN
Definition: kaldi-error.h:130
fst::StdArc::Label Label
fst::StdArc::Weight Weight
#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 27 of file lattice-simple-decoder.cc.

References LatticeSimpleDecoder::active_toks_, LatticeSimpleDecoder::ClearActiveTokens(), LatticeSimpleDecoder::cur_toks_, LatticeSimpleDecoder::decoding_finalized_, LatticeSimpleDecoder::final_costs_, LatticeSimpleDecoder::fst_, KALDI_ASSERT, LatticeSimpleDecoder::num_toks_, LatticeSimpleDecoder::prev_toks_, LatticeSimpleDecoder::ProcessNonemitting(), and LatticeSimpleDecoder::warned_.

Referenced by LatticeSimpleDecoder::Decode().

27  {
28  // clean up from last time:
29  cur_toks_.clear();
30  prev_toks_.clear();
32  warned_ = false;
33  decoding_finalized_ = false;
34  final_costs_.clear();
35  num_toks_ = 0;
36  StateId start_state = fst_.Start();
37  KALDI_ASSERT(start_state != fst::kNoStateId);
38  active_toks_.resize(1);
39  Token *start_tok = new Token(0.0, 0.0, NULL, NULL);
40  active_toks_[0].toks = start_tok;
41  cur_toks_[start_state] = start_tok;
42  num_toks_++;
44 }
std::vector< TokenList > active_toks_
bool decoding_finalized_
decoding_finalized_ is true if someone called FinalizeDecoding().
unordered_map< Token *, BaseFloat > final_costs_
For the meaning of the next 3 variables, see the comment for decoding_finalized_ above., and ComputeFinalCosts().
unordered_map< StateId, Token * > prev_toks_
const fst::Fst< fst::StdArc > & fst_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
unordered_map< StateId, Token * > cur_toks_
void ProcessEmitting ( DecodableInterface decodable)
private

Definition at line 510 of file lattice-simple-decoder.cc.

References LatticeSimpleDecoder::active_toks_, LatticeSimpleDecoderConfig::beam, LatticeSimpleDecoder::config_, LatticeSimpleDecoder::cur_toks_, LatticeSimpleDecoder::FindOrAddToken(), LatticeSimpleDecoder::fst_, LatticeSimpleDecoder::Token::links, DecodableInterface::LogLikelihood(), LatticeSimpleDecoder::prev_toks_, and LatticeSimpleDecoder::Token::tot_cost.

Referenced by LatticeSimpleDecoder::Decode().

510  {
511  int32 frame = active_toks_.size() - 1; // frame is the frame-index
512  // (zero-based) used to get likelihoods
513  // from the decodable object.
514  active_toks_.resize(active_toks_.size() + 1);
515  prev_toks_.clear();
516  cur_toks_.swap(prev_toks_);
517 
518  // Processes emitting arcs for one frame. Propagates from
519  // prev_toks_ to cur_toks_.
520  BaseFloat cutoff = std::numeric_limits<BaseFloat>::infinity();
521  for (unordered_map<StateId, Token*>::iterator iter = prev_toks_.begin();
522  iter != prev_toks_.end();
523  ++iter) {
524  StateId state = iter->first;
525  Token *tok = iter->second;
526  for (fst::ArcIterator<fst::Fst<Arc> > aiter(fst_, state);
527  !aiter.Done();
528  aiter.Next()) {
529  const Arc &arc = aiter.Value();
530  if (arc.ilabel != 0) { // propagate..
531  BaseFloat ac_cost = -decodable->LogLikelihood(frame, arc.ilabel),
532  graph_cost = arc.weight.Value(),
533  cur_cost = tok->tot_cost,
534  tot_cost = cur_cost + ac_cost + graph_cost;
535  if (tot_cost > cutoff) continue;
536  else if (tot_cost + config_.beam < cutoff)
537  cutoff = tot_cost + config_.beam;
538  // AddToken adds the next_tok to cur_toks_ (if not already present).
539  Token *next_tok = FindOrAddToken(arc.nextstate, frame + 1, tot_cost,
540  true, NULL);
541 
542  // Add ForwardLink from tok to next_tok (put on head of list tok->links)
543  tok->links = new ForwardLink(next_tok, arc.ilabel, arc.olabel,
544  graph_cost, ac_cost, tok->links);
545  }
546  }
547  }
548 }
std::vector< TokenList > active_toks_
LatticeSimpleDecoderConfig config_
float BaseFloat
Definition: kaldi-types.h:29
Token * FindOrAddToken(StateId state, int32 frame_plus_one, BaseFloat tot_cost, bool emitting, bool *changed)
unordered_map< StateId, Token * > prev_toks_
const fst::Fst< fst::StdArc > & fst_
unordered_map< StateId, Token * > cur_toks_
void ProcessNonemitting ( )
private

Definition at line 550 of file lattice-simple-decoder.cc.

References LatticeSimpleDecoder::active_toks_, LatticeSimpleDecoderConfig::beam, LatticeSimpleDecoder::config_, LatticeSimpleDecoder::cur_toks_, LatticeSimpleDecoder::Token::DeleteForwardLinks(), LatticeSimpleDecoder::FindOrAddToken(), LatticeSimpleDecoder::fst_, KALDI_ASSERT, KALDI_ERR, LatticeSimpleDecoder::Token::links, LatticeSimpleDecoder::Token::tot_cost, and LatticeSimpleDecoder::warned_.

Referenced by LatticeSimpleDecoder::Decode(), and LatticeSimpleDecoder::InitDecoding().

550  {
551  KALDI_ASSERT(!active_toks_.empty());
552  int32 frame = static_cast<int32>(active_toks_.size()) - 2;
553  // Note: "frame" is the time-index we just processed, or -1 if
554  // we are processing the nonemitting transitions before the
555  // first frame (called from InitDecoding()).
556 
557  // Processes nonemitting arcs for one frame. Propagates within
558  // cur_toks_. Note-- this queue structure is is not very optimal as
559  // it may cause us to process states unnecessarily (e.g. more than once),
560  // but in the baseline code, turning this vector into a set to fix this
561  // problem did not improve overall speed.
562  std::vector<StateId> queue;
563  BaseFloat best_cost = std::numeric_limits<BaseFloat>::infinity();
564  for (unordered_map<StateId, Token*>::iterator iter = cur_toks_.begin();
565  iter != cur_toks_.end();
566  ++iter) {
567  queue.push_back(iter->first);
568  best_cost = std::min(best_cost, iter->second->tot_cost);
569  }
570  if (queue.empty()) {
571  if (!warned_) {
572  KALDI_ERR << "Error in ProcessEmitting: no surviving tokens: frame is "
573  << frame;
574  warned_ = true;
575  }
576  }
577  BaseFloat cutoff = best_cost + config_.beam;
578 
579  while (!queue.empty()) {
580  StateId state = queue.back();
581  queue.pop_back();
582  Token *tok = cur_toks_[state];
583  // If "tok" has any existing forward links, delete them,
584  // because we're about to regenerate them. This is a kind
585  // of non-optimality (remember, this is the simple decoder),
586  // but since most states are emitting it's not a huge issue.
587  tok->DeleteForwardLinks();
588  tok->links = NULL;
589  for (fst::ArcIterator<fst::Fst<Arc> > aiter(fst_, state);
590  !aiter.Done();
591  aiter.Next()) {
592  const Arc &arc = aiter.Value();
593  if (arc.ilabel == 0) { // propagate nonemitting only...
594  BaseFloat graph_cost = arc.weight.Value(),
595  cur_cost = tok->tot_cost,
596  tot_cost = cur_cost + graph_cost;
597  if (tot_cost < cutoff) {
598  bool changed;
599  Token *new_tok = FindOrAddToken(arc.nextstate, frame + 1, tot_cost,
600  false, &changed);
601 
602  tok->links = new ForwardLink(new_tok, 0, arc.olabel,
603  graph_cost, 0, tok->links);
604 
605  // "changed" tells us whether the new token has a different
606  // cost from before, or is new [if so, add into queue].
607  if (changed)
608  queue.push_back(arc.nextstate);
609  }
610  }
611  }
612  }
613 }
std::vector< TokenList > active_toks_
LatticeSimpleDecoderConfig config_
float BaseFloat
Definition: kaldi-types.h:29
Token * FindOrAddToken(StateId state, int32 frame_plus_one, BaseFloat tot_cost, bool emitting, bool *changed)
const fst::Fst< fst::StdArc > & fst_
#define KALDI_ERR
Definition: kaldi-error.h:127
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
unordered_map< StateId, Token * > cur_toks_
void PruneActiveTokens ( BaseFloat  delta)
private

Definition at line 462 of file lattice-simple-decoder.cc.

References LatticeSimpleDecoder::active_toks_, KALDI_VLOG, LatticeSimpleDecoder::num_toks_, LatticeSimpleDecoder::NumFramesDecoded(), LatticeSimpleDecoder::PruneForwardLinks(), and LatticeSimpleDecoder::PruneTokensForFrame().

Referenced by LatticeSimpleDecoder::Decode().

462  {
463  int32 cur_frame_plus_one = NumFramesDecoded();
464  int32 num_toks_begin = num_toks_;
465  // The index "f" below represents a "frame plus one", i.e. you'd have to subtract
466  // one to get the corresponding index for the decodable object.
467  for (int32 f = cur_frame_plus_one - 1; f >= 0; f--) {
468  // Reason why we need to prune forward links in this situation:
469  // (1) we have never pruned them
470  // (2) we never pruned the forward links on the next frame, which
471  //
472  if (active_toks_[f].must_prune_forward_links) {
473  bool extra_costs_changed = false, links_pruned = false;
474  PruneForwardLinks(f, &extra_costs_changed, &links_pruned, delta);
475  if (extra_costs_changed && f > 0)
476  active_toks_[f-1].must_prune_forward_links = true;
477  if (links_pruned)
478  active_toks_[f].must_prune_tokens = true;
479  active_toks_[f].must_prune_forward_links = false;
480  }
481  if (f+1 < cur_frame_plus_one &&
482  active_toks_[f+1].must_prune_tokens) {
483  PruneTokensForFrame(f+1);
484  active_toks_[f+1].must_prune_tokens = false;
485  }
486  }
487  KALDI_VLOG(3) << "PruneActiveTokens: pruned tokens from " << num_toks_begin
488  << " to " << num_toks_;
489 }
std::vector< TokenList > active_toks_
void PruneForwardLinks(int32 frame, bool *extra_costs_changed, bool *links_pruned, BaseFloat delta)
#define KALDI_VLOG(v)
Definition: kaldi-error.h:136
void PruneCurrentTokens ( BaseFloat  beam,
unordered_map< StateId, Token * > *  toks 
)
private

Definition at line 634 of file lattice-simple-decoder.cc.

References rnnlm::i, and KALDI_VLOG.

Referenced by LatticeSimpleDecoder::Decode().

634  {
635  if (toks->empty()) {
636  KALDI_VLOG(2) << "No tokens to prune.\n";
637  return;
638  }
639  BaseFloat best_cost = 1.0e+10; // positive == high cost == bad.
640  for (unordered_map<StateId, Token*>::iterator iter = toks->begin();
641  iter != toks->end(); ++iter) {
642  best_cost =
643  std::min(best_cost,
644  static_cast<BaseFloat>(iter->second->tot_cost));
645  }
646  std::vector<StateId> retained;
647  BaseFloat cutoff = best_cost + beam;
648  for (unordered_map<StateId, Token*>::iterator iter = toks->begin();
649  iter != toks->end(); ++iter) {
650  if (iter->second->tot_cost < cutoff)
651  retained.push_back(iter->first);
652  }
653  unordered_map<StateId, Token*> tmp;
654  for (size_t i = 0; i < retained.size(); i++) {
655  tmp[retained[i]] = (*toks)[retained[i]];
656  }
657  KALDI_VLOG(2) << "Pruned to "<<(retained.size())<<" toks.\n";
658  tmp.swap(*toks);
659 }
float BaseFloat
Definition: kaldi-types.h:29
#define KALDI_VLOG(v)
Definition: kaldi-error.h:136
void PruneForwardLinks ( int32  frame,
bool *  extra_costs_changed,
bool *  links_pruned,
BaseFloat  delta 
)
private

Definition at line 228 of file lattice-simple-decoder.cc.

References LatticeSimpleDecoder::ForwardLink::acoustic_cost, LatticeSimpleDecoder::active_toks_, LatticeSimpleDecoder::config_, LatticeSimpleDecoder::Token::extra_cost, LatticeSimpleDecoder::ForwardLink::graph_cost, KALDI_ASSERT, KALDI_WARN, LatticeSimpleDecoderConfig::lattice_beam, LatticeSimpleDecoder::ForwardLink::next, LatticeSimpleDecoder::ForwardLink::next_tok, LatticeSimpleDecoder::Token::tot_cost, and LatticeSimpleDecoder::warned_.

Referenced by LatticeSimpleDecoder::FinalizeDecoding(), and LatticeSimpleDecoder::PruneActiveTokens().

230  {
231  // We have to iterate until there is no more change, because the links
232  // are not guaranteed to be in topological order.
233 
234  *extra_costs_changed = false;
235  *links_pruned = false;
236  KALDI_ASSERT(frame >= 0 && frame < active_toks_.size());
237  if (active_toks_[frame].toks == NULL ) { // empty list; this should
238  // not happen.
239  if (!warned_) {
240  KALDI_WARN << "No tokens alive [doing pruning].. warning first "
241  "time only for each utterance\n";
242  warned_ = true;
243  }
244  }
245 
246  bool changed = true;
247  while (changed) {
248  changed = false;
249  for (Token *tok = active_toks_[frame].toks; tok != NULL; tok = tok->next) {
250  ForwardLink *link, *prev_link = NULL;
251  // will recompute tok_extra_cost.
252  BaseFloat tok_extra_cost = std::numeric_limits<BaseFloat>::infinity();
253  for (link = tok->links; link != NULL; ) {
254  // See if we need to excise this link...
255  Token *next_tok = link->next_tok;
256  BaseFloat link_extra_cost = next_tok->extra_cost +
257  ((tok->tot_cost + link->acoustic_cost + link->graph_cost)
258  - next_tok->tot_cost);
259  KALDI_ASSERT(link_extra_cost == link_extra_cost); // check for NaN
260  if (link_extra_cost > config_.lattice_beam) { // excise link
261  ForwardLink *next_link = link->next;
262  if (prev_link != NULL) prev_link->next = next_link;
263  else tok->links = next_link;
264  delete link;
265  link = next_link; // advance link but leave prev_link the same.
266  *links_pruned = true;
267  } else { // keep the link and update the tok_extra_cost if needed.
268  if (link_extra_cost < 0.0) { // this is just a precaution.
269  if (link_extra_cost < -0.01)
270  KALDI_WARN << "Negative extra_cost: " << link_extra_cost;
271  link_extra_cost = 0.0;
272  }
273  if (link_extra_cost < tok_extra_cost)
274  tok_extra_cost = link_extra_cost;
275  prev_link = link;
276  link = link->next;
277  }
278  }
279  if (fabs(tok_extra_cost - tok->extra_cost) > delta)
280  changed = true;
281  tok->extra_cost = tok_extra_cost; // will be +infinity or <= lattice_beam_.
282  }
283  if (changed) *extra_costs_changed = true;
284 
285  // Note: it's theoretically possible that aggressive compiler
286  // optimizations could cause an infinite loop here for small delta and
287  // high-dynamic-range scores.
288  }
289 }
std::vector< TokenList > active_toks_
LatticeSimpleDecoderConfig config_
float BaseFloat
Definition: kaldi-types.h:29
#define KALDI_WARN
Definition: kaldi-error.h:130
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void PruneForwardLinksFinal ( )
private

Definition at line 338 of file lattice-simple-decoder.cc.

References LatticeSimpleDecoder::ForwardLink::acoustic_cost, LatticeSimpleDecoder::active_toks_, kaldi::ApproxEqual(), LatticeSimpleDecoder::ComputeFinalCosts(), LatticeSimpleDecoder::config_, LatticeSimpleDecoder::cur_toks_, LatticeSimpleDecoder::decoding_finalized_, LatticeSimpleDecoder::Token::extra_cost, LatticeSimpleDecoder::final_best_cost_, LatticeSimpleDecoder::final_costs_, LatticeSimpleDecoder::final_relative_cost_, LatticeSimpleDecoder::ForwardLink::graph_cost, KALDI_ASSERT, KALDI_WARN, LatticeSimpleDecoderConfig::lattice_beam, LatticeSimpleDecoder::ForwardLink::next, LatticeSimpleDecoder::ForwardLink::next_tok, and LatticeSimpleDecoder::Token::tot_cost.

Referenced by LatticeSimpleDecoder::FinalizeDecoding().

338  {
339  KALDI_ASSERT(!active_toks_.empty());
340  int32 frame_plus_one = active_toks_.size() - 1;
341 
342  if (active_toks_[frame_plus_one].toks == NULL) // empty list; should not happen.
343  KALDI_WARN << "No tokens alive at end of file\n";
344 
345  typedef unordered_map<Token*, BaseFloat>::const_iterator IterType;
347  decoding_finalized_ = true;
348  // We're about to delete some of the tokens active on the final frame, so we
349  // clear cur_toks_ because otherwise it would then contain dangling pointers.
350  cur_toks_.clear();
351 
352  // Now go through tokens on this frame, pruning forward links... may have to
353  // iterate a few times until there is no more change, because the list is not
354  // in topological order. This is a modified version of the code in
355  // PruneForwardLinks, but here we also take account of the final-probs.
356  bool changed = true;
357  BaseFloat delta = 1.0e-05;
358  while (changed) {
359  changed = false;
360  for (Token *tok = active_toks_[frame_plus_one].toks;
361  tok != NULL; tok = tok->next) {
362  ForwardLink *link, *prev_link=NULL;
363  // will recompute tok_extra_cost. It has a term in it that corresponds
364  // to the "final-prob", so instead of initializing tok_extra_cost to infinity
365  // below we set it to the difference between the (score+final_prob) of this token,
366  // and the best such (score+final_prob).
367 
368  BaseFloat final_cost;
369  if (final_costs_.empty()) {
370  final_cost = 0.0;
371  } else {
372  IterType iter = final_costs_.find(tok);
373  if (iter != final_costs_.end())
374  final_cost = iter->second;
375  else
376  final_cost = std::numeric_limits<BaseFloat>::infinity();
377  }
378  BaseFloat tok_extra_cost = tok->tot_cost + final_cost - final_best_cost_;
379  // tok_extra_cost will be a "min" over either directly being final, or
380  // being indirectly final through other links, and the loop below may
381  // decrease its value:
382  for (link = tok->links; link != NULL; ) {
383  // See if we need to excise this link...
384  Token *next_tok = link->next_tok;
385  BaseFloat link_extra_cost = next_tok->extra_cost +
386  ((tok->tot_cost + link->acoustic_cost + link->graph_cost)
387  - next_tok->tot_cost);
388  if (link_extra_cost > config_.lattice_beam) { // excise link
389  ForwardLink *next_link = link->next;
390  if (prev_link != NULL) prev_link->next = next_link;
391  else tok->links = next_link;
392  delete link;
393  link = next_link; // advance link but leave prev_link the same.
394  } else { // keep the link and update the tok_extra_cost if needed.
395  if (link_extra_cost < 0.0) { // this is just a precaution.
396  if (link_extra_cost < -0.01)
397  KALDI_WARN << "Negative extra_cost: " << link_extra_cost;
398  link_extra_cost = 0.0;
399  }
400  if (link_extra_cost < tok_extra_cost)
401  tok_extra_cost = link_extra_cost;
402  prev_link = link;
403  link = link->next;
404  }
405  }
406  // prune away tokens worse than lattice_beam above best path. This step
407  // was not necessary in the non-final case because then, this case
408  // showed up as having no forward links. Here, the tok_extra_cost has
409  // an extra component relating to the final-prob.
410  if (tok_extra_cost > config_.lattice_beam)
411  tok_extra_cost = std::numeric_limits<BaseFloat>::infinity();
412  // to be pruned in PruneTokensForFrame
413 
414  if (!ApproxEqual(tok->extra_cost, tok_extra_cost, delta))
415  changed = true;
416  tok->extra_cost = tok_extra_cost; // will be +infinity or <= lattice_beam_.
417  }
418  } // while changed
419 }
std::vector< TokenList > active_toks_
LatticeSimpleDecoderConfig config_
bool decoding_finalized_
decoding_finalized_ is true if someone called FinalizeDecoding().
unordered_map< Token *, BaseFloat > final_costs_
For the meaning of the next 3 variables, see the comment for decoding_finalized_ above., and ComputeFinalCosts().
void ComputeFinalCosts(unordered_map< Token *, BaseFloat > *final_costs, BaseFloat *final_relative_cost, BaseFloat *final_best_cost) const
float BaseFloat
Definition: kaldi-types.h:29
#define KALDI_WARN
Definition: kaldi-error.h:130
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
unordered_map< StateId, Token * > cur_toks_
static bool ApproxEqual(float a, float b, float relative_tolerance=0.001)
return abs(a - b) <= relative_tolerance * (abs(a)+abs(b)).
Definition: kaldi-math.h:262
void PruneTokensForFrame ( int32  frame)
private

Definition at line 436 of file lattice-simple-decoder.cc.

References LatticeSimpleDecoder::active_toks_, LatticeSimpleDecoder::Token::extra_cost, KALDI_ASSERT, KALDI_WARN, LatticeSimpleDecoder::Token::next, and LatticeSimpleDecoder::num_toks_.

Referenced by LatticeSimpleDecoder::FinalizeDecoding(), and LatticeSimpleDecoder::PruneActiveTokens().

436  {
437  KALDI_ASSERT(frame >= 0 && frame < active_toks_.size());
438  Token *&toks = active_toks_[frame].toks;
439  if (toks == NULL)
440  KALDI_WARN << "No tokens alive [doing pruning]";
441  Token *tok, *next_tok, *prev_tok = NULL;
442  for (tok = toks; tok != NULL; tok = next_tok) {
443  next_tok = tok->next;
444  if (tok->extra_cost == std::numeric_limits<BaseFloat>::infinity()) {
445  // Next token is unreachable from end of graph; excise tok from list
446  // and delete tok.
447  if (prev_tok != NULL) prev_tok->next = tok->next;
448  else toks = tok->next;
449  delete tok;
450  num_toks_--;
451  } else {
452  prev_tok = tok;
453  }
454  }
455 }
std::vector< TokenList > active_toks_
#define KALDI_WARN
Definition: kaldi-error.h:130
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
bool ReachedFinal ( ) const
inline

says whether a final-state was active on the last frame.

If it was not, the lattice (or traceback) will end with states that are not final-states.

Definition at line 100 of file lattice-simple-decoder.h.

References LatticeSimpleDecoder::FinalRelativeCost().

Referenced by kaldi::DecodeUtteranceLatticeSimple().

100  {
101  return FinalRelativeCost() != std::numeric_limits<BaseFloat>::infinity();
102  }
BaseFloat FinalRelativeCost() const
FinalRelativeCost() serves the same purpose as ReachedFinal(), but gives more information.

Member Data Documentation

bool decoding_finalized_
private

decoding_finalized_ is true if someone called FinalizeDecoding().

[note, calling this is optional]. If true, it's forbidden to decode more. Also, if this is set, then the output of ComputeFinalCosts() is in the next three variables. The reason we need to do this is that after FinalizeDecoding() calls PruneTokensForFrame() for the final frame, some of the tokens on the last frame are freed, so we free the list from cur_toks_ to avoid having dangling pointers hanging around.

Definition at line 306 of file lattice-simple-decoder.h.

Referenced by LatticeSimpleDecoder::ComputeFinalCosts(), LatticeSimpleDecoder::FinalRelativeCost(), LatticeSimpleDecoder::GetRawLattice(), LatticeSimpleDecoder::InitDecoding(), and LatticeSimpleDecoder::PruneForwardLinksFinal().

BaseFloat final_best_cost_
private
unordered_map<Token*, BaseFloat> final_costs_
private

For the meaning of the next 3 variables, see the comment for decoding_finalized_ above., and ComputeFinalCosts().

Definition at line 309 of file lattice-simple-decoder.h.

Referenced by LatticeSimpleDecoder::Decode(), LatticeSimpleDecoder::GetRawLattice(), LatticeSimpleDecoder::InitDecoding(), and LatticeSimpleDecoder::PruneForwardLinksFinal().

BaseFloat final_relative_cost_
private
unordered_map<StateId, Token*> prev_toks_
private

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