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

A bit more optimized version of the lattice decoder. More...

#include <lattice-faster-decoder.h>

Collaboration diagram for LatticeFasterDecoder:

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

 LatticeFasterDecoder (const fst::Fst< fst::StdArc > &fst, const LatticeFasterDecoderConfig &config)
 
 LatticeFasterDecoder (const LatticeFasterDecoderConfig &config, fst::Fst< fst::StdArc > *fst)
 
void SetOptions (const LatticeFasterDecoderConfig &config)
 
const LatticeFasterDecoderConfigGetOptions () const
 
 ~LatticeFasterDecoder ()
 
bool Decode (DecodableInterface *decodable)
 Decodes until there are no more frames left in the "decodable" object. More...
 
bool ReachedFinal () const
 says whether a final-state was active on the last frame. More...
 
bool GetBestPath (Lattice *ofst, bool use_final_probs=true) const
 Outputs an FST corresponding to the single best path through the lattice. More...
 
bool GetRawLattice (Lattice *ofst, bool use_final_probs=true) const
 Outputs an FST corresponding to the raw, state-level tracebacks. More...
 
bool GetLattice (CompactLattice *ofst, bool use_final_probs=true) const
 [Deprecated, users should now use GetRawLattice and determinize it themselves, e.g. 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. 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...
 
int32 NumFramesDecoded () const
 

Private Types

typedef HashList< StateId,
Token * >::Elem 
Elem
 

Private Member Functions

void PossiblyResizeHash (size_t num_toks)
 
TokenFindOrAddToken (StateId state, int32 frame_plus_one, BaseFloat tot_cost, bool *changed)
 
void PruneForwardLinks (int32 frame_plus_one, bool *extra_costs_changed, bool *links_pruned, BaseFloat delta)
 
void ComputeFinalCosts (unordered_map< Token *, BaseFloat > *final_costs, BaseFloat *final_relative_cost, BaseFloat *final_best_cost) const
 
void PruneForwardLinksFinal ()
 
void PruneTokensForFrame (int32 frame_plus_one)
 
void PruneActiveTokens (BaseFloat delta)
 
BaseFloat GetCutoff (Elem *list_head, size_t *tok_count, BaseFloat *adaptive_beam, Elem **best_elem)
 Gets the weight cutoff. Also counts the active tokens. More...
 
BaseFloat ProcessEmitting (DecodableInterface *decodable)
 Processes emitting arcs for one frame. More...
 
void ProcessNonemitting (BaseFloat cost_cutoff)
 Processes nonemitting (epsilon) arcs for one frame. More...
 
void DeleteElems (Elem *list)
 
void ClearActiveTokens ()
 
 KALDI_DISALLOW_COPY_AND_ASSIGN (LatticeFasterDecoder)
 

Static Private Member Functions

static void TopSortTokens (Token *tok_list, std::vector< Token * > *topsorted_list)
 

Private Attributes

HashList< StateId, Token * > toks_
 
std::vector< TokenListactive_toks_
 
std::vector< StateIdqueue_
 
std::vector< BaseFloattmp_array_
 
const fst::Fst< fst::StdArc > & fst_
 
bool delete_fst_
 
std::vector< BaseFloatcost_offsets_
 
LatticeFasterDecoderConfig 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

A bit more optimized version of the lattice decoder.

See Lattice generation FasterDecoder: a more optimized decoder and SimpleDecoder: the simplest possible decoder for more information.

Definition at line 98 of file lattice-faster-decoder.h.

Member Typedef Documentation

typedef fst::StdArc Arc

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

typedef HashList<StateId, Token*>::Elem Elem
private

Definition at line 267 of file lattice-faster-decoder.h.

typedef Arc::Label Label

Definition at line 101 of file lattice-faster-decoder.h.

typedef Arc::StateId StateId

Definition at line 102 of file lattice-faster-decoder.h.

typedef Arc::Weight Weight

Definition at line 103 of file lattice-faster-decoder.h.

Constructor & Destructor Documentation

LatticeFasterDecoder ( const fst::Fst< fst::StdArc > &  fst,
const LatticeFasterDecoderConfig config 
)

Definition at line 33 of file lattice-faster-decoder.cc.

References LatticeFasterDecoderConfig::Check(), HashList< I, T >::SetSize(), and LatticeFasterDecoder::toks_.

34  :
35  fst_(fst), delete_fst_(false), config_(config), num_toks_(0) {
36  config.Check();
37  toks_.SetSize(1000); // just so on the first frame we do something reasonable.
38 }
HashList< StateId, Token * > toks_
Definition: graph.dox:21
const fst::Fst< fst::StdArc > & fst_
void SetSize(size_t sz)
SetSize tells the object how many hash buckets to allocate (should typically be at least twice the nu...
Definition: hash-list-inl.h:37
LatticeFasterDecoderConfig config_
LatticeFasterDecoder ( const LatticeFasterDecoderConfig config,
fst::Fst< fst::StdArc > *  fst 
)

Definition at line 41 of file lattice-faster-decoder.cc.

References LatticeFasterDecoderConfig::Check(), HashList< I, T >::SetSize(), and LatticeFasterDecoder::toks_.

42  :
43  fst_(*fst), delete_fst_(true), config_(config), num_toks_(0) {
44  config.Check();
45  toks_.SetSize(1000); // just so on the first frame we do something reasonable.
46 }
HashList< StateId, Token * > toks_
Definition: graph.dox:21
const fst::Fst< fst::StdArc > & fst_
void SetSize(size_t sz)
SetSize tells the object how many hash buckets to allocate (should typically be at least twice the nu...
Definition: hash-list-inl.h:37
LatticeFasterDecoderConfig config_

Definition at line 49 of file lattice-faster-decoder.cc.

References HashList< I, T >::Clear(), LatticeFasterDecoder::ClearActiveTokens(), LatticeFasterDecoder::delete_fst_, LatticeFasterDecoder::DeleteElems(), LatticeFasterDecoder::fst_, and LatticeFasterDecoder::toks_.

49  {
52  if (delete_fst_) delete &(fst_);
53 }
HashList< StateId, Token * > toks_
const fst::Fst< fst::StdArc > & fst_
Elem * Clear()
Clears the hash and gives the head of the current list to the user; ownership is transferred to the u...
Definition: hash-list-inl.h:46

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.

You can keep calling it each time more frames become available. If max_num_frames is specified, it specifies the maximum number of frames the function will decode before returning.

Definition at line 573 of file lattice-faster-decoder.cc.

References LatticeFasterDecoder::active_toks_, LatticeFasterDecoder::config_, LatticeFasterDecoder::decoding_finalized_, KALDI_ASSERT, LatticeFasterDecoderConfig::lattice_beam, LatticeFasterDecoder::NumFramesDecoded(), DecodableInterface::NumFramesReady(), LatticeFasterDecoder::ProcessEmitting(), LatticeFasterDecoder::ProcessNonemitting(), LatticeFasterDecoderConfig::prune_interval, LatticeFasterDecoderConfig::prune_scale, and LatticeFasterDecoder::PruneActiveTokens().

574  {
576  "You must call InitDecoding() before AdvanceDecoding");
577  int32 num_frames_ready = decodable->NumFramesReady();
578  // num_frames_ready must be >= num_frames_decoded, or else
579  // the number of frames ready must have decreased (which doesn't
580  // make sense) or the decodable object changed between calls
581  // (which isn't allowed).
582  KALDI_ASSERT(num_frames_ready >= NumFramesDecoded());
583  int32 target_frames_decoded = num_frames_ready;
584  if (max_num_frames >= 0)
585  target_frames_decoded = std::min(target_frames_decoded,
586  NumFramesDecoded() + max_num_frames);
587  while (NumFramesDecoded() < target_frames_decoded) {
588  if (NumFramesDecoded() % config_.prune_interval == 0) {
590  }
591  BaseFloat cost_cutoff = ProcessEmitting(decodable);
592  ProcessNonemitting(cost_cutoff);
593  }
594 }
void PruneActiveTokens(BaseFloat delta)
std::vector< TokenList > active_toks_
BaseFloat ProcessEmitting(DecodableInterface *decodable)
Processes emitting arcs for one frame.
float BaseFloat
Definition: kaldi-types.h:29
void ProcessNonemitting(BaseFloat cost_cutoff)
Processes nonemitting (epsilon) arcs for one frame.
bool decoding_finalized_
decoding_finalized_ is true if someone called FinalizeDecoding().
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
LatticeFasterDecoderConfig config_
void ClearActiveTokens ( )
private

Definition at line 848 of file lattice-faster-decoder.cc.

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

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

848  { // a cleanup routine, at utt end/begin
849  for (size_t i = 0; i < active_toks_.size(); i++) {
850  // Delete all tokens alive on this frame, and any forward
851  // links they may have.
852  for (Token *tok = active_toks_[i].toks; tok != NULL; ) {
853  tok->DeleteForwardLinks();
854  Token *next_tok = tok->next;
855  delete tok;
856  num_toks_--;
857  tok = next_tok;
858  }
859  }
860  active_toks_.clear();
861  KALDI_ASSERT(num_toks_ == 0);
862 }
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 531 of file lattice-faster-decoder.cc.

References LatticeFasterDecoder::decoding_finalized_, LatticeFasterDecoder::fst_, HashList< I, T >::GetList(), KALDI_ASSERT, LatticeFasterDecoder::toks_, and LatticeFasterDecoder::Token::tot_cost.

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

534  {
536  if (final_costs != NULL)
537  final_costs->clear();
538  const Elem *final_toks = toks_.GetList();
539  BaseFloat infinity = std::numeric_limits<BaseFloat>::infinity();
540  BaseFloat best_cost = infinity,
541  best_cost_with_final = infinity;
542  while (final_toks != NULL) {
543  StateId state = final_toks->key;
544  Token *tok = final_toks->val;
545  const Elem *next = final_toks->tail;
546  BaseFloat final_cost = fst_.Final(state).Value();
547  BaseFloat cost = tok->tot_cost,
548  cost_with_final = cost + final_cost;
549  best_cost = std::min(cost, best_cost);
550  best_cost_with_final = std::min(cost_with_final, best_cost_with_final);
551  if (final_costs != NULL && final_cost != infinity)
552  (*final_costs)[tok] = final_cost;
553  final_toks = next;
554  }
555  if (final_relative_cost != NULL) {
556  if (best_cost == infinity && best_cost_with_final == infinity) {
557  // Likely this will only happen if there are no tokens surviving.
558  // This seems the least bad way to handle it.
559  *final_relative_cost = infinity;
560  } else {
561  *final_relative_cost = best_cost_with_final - best_cost;
562  }
563  }
564  if (final_best_cost != NULL) {
565  if (best_cost_with_final != infinity) { // final-state exists.
566  *final_best_cost = best_cost_with_final;
567  } else { // no final-state exists.
568  *final_best_cost = best_cost;
569  }
570  }
571 }
HashList< StateId, Token * > toks_
const fst::Fst< fst::StdArc > & fst_
float BaseFloat
Definition: kaldi-types.h:29
bool decoding_finalized_
decoding_finalized_ is true if someone called FinalizeDecoding().
const Elem * GetList() const
Gives the head of the current list to the user.
Definition: hash-list-inl.h:61
HashList< StateId, Token * >::Elem Elem
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
bool Decode ( DecodableInterface decodable)

Decodes until there are no more frames left in the "decodable" object.

note, this may block waiting for input if the "decodable" object blocks. Returns true if any kind of traceback is available (not necessarily from a final state).

Definition at line 77 of file lattice-faster-decoder.cc.

References LatticeFasterDecoder::active_toks_, LatticeFasterDecoder::config_, LatticeFasterDecoder::FinalizeDecoding(), LatticeFasterDecoder::InitDecoding(), DecodableInterface::IsLastFrame(), LatticeFasterDecoderConfig::lattice_beam, LatticeFasterDecoder::NumFramesDecoded(), LatticeFasterDecoder::ProcessEmitting(), LatticeFasterDecoder::ProcessNonemitting(), LatticeFasterDecoderConfig::prune_interval, LatticeFasterDecoderConfig::prune_scale, and LatticeFasterDecoder::PruneActiveTokens().

Referenced by kaldi::DecodeUtteranceLatticeFaster(), and DecodeUtteranceLatticeFasterClass::operator()().

77  {
78  InitDecoding();
79 
80  // We use 1-based indexing for frames in this decoder (if you view it in
81  // terms of features), but note that the decodable object uses zero-based
82  // numbering, which we have to correct for when we call it.
83 
84  while (!decodable->IsLastFrame(NumFramesDecoded() - 1)) {
87  BaseFloat cost_cutoff = ProcessEmitting(decodable);
88  ProcessNonemitting(cost_cutoff);
89  }
91 
92  // Returns true if we have any kind of traceback available (not necessarily
93  // to the end state; query ReachedFinal() for that).
94  return !active_toks_.empty() && active_toks_.back().toks != NULL;
95 }
void FinalizeDecoding()
This function may be optionally called after AdvanceDecoding(), when you do not plan to decode any fu...
void PruneActiveTokens(BaseFloat delta)
std::vector< TokenList > active_toks_
BaseFloat ProcessEmitting(DecodableInterface *decodable)
Processes emitting arcs for one frame.
float BaseFloat
Definition: kaldi-types.h:29
void ProcessNonemitting(BaseFloat cost_cutoff)
Processes nonemitting (epsilon) arcs for one frame.
void InitDecoding()
InitDecoding initializes the decoding, and should only be used if you intend to call AdvanceDecoding(...
LatticeFasterDecoderConfig config_
void DeleteElems ( Elem list)
private

Definition at line 841 of file lattice-faster-decoder.cc.

References HashList< I, T >::Delete(), and LatticeFasterDecoder::toks_.

Referenced by LatticeFasterDecoder::InitDecoding(), LatticeFasterDecoder::PruneForwardLinksFinal(), and LatticeFasterDecoder::~LatticeFasterDecoder().

841  {
842  for (Elem *e = list, *e_tail; e != NULL; e = e_tail) {
843  e_tail = e->tail;
844  toks_.Delete(e);
845  }
846 }
HashList< StateId, Token * > toks_
HashList< StateId, Token * >::Elem Elem
void Delete(Elem *e)
Think of this like delete().
Definition: hash-list-inl.h:66
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 599 of file lattice-faster-decoder.cc.

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

Referenced by LatticeFasterDecoder::Decode().

599  {
600  int32 final_frame_plus_one = NumFramesDecoded();
601  int32 num_toks_begin = num_toks_;
602  // PruneForwardLinksFinal() prunes final frame (with final-probs), and
603  // sets decoding_finalized_.
605  for (int32 f = final_frame_plus_one - 1; f >= 0; f--) {
606  bool b1, b2; // values not used.
607  BaseFloat dontcare = 0.0; // delta of zero means we must always update
608  PruneForwardLinks(f, &b1, &b2, dontcare);
609  PruneTokensForFrame(f + 1);
610  }
612  KALDI_VLOG(4) << "pruned tokens from " << num_toks_begin
613  << " to " << num_toks_;
614 }
void PruneForwardLinks(int32 frame_plus_one, bool *extra_costs_changed, bool *links_pruned, BaseFloat delta)
float BaseFloat
Definition: kaldi-types.h:29
void PruneTokensForFrame(int32 frame_plus_one)
#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 459 of file lattice-faster-decoder.cc.

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

Referenced by LatticeFasterDecoder::ReachedFinal().

459  {
460  if (!decoding_finalized_) {
461  BaseFloat relative_cost;
462  ComputeFinalCosts(NULL, &relative_cost, NULL);
463  return relative_cost;
464  } else {
465  // we're not allowed to call that function if FinalizeDecoding() has
466  // been called; return a cached value.
467  return final_relative_cost_;
468  }
469 }
float BaseFloat
Definition: kaldi-types.h:29
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
LatticeFasterDecoder::Token * FindOrAddToken ( StateId  state,
int32  frame_plus_one,
BaseFloat  tot_cost,
bool *  changed 
)
inlineprivate

Definition at line 258 of file lattice-faster-decoder.cc.

References LatticeFasterDecoder::active_toks_, HashList< I, T >::Find(), HashList< I, T >::Insert(), KALDI_ASSERT, LatticeFasterDecoder::num_toks_, LatticeFasterDecoder::toks_, and LatticeFasterDecoder::Token::tot_cost.

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

259  {
260  // Returns the Token pointer. Sets "changed" (if non-NULL) to true
261  // if the token was newly created or the cost changed.
262  KALDI_ASSERT(frame_plus_one < active_toks_.size());
263  Token *&toks = active_toks_[frame_plus_one].toks;
264  Elem *e_found = toks_.Find(state);
265  if (e_found == NULL) { // no such token presently.
266  const BaseFloat extra_cost = 0.0;
267  // tokens on the currently final frame have zero extra_cost
268  // as any of them could end up
269  // on the winning path.
270  Token *new_tok = new Token (tot_cost, extra_cost, NULL, toks);
271  // NULL: no forward links yet
272  toks = new_tok;
273  num_toks_++;
274  toks_.Insert(state, new_tok);
275  if (changed) *changed = true;
276  return new_tok;
277  } else {
278  Token *tok = e_found->val; // There is an existing Token for this state.
279  if (tok->tot_cost > tot_cost) { // replace old token
280  tok->tot_cost = tot_cost;
281  // we don't allocate a new token, the old stays linked in active_toks_
282  // we only replace the tot_cost
283  // in the current frame, there are no forward links (and no extra_cost)
284  // only in ProcessNonemitting we have to delete forward links
285  // in case we visit a state for the second time
286  // those forward links, that lead to this replaced token before:
287  // they remain and will hopefully be pruned later (PruneForwardLinks...)
288  if (changed) *changed = true;
289  } else {
290  if (changed) *changed = false;
291  }
292  return tok;
293  }
294 }
HashList< StateId, Token * > toks_
std::vector< TokenList > active_toks_
void Insert(I key, T val)
Insert inserts a new element into the hashtable/stored list.
float BaseFloat
Definition: kaldi-types.h:29
HashList< StateId, Token * >::Elem Elem
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
Elem * Find(I key)
Find tries to find this element in the current list using the hashtable.
Definition: hash-list-inl.h:72
bool GetBestPath ( Lattice ofst,
bool  use_final_probs = true 
) const

Outputs an FST corresponding to the single best path through the lattice.

Returns true if result is nonempty (using the return status is deprecated, it will become void). If "use_final_probs" is true AND we reached the final-state of the graph then it will include those as final-probs, else it will treat all final-probs as one. Note: this just calls GetRawLattice() and figures out the shortest path.

Definition at line 99 of file lattice-faster-decoder.cc.

References LatticeFasterDecoder::GetRawLattice().

Referenced by kaldi::DecodeUtteranceLatticeFaster(), and DecodeUtteranceLatticeFasterClass::~DecodeUtteranceLatticeFasterClass().

100  {
101  Lattice raw_lat;
102  GetRawLattice(&raw_lat, use_final_probs);
103  ShortestPath(raw_lat, olat);
104  return (olat->NumStates() != 0);
105 }
bool GetRawLattice(Lattice *ofst, bool use_final_probs=true) const
Outputs an FST corresponding to the raw, state-level tracebacks.
fst::VectorFst< LatticeArc > Lattice
Definition: kaldi-lattice.h:44
BaseFloat GetCutoff ( Elem list_head,
size_t *  tok_count,
BaseFloat adaptive_beam,
Elem **  best_elem 
)
private

Gets the weight cutoff. Also counts the active tokens.

Definition at line 617 of file lattice-faster-decoder.cc.

References LatticeFasterDecoderConfig::beam, LatticeFasterDecoderConfig::beam_delta, LatticeFasterDecoder::config_, count, KALDI_VLOG, LatticeFasterDecoderConfig::max_active, LatticeFasterDecoderConfig::min_active, LatticeFasterDecoder::NumFramesDecoded(), and LatticeFasterDecoder::tmp_array_.

Referenced by LatticeFasterDecoder::ProcessEmitting().

618  {
619  BaseFloat best_weight = std::numeric_limits<BaseFloat>::infinity();
620  // positive == high cost == bad.
621  size_t count = 0;
622  if (config_.max_active == std::numeric_limits<int32>::max() &&
623  config_.min_active == 0) {
624  for (Elem *e = list_head; e != NULL; e = e->tail, count++) {
625  BaseFloat w = static_cast<BaseFloat>(e->val->tot_cost);
626  if (w < best_weight) {
627  best_weight = w;
628  if (best_elem) *best_elem = e;
629  }
630  }
631  if (tok_count != NULL) *tok_count = count;
632  if (adaptive_beam != NULL) *adaptive_beam = config_.beam;
633  return best_weight + config_.beam;
634  } else {
635  tmp_array_.clear();
636  for (Elem *e = list_head; e != NULL; e = e->tail, count++) {
637  BaseFloat w = e->val->tot_cost;
638  tmp_array_.push_back(w);
639  if (w < best_weight) {
640  best_weight = w;
641  if (best_elem) *best_elem = e;
642  }
643  }
644  if (tok_count != NULL) *tok_count = count;
645 
646  BaseFloat beam_cutoff = best_weight + config_.beam,
647  min_active_cutoff = std::numeric_limits<BaseFloat>::infinity(),
648  max_active_cutoff = std::numeric_limits<BaseFloat>::infinity();
649 
650  KALDI_VLOG(6) << "Number of tokens active on frame " << NumFramesDecoded()
651  << " is " << tmp_array_.size();
652 
653  if (tmp_array_.size() > static_cast<size_t>(config_.max_active)) {
654  std::nth_element(tmp_array_.begin(),
655  tmp_array_.begin() + config_.max_active,
656  tmp_array_.end());
657  max_active_cutoff = tmp_array_[config_.max_active];
658  }
659  if (max_active_cutoff < beam_cutoff) { // max_active is tighter than beam.
660  if (adaptive_beam)
661  *adaptive_beam = max_active_cutoff - best_weight + config_.beam_delta;
662  return max_active_cutoff;
663  }
664  if (tmp_array_.size() > static_cast<size_t>(config_.min_active)) {
665  if (config_.min_active == 0) min_active_cutoff = best_weight;
666  else {
667  std::nth_element(tmp_array_.begin(),
668  tmp_array_.begin() + config_.min_active,
669  tmp_array_.size() > static_cast<size_t>(config_.max_active) ?
670  tmp_array_.begin() + config_.max_active :
671  tmp_array_.end());
672  min_active_cutoff = tmp_array_[config_.min_active];
673  }
674  }
675  if (min_active_cutoff > beam_cutoff) { // min_active is looser than beam.
676  if (adaptive_beam)
677  *adaptive_beam = min_active_cutoff - best_weight + config_.beam_delta;
678  return min_active_cutoff;
679  } else {
680  *adaptive_beam = config_.beam;
681  return beam_cutoff;
682  }
683  }
684 }
std::vector< BaseFloat > tmp_array_
const size_t count
float BaseFloat
Definition: kaldi-types.h:29
HashList< StateId, Token * >::Elem Elem
#define KALDI_VLOG(v)
Definition: kaldi-error.h:136
LatticeFasterDecoderConfig config_
bool GetLattice ( CompactLattice ofst,
bool  use_final_probs = true 
) const

[Deprecated, users should now use GetRawLattice and determinize it themselves, e.g.

using DeterminizeLatticePhonePrunedWrapper]. Outputs an FST corresponding to the lattice-determinized lattice (one path per word sequence). Returns true if result is nonempty. If "use_final_probs" is true AND we reached the final-state of the graph then it will include those as final-probs, else it will treat all final-probs as one.

Definition at line 197 of file lattice-faster-decoder.cc.

References LatticeFasterDecoder::config_, LatticeFasterDecoderConfig::det_opts, fst::DeterminizeLatticePruned(), LatticeFasterDecoder::GetRawLattice(), LatticeFasterDecoderConfig::lattice_beam, DeterminizeLatticePrunedOptions::max_mem, and DeterminizeLatticePhonePrunedOptions::max_mem.

198  {
199  Lattice raw_fst;
200  GetRawLattice(&raw_fst, use_final_probs);
201  Invert(&raw_fst); // make it so word labels are on the input.
202  // (in phase where we get backward-costs).
203  fst::ILabelCompare<LatticeArc> ilabel_comp;
204  ArcSort(&raw_fst, ilabel_comp); // sort on ilabel; makes
205  // lattice-determinization more efficient.
206 
208  lat_opts.max_mem = config_.det_opts.max_mem;
209 
210  DeterminizeLatticePruned(raw_fst, config_.lattice_beam, ofst, lat_opts);
211  raw_fst.DeleteStates(); // Free memory-- raw_fst no longer needed.
212  Connect(ofst); // Remove unreachable states... there might be
213  // a small number of these, in some cases.
214  // Note: if something went wrong and the raw lattice was empty,
215  // we should still get to this point in the code without warnings or failures.
216  return (ofst->NumStates() != 0);
217 }
bool GetRawLattice(Lattice *ofst, bool use_final_probs=true) const
Outputs an FST corresponding to the raw, state-level tracebacks.
bool DeterminizeLatticePruned(const ExpandedFst< ArcTpl< Weight > > &ifst, double beam, MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > *ofst, DeterminizeLatticePrunedOptions opts)
fst::VectorFst< LatticeArc > Lattice
Definition: kaldi-lattice.h:44
fst::DeterminizeLatticePhonePrunedOptions det_opts
LatticeFasterDecoderConfig config_
const LatticeFasterDecoderConfig& GetOptions ( ) const
inline

Definition at line 119 of file lattice-faster-decoder.h.

References LatticeFasterDecoder::config_.

Referenced by kaldi::DecodeUtteranceLatticeFaster(), and DecodeUtteranceLatticeFasterClass::operator()().

119  {
120  return config_;
121  }
LatticeFasterDecoderConfig config_
bool GetRawLattice ( Lattice ofst,
bool  use_final_probs = true 
) const

Outputs an FST corresponding to the raw, state-level tracebacks.

Returns true if result is nonempty. If "use_final_probs" is true AND we reached the final-state of the graph then it will include those as final-probs, else it will treat all final-probs as one. The raw lattice will be topologically sorted.

Definition at line 109 of file lattice-faster-decoder.cc.

References LatticeFasterDecoder::active_toks_, LatticeFasterDecoder::ComputeFinalCosts(), LatticeFasterDecoder::cost_offsets_, LatticeFasterDecoder::decoding_finalized_, LatticeFasterDecoder::final_costs_, rnnlm::i, KALDI_ASSERT, KALDI_ERR, KALDI_VLOG, KALDI_WARN, LatticeFasterDecoder::ForwardLink::next, LatticeFasterDecoder::num_toks_, LatticeWeightTpl< BaseFloat >::One(), and LatticeFasterDecoder::TopSortTokens().

Referenced by kaldi::DecodeUtteranceLatticeFaster(), LatticeFasterDecoder::GetBestPath(), LatticeFasterDecoder::GetLattice(), and DecodeUtteranceLatticeFasterClass::operator()().

110  {
111  typedef LatticeArc Arc;
112  typedef Arc::StateId StateId;
113  typedef Arc::Weight Weight;
114  typedef Arc::Label Label;
115 
116  // Note: you can't use the old interface (Decode()) if you want to
117  // get the lattice with use_final_probs = false. You'd have to do
118  // InitDecoding() and then AdvanceDecoding().
119  if (decoding_finalized_ && !use_final_probs)
120  KALDI_ERR << "You cannot call FinalizeDecoding() and then call "
121  << "GetRawLattice() with use_final_probs == false";
122 
123  unordered_map<Token*, BaseFloat> final_costs_local;
124 
125  const unordered_map<Token*, BaseFloat> &final_costs =
126  (decoding_finalized_ ? final_costs_ : final_costs_local);
127  if (!decoding_finalized_ && use_final_probs)
128  ComputeFinalCosts(&final_costs_local, NULL, NULL);
129 
130  ofst->DeleteStates();
131  // num-frames plus one (since frames are one-based, and we have
132  // an extra frame for the start-state).
133  int32 num_frames = active_toks_.size() - 1;
134  KALDI_ASSERT(num_frames > 0);
135  const int32 bucket_count = num_toks_/2 + 3;
136  unordered_map<Token*, StateId> tok_map(bucket_count);
137  // First create all states.
138  std::vector<Token*> token_list;
139  for (int32 f = 0; f <= num_frames; f++) {
140  if (active_toks_[f].toks == NULL) {
141  KALDI_WARN << "GetRawLattice: no tokens active on frame " << f
142  << ": not producing lattice.\n";
143  return false;
144  }
145  TopSortTokens(active_toks_[f].toks, &token_list);
146  for (size_t i = 0; i < token_list.size(); i++)
147  if (token_list[i] != NULL)
148  tok_map[token_list[i]] = ofst->AddState();
149  }
150  // The next statement sets the start state of the output FST. Because we
151  // topologically sorted the tokens, state zero must be the start-state.
152  ofst->SetStart(0);
153 
154  KALDI_VLOG(4) << "init:" << num_toks_/2 + 3 << " buckets:"
155  << tok_map.bucket_count() << " load:" << tok_map.load_factor()
156  << " max:" << tok_map.max_load_factor();
157  // Now create all arcs.
158  for (int32 f = 0; f <= num_frames; f++) {
159  for (Token *tok = active_toks_[f].toks; tok != NULL; tok = tok->next) {
160  StateId cur_state = tok_map[tok];
161  for (ForwardLink *l = tok->links;
162  l != NULL;
163  l = l->next) {
164  unordered_map<Token*, StateId>::const_iterator iter =
165  tok_map.find(l->next_tok);
166  StateId nextstate = iter->second;
167  KALDI_ASSERT(iter != tok_map.end());
168  BaseFloat cost_offset = 0.0;
169  if (l->ilabel != 0) { // emitting..
170  KALDI_ASSERT(f >= 0 && f < cost_offsets_.size());
171  cost_offset = cost_offsets_[f];
172  }
173  Arc arc(l->ilabel, l->olabel,
174  Weight(l->graph_cost, l->acoustic_cost - cost_offset),
175  nextstate);
176  ofst->AddArc(cur_state, arc);
177  }
178  if (f == num_frames) {
179  if (use_final_probs && !final_costs.empty()) {
180  unordered_map<Token*, BaseFloat>::const_iterator iter =
181  final_costs.find(tok);
182  if (iter != final_costs.end())
183  ofst->SetFinal(cur_state, LatticeWeight(iter->second, 0));
184  } else {
185  ofst->SetFinal(cur_state, LatticeWeight::One());
186  }
187  }
188  }
189  }
190  return (ofst->NumStates() > 0);
191 }
fst::StdArc::StateId StateId
fst::ArcTpl< LatticeWeight > LatticeArc
Definition: kaldi-lattice.h:40
std::vector< BaseFloat > cost_offsets_
std::vector< TokenList > active_toks_
static void TopSortTokens(Token *tok_list, std::vector< Token * > *topsorted_list)
fst::LatticeWeightTpl< BaseFloat > LatticeWeight
Definition: kaldi-lattice.h:32
float BaseFloat
Definition: kaldi-types.h:29
static const LatticeWeightTpl One()
#define KALDI_ERR
Definition: kaldi-error.h:127
#define KALDI_WARN
Definition: kaldi-error.h:130
fst::StdArc::Label Label
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::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
#define KALDI_VLOG(v)
Definition: kaldi-error.h:136
void ComputeFinalCosts(unordered_map< Token *, BaseFloat > *final_costs, BaseFloat *final_relative_cost, BaseFloat *final_best_cost) const
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 also call InitDecoding if you have already decoded an utterance and want to start with a new utterance.

Definition at line 55 of file lattice-faster-decoder.cc.

References LatticeFasterDecoder::active_toks_, LatticeFasterDecoderConfig::beam, HashList< I, T >::Clear(), LatticeFasterDecoder::ClearActiveTokens(), LatticeFasterDecoder::config_, LatticeFasterDecoder::cost_offsets_, LatticeFasterDecoder::decoding_finalized_, LatticeFasterDecoder::DeleteElems(), LatticeFasterDecoder::final_costs_, LatticeFasterDecoder::fst_, HashList< I, T >::Insert(), KALDI_ASSERT, LatticeFasterDecoder::num_toks_, LatticeFasterDecoder::ProcessNonemitting(), LatticeFasterDecoder::toks_, and LatticeFasterDecoder::warned_.

Referenced by LatticeFasterDecoder::Decode().

55  {
56  // clean up from last time:
58  cost_offsets_.clear();
60  warned_ = false;
61  num_toks_ = 0;
62  decoding_finalized_ = false;
63  final_costs_.clear();
64  StateId start_state = fst_.Start();
65  KALDI_ASSERT(start_state != fst::kNoStateId);
66  active_toks_.resize(1);
67  Token *start_tok = new Token(0.0, 0.0, NULL, NULL);
68  active_toks_[0].toks = start_tok;
69  toks_.Insert(start_state, start_tok);
70  num_toks_++;
72 }
std::vector< BaseFloat > cost_offsets_
HashList< StateId, Token * > toks_
std::vector< TokenList > active_toks_
void Insert(I key, T val)
Insert inserts a new element into the hashtable/stored list.
const fst::Fst< fst::StdArc > & fst_
void ProcessNonemitting(BaseFloat cost_cutoff)
Processes nonemitting (epsilon) arcs for one frame.
Elem * Clear()
Clears the hash and gives the head of the current list to the user; ownership is transferred to the u...
Definition: hash-list-inl.h:46
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().
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
LatticeFasterDecoderConfig config_
KALDI_DISALLOW_COPY_AND_ASSIGN ( LatticeFasterDecoder  )
private
void PossiblyResizeHash ( size_t  num_toks)
private

Definition at line 219 of file lattice-faster-decoder.cc.

References LatticeFasterDecoder::config_, LatticeFasterDecoderConfig::hash_ratio, HashList< I, T >::SetSize(), HashList< I, T >::Size(), and LatticeFasterDecoder::toks_.

Referenced by LatticeFasterDecoder::ProcessEmitting().

219  {
220  size_t new_sz = static_cast<size_t>(static_cast<BaseFloat>(num_toks)
221  * config_.hash_ratio);
222  if (new_sz > toks_.Size()) {
223  toks_.SetSize(new_sz);
224  }
225 }
HashList< StateId, Token * > toks_
float BaseFloat
Definition: kaldi-types.h:29
void SetSize(size_t sz)
SetSize tells the object how many hash buckets to allocate (should typically be at least twice the nu...
Definition: hash-list-inl.h:37
size_t Size()
Returns current number of hash buckets.
Definition: hash-list.h:115
LatticeFasterDecoderConfig config_
BaseFloat ProcessEmitting ( DecodableInterface decodable)
private

Processes emitting arcs for one frame.

Propagates from prev_toks_ to cur_toks_. Returns the cost cutoff for subsequent ProcessNonemitting() to use.

Definition at line 686 of file lattice-faster-decoder.cc.

References LatticeFasterDecoder::active_toks_, HashList< I, T >::Clear(), LatticeFasterDecoder::cost_offsets_, HashList< I, T >::Delete(), LatticeFasterDecoder::FindOrAddToken(), LatticeFasterDecoder::fst_, LatticeFasterDecoder::GetCutoff(), KALDI_ASSERT, KALDI_VLOG, LatticeFasterDecoder::Token::links, DecodableInterface::LogLikelihood(), LatticeFasterDecoder::NumFramesDecoded(), LatticeFasterDecoder::PossiblyResizeHash(), fst::Times(), LatticeFasterDecoder::toks_, and LatticeFasterDecoder::Token::tot_cost.

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

686  {
687  KALDI_ASSERT(active_toks_.size() > 0);
688  int32 frame = active_toks_.size() - 1; // frame is the frame-index
689  // (zero-based) used to get likelihoods
690  // from the decodable object.
691  active_toks_.resize(active_toks_.size() + 1);
692 
693  Elem *final_toks = toks_.Clear(); // analogous to swapping prev_toks_ / cur_toks_
694  // in simple-decoder.h. Removes the Elems from
695  // being indexed in the hash in toks_.
696  Elem *best_elem = NULL;
697  BaseFloat adaptive_beam;
698  size_t tok_cnt;
699  BaseFloat cur_cutoff = GetCutoff(final_toks, &tok_cnt, &adaptive_beam, &best_elem);
700  KALDI_VLOG(6) << "Adaptive beam on frame " << NumFramesDecoded() << " is "
701  << adaptive_beam;
702 
703  PossiblyResizeHash(tok_cnt); // This makes sure the hash is always big enough.
704 
705  BaseFloat next_cutoff = std::numeric_limits<BaseFloat>::infinity();
706  // pruning "online" before having seen all tokens
707 
708  BaseFloat cost_offset = 0.0; // Used to keep probabilities in a good
709  // dynamic range.
710 
711  // First process the best token to get a hopefully
712  // reasonably tight bound on the next cutoff. The only
713  // products of the next block are "next_cutoff" and "cost_offset".
714  if (best_elem) {
715  StateId state = best_elem->key;
716  Token *tok = best_elem->val;
717  cost_offset = - tok->tot_cost;
718  for (fst::ArcIterator<fst::Fst<Arc> > aiter(fst_, state);
719  !aiter.Done();
720  aiter.Next()) {
721  Arc arc = aiter.Value();
722  if (arc.ilabel != 0) { // propagate..
723  arc.weight = Times(arc.weight,
724  Weight(cost_offset -
725  decodable->LogLikelihood(frame, arc.ilabel)));
726  BaseFloat new_weight = arc.weight.Value() + tok->tot_cost;
727  if (new_weight + adaptive_beam < next_cutoff)
728  next_cutoff = new_weight + adaptive_beam;
729  }
730  }
731  }
732 
733  // Store the offset on the acoustic likelihoods that we're applying.
734  // Could just do cost_offsets_.push_back(cost_offset), but we
735  // do it this way as it's more robust to future code changes.
736  cost_offsets_.resize(frame + 1, 0.0);
737  cost_offsets_[frame] = cost_offset;
738 
739  // the tokens are now owned here, in final_toks, and the hash is empty.
740  // 'owned' is a complex thing here; the point is we need to call DeleteElem
741  // on each elem 'e' to let toks_ know we're done with them.
742  for (Elem *e = final_toks, *e_tail; e != NULL; e = e_tail) {
743  // loop this way because we delete "e" as we go.
744  StateId state = e->key;
745  Token *tok = e->val;
746  if (tok->tot_cost <= cur_cutoff) {
747  for (fst::ArcIterator<fst::Fst<Arc> > aiter(fst_, state);
748  !aiter.Done();
749  aiter.Next()) {
750  const Arc &arc = aiter.Value();
751  if (arc.ilabel != 0) { // propagate..
752  BaseFloat ac_cost = cost_offset -
753  decodable->LogLikelihood(frame, arc.ilabel),
754  graph_cost = arc.weight.Value(),
755  cur_cost = tok->tot_cost,
756  tot_cost = cur_cost + ac_cost + graph_cost;
757  if (tot_cost > next_cutoff) continue;
758  else if (tot_cost + adaptive_beam < next_cutoff)
759  next_cutoff = tot_cost + adaptive_beam; // prune by best current token
760  // Note: the frame indexes into active_toks_ are one-based,
761  // hence the + 1.
762  Token *next_tok = FindOrAddToken(arc.nextstate,
763  frame + 1, tot_cost, NULL);
764  // NULL: no change indicator needed
765 
766  // Add ForwardLink from tok to next_tok (put on head of list tok->links)
767  tok->links = new ForwardLink(next_tok, arc.ilabel, arc.olabel,
768  graph_cost, ac_cost, tok->links);
769  }
770  } // for all arcs
771  }
772  e_tail = e->tail;
773  toks_.Delete(e); // delete Elem
774  }
775  return next_cutoff;
776 }
std::vector< BaseFloat > cost_offsets_
HashList< StateId, Token * > toks_
std::vector< TokenList > active_toks_
const fst::Fst< fst::StdArc > & fst_
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
float BaseFloat
Definition: kaldi-types.h:29
Elem * Clear()
Clears the hash and gives the head of the current list to the user; ownership is transferred to the u...
Definition: hash-list-inl.h:46
HashList< StateId, Token * >::Elem Elem
Token * FindOrAddToken(StateId state, int32 frame_plus_one, BaseFloat tot_cost, bool *changed)
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
#define KALDI_VLOG(v)
Definition: kaldi-error.h:136
void PossiblyResizeHash(size_t num_toks)
void Delete(Elem *e)
Think of this like delete().
Definition: hash-list-inl.h:66
BaseFloat GetCutoff(Elem *list_head, size_t *tok_count, BaseFloat *adaptive_beam, Elem **best_elem)
Gets the weight cutoff. Also counts the active tokens.
void ProcessNonemitting ( BaseFloat  cost_cutoff)
private

Processes nonemitting (epsilon) arcs for one frame.

Called after ProcessEmitting() on each frame. The cost cutoff is computed by the preceding ProcessEmitting().

Definition at line 778 of file lattice-faster-decoder.cc.

References LatticeFasterDecoder::active_toks_, LatticeFasterDecoder::Token::DeleteForwardLinks(), HashList< I, T >::Find(), LatticeFasterDecoder::FindOrAddToken(), LatticeFasterDecoder::fst_, HashList< I, T >::GetList(), KALDI_ASSERT, KALDI_WARN, LatticeFasterDecoder::Token::links, LatticeFasterDecoder::queue_, LatticeFasterDecoder::toks_, LatticeFasterDecoder::Token::tot_cost, and LatticeFasterDecoder::warned_.

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

778  {
779  KALDI_ASSERT(!active_toks_.empty());
780  int32 frame = static_cast<int32>(active_toks_.size()) - 2;
781  // Note: "frame" is the time-index we just processed, or -1 if
782  // we are processing the nonemitting transitions before the
783  // first frame (called from InitDecoding()).
784 
785  // Processes nonemitting arcs for one frame. Propagates within toks_.
786  // Note-- this queue structure is is not very optimal as
787  // it may cause us to process states unnecessarily (e.g. more than once),
788  // but in the baseline code, turning this vector into a set to fix this
789  // problem did not improve overall speed.
790 
791  KALDI_ASSERT(queue_.empty());
792  for (const Elem *e = toks_.GetList(); e != NULL; e = e->tail)
793  queue_.push_back(e->key);
794  if (queue_.empty()) {
795  if (!warned_) {
796  KALDI_WARN << "Error, no surviving tokens: frame is " << frame;
797  warned_ = true;
798  }
799  }
800 
801  while (!queue_.empty()) {
802  StateId state = queue_.back();
803  queue_.pop_back();
804 
805  Token *tok = toks_.Find(state)->val; // would segfault if state not in toks_ but this can't happen.
806  BaseFloat cur_cost = tok->tot_cost;
807  if (cur_cost > cutoff) // Don't bother processing successors.
808  continue;
809  // If "tok" has any existing forward links, delete them,
810  // because we're about to regenerate them. This is a kind
811  // of non-optimality (remember, this is the simple decoder),
812  // but since most states are emitting it's not a huge issue.
813  tok->DeleteForwardLinks(); // necessary when re-visiting
814  tok->links = NULL;
815  for (fst::ArcIterator<fst::Fst<Arc> > aiter(fst_, state);
816  !aiter.Done();
817  aiter.Next()) {
818  const Arc &arc = aiter.Value();
819  if (arc.ilabel == 0) { // propagate nonemitting only...
820  BaseFloat graph_cost = arc.weight.Value(),
821  tot_cost = cur_cost + graph_cost;
822  if (tot_cost < cutoff) {
823  bool changed;
824 
825  Token *new_tok = FindOrAddToken(arc.nextstate, frame + 1, tot_cost,
826  &changed);
827 
828  tok->links = new ForwardLink(new_tok, 0, arc.olabel,
829  graph_cost, 0, tok->links);
830 
831  // "changed" tells us whether the new token has a different
832  // cost from before, or is new [if so, add into queue].
833  if (changed) queue_.push_back(arc.nextstate);
834  }
835  }
836  } // for all arcs
837  } // while queue not empty
838 }
HashList< StateId, Token * > toks_
std::vector< TokenList > active_toks_
const fst::Fst< fst::StdArc > & fst_
float BaseFloat
Definition: kaldi-types.h:29
#define KALDI_WARN
Definition: kaldi-error.h:130
const Elem * GetList() const
Gives the head of the current list to the user.
Definition: hash-list-inl.h:61
HashList< StateId, Token * >::Elem Elem
Token * FindOrAddToken(StateId state, int32 frame_plus_one, BaseFloat tot_cost, bool *changed)
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
Elem * Find(I key)
Find tries to find this element in the current list using the hashtable.
Definition: hash-list-inl.h:72
void PruneActiveTokens ( BaseFloat  delta)
private

Definition at line 502 of file lattice-faster-decoder.cc.

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

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

502  {
503  int32 cur_frame_plus_one = NumFramesDecoded();
504  int32 num_toks_begin = num_toks_;
505  // The index "f" below represents a "frame plus one", i.e. you'd have to subtract
506  // one to get the corresponding index for the decodable object.
507  for (int32 f = cur_frame_plus_one - 1; f >= 0; f--) {
508  // Reason why we need to prune forward links in this situation:
509  // (1) we have never pruned them (new TokenList)
510  // (2) we have not yet pruned the forward links to the next f,
511  // after any of those tokens have changed their extra_cost.
512  if (active_toks_[f].must_prune_forward_links) {
513  bool extra_costs_changed = false, links_pruned = false;
514  PruneForwardLinks(f, &extra_costs_changed, &links_pruned, delta);
515  if (extra_costs_changed && f > 0) // any token has changed extra_cost
516  active_toks_[f-1].must_prune_forward_links = true;
517  if (links_pruned) // any link was pruned
518  active_toks_[f].must_prune_tokens = true;
519  active_toks_[f].must_prune_forward_links = false; // job done
520  }
521  if (f+1 < cur_frame_plus_one && // except for last f (no forward links)
522  active_toks_[f+1].must_prune_tokens) {
523  PruneTokensForFrame(f+1);
524  active_toks_[f+1].must_prune_tokens = false;
525  }
526  }
527  KALDI_VLOG(4) << "PruneActiveTokens: pruned tokens from " << num_toks_begin
528  << " to " << num_toks_;
529 }
void PruneForwardLinks(int32 frame_plus_one, bool *extra_costs_changed, bool *links_pruned, BaseFloat delta)
std::vector< TokenList > active_toks_
void PruneTokensForFrame(int32 frame_plus_one)
#define KALDI_VLOG(v)
Definition: kaldi-error.h:136
void PruneForwardLinks ( int32  frame_plus_one,
bool *  extra_costs_changed,
bool *  links_pruned,
BaseFloat  delta 
)
private

Definition at line 299 of file lattice-faster-decoder.cc.

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

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

301  {
302  // delta is the amount by which the extra_costs must change
303  // If delta is larger, we'll tend to go back less far
304  // toward the beginning of the file.
305  // extra_costs_changed is set to true if extra_cost was changed for any token
306  // links_pruned is set to true if any link in any token was pruned
307 
308  *extra_costs_changed = false;
309  *links_pruned = false;
310  KALDI_ASSERT(frame_plus_one >= 0 && frame_plus_one < active_toks_.size());
311  if (active_toks_[frame_plus_one].toks == NULL) { // empty list; should not happen.
312  if (!warned_) {
313  KALDI_WARN << "No tokens alive [doing pruning].. warning first "
314  "time only for each utterance\n";
315  warned_ = true;
316  }
317  }
318 
319  // We have to iterate until there is no more change, because the links
320  // are not guaranteed to be in topological order.
321  bool changed = true; // difference new minus old extra cost >= delta ?
322  while (changed) {
323  changed = false;
324  for (Token *tok = active_toks_[frame_plus_one].toks;
325  tok != NULL; tok = tok->next) {
326  ForwardLink *link, *prev_link = NULL;
327  // will recompute tok_extra_cost for tok.
328  BaseFloat tok_extra_cost = std::numeric_limits<BaseFloat>::infinity();
329  // tok_extra_cost is the best (min) of link_extra_cost of outgoing links
330  for (link = tok->links; link != NULL; ) {
331  // See if we need to excise this link...
332  Token *next_tok = link->next_tok;
333  BaseFloat link_extra_cost = next_tok->extra_cost +
334  ((tok->tot_cost + link->acoustic_cost + link->graph_cost)
335  - next_tok->tot_cost); // difference in brackets is >= 0
336  // link_exta_cost is the difference in score between the best paths
337  // through link source state and through link destination state
338  KALDI_ASSERT(link_extra_cost == link_extra_cost); // check for NaN
339  if (link_extra_cost > config_.lattice_beam) { // excise link
340  ForwardLink *next_link = link->next;
341  if (prev_link != NULL) prev_link->next = next_link;
342  else tok->links = next_link;
343  delete link;
344  link = next_link; // advance link but leave prev_link the same.
345  *links_pruned = true;
346  } else { // keep the link and update the tok_extra_cost if needed.
347  if (link_extra_cost < 0.0) { // this is just a precaution.
348  if (link_extra_cost < -0.01)
349  KALDI_WARN << "Negative extra_cost: " << link_extra_cost;
350  link_extra_cost = 0.0;
351  }
352  if (link_extra_cost < tok_extra_cost)
353  tok_extra_cost = link_extra_cost;
354  prev_link = link; // move to next link
355  link = link->next;
356  }
357  } // for all outgoing links
358  if (fabs(tok_extra_cost - tok->extra_cost) > delta)
359  changed = true; // difference new minus old is bigger than delta
360  tok->extra_cost = tok_extra_cost;
361  // will be +infinity or <= lattice_beam_.
362  // infinity indicates, that no forward link survived pruning
363  } // for all Token on active_toks_[frame]
364  if (changed) *extra_costs_changed = true;
365 
366  // Note: it's theoretically possible that aggressive compiler
367  // optimizations could cause an infinite loop here for small delta and
368  // high-dynamic-range scores.
369  } // while changed
370 }
std::vector< TokenList > active_toks_
float BaseFloat
Definition: kaldi-types.h:29
#define KALDI_WARN
Definition: kaldi-error.h:130
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
LatticeFasterDecoderConfig config_
void PruneForwardLinksFinal ( )
private

Definition at line 375 of file lattice-faster-decoder.cc.

References LatticeFasterDecoder::ForwardLink::acoustic_cost, LatticeFasterDecoder::active_toks_, kaldi::ApproxEqual(), HashList< I, T >::Clear(), LatticeFasterDecoder::ComputeFinalCosts(), LatticeFasterDecoder::config_, LatticeFasterDecoder::decoding_finalized_, LatticeFasterDecoder::DeleteElems(), LatticeFasterDecoder::Token::extra_cost, LatticeFasterDecoder::final_best_cost_, LatticeFasterDecoder::final_costs_, LatticeFasterDecoder::final_relative_cost_, LatticeFasterDecoder::ForwardLink::graph_cost, KALDI_ASSERT, KALDI_WARN, LatticeFasterDecoderConfig::lattice_beam, LatticeFasterDecoder::ForwardLink::next, LatticeFasterDecoder::ForwardLink::next_tok, LatticeFasterDecoder::toks_, and LatticeFasterDecoder::Token::tot_cost.

Referenced by LatticeFasterDecoder::FinalizeDecoding().

375  {
376  KALDI_ASSERT(!active_toks_.empty());
377  int32 frame_plus_one = active_toks_.size() - 1;
378 
379  if (active_toks_[frame_plus_one].toks == NULL) // empty list; should not happen.
380  KALDI_WARN << "No tokens alive at end of file";
381 
382  typedef unordered_map<Token*, BaseFloat>::const_iterator IterType;
384  decoding_finalized_ = true;
385  // We call DeleteElems() as a nicety, not because it's really necessary;
386  // otherwise there would be a time, after calling PruneTokensForFrame() on the
387  // final frame, when toks_.GetList() or toks_.Clear() would contain pointers
388  // to nonexistent tokens.
390 
391  // Now go through tokens on this frame, pruning forward links... may have to
392  // iterate a few times until there is no more change, because the list is not
393  // in topological order. This is a modified version of the code in
394  // PruneForwardLinks, but here we also take account of the final-probs.
395  bool changed = true;
396  BaseFloat delta = 1.0e-05;
397  while (changed) {
398  changed = false;
399  for (Token *tok = active_toks_[frame_plus_one].toks;
400  tok != NULL; tok = tok->next) {
401  ForwardLink *link, *prev_link = NULL;
402  // will recompute tok_extra_cost. It has a term in it that corresponds
403  // to the "final-prob", so instead of initializing tok_extra_cost to infinity
404  // below we set it to the difference between the (score+final_prob) of this token,
405  // and the best such (score+final_prob).
406  BaseFloat final_cost;
407  if (final_costs_.empty()) {
408  final_cost = 0.0;
409  } else {
410  IterType iter = final_costs_.find(tok);
411  if (iter != final_costs_.end())
412  final_cost = iter->second;
413  else
414  final_cost = std::numeric_limits<BaseFloat>::infinity();
415  }
416  BaseFloat tok_extra_cost = tok->tot_cost + final_cost - final_best_cost_;
417  // tok_extra_cost will be a "min" over either directly being final, or
418  // being indirectly final through other links, and the loop below may
419  // decrease its value:
420  for (link = tok->links; link != NULL; ) {
421  // See if we need to excise this link...
422  Token *next_tok = link->next_tok;
423  BaseFloat link_extra_cost = next_tok->extra_cost +
424  ((tok->tot_cost + link->acoustic_cost + link->graph_cost)
425  - next_tok->tot_cost);
426  if (link_extra_cost > config_.lattice_beam) { // excise link
427  ForwardLink *next_link = link->next;
428  if (prev_link != NULL) prev_link->next = next_link;
429  else tok->links = next_link;
430  delete link;
431  link = next_link; // advance link but leave prev_link the same.
432  } else { // keep the link and update the tok_extra_cost if needed.
433  if (link_extra_cost < 0.0) { // this is just a precaution.
434  if (link_extra_cost < -0.01)
435  KALDI_WARN << "Negative extra_cost: " << link_extra_cost;
436  link_extra_cost = 0.0;
437  }
438  if (link_extra_cost < tok_extra_cost)
439  tok_extra_cost = link_extra_cost;
440  prev_link = link;
441  link = link->next;
442  }
443  }
444  // prune away tokens worse than lattice_beam above best path. This step
445  // was not necessary in the non-final case because then, this case
446  // showed up as having no forward links. Here, the tok_extra_cost has
447  // an extra component relating to the final-prob.
448  if (tok_extra_cost > config_.lattice_beam)
449  tok_extra_cost = std::numeric_limits<BaseFloat>::infinity();
450  // to be pruned in PruneTokensForFrame
451 
452  if (!ApproxEqual(tok->extra_cost, tok_extra_cost, delta))
453  changed = true;
454  tok->extra_cost = tok_extra_cost; // will be +infinity or <= lattice_beam_.
455  }
456  } // while changed
457 }
HashList< StateId, Token * > toks_
std::vector< TokenList > active_toks_
float BaseFloat
Definition: kaldi-types.h:29
#define KALDI_WARN
Definition: kaldi-error.h:130
Elem * Clear()
Clears the hash and gives the head of the current list to the user; ownership is transferred to the u...
Definition: hash-list-inl.h:46
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().
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
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 ComputeFinalCosts(unordered_map< Token *, BaseFloat > *final_costs, BaseFloat *final_relative_cost, BaseFloat *final_best_cost) const
LatticeFasterDecoderConfig config_
void PruneTokensForFrame ( int32  frame_plus_one)
private

Definition at line 476 of file lattice-faster-decoder.cc.

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

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

476  {
477  KALDI_ASSERT(frame_plus_one >= 0 && frame_plus_one < active_toks_.size());
478  Token *&toks = active_toks_[frame_plus_one].toks;
479  if (toks == NULL)
480  KALDI_WARN << "No tokens alive [doing pruning]";
481  Token *tok, *next_tok, *prev_tok = NULL;
482  for (tok = toks; tok != NULL; tok = next_tok) {
483  next_tok = tok->next;
484  if (tok->extra_cost == std::numeric_limits<BaseFloat>::infinity()) {
485  // token is unreachable from end of graph; (no forward links survived)
486  // excise tok from list and delete tok.
487  if (prev_tok != NULL) prev_tok->next = tok->next;
488  else toks = tok->next;
489  delete tok;
490  num_toks_--;
491  } else { // fetch next Token
492  prev_tok = tok;
493  }
494  }
495 }
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 134 of file lattice-faster-decoder.h.

References LatticeFasterDecoder::FinalRelativeCost().

Referenced by kaldi::DecodeUtteranceLatticeFaster(), and DecodeUtteranceLatticeFasterClass::operator()().

134  {
135  return FinalRelativeCost() != std::numeric_limits<BaseFloat>::infinity();
136  }
BaseFloat FinalRelativeCost() const
FinalRelativeCost() serves the same purpose as ReachedFinal(), but gives more information.
void SetOptions ( const LatticeFasterDecoderConfig config)
inline

Definition at line 115 of file lattice-faster-decoder.h.

References LatticeFasterDecoder::config_.

115  {
116  config_ = config;
117  }
LatticeFasterDecoderConfig config_
void TopSortTokens ( Token tok_list,
std::vector< Token * > *  topsorted_list 
)
staticprivate

Definition at line 865 of file lattice-faster-decoder.cc.

References KALDI_ASSERT, LatticeFasterDecoder::Token::links, LatticeFasterDecoder::ForwardLink::next, and LatticeFasterDecoder::Token::next.

Referenced by LatticeFasterDecoder::GetRawLattice().

866  {
867  unordered_map<Token*, int32> token2pos;
868  typedef unordered_map<Token*, int32>::iterator IterType;
869  int32 num_toks = 0;
870  for (Token *tok = tok_list; tok != NULL; tok = tok->next)
871  num_toks++;
872  int32 cur_pos = 0;
873  // We assign the tokens numbers num_toks - 1, ... , 2, 1, 0.
874  // This is likely to be in closer to topological order than
875  // if we had given them ascending order, because of the way
876  // new tokens are put at the front of the list.
877  for (Token *tok = tok_list; tok != NULL; tok = tok->next)
878  token2pos[tok] = num_toks - ++cur_pos;
879 
880  unordered_set<Token*> reprocess;
881 
882  for (IterType iter = token2pos.begin(); iter != token2pos.end(); ++iter) {
883  Token *tok = iter->first;
884  int32 pos = iter->second;
885  for (ForwardLink *link = tok->links; link != NULL; link = link->next) {
886  if (link->ilabel == 0) {
887  // We only need to consider epsilon links, since non-epsilon links
888  // transition between frames and this function only needs to sort a list
889  // of tokens from a single frame.
890  IterType following_iter = token2pos.find(link->next_tok);
891  if (following_iter != token2pos.end()) { // another token on this frame,
892  // so must consider it.
893  int32 next_pos = following_iter->second;
894  if (next_pos < pos) { // reassign the position of the next Token.
895  following_iter->second = cur_pos++;
896  reprocess.insert(link->next_tok);
897  }
898  }
899  }
900  }
901  // In case we had previously assigned this token to be reprocessed, we can
902  // erase it from that set because it's "happy now" (we just processed it).
903  reprocess.erase(tok);
904  }
905 
906  size_t max_loop = 1000000, loop_count; // max_loop is to detect epsilon cycles.
907  for (loop_count = 0;
908  !reprocess.empty() && loop_count < max_loop; ++loop_count) {
909  std::vector<Token*> reprocess_vec;
910  for (unordered_set<Token*>::iterator iter = reprocess.begin();
911  iter != reprocess.end(); ++iter)
912  reprocess_vec.push_back(*iter);
913  reprocess.clear();
914  for (std::vector<Token*>::iterator iter = reprocess_vec.begin();
915  iter != reprocess_vec.end(); ++iter) {
916  Token *tok = *iter;
917  int32 pos = token2pos[tok];
918  // Repeat the processing we did above (for comments, see above).
919  for (ForwardLink *link = tok->links; link != NULL; link = link->next) {
920  if (link->ilabel == 0) {
921  IterType following_iter = token2pos.find(link->next_tok);
922  if (following_iter != token2pos.end()) {
923  int32 next_pos = following_iter->second;
924  if (next_pos < pos) {
925  following_iter->second = cur_pos++;
926  reprocess.insert(link->next_tok);
927  }
928  }
929  }
930  }
931  }
932  }
933  KALDI_ASSERT(loop_count < max_loop && "Epsilon loops exist in your decoding "
934  "graph (this is not allowed!)");
935 
936  topsorted_list->clear();
937  topsorted_list->resize(cur_pos, NULL); // create a list with NULLs in between.
938  for (IterType iter = token2pos.begin(); iter != token2pos.end(); ++iter)
939  (*topsorted_list)[iter->second] = iter->first;
940 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169

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 toks_ to avoid having dangling pointers hanging around.

Definition at line 381 of file lattice-faster-decoder.h.

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

bool delete_fst_
private
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 384 of file lattice-faster-decoder.h.

Referenced by LatticeFasterDecoder::GetRawLattice(), LatticeFasterDecoder::InitDecoding(), and LatticeFasterDecoder::PruneForwardLinksFinal().

BaseFloat final_relative_cost_
private
std::vector<StateId> queue_
private

Definition at line 361 of file lattice-faster-decoder.h.

Referenced by LatticeFasterDecoder::ProcessNonemitting().

std::vector<BaseFloat> tmp_array_
private

Definition at line 362 of file lattice-faster-decoder.h.

Referenced by LatticeFasterDecoder::GetCutoff().


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