LatticeIncrementalOnlineDecoderTpl< FST > Class Template Reference

LatticeIncrementalOnlineDecoderTpl is as LatticeIncrementalDecoderTpl but also supports an efficient way to get the best path (see the function BestPathEnd()), which is useful in endpointing and in situations where you might want to frequently access the best path. More...

#include <lattice-incremental-online-decoder.h>

Inheritance diagram for LatticeIncrementalOnlineDecoderTpl< FST >:

Collaboration diagram for LatticeIncrementalOnlineDecoderTpl< FST >:

Classes
struct	BestPathIterator

Public Types
using	Arc = typename FST::Arc
using	Label = typename Arc::Label
using	StateId = typename Arc::StateId
using	Weight = typename Arc::Weight
using	Token = decoder::BackpointerToken
using	ForwardLinkT = decoder::ForwardLink< Token >
Public Types inherited from LatticeIncrementalDecoderTpl< FST, decoder::BackpointerToken >
using	Arc = typename FST::Arc
using	Label = typename Arc::Label
using	StateId = typename Arc::StateId
using	Weight = typename Arc::Weight
using	ForwardLinkT = decoder::ForwardLink< decoder::BackpointerToken >

Public Member Functions
	LatticeIncrementalOnlineDecoderTpl (const FST &fst, const TransitionModel &trans_model, const LatticeIncrementalDecoderConfig &config)
	LatticeIncrementalOnlineDecoderTpl (const LatticeIncrementalDecoderConfig &config, FST *fst, const TransitionModel &trans_model)
bool	GetBestPath (Lattice *ofst, bool use_final_probs=true) const
	Outputs an FST corresponding to the single best path through the lattice. More...
BestPathIterator	BestPathEnd (bool use_final_probs, BaseFloat *final_cost=NULL) const
	This function returns an iterator that can be used to trace back the best path. More...
BestPathIterator	TraceBackBestPath (BestPathIterator iter, LatticeArc *arc) const
	This function can be used in conjunction with BestPathEnd() to trace back the best path one link at a time (e.g. More...
	KALDI_DISALLOW_COPY_AND_ASSIGN (LatticeIncrementalOnlineDecoderTpl)
Public Member Functions inherited from LatticeIncrementalDecoderTpl< FST, decoder::BackpointerToken >
	LatticeIncrementalDecoderTpl (const FST &fst, const TransitionModel &trans_model, const LatticeIncrementalDecoderConfig &config)
	LatticeIncrementalDecoderTpl (const LatticeIncrementalDecoderConfig &config, FST *fst, const TransitionModel &trans_model)
void	SetOptions (const LatticeIncrementalDecoderConfig &config)
const LatticeIncrementalDecoderConfig &	GetOptions () const
	~LatticeIncrementalDecoderTpl ()
bool	Decode (DecodableInterface *decodable)
	CAUTION: it's unlikely that you will ever want to call this function. More...
bool	ReachedFinal () const
	says whether a final-state was active on the last frame. More...
const CompactLattice &	GetLattice (int32 num_frames_to_include, bool use_final_probs=false)
	This decoder has no GetBestPath() function. More...
int	NumFramesInLattice () const
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...
BaseFloat	FinalRelativeCost () const
	FinalRelativeCost() serves the same purpose as ReachedFinal(), but gives more information. More...
int32	NumFramesDecoded () const
	Returns the number of frames decoded so far. More...
void	FinalizeDecoding ()
	Finalizes the decoding, doing an extra pruning step on the last frame that uses the final-probs. More...

Additional Inherited Members
Protected Types inherited from LatticeIncrementalDecoderTpl< FST, decoder::BackpointerToken >
using	Elem = typename HashList< StateId, decoder::BackpointerToken *>::Elem
Protected Member Functions inherited from LatticeIncrementalDecoderTpl< FST, decoder::BackpointerToken >
void	PossiblyResizeHash (size_t num_toks)
decoder::BackpointerToken *	FindOrAddToken (StateId state, int32 frame_plus_one, BaseFloat tot_cost, decoder::BackpointerToken *backpointer, bool *changed)
void	PruneForwardLinks (int32 frame_plus_one, bool *extra_costs_changed, bool *links_pruned, BaseFloat delta)
void	ComputeFinalCosts (unordered_map< decoder::BackpointerToken *, 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)
void	ProcessNonemitting (BaseFloat cost_cutoff)
Label	AllocateNewTokenLabel ()
void	DeleteElems (Elem *list)
void	ClearActiveTokens ()
int32	GetNumToksForFrame (int32 frame)
void	UpdateLatticeDeterminization ()
	UpdateLatticeDeterminization() ensures the work of determinization is kept up to date so that when you do need the lattice you can get it fast. More...
	KALDI_DISALLOW_COPY_AND_ASSIGN (LatticeIncrementalDecoderTpl)
Static Protected Member Functions inherited from LatticeIncrementalDecoderTpl< FST, decoder::BackpointerToken >
static void	DeleteForwardLinks (decoder::BackpointerToken *tok)
	NOTE: for parts the internal implementation that are shared with LatticeFasterDecoer, we have removed the comments. More...
Protected Attributes inherited from LatticeIncrementalDecoderTpl< FST, decoder::BackpointerToken >
HashList< StateId, decoder::BackpointerToken *>	toks_
std::vector< TokenList >	active_toks_
std::vector< StateId >	queue_
std::vector< BaseFloat >	tmp_array_
const FST *	fst_
bool	delete_fst_
std::vector< BaseFloat >	cost_offsets_
int32	num_toks_
bool	warned_
bool	decoding_finalized_
unordered_map< decoder::BackpointerToken *, BaseFloat >	final_costs_
BaseFloat	final_relative_cost_
BaseFloat	final_best_cost_
LatticeIncrementalDecoderConfig	config_
LatticeIncrementalDeterminizer	determinizer_
	Much of the the incremental determinization algorithm is encapsulated in the determinize_ object. More...
unordered_map< decoder::BackpointerToken *, StateId >	temp_token_map_
int32	num_frames_in_lattice_
	num_frames_in_lattice_ is the highest `num_frames_to_include_` argument for any prior call to GetLattice(). More...
unordered_map< decoder::BackpointerToken *, Label >	token2label_map_
unordered_map< decoder::BackpointerToken *, Label >	token2label_map_temp_
Label	next_token_label_

Detailed Description

template<typename FST>
class kaldi::LatticeIncrementalOnlineDecoderTpl< FST >

LatticeIncrementalOnlineDecoderTpl is as LatticeIncrementalDecoderTpl but also supports an efficient way to get the best path (see the function BestPathEnd()), which is useful in endpointing and in situations where you might want to frequently access the best path.

This is only templated on the FST type, since the Token type is required to be BackpointerToken. Actually it only makes sense to instantiate LatticeIncrementalDecoderTpl with Token == BackpointerToken if you do so indirectly via this child class.

Definition at line 51 of file lattice-incremental-online-decoder.h.

Member Typedef Documentation

Arc

using Arc = typename FST::Arc

Definition at line 54 of file lattice-incremental-online-decoder.h.

ForwardLinkT

using ForwardLinkT = decoder::ForwardLink<Token>

Definition at line 59 of file lattice-incremental-online-decoder.h.

Label

using Label = typename Arc::Label

Definition at line 55 of file lattice-incremental-online-decoder.h.

StateId

using StateId = typename Arc::StateId

Definition at line 56 of file lattice-incremental-online-decoder.h.

Token

using Token = decoder::BackpointerToken

Definition at line 58 of file lattice-incremental-online-decoder.h.

Weight

using Weight = typename Arc::Weight

Definition at line 57 of file lattice-incremental-online-decoder.h.

Constructor & Destructor Documentation

LatticeIncrementalOnlineDecoderTpl() [1/2]

LatticeIncrementalOnlineDecoderTpl ( const FST &  fst, const TransitionModel &  trans_model, const LatticeIncrementalDecoderConfig &  config  )

inline

Definition at line 64 of file lattice-incremental-online-decoder.h.

                                                                              :
      LatticeIncrementalDecoderTpl<FST, Token>(fst, trans_model, config) { }

LatticeIncrementalOnlineDecoderTpl() [2/2]

LatticeIncrementalOnlineDecoderTpl ( const LatticeIncrementalDecoderConfig &  config, FST *  fst, const TransitionModel &  trans_model  )

inline

Definition at line 71 of file lattice-incremental-online-decoder.h.

                                       :
      LatticeIncrementalDecoderTpl<FST, Token>(config, fst, trans_model) { }

Member Function Documentation

BestPathEnd()

LatticeIncrementalOnlineDecoderTpl< FST >::BestPathIterator BestPathEnd	(	bool	use_final_probs,
		BaseFloat *	final_cost = NULL
	)		const

This function returns an iterator that can be used to trace back the best path.

If use_final_probs == true and at least one final state survived till the end, it will use the final-probs in working out the best final Token, and will output the final cost to *final_cost (if non-NULL), else it will use only the forward likelihood, and will put zero in *final_cost (if non-NULL). Requires that NumFramesDecoded() > 0.

Definition at line 54 of file lattice-incremental-online-decoder.cc.

References KALDI_ASSERT, KALDI_ERR, KALDI_WARN, and BackpointerToken::next.

Referenced by OnlineSilenceWeighting::ComputeCurrentTraceback(), and LatticeIncrementalOnlineDecoderTpl< FST >::BestPathIterator::Done().

                                     {
  if (this->decoding_finalized_ && !use_final_probs)
    KALDI_ERR << "You cannot call FinalizeDecoding() and then call "
              << "BestPathEnd() with use_final_probs == false";
  KALDI_ASSERT(this->NumFramesDecoded() > 0 &&
               "You cannot call BestPathEnd if no frames were decoded.");

  unordered_map<Token*, BaseFloat> final_costs_local;

  const unordered_map<Token*, BaseFloat> &final_costs =
      (this->decoding_finalized_ ? this->final_costs_ :final_costs_local);
  if (!this->decoding_finalized_ && use_final_probs)
    this->ComputeFinalCosts(&final_costs_local, NULL, NULL);

  // Singly linked list of tokens on last frame (access list through "next"
  // pointer).
  BaseFloat best_cost = std::numeric_limits<BaseFloat>::infinity();
  BaseFloat best_final_cost = 0;
  Token *best_tok = NULL;
  for (Token *tok = this->active_toks_.back().toks;
       tok != NULL; tok = tok->next) {
    BaseFloat cost = tok->tot_cost, final_cost = 0.0;
    if (use_final_probs && !final_costs.empty()) {
      // if we are instructed to use final-probs, and any final tokens were
      // active on final frame, include the final-prob in the cost of the token.
      typename unordered_map<Token*, BaseFloat>::const_iterator
          iter = final_costs.find(tok);
      if (iter != final_costs.end()) {
        final_cost = iter->second;
        cost += final_cost;
      } else {
        cost = std::numeric_limits<BaseFloat>::infinity();
      }
    }
    if (cost < best_cost) {
      best_cost = cost;
      best_tok = tok;
      best_final_cost = final_cost;
    }
  }
  if (best_tok == NULL) {  // this should not happen, and is likely a code error or
    // caused by infinities in likelihoods, but I'm not making
    // it a fatal error for now.
    KALDI_WARN << "No final token found.";
  }
  if (final_cost_out == NULL)
    *final_cost_out = best_final_cost;
  return BestPathIterator(best_tok, this->NumFramesDecoded() - 1);
}

GetBestPath()

bool GetBestPath	(	Lattice *	ofst,
		bool	use_final_probs = true
	)		const

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

This is quite efficient because it doesn't get the entire raw lattice and find the best path through it; instead, it uses the BestPathEnd and BestPathIterator so it basically traces it back 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.

Definition at line 32 of file lattice-incremental-online-decoder.cc.

References LatticeIncrementalOnlineDecoderTpl< FST >::BestPathIterator::Done().

Referenced by LatticeIncrementalOnlineDecoderTpl< FST >::BestPathIterator::Done().

                                                                                 {
  olat->DeleteStates();
  BaseFloat final_graph_cost;
  BestPathIterator iter = BestPathEnd(use_final_probs, &final_graph_cost);
  if (iter.Done())
    return false;  // would have printed warning.
  StateId state = olat->AddState();
  olat->SetFinal(state, LatticeWeight(final_graph_cost, 0.0));
  while (!iter.Done()) {
    LatticeArc arc;
    iter = TraceBackBestPath(iter, &arc);
    arc.nextstate = state;
    StateId new_state = olat->AddState();
    olat->AddArc(new_state, arc);
    state = new_state;
  }
  olat->SetStart(state);
  return true;
}

KALDI_DISALLOW_COPY_AND_ASSIGN()

KALDI_DISALLOW_COPY_AND_ASSIGN

(

LatticeIncrementalOnlineDecoderTpl< FST >

)

Referenced by LatticeIncrementalOnlineDecoderTpl< FST >::BestPathIterator::Done().

TraceBackBestPath()

LatticeIncrementalOnlineDecoderTpl< FST >::BestPathIterator TraceBackBestPath	(	BestPathIterator	iter,
		LatticeArc *	arc
	)		const

This function can be used in conjunction with BestPathEnd() to trace back the best path one link at a time (e.g.

this can be useful in endpoint detection). By "link" we mean a link in the graph; not all links cross frame boundaries, but each time you see a nonzero ilabel you can interpret that as a frame. The return value is the updated iterator. It outputs the ilabel and olabel, and the (graph and acoustic) weight to the "arc" pointer, while leaving its "nextstate" variable unchanged.

Definition at line 108 of file lattice-incremental-online-decoder.cc.

References ForwardLink< Token >::acoustic_cost, LatticeIncrementalOnlineDecoderTpl< FST >::BestPathIterator::Done(), LatticeIncrementalOnlineDecoderTpl< FST >::BestPathIterator::frame, ForwardLink< Token >::graph_cost, ForwardLink< Token >::ilabel, KALDI_ASSERT, KALDI_ERR, ForwardLink< Token >::next, ForwardLink< Token >::next_tok, ForwardLink< Token >::olabel, LatticeWeightTpl< BaseFloat >::One(), and LatticeIncrementalOnlineDecoderTpl< FST >::BestPathIterator::tok.

Referenced by OnlineSilenceWeighting::ComputeCurrentTraceback(), and LatticeIncrementalOnlineDecoderTpl< FST >::BestPathIterator::Done().

                                                   {
  KALDI_ASSERT(!iter.Done() && oarc != NULL);
  Token *tok = static_cast<Token*>(iter.tok);
  int32 cur_t = iter.frame, ret_t = cur_t;
  if (tok->backpointer != NULL) {
    ForwardLinkT *link;
    for (link = tok->backpointer->links;
         link != NULL; link = link->next) {
      if (link->next_tok == tok) { // this is the link to "tok"
        oarc->ilabel = link->ilabel;
        oarc->olabel = link->olabel;
        BaseFloat graph_cost = link->graph_cost,
            acoustic_cost = link->acoustic_cost;
        if (link->ilabel != 0) {
          KALDI_ASSERT(static_cast<size_t>(cur_t) < this->cost_offsets_.size());
          acoustic_cost -= this->cost_offsets_[cur_t];
          ret_t--;
        }
        oarc->weight = LatticeWeight(graph_cost, acoustic_cost);
        break;
      }
    }
    if (link == NULL) { // Did not find correct link.
      KALDI_ERR << "Error tracing best-path back (likely "
                << "bug in token-pruning algorithm)";
    }
  } else {
    oarc->ilabel = 0;
    oarc->olabel = 0;
    oarc->weight = LatticeWeight::One(); // zero costs.
  }
  return BestPathIterator(tok->backpointer, ret_t);
}

---

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

• decoder/lattice-incremental-online-decoder.h
• decoder/lattice-incremental-online-decoder.cc