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...
 
template<typename FstType >
BaseFloat ProcessEmitting (DecodableInterface *decodable)
 Processes emitting arcs for one frame. More...
 
BaseFloat ProcessEmittingWrapper (DecodableInterface *decodable)
 
template<typename FstType >
void ProcessNonemitting (BaseFloat cost_cutoff)
 Processes nonemitting (epsilon) arcs for one frame. More...
 
void ProcessNonemittingWrapper (BaseFloat cost_cutoff)
 
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 99 of file lattice-faster-decoder.h.

Member Typedef Documentation

typedef fst::StdArc Arc

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

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

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

typedef Arc::Label Label

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

typedef Arc::StateId StateId

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

typedef Arc::Weight Weight

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

Constructor & Destructor Documentation

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

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

References LatticeFasterDecoderConfig::Check(), and LatticeFasterDecoder::toks_.

35  :
36  fst_(fst), delete_fst_(false), config_(config), num_toks_(0) {
37  config.Check();
38  toks_.SetSize(1000); // just so on the first frame we do something reasonable.
39 }
HashList< StateId, Token * > toks_
Definition: graph.dox:21
const fst::Fst< fst::StdArc > & fst_
LatticeFasterDecoderConfig config_
LatticeFasterDecoder ( const LatticeFasterDecoderConfig config,
fst::Fst< fst::StdArc > *  fst 
)

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

References LatticeFasterDecoderConfig::Check(), and LatticeFasterDecoder::toks_.

43  :
44  fst_(*fst), delete_fst_(true), config_(config), num_toks_(0) {
45  config.Check();
46  toks_.SetSize(1000); // just so on the first frame we do something reasonable.
47 }
HashList< StateId, Token * > toks_
Definition: graph.dox:21
const fst::Fst< fst::StdArc > & fst_
LatticeFasterDecoderConfig config_

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 574 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::ProcessEmittingWrapper(), LatticeFasterDecoder::ProcessNonemittingWrapper(), LatticeFasterDecoderConfig::prune_interval, LatticeFasterDecoderConfig::prune_scale, and LatticeFasterDecoder::PruneActiveTokens().

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

Definition at line 884 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().

884  { // a cleanup routine, at utt end/begin
885  for (size_t i = 0; i < active_toks_.size(); i++) {
886  // Delete all tokens alive on this frame, and any forward
887  // links they may have.
888  for (Token *tok = active_toks_[i].toks; tok != NULL; ) {
889  tok->DeleteForwardLinks();
890  Token *next_tok = tok->next;
891  delete tok;
892  num_toks_--;
893  tok = next_tok;
894  }
895  }
896  active_toks_.clear();
897  KALDI_ASSERT(num_toks_ == 0);
898 }
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 532 of file lattice-faster-decoder.cc.

References LatticeFasterDecoder::decoding_finalized_, LatticeFasterDecoder::fst_, KALDI_ASSERT, HashList< I, T >::Elem::key, HashList< I, T >::Elem::tail, LatticeFasterDecoder::toks_, LatticeFasterDecoder::Token::tot_cost, and HashList< I, T >::Elem::val.

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

535  {
537  if (final_costs != NULL)
538  final_costs->clear();
539  const Elem *final_toks = toks_.GetList();
540  BaseFloat infinity = std::numeric_limits<BaseFloat>::infinity();
541  BaseFloat best_cost = infinity,
542  best_cost_with_final = infinity;
543  while (final_toks != NULL) {
544  StateId state = final_toks->key;
545  Token *tok = final_toks->val;
546  const Elem *next = final_toks->tail;
547  BaseFloat final_cost = fst_.Final(state).Value();
548  BaseFloat cost = tok->tot_cost,
549  cost_with_final = cost + final_cost;
550  best_cost = std::min(cost, best_cost);
551  best_cost_with_final = std::min(cost_with_final, best_cost_with_final);
552  if (final_costs != NULL && final_cost != infinity)
553  (*final_costs)[tok] = final_cost;
554  final_toks = next;
555  }
556  if (final_relative_cost != NULL) {
557  if (best_cost == infinity && best_cost_with_final == infinity) {
558  // Likely this will only happen if there are no tokens surviving.
559  // This seems the least bad way to handle it.
560  *final_relative_cost = infinity;
561  } else {
562  *final_relative_cost = best_cost_with_final - best_cost;
563  }
564  }
565  if (final_best_cost != NULL) {
566  if (best_cost_with_final != infinity) { // final-state exists.
567  *final_best_cost = best_cost_with_final;
568  } else { // no final-state exists.
569  *final_best_cost = best_cost;
570  }
571  }
572 }
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().
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 78 of file lattice-faster-decoder.cc.

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

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

78  {
79  InitDecoding();
80 
81  // We use 1-based indexing for frames in this decoder (if you view it in
82  // terms of features), but note that the decodable object uses zero-based
83  // numbering, which we have to correct for when we call it.
84 
85  while (!decodable->IsLastFrame(NumFramesDecoded() - 1)) {
88  BaseFloat cost_cutoff = ProcessEmittingWrapper(decodable);
89  ProcessNonemittingWrapper(cost_cutoff);
90  }
92 
93  // Returns true if we have any kind of traceback available (not necessarily
94  // to the end state; query ReachedFinal() for that).
95  return !active_toks_.empty() && active_toks_.back().toks != NULL;
96 }
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_
float BaseFloat
Definition: kaldi-types.h:29
void InitDecoding()
InitDecoding initializes the decoding, and should only be used if you intend to call AdvanceDecoding(...
BaseFloat ProcessEmittingWrapper(DecodableInterface *decodable)
void ProcessNonemittingWrapper(BaseFloat cost_cutoff)
LatticeFasterDecoderConfig config_
void DeleteElems ( Elem list)
private

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

References LatticeFasterDecoder::toks_.

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

877  {
878  for (Elem *e = list, *e_tail; e != NULL; e = e_tail) {
879  e_tail = e->tail;
880  toks_.Delete(e);
881  }
882 }
HashList< StateId, Token * > toks_
HashList< StateId, Token * >::Elem Elem
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 600 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().

600  {
601  int32 final_frame_plus_one = NumFramesDecoded();
602  int32 num_toks_begin = num_toks_;
603  // PruneForwardLinksFinal() prunes final frame (with final-probs), and
604  // sets decoding_finalized_.
606  for (int32 f = final_frame_plus_one - 1; f >= 0; f--) {
607  bool b1, b2; // values not used.
608  BaseFloat dontcare = 0.0; // delta of zero means we must always update
609  PruneForwardLinks(f, &b1, &b2, dontcare);
610  PruneTokensForFrame(f + 1);
611  }
613  KALDI_VLOG(4) << "pruned tokens from " << num_toks_begin
614  << " to " << num_toks_;
615 }
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 460 of file lattice-faster-decoder.cc.

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

Referenced by LatticeFasterDecoder::ReachedFinal().

460  {
461  if (!decoding_finalized_) {
462  BaseFloat relative_cost;
463  ComputeFinalCosts(NULL, &relative_cost, NULL);
464  return relative_cost;
465  } else {
466  // we're not allowed to call that function if FinalizeDecoding() has
467  // been called; return a cached value.
468  return final_relative_cost_;
469  }
470 }
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 259 of file lattice-faster-decoder.cc.

References LatticeFasterDecoder::active_toks_, KALDI_ASSERT, LatticeFasterDecoder::num_toks_, LatticeFasterDecoder::toks_, LatticeFasterDecoder::Token::tot_cost, and HashList< I, T >::Elem::val.

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

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

References LatticeFasterDecoder::GetRawLattice().

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

101  {
102  Lattice raw_lat;
103  GetRawLattice(&raw_lat, use_final_probs);
104  ShortestPath(raw_lat, olat);
105  return (olat->NumStates() != 0);
106 }
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 618 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(), HashList< I, T >::Elem::tail, and LatticeFasterDecoder::tmp_array_.

Referenced by LatticeFasterDecoder::ProcessEmitting().

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

199  {
200  Lattice raw_fst;
201  GetRawLattice(&raw_fst, use_final_probs);
202  Invert(&raw_fst); // make it so word labels are on the input.
203  // (in phase where we get backward-costs).
204  fst::ILabelCompare<LatticeArc> ilabel_comp;
205  ArcSort(&raw_fst, ilabel_comp); // sort on ilabel; makes
206  // lattice-determinization more efficient.
207 
209  lat_opts.max_mem = config_.det_opts.max_mem;
210 
211  DeterminizeLatticePruned(raw_fst, config_.lattice_beam, ofst, lat_opts);
212  raw_fst.DeleteStates(); // Free memory-- raw_fst no longer needed.
213  Connect(ofst); // Remove unreachable states... there might be
214  // a small number of these, in some cases.
215  // Note: if something went wrong and the raw lattice was empty,
216  // we should still get to this point in the code without warnings or failures.
217  return (ofst->NumStates() != 0);
218 }
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 120 of file lattice-faster-decoder.h.

References LatticeFasterDecoder::config_.

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

120  {
121  return config_;
122  }
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 110 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()().

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

References LatticeFasterDecoder::active_toks_, LatticeFasterDecoderConfig::beam, LatticeFasterDecoder::ClearActiveTokens(), LatticeFasterDecoder::config_, LatticeFasterDecoder::cost_offsets_, LatticeFasterDecoder::decoding_finalized_, LatticeFasterDecoder::DeleteElems(), LatticeFasterDecoder::final_costs_, LatticeFasterDecoder::fst_, KALDI_ASSERT, LatticeFasterDecoder::num_toks_, LatticeFasterDecoder::ProcessNonemittingWrapper(), LatticeFasterDecoder::toks_, and LatticeFasterDecoder::warned_.

Referenced by LatticeFasterDecoder::Decode().

56  {
57  // clean up from last time:
58  DeleteElems(toks_.Clear());
59  cost_offsets_.clear();
61  warned_ = false;
62  num_toks_ = 0;
63  decoding_finalized_ = false;
64  final_costs_.clear();
65  StateId start_state = fst_.Start();
66  KALDI_ASSERT(start_state != fst::kNoStateId);
67  active_toks_.resize(1);
68  Token *start_tok = new Token(0.0, 0.0, NULL, NULL);
69  active_toks_[0].toks = start_tok;
70  toks_.Insert(start_state, start_tok);
71  num_toks_++;
73 }
std::vector< BaseFloat > cost_offsets_
HashList< StateId, Token * > toks_
std::vector< TokenList > active_toks_
const fst::Fst< fst::StdArc > & fst_
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
void ProcessNonemittingWrapper(BaseFloat cost_cutoff)
LatticeFasterDecoderConfig config_
KALDI_DISALLOW_COPY_AND_ASSIGN ( LatticeFasterDecoder  )
private
void PossiblyResizeHash ( size_t  num_toks)
private

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

References LatticeFasterDecoder::config_, LatticeFasterDecoderConfig::hash_ratio, and LatticeFasterDecoder::toks_.

Referenced by LatticeFasterDecoder::ProcessEmitting().

220  {
221  size_t new_sz = static_cast<size_t>(static_cast<BaseFloat>(num_toks)
222  * config_.hash_ratio);
223  if (new_sz > toks_.Size()) {
224  toks_.SetSize(new_sz);
225  }
226 }
HashList< StateId, Token * > toks_
float BaseFloat
Definition: kaldi-types.h:29
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. Templated on FST type for speed; called via ProcessEmittingWrapper().

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

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

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

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

References LatticeFasterDecoder::fst_.

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

786  {
787  if (fst_.Type() == "const") {
788  return LatticeFasterDecoder::ProcessEmitting<fst::ConstFst<Arc>>(decodable);
789  } else if (fst_.Type() == "vector") {
790  return LatticeFasterDecoder::ProcessEmitting<fst::VectorFst<Arc>>(decodable);
791  } else {
792  return LatticeFasterDecoder::ProcessEmitting<fst::Fst<Arc>>(decodable);
793  }
794 }
const fst::Fst< fst::StdArc > & fst_
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(). the templated design is similar to ProcessEmitting()

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

References LatticeFasterDecoder::active_toks_, LatticeFasterDecoder::Token::DeleteForwardLinks(), LatticeFasterDecoder::FindOrAddToken(), LatticeFasterDecoder::fst_, KALDI_ASSERT, KALDI_WARN, LatticeFasterDecoder::Token::links, LatticeFasterDecoder::queue_, LatticeFasterDecoder::toks_, LatticeFasterDecoder::Token::tot_cost, and LatticeFasterDecoder::warned_.

797  {
798  KALDI_ASSERT(!active_toks_.empty());
799  int32 frame = static_cast<int32>(active_toks_.size()) - 2;
800  // Note: "frame" is the time-index we just processed, or -1 if
801  // we are processing the nonemitting transitions before the
802  // first frame (called from InitDecoding()).
803  const FstType &fst = dynamic_cast<const FstType&>(fst_);
804 
805  // Processes nonemitting arcs for one frame. Propagates within toks_.
806  // Note-- this queue structure is is not very optimal as
807  // it may cause us to process states unnecessarily (e.g. more than once),
808  // but in the baseline code, turning this vector into a set to fix this
809  // problem did not improve overall speed.
810 
811  KALDI_ASSERT(queue_.empty());
812  for (const Elem *e = toks_.GetList(); e != NULL; e = e->tail)
813  queue_.push_back(e->key);
814  if (queue_.empty()) {
815  if (!warned_) {
816  KALDI_WARN << "Error, no surviving tokens: frame is " << frame;
817  warned_ = true;
818  }
819  }
820 
821  while (!queue_.empty()) {
822  StateId state = queue_.back();
823  queue_.pop_back();
824 
825  Token *tok = toks_.Find(state)->val; // would segfault if state not in toks_ but this can't happen.
826  BaseFloat cur_cost = tok->tot_cost;
827  if (cur_cost > cutoff) // Don't bother processing successors.
828  continue;
829  // If "tok" has any existing forward links, delete them,
830  // because we're about to regenerate them. This is a kind
831  // of non-optimality (remember, this is the simple decoder),
832  // but since most states are emitting it's not a huge issue.
833  tok->DeleteForwardLinks(); // necessary when re-visiting
834  tok->links = NULL;
835  for (fst::ArcIterator<FstType> aiter(fst, state);
836  !aiter.Done();
837  aiter.Next()) {
838  const Arc &arc = aiter.Value();
839  if (arc.ilabel == 0) { // propagate nonemitting only...
840  BaseFloat graph_cost = arc.weight.Value(),
841  tot_cost = cur_cost + graph_cost;
842  if (tot_cost < cutoff) {
843  bool changed;
844 
845  Token *new_tok = FindOrAddToken(arc.nextstate, frame + 1, tot_cost,
846  &changed);
847 
848  tok->links = new ForwardLink(new_tok, 0, arc.olabel,
849  graph_cost, 0, tok->links);
850 
851  // "changed" tells us whether the new token has a different
852  // cost from before, or is new [if so, add into queue].
853  if (changed) queue_.push_back(arc.nextstate);
854  }
855  }
856  } // for all arcs
857  } // while queue not empty
858 }
HashList< StateId, Token * > toks_
Definition: graph.dox:21
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
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
void ProcessNonemittingWrapper ( BaseFloat  cost_cutoff)
private

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

References LatticeFasterDecoder::fst_.

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

867  {
868  if (fst_.Type() == "const") {
869  return LatticeFasterDecoder::ProcessNonemitting<fst::ConstFst<Arc>>(cost_cutoff);
870  } else if (fst_.Type() == "vector") {
871  return LatticeFasterDecoder::ProcessNonemitting<fst::VectorFst<Arc>>(cost_cutoff);
872  } else {
873  return LatticeFasterDecoder::ProcessNonemitting<fst::ConstFst<Arc>>(cost_cutoff);
874  }
875 }
const fst::Fst< fst::StdArc > & fst_
void PruneActiveTokens ( BaseFloat  delta)
private

Definition at line 503 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().

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

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

References LatticeFasterDecoder::ForwardLink::acoustic_cost, LatticeFasterDecoder::active_toks_, kaldi::ApproxEqual(), 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().

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

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

References LatticeFasterDecoder::FinalRelativeCost().

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

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

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

References LatticeFasterDecoder::config_.

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

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

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

Referenced by LatticeFasterDecoder::GetRawLattice().

902  {
903  unordered_map<Token*, int32> token2pos;
904  typedef unordered_map<Token*, int32>::iterator IterType;
905  int32 num_toks = 0;
906  for (Token *tok = tok_list; tok != NULL; tok = tok->next)
907  num_toks++;
908  int32 cur_pos = 0;
909  // We assign the tokens numbers num_toks - 1, ... , 2, 1, 0.
910  // This is likely to be in closer to topological order than
911  // if we had given them ascending order, because of the way
912  // new tokens are put at the front of the list.
913  for (Token *tok = tok_list; tok != NULL; tok = tok->next)
914  token2pos[tok] = num_toks - ++cur_pos;
915 
916  unordered_set<Token*> reprocess;
917 
918  for (IterType iter = token2pos.begin(); iter != token2pos.end(); ++iter) {
919  Token *tok = iter->first;
920  int32 pos = iter->second;
921  for (ForwardLink *link = tok->links; link != NULL; link = link->next) {
922  if (link->ilabel == 0) {
923  // We only need to consider epsilon links, since non-epsilon links
924  // transition between frames and this function only needs to sort a list
925  // of tokens from a single frame.
926  IterType following_iter = token2pos.find(link->next_tok);
927  if (following_iter != token2pos.end()) { // another token on this frame,
928  // so must consider it.
929  int32 next_pos = following_iter->second;
930  if (next_pos < pos) { // reassign the position of the next Token.
931  following_iter->second = cur_pos++;
932  reprocess.insert(link->next_tok);
933  }
934  }
935  }
936  }
937  // In case we had previously assigned this token to be reprocessed, we can
938  // erase it from that set because it's "happy now" (we just processed it).
939  reprocess.erase(tok);
940  }
941 
942  size_t max_loop = 1000000, loop_count; // max_loop is to detect epsilon cycles.
943  for (loop_count = 0;
944  !reprocess.empty() && loop_count < max_loop; ++loop_count) {
945  std::vector<Token*> reprocess_vec;
946  for (unordered_set<Token*>::iterator iter = reprocess.begin();
947  iter != reprocess.end(); ++iter)
948  reprocess_vec.push_back(*iter);
949  reprocess.clear();
950  for (std::vector<Token*>::iterator iter = reprocess_vec.begin();
951  iter != reprocess_vec.end(); ++iter) {
952  Token *tok = *iter;
953  int32 pos = token2pos[tok];
954  // Repeat the processing we did above (for comments, see above).
955  for (ForwardLink *link = tok->links; link != NULL; link = link->next) {
956  if (link->ilabel == 0) {
957  IterType following_iter = token2pos.find(link->next_tok);
958  if (following_iter != token2pos.end()) {
959  int32 next_pos = following_iter->second;
960  if (next_pos < pos) {
961  following_iter->second = cur_pos++;
962  reprocess.insert(link->next_tok);
963  }
964  }
965  }
966  }
967  }
968  }
969  KALDI_ASSERT(loop_count < max_loop && "Epsilon loops exist in your decoding "
970  "graph (this is not allowed!)");
971 
972  topsorted_list->clear();
973  topsorted_list->resize(cur_pos, NULL); // create a list with NULLs in between.
974  for (IterType iter = token2pos.begin(); iter != token2pos.end(); ++iter)
975  (*topsorted_list)[iter->second] = iter->first;
976 }
#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 388 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 391 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 368 of file lattice-faster-decoder.h.

Referenced by LatticeFasterDecoder::ProcessNonemitting().

std::vector<BaseFloat> tmp_array_
private

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

Referenced by LatticeFasterDecoder::GetCutoff().


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