LatticeFasterOnlineDecoderTpl< FST > Class Template Reference

LatticeFasterOnlineDecoderTpl is as LatticeFasterDecoderTpl 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-faster-online-decoder.h>

Inheritance diagram for LatticeFasterOnlineDecoderTpl< FST >:

Collaboration diagram for LatticeFasterOnlineDecoderTpl< 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 LatticeFasterDecoderTpl< 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
	LatticeFasterOnlineDecoderTpl (const FST &fst, const LatticeFasterDecoderConfig &config)
	LatticeFasterOnlineDecoderTpl (const LatticeFasterDecoderConfig &config, FST *fst)
bool	GetBestPath (Lattice *ofst, bool use_final_probs=true) const
	Outputs an FST corresponding to the single best path through the lattice. More...
bool	TestGetBestPath (bool use_final_probs=true) const
	This function does a self-test of GetBestPath(). 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...
bool	GetRawLatticePruned (Lattice *ofst, bool use_final_probs, BaseFloat beam) const
	Behaves the same as GetRawLattice but only processes tokens whose extra_cost is smaller than the best-cost plus the specified beam. More...
	KALDI_DISALLOW_COPY_AND_ASSIGN (LatticeFasterOnlineDecoderTpl)
Public Member Functions inherited from LatticeFasterDecoderTpl< FST, decoder::BackpointerToken >
	LatticeFasterDecoderTpl (const FST &fst, const LatticeFasterDecoderConfig &config)
	LatticeFasterDecoderTpl (const LatticeFasterDecoderConfig &config, FST *fst)
void	SetOptions (const LatticeFasterDecoderConfig &config)
const LatticeFasterDecoderConfig &	GetOptions () const
	~LatticeFasterDecoderTpl ()
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

Additional Inherited Members
Protected Types inherited from LatticeFasterDecoderTpl< FST, decoder::BackpointerToken >
using	Elem = typename HashList< StateId, decoder::BackpointerToken *>::Elem
Protected Member Functions inherited from LatticeFasterDecoderTpl< FST, decoder::BackpointerToken >
void	PossiblyResizeHash (size_t num_toks)
Elem *	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)
	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 (LatticeFasterDecoderTpl)
Static Protected Member Functions inherited from LatticeFasterDecoderTpl< FST, decoder::BackpointerToken >
static void	DeleteForwardLinks (decoder::BackpointerToken *tok)
static void	TopSortTokens (decoder::BackpointerToken *tok_list, std::vector< decoder::BackpointerToken * > *topsorted_list)
Protected Attributes inherited from LatticeFasterDecoderTpl< FST, decoder::BackpointerToken >
HashList< StateId, decoder::BackpointerToken *>	toks_
std::vector< TokenList >	active_toks_
std::vector< const Elem * >	queue_
std::vector< BaseFloat >	tmp_array_
const FST *	fst_
bool	delete_fst_
std::vector< BaseFloat >	cost_offsets_
LatticeFasterDecoderConfig	config_
int32	num_toks_
bool	warned_
bool	decoding_finalized_
	decoding_finalized_ is true if someone called FinalizeDecoding(). More...
unordered_map< decoder::BackpointerToken *, BaseFloat >	final_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

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

LatticeFasterOnlineDecoderTpl is as LatticeFasterDecoderTpl 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 LatticeFasterDecoderTpl with Token == BackpointerToken if you do so indirectly via this child class.

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

Member Typedef Documentation

Arc

using Arc = typename FST::Arc

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

ForwardLinkT

using ForwardLinkT = decoder::ForwardLink<Token>

Definition at line 62 of file lattice-faster-online-decoder.h.

Label

using Label = typename Arc::Label

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

StateId

using StateId = typename Arc::StateId

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

Token

using Token = decoder::BackpointerToken

Definition at line 61 of file lattice-faster-online-decoder.h.

Weight

using Weight = typename Arc::Weight

Definition at line 60 of file lattice-faster-online-decoder.h.

Constructor & Destructor Documentation

LatticeFasterOnlineDecoderTpl() [1/2]

LatticeFasterOnlineDecoderTpl ( const FST &  fst, const LatticeFasterDecoderConfig &  config  )

inline

Definition at line 67 of file lattice-faster-online-decoder.h.

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

LatticeFasterOnlineDecoderTpl() [2/2]

LatticeFasterOnlineDecoderTpl ( const LatticeFasterDecoderConfig &  config, FST *  fst  )

inline

Definition at line 73 of file lattice-faster-online-decoder.h.

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

Member Function Documentation

BestPathEnd()

LatticeFasterOnlineDecoderTpl< 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 78 of file lattice-faster-online-decoder.cc.

Referenced by OnlineSilenceWeighting::ComputeCurrentTraceback(), and LatticeFasterOnlineDecoderTpl< 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)
    *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 56 of file lattice-faster-online-decoder.cc.

Referenced by LatticeFasterOnlineDecoderTpl< FST >::BestPathIterator::Done(), SingleUtteranceNnet2Decoder::GetBestPath(), SingleUtteranceGmmDecoder::GetBestPath(), and SingleUtteranceNnet2DecoderThreaded::GetBestPath().

                                                                                 {
  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;
}

GetRawLatticePruned()

bool GetRawLatticePruned	(	Lattice *	ofst,
		bool	use_final_probs,
		BaseFloat	beam
	)		const

Behaves the same as GetRawLattice but only processes tokens whose extra_cost is smaller than the best-cost plus the specified beam.

It is only worthwhile to call this function if beam is less than the lattice_beam specified in the config; otherwise, it would return essentially the same thing as GetRawLattice, but more slowly.

Definition at line 168 of file lattice-faster-online-decoder.cc.

Referenced by LatticeFasterOnlineDecoderTpl< FST >::BestPathIterator::Done(), and SingleUtteranceGmmDecoder::GetGaussianPosteriors().

                          {
  typedef LatticeArc Arc;
  typedef Arc::StateId StateId;
  typedef Arc::Weight Weight;
  typedef Arc::Label Label;

  // Note: you can't use the old interface (Decode()) if you want to
  // get the lattice with use_final_probs = false.  You'd have to do
  // InitDecoding() and then AdvanceDecoding().
  if (this->decoding_finalized_ && !use_final_probs)
    KALDI_ERR << "You cannot call FinalizeDecoding() and then call "
              << "GetRawLattice() with use_final_probs == false";

  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);

  ofst->DeleteStates();
  // num-frames plus one (since frames are one-based, and we have
  // an extra frame for the start-state).
  int32 num_frames = this->active_toks_.size() - 1;
  KALDI_ASSERT(num_frames > 0);
  for (int32 f = 0; f <= num_frames; f++) {
    if (this->active_toks_[f].toks == NULL) {
      KALDI_WARN << "No tokens active on frame " << f
                 << ": not producing lattice.\n";
      return false;
    }
  }
  unordered_map<Token*, StateId> tok_map;
  std::queue<std::pair<Token*, int32> > tok_queue;
  // First initialize the queue and states.  Put the initial state on the queue;
  // this is the last token in the list active_toks_[0].toks.
  for (Token *tok = this->active_toks_[0].toks;
       tok != NULL; tok = tok->next) {
    if (tok->next == NULL) {
      tok_map[tok] = ofst->AddState();
      ofst->SetStart(tok_map[tok]);
      std::pair<Token*, int32> tok_pair(tok, 0);  // #frame = 0
      tok_queue.push(tok_pair);
    }
  }

  // Next create states for "good" tokens
  while (!tok_queue.empty()) {
    std::pair<Token*, int32> cur_tok_pair = tok_queue.front();
    tok_queue.pop();
    Token *cur_tok = cur_tok_pair.first;
    int32 cur_frame = cur_tok_pair.second;
    KALDI_ASSERT(cur_frame >= 0 &&
                 cur_frame <= this->cost_offsets_.size());

    typename unordered_map<Token*, StateId>::const_iterator iter =
        tok_map.find(cur_tok);
    KALDI_ASSERT(iter != tok_map.end());
    StateId cur_state = iter->second;

    for (ForwardLinkT *l = cur_tok->links;
         l != NULL;
         l = l->next) {
      Token *next_tok = l->next_tok;
      if (next_tok->extra_cost < beam) {
        // so both the current and the next token are good; create the arc
        int32 next_frame = l->ilabel == 0 ? cur_frame : cur_frame + 1;
        StateId nextstate;
        if (tok_map.find(next_tok) == tok_map.end()) {
          nextstate = tok_map[next_tok] = ofst->AddState();
          tok_queue.push(std::pair<Token*, int32>(next_tok, next_frame));
        } else {
          nextstate = tok_map[next_tok];
        }
        BaseFloat cost_offset = (l->ilabel != 0 ?
                                 this->cost_offsets_[cur_frame] : 0);
        Arc arc(l->ilabel, l->olabel,
                Weight(l->graph_cost, l->acoustic_cost - cost_offset),
                nextstate);
        ofst->AddArc(cur_state, arc);
      }
    }
    if (cur_frame == num_frames) {
      if (use_final_probs && !final_costs.empty()) {
        typename unordered_map<Token*, BaseFloat>::const_iterator iter =
            final_costs.find(cur_tok);
        if (iter != final_costs.end())
          ofst->SetFinal(cur_state, LatticeWeight(iter->second, 0));
      } else {
        ofst->SetFinal(cur_state, LatticeWeight::One());
      }
    }
  }
  return (ofst->NumStates() != 0);
}

KALDI_DISALLOW_COPY_AND_ASSIGN()

KALDI_DISALLOW_COPY_AND_ASSIGN

(

LatticeFasterOnlineDecoderTpl< FST >

)

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

TestGetBestPath()

bool TestGetBestPath

(

bool

use_final_probs = true

)

const

This function does a self-test of GetBestPath().

Returns true on success; returns false and prints a warning on failure.

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

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

                                {
  Lattice lat1;
  {
    Lattice raw_lat;
    this->GetRawLattice(&raw_lat, use_final_probs);
    ShortestPath(raw_lat, &lat1);
  }
  Lattice lat2;
  GetBestPath(&lat2, use_final_probs);
  BaseFloat delta = 0.1;
  int32 num_paths = 1;
  if (!fst::RandEquivalent(lat1, lat2, num_paths, delta, rand())) {
    KALDI_WARN << "Best-path test failed";
    return false;
  } else {
    return true;
  }
}

TraceBackBestPath()

LatticeFasterOnlineDecoderTpl< 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 132 of file lattice-faster-online-decoder.cc.

Referenced by OnlineSilenceWeighting::ComputeCurrentTraceback(), and LatticeFasterOnlineDecoderTpl< 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-faster-online-decoder.h
• decoder/lattice-faster-online-decoder.cc