LatticeIncrementalDecoderTpl< FST, Token > Class Template Reference

This is an extention to the "normal" lattice-generating decoder. More...

#include <lattice-incremental-decoder.h>

Collaboration diagram for LatticeIncrementalDecoderTpl< FST, Token >:

Classes
struct	TokenList

Public Types
using	Arc = typename FST::Arc
using	Label = typename Arc::Label
using	StateId = typename Arc::StateId
using	Weight = typename Arc::Weight
using	ForwardLinkT = decoder::ForwardLink< Token >

Public Member Functions
	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...

Protected Types
using	Elem = typename HashList< StateId, Token * >::Elem

Protected Member Functions
void	PossiblyResizeHash (size_t num_toks)
Token *	FindOrAddToken (StateId state, int32 frame_plus_one, BaseFloat tot_cost, Token *backpointer, bool *changed)
void	PruneForwardLinks (int32 frame_plus_one, bool *extra_costs_changed, bool *links_pruned, BaseFloat delta)
void	ComputeFinalCosts (unordered_map< Token *, BaseFloat > *final_costs, BaseFloat *final_relative_cost, BaseFloat *final_best_cost) const
void	PruneForwardLinksFinal ()
void	PruneTokensForFrame (int32 frame_plus_one)
void	PruneActiveTokens (BaseFloat delta)
BaseFloat	GetCutoff (Elem *list_head, size_t *tok_count, BaseFloat *adaptive_beam, Elem **best_elem)
	Gets the weight cutoff. Also counts the active tokens. More...
BaseFloat	ProcessEmitting (DecodableInterface *decodable)
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
static void	DeleteForwardLinks (Token *tok)
	NOTE: for parts the internal implementation that are shared with LatticeFasterDecoer, we have removed the comments. More...

Protected Attributes
HashList< StateId, Token * >	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< Token *, 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< Token *, 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< Token *, Label >	token2label_map_
unordered_map< Token *, Label >	token2label_map_temp_
Label	next_token_label_

Detailed Description

template<typename FST, typename Token = decoder::StdToken>
class kaldi::LatticeIncrementalDecoderTpl< FST, Token >

This is an extention to the "normal" lattice-generating decoder.

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

The main difference is the incremental determinization which will be discussed in the function GetLattice(). This means that the work of determinizatin isn't done all at once at the end of the file, but incrementally while decoding. See the comment at the top of this file for more explanation.

The decoder is templated on the FST type and the token type. The token type will normally be StdToken, but also may be BackpointerToken which is to support quick lookup of the current best path (see lattice-faster-online-decoder.h)

The FST you invoke this decoder with is expected to be of type Fst::Fst<fst::StdArc>, a.k.a. StdFst, or GrammarFst. If you invoke it with FST == StdFst and it notices that the actual FST type is fst::VectorFst<fst::StdArc> or fst::ConstFst<fst::StdArc>, the decoder object will internally cast itself to one that is templated on those more specific types; this is an optimization for speed.

Definition at line 465 of file lattice-incremental-decoder.h.

Member Typedef Documentation

Arc

using Arc = typename FST::Arc

Definition at line 467 of file lattice-incremental-decoder.h.

Elem

using Elem = typename HashList<StateId, Token *>::Elem

protected

Definition at line 625 of file lattice-incremental-decoder.h.

ForwardLinkT

using ForwardLinkT = decoder::ForwardLink<Token>

Definition at line 471 of file lattice-incremental-decoder.h.

Label

using Label = typename Arc::Label

Definition at line 468 of file lattice-incremental-decoder.h.

StateId

using StateId = typename Arc::StateId

Definition at line 469 of file lattice-incremental-decoder.h.

Weight

using Weight = typename Arc::Weight

Definition at line 470 of file lattice-incremental-decoder.h.

Constructor & Destructor Documentation

LatticeIncrementalDecoderTpl() [1/2]

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

Definition at line 28 of file lattice-incremental-decoder.cc.

    : fst_(&fst),
      delete_fst_(false),
      num_toks_(0),
      config_(config),
      determinizer_(trans_model, config) {
  config.Check();
  toks_.SetSize(1000); // just so on the first frame we do something reasonable.
}

LatticeIncrementalDecoderTpl() [2/2]

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

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

    : fst_(fst),
      delete_fst_(true),
      num_toks_(0),
      config_(config),
      determinizer_(trans_model, config) {
  config.Check();
  toks_.SetSize(1000); // just so on the first frame we do something reasonable.
}

~LatticeIncrementalDecoderTpl()

~LatticeIncrementalDecoderTpl

(

)

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

                                                                        {
  DeleteElems(toks_.Clear());
  ClearActiveTokens();
  if (delete_fst_) delete fst_;
}

Member Function Documentation

AdvanceDecoding()

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 (this is the normal pattern in a real-time/online decoding scenario). If max_num_frames is specified, it specifies the maximum number of frames the function will decode before returning.

Definition at line 539 of file lattice-incremental-decoder.cc.

Referenced by LatticeIncrementalDecoderTpl< FST, decoder::BackpointerToken >::AdvanceDecoding().

                                                         {
  if (std::is_same<FST, fst::Fst<fst::StdArc> >::value) {
    // if the type 'FST' is the FST base-class, then see if the FST type of fst_
    // is actually VectorFst or ConstFst.  If so, call the AdvanceDecoding()
    // function after casting *this to the more specific type.
    if (fst_->Type() == "const") {
      LatticeIncrementalDecoderTpl<fst::ConstFst<fst::StdArc>, Token> *this_cast =
          reinterpret_cast<
              LatticeIncrementalDecoderTpl<fst::ConstFst<fst::StdArc>, Token> *>(
              this);
      this_cast->AdvanceDecoding(decodable, max_num_frames);
      return;
    } else if (fst_->Type() == "vector") {
      LatticeIncrementalDecoderTpl<fst::VectorFst<fst::StdArc>, Token> *this_cast =
          reinterpret_cast<
              LatticeIncrementalDecoderTpl<fst::VectorFst<fst::StdArc>, Token> *>(
              this);
      this_cast->AdvanceDecoding(decodable, max_num_frames);
      return;
    }
  }

  KALDI_ASSERT(!active_toks_.empty() && !decoding_finalized_ &&
               "You must call InitDecoding() before AdvanceDecoding");
  int32 num_frames_ready = decodable->NumFramesReady();
  // num_frames_ready must be >= num_frames_decoded, or else
  // the number of frames ready must have decreased (which doesn't
  // make sense) or the decodable object changed between calls
  // (which isn't allowed).
  KALDI_ASSERT(num_frames_ready >= NumFramesDecoded());
  int32 target_frames_decoded = num_frames_ready;
  if (max_num_frames >= 0)
    target_frames_decoded =
        std::min(target_frames_decoded, NumFramesDecoded() + max_num_frames);
  while (NumFramesDecoded() < target_frames_decoded) {
    if (NumFramesDecoded() % config_.prune_interval == 0) {
      PruneActiveTokens(config_.lattice_beam * config_.prune_scale);
    }
    BaseFloat cost_cutoff = ProcessEmitting(decodable);
    ProcessNonemitting(cost_cutoff);
  }
  UpdateLatticeDeterminization();
}

AllocateNewTokenLabel()

Label AllocateNewTokenLabel ( )

inlineprotected

Definition at line 684 of file lattice-incremental-decoder.h.

{ return next_token_label_++; }

ClearActiveTokens()

void ClearActiveTokens ( )

protected

Definition at line 852 of file lattice-incremental-decoder.cc.

                                   { // a cleanup routine, at utt end/begin
  for (size_t i = 0; i < active_toks_.size(); i++) {
    // Delete all tokens alive on this frame, and any forward
    // links they may have.
    for (Token *tok = active_toks_[i].toks; tok != NULL;) {
      DeleteForwardLinks(tok);
      Token *next_tok = tok->next;
      delete tok;
      num_toks_--;
      tok = next_tok;
    }
  }
  active_toks_.clear();
  KALDI_ASSERT(num_toks_ == 0);
}

ComputeFinalCosts()

void ComputeFinalCosts ( unordered_map< Token *, BaseFloat > *  final_costs, BaseFloat *  final_relative_cost, BaseFloat *  final_best_cost  ) const

protected

Definition at line 492 of file lattice-incremental-decoder.cc.

                                      {
  if (decoding_finalized_) {
    // If we finalized decoding, the list toks_ will no longer exist, so return
    // something we already computed.
    if (final_costs) *final_costs = final_costs_;
    if (final_relative_cost) *final_relative_cost = final_relative_cost_;
    if (final_best_cost) *final_best_cost = final_best_cost_;
    return;
  }
  if (final_costs != NULL) final_costs->clear();
  const Elem *final_toks = toks_.GetList();
  BaseFloat infinity = std::numeric_limits<BaseFloat>::infinity();
  BaseFloat best_cost = infinity, best_cost_with_final = infinity;

  while (final_toks != NULL) {
    StateId state = final_toks->key;
    Token *tok = final_toks->val;
    const Elem *next = final_toks->tail;
    BaseFloat final_cost = fst_->Final(state).Value();
    BaseFloat cost = tok->tot_cost, cost_with_final = cost + final_cost;
    best_cost = std::min(cost, best_cost);
    best_cost_with_final = std::min(cost_with_final, best_cost_with_final);
    if (final_costs != NULL && final_cost != infinity)
      (*final_costs)[tok] = final_cost;
    final_toks = next;
  }
  if (final_relative_cost != NULL) {
    if (best_cost == infinity && best_cost_with_final == infinity) {
      // Likely this will only happen if there are no tokens surviving.
      // This seems the least bad way to handle it.
      *final_relative_cost = infinity;
    } else {
      *final_relative_cost = best_cost_with_final - best_cost;
    }
  }
  if (final_best_cost != NULL) {
    if (best_cost_with_final != infinity) { // final-state exists.
      *final_best_cost = best_cost_with_final;
    } else { // no final-state exists.
      *final_best_cost = best_cost;
    }
  }
}

Decode()

bool Decode

(

DecodableInterface *

decodable

)

CAUTION: it's unlikely that you will ever want to call this function.

In a scenario where you have the entire file and just want to decode it, there is no point using this decoder.

An example of how to do decoding together with incremental determinization. It decodes until there are no more frames left in the "decodable" object.

In this example, config_.determinize_delay, config_.determinize_period and config_.determinize_max_active are used to determine the time to call GetLattice().

Users will probably want to use appropriate combinations of AdvanceDecoding() and GetLattice() to build their application; this just gives you some idea how.

The function returns true if any kind of traceback is available (not necessarily from a final state).

Definition at line 121 of file lattice-incremental-decoder.cc.

Referenced by kaldi::DecodeUtteranceLatticeIncremental().

                                                                                   {
  InitDecoding();

  // We use 1-based indexing for frames in this decoder (if you view it in
  // terms of features), but note that the decodable object uses zero-based
  // numbering, which we have to correct for when we call it.

  while (!decodable->IsLastFrame(NumFramesDecoded() - 1)) {
    if (NumFramesDecoded() % config_.prune_interval == 0) {
      PruneActiveTokens(config_.lattice_beam * config_.prune_scale);
    }
    UpdateLatticeDeterminization();

    BaseFloat cost_cutoff = ProcessEmitting(decodable);
    ProcessNonemitting(cost_cutoff);
  }
  Timer timer;
  FinalizeDecoding();
  bool use_final_probs = true;
  GetLattice(NumFramesDecoded(), use_final_probs);
  KALDI_VLOG(2) << "Delay time during and after FinalizeDecoding()"
                << "(secs): " << timer.Elapsed();

  // Returns true if we have any kind of traceback available (not necessarily
  // to the end state; query ReachedFinal() for that).
  return !active_toks_.empty() && active_toks_.back().toks != NULL;
}

DeleteElems()

void DeleteElems ( Elem *  list )

protected

Definition at line 843 of file lattice-incremental-decoder.cc.

                                                                     {
  for (Elem *e = list, *e_tail; e != NULL; e = e_tail) {
    e_tail = e->tail;
    toks_.Delete(e);
  }
}

DeleteForwardLinks()

void DeleteForwardLinks ( Token *  tok )

inlinestaticprotected

NOTE: for parts the internal implementation that are shared with LatticeFasterDecoer, we have removed the comments.

Definition at line 765 of file lattice-incremental-decoder.cc.

                                                                            {
  ForwardLinkT *l = tok->links, *m;
  while (l != NULL) {
    m = l->next;
    delete l;
    l = m;
  }
  tok->links = NULL;
}

FinalizeDecoding()

void FinalizeDecoding

(

)

Finalizes the decoding, doing an extra pruning step on the last frame that uses the final-probs.

May be called only once.

Definition at line 588 of file lattice-incremental-decoder.cc.

                                                                {
  int32 final_frame_plus_one = NumFramesDecoded();
  int32 num_toks_begin = num_toks_;
  // PruneForwardLinksFinal() prunes the final frame (with final-probs), and
  // sets decoding_finalized_.
  PruneForwardLinksFinal();
  for (int32 f = final_frame_plus_one - 1; f >= 0; f--) {
    bool b1, b2;              // values not used.
    BaseFloat dontcare = 0.0; // delta of zero means we must always update
    PruneForwardLinks(f, &b1, &b2, dontcare);
    PruneTokensForFrame(f + 1);
  }
  PruneTokensForFrame(0);
  KALDI_VLOG(4) << "pruned tokens from " << num_toks_begin << " to " << num_toks_;
}

FinalRelativeCost()

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 409 of file lattice-incremental-decoder.cc.

                                                                            {
  BaseFloat relative_cost;
  ComputeFinalCosts(NULL, &relative_cost, NULL);
  return relative_cost;
}

FindOrAddToken()

Token * FindOrAddToken ( StateId  state, int32  frame_plus_one, BaseFloat  tot_cost, Token *  backpointer, bool *  changed  )

inlineprotected

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

                   {
  // Returns the Token pointer.  Sets "changed" (if non-NULL) to true
  // if the token was newly created or the cost changed.
  KALDI_ASSERT(frame_plus_one < active_toks_.size());
  Token *&toks = active_toks_[frame_plus_one].toks;
  Elem *e_found = toks_.Find(state);
  if (e_found == NULL) { // no such token presently.
    const BaseFloat extra_cost = 0.0;
    // tokens on the currently final frame have zero extra_cost
    // as any of them could end up
    // on the winning path.
    Token *new_tok = new Token(tot_cost, extra_cost, NULL, toks, backpointer);
    // NULL: no forward links yet
    toks = new_tok;
    num_toks_++;
    toks_.Insert(state, new_tok);
    if (changed) *changed = true;
    return new_tok;
  } else {
    Token *tok = e_found->val;      // There is an existing Token for this state.
    if (tok->tot_cost > tot_cost) { // replace old token
      tok->tot_cost = tot_cost;
      // SetBackpointer() just does tok->backpointer = backpointer in
      // the case where Token == BackpointerToken, else nothing.
      tok->SetBackpointer(backpointer);
      // we don't allocate a new token, the old stays linked in active_toks_
      // we only replace the tot_cost
      // in the current frame, there are no forward links (and no extra_cost)
      // only in ProcessNonemitting we have to delete forward links
      // in case we visit a state for the second time
      // those forward links, that lead to this replaced token before:
      // they remain and will hopefully be pruned later (PruneForwardLinks...)
      if (changed) *changed = true;
    } else {
      if (changed) *changed = false;
    }
    return tok;
  }
}

GetCutoff()

BaseFloat GetCutoff ( Elem *  list_head, size_t *  tok_count, BaseFloat *  adaptive_beam, Elem **  best_elem  )

protected

Gets the weight cutoff. Also counts the active tokens.

Definition at line 606 of file lattice-incremental-decoder.cc.

                                                                                    {
  BaseFloat best_weight = std::numeric_limits<BaseFloat>::infinity();
  // positive == high cost == bad.
  size_t count = 0;
  if (config_.max_active == std::numeric_limits<int32>::max() &&
      config_.min_active == 0) {
    for (Elem *e = list_head; e != NULL; e = e->tail, count++) {
      BaseFloat w = static_cast<BaseFloat>(e->val->tot_cost);
      if (w < best_weight) {
        best_weight = w;
        if (best_elem) *best_elem = e;
      }
    }
    if (tok_count != NULL) *tok_count = count;
    if (adaptive_beam != NULL) *adaptive_beam = config_.beam;
    return best_weight + config_.beam;
  } else {
    tmp_array_.clear();
    for (Elem *e = list_head; e != NULL; e = e->tail, count++) {
      BaseFloat w = e->val->tot_cost;
      tmp_array_.push_back(w);
      if (w < best_weight) {
        best_weight = w;
        if (best_elem) *best_elem = e;
      }
    }
    if (tok_count != NULL) *tok_count = count;

    BaseFloat beam_cutoff = best_weight + config_.beam,
              min_active_cutoff = std::numeric_limits<BaseFloat>::infinity(),
              max_active_cutoff = std::numeric_limits<BaseFloat>::infinity();

    KALDI_VLOG(6) << "Number of tokens active on frame " << NumFramesDecoded()
                  << " is " << tmp_array_.size();

    if (tmp_array_.size() > static_cast<size_t>(config_.max_active)) {
      std::nth_element(tmp_array_.begin(), tmp_array_.begin() + config_.max_active,
                       tmp_array_.end());
      max_active_cutoff = tmp_array_[config_.max_active];
    }
    if (max_active_cutoff < beam_cutoff) { // max_active is tighter than beam.
      if (adaptive_beam)
        *adaptive_beam = max_active_cutoff - best_weight + config_.beam_delta;
      return max_active_cutoff;
    }
    if (tmp_array_.size() > static_cast<size_t>(config_.min_active)) {
      if (config_.min_active == 0)
        min_active_cutoff = best_weight;
      else {
        std::nth_element(tmp_array_.begin(), tmp_array_.begin() + config_.min_active,
                         tmp_array_.size() > static_cast<size_t>(config_.max_active)
                             ? tmp_array_.begin() + config_.max_active
                             : tmp_array_.end());
        min_active_cutoff = tmp_array_[config_.min_active];
      }
    }
    if (min_active_cutoff > beam_cutoff) { // min_active is looser than beam.
      if (adaptive_beam)
        *adaptive_beam = min_active_cutoff - best_weight + config_.beam_delta;
      return min_active_cutoff;
    } else {
      *adaptive_beam = config_.beam;
      return beam_cutoff;
    }
  }
}

GetLattice()

const CompactLattice & GetLattice	(	int32	num_frames_to_include,
		bool	use_final_probs = false
	)

This decoder has no GetBestPath() function.

If you need that functionality you should probably use lattice-incremental-online-decoder.h, which makes it very efficient to obtain the best path. This GetLattice() function returns the lattice containing `num_frames_to_decode` frames; this will be all frames decoded so far, if you let num_frames_to_decode == NumFramesDecoded(), but it will generally be better to make it a few frames less than that to avoid the lattice having too many active states at the end.

Parameters

[in]	num_frames_to_include	The number of frames that you want to be included in the lattice. Must be >= NumFramesInLattice() and <= NumFramesDecoded().
[in]	use_final_probs	True if you want the final-probs of HCLG to be included in the output lattice. Must not be set to true if num_frames_to_include != NumFramesDecoded(). Must be set to true if you have previously called FinalizeDecoding().

(If no state was final on frame `num_frames_to_include`, the final-probs won't be included regardless of `use_final_probs`; you can test whether this was the case by calling ReachedFinal().

Returns

clat The CompactLattice representing what has been decoded up until `num_frames_to_include` (e.g., LatticeStateTimes() on this lattice would return `num_frames_to_include`).

See also UpdateLatticeDeterminizaton(). Caution: this const ref is only valid until the next time you call AdvanceDecoding() or GetLattice().

CAUTION: the lattice may contain disconnnected states; you should call Connect() on the output before writing it out.

Definition at line 870 of file lattice-incremental-decoder.cc.

Referenced by kaldi::DecodeUtteranceLatticeIncremental().

                          {
  KALDI_ASSERT(num_frames_to_include >= num_frames_in_lattice_ &&
               num_frames_to_include <= NumFramesDecoded());


  if (num_frames_in_lattice_ > 0 &&
      determinizer_.GetLattice().NumStates() == 0) {
    /* Something went wrong, lattice is empty and will continue to be empty.
       User-level code should detect and deal with this.
     */
    num_frames_in_lattice_ = num_frames_to_include;
    return determinizer_.GetLattice();
  }

  if (decoding_finalized_ && !use_final_probs) {
    // This is not supported
    KALDI_ERR << "You cannot get the lattice without final-probs after "
        "calling FinalizeDecoding().";
  }
  if (use_final_probs && num_frames_to_include != NumFramesDecoded()) {
    /* This is because we only remember the relation between HCLG states and
       Tokens for the current frame; the Token does not have a `state` field. */
    KALDI_ERR << "use-final-probs may no be true if you are not "
        "getting a lattice for all frames decoded so far.";
  }


  if (num_frames_to_include > num_frames_in_lattice_) {
    /* Make sure the token-pruning is up to date.   If we just pruned the tokens,
       this will do very little work. */
    PruneActiveTokens(config_.lattice_beam * config_.prune_scale);

    if (determinizer_.GetLattice().NumStates() == 0 ||
        determinizer_.GetLattice().Final(0) != CompactLatticeWeight::Zero()) {
      num_frames_in_lattice_ = 0;
      determinizer_.Init();
    }

    Lattice chunk_lat;

    unordered_map<Label, LatticeArc::StateId> token_label2state;
    if (num_frames_in_lattice_ != 0) {
      determinizer_.InitializeRawLatticeChunk(&chunk_lat,
                                              &token_label2state);
    }

    // tok_map will map from Token* to state-id in chunk_lat.
    // The cur and prev versions alternate on different frames.
    unordered_map<Token*, StateId> &tok2state_map(temp_token_map_);
    tok2state_map.clear();

    unordered_map<Token*, Label> &next_token2label_map(token2label_map_temp_);
    next_token2label_map.clear();

    { // Deal with the last frame in the chunk, the one numbered `num_frames_to_include`.
      // (Yes, this is backwards).   We allocate token labels, and set tokens as
      // final, but don't add any transitions.  This may leave some states
      // disconnected (e.g. due to chains of nonemitting arcs), but it's OK; we'll
      // fix it when we generate the next chunk of lattice.
      int32 frame = num_frames_to_include;
      // Allocate state-ids for all tokens on this frame.

      for (Token *tok = active_toks_[frame].toks; tok != NULL; tok = tok->next) {
        /* If we included the final-costs at this stage, they will cause
           non-final states to be pruned out from the end of the lattice. */
        BaseFloat final_cost;
        {  // This block computes final_cost
          if (decoding_finalized_) {
            if (final_costs_.empty()) {
              final_cost = 0.0;  /* No final-state survived, so treat all as final
                                  * with probability One(). */
            } else {
              auto iter = final_costs_.find(tok);
              if (iter == final_costs_.end())
                final_cost = std::numeric_limits<BaseFloat>::infinity();
              else
                final_cost = iter->second;
            }
          } else {
            /* this is a `fake` final-cost used to guide pruning.  It's as if we
               set the betas (backward-probs) on the final frame to the
               negatives of the corresponding alphas, so all tokens on the last
               frae will be on a best path..  the extra_cost for each token
               always corresponds to its alpha+beta on this assumption.  We want
               the final_cost here to correspond to the beta (backward-prob), so
               we get that by final_cost = extra_cost - tot_cost.
               [The tot_cost is the forward/alpha cost.]
            */
            final_cost = tok->extra_cost - tok->tot_cost;
          }
        }

        StateId state = chunk_lat.AddState();
        tok2state_map[tok] = state;
        if (final_cost < std::numeric_limits<BaseFloat>::infinity()) {
          next_token2label_map[tok] = AllocateNewTokenLabel();
          StateId token_final_state = chunk_lat.AddState();
          LatticeArc::Label ilabel = 0,
              olabel = (next_token2label_map[tok] = AllocateNewTokenLabel());
          chunk_lat.AddArc(state,
                           LatticeArc(ilabel, olabel,
                                      LatticeWeight::One(),
                                      token_final_state));
          chunk_lat.SetFinal(token_final_state, LatticeWeight(final_cost, 0.0));
        }
      }
    }

    // Go in reverse order over the remaining frames so we can create arcs as we
    // go, and their destination-states will already be in the map.
    for (int32 frame = num_frames_to_include;
         frame >= num_frames_in_lattice_; frame--) {
      // The conditional below is needed for the last frame of the utterance.
      BaseFloat cost_offset = (frame < cost_offsets_.size() ?
                               cost_offsets_[frame] : 0.0);

      // For the first frame of the chunk, we need to make sure the states are
      // the ones created by InitializeRawLatticeChunk() (where not pruned away).
      if (frame == num_frames_in_lattice_ && num_frames_in_lattice_ != 0) {
        for (Token *tok = active_toks_[frame].toks; tok != NULL; tok = tok->next) {
          auto iter = token2label_map_.find(tok);
          KALDI_ASSERT(iter != token2label_map_.end());
          Label token_label = iter->second;
          auto iter2 = token_label2state.find(token_label);
          if (iter2 != token_label2state.end()) {
            StateId state = iter2->second;
            tok2state_map[tok] = state;
          } else {
            // Some states may have been pruned out, but we should still allocate
            // them.  They might have been part of chains of nonemitting arcs
            // where the state became disconnected because the last chunk didn't
            // include arcs starting at this frame.
            StateId state = chunk_lat.AddState();
            tok2state_map[tok] = state;
          }
        }
      } else if (frame != num_frames_to_include) {  // We already created states
                                                    // for the last frame.
        for (Token *tok = active_toks_[frame].toks; tok != NULL; tok = tok->next) {
          StateId state = chunk_lat.AddState();
          tok2state_map[tok] = state;
        }
      }
      for (Token *tok = active_toks_[frame].toks; tok != NULL; tok = tok->next) {
        auto iter = tok2state_map.find(tok);
        KALDI_ASSERT(iter != tok2state_map.end());
        StateId cur_state = iter->second;
        for (ForwardLinkT *l = tok->links; l != NULL; l = l->next) {
          auto next_iter = tok2state_map.find(l->next_tok);
          if (next_iter == tok2state_map.end()) {
            // Emitting arcs from the last frame we're including -- ignore
            // these.
            KALDI_ASSERT(frame == num_frames_to_include);
            continue;
          }
          StateId next_state = next_iter->second;
          BaseFloat this_offset = (l->ilabel != 0 ? cost_offset : 0);
          LatticeArc arc(l->ilabel, l->olabel,
                         LatticeWeight(l->graph_cost, l->acoustic_cost - this_offset),
                         next_state);
          // Note: the epsilons get redundantly included at the end and beginning
          // of successive chunks.  These will get removed in the determinization.
          chunk_lat.AddArc(cur_state, arc);
        }
      }
    }
    if (num_frames_in_lattice_ == 0) {
      // This block locates the start token.  NOTE: we use the fact that in the
      // linked list of tokens, things are added at the head, so the start state
      // must be at the tail.  If this data structure is changed in future, we
      // might need to explicitly store the start token as a class member.
      Token *tok = active_toks_[0].toks;
      if (tok == NULL) {
        KALDI_WARN << "No tokens exist on start frame";
        return determinizer_.GetLattice();  // will be empty.
      }
      while (tok->next != NULL)
        tok = tok->next;
      Token *start_token = tok;
      auto iter = tok2state_map.find(start_token);
      KALDI_ASSERT(iter != tok2state_map.end());
      StateId start_state = iter->second;
      chunk_lat.SetStart(start_state);
    }
    token2label_map_.swap(next_token2label_map);

    // bool finished_before_beam =
    determinizer_.AcceptRawLatticeChunk(&chunk_lat);
    // We are ignoring the return status, which say whether it finished before the beam.

    num_frames_in_lattice_ = num_frames_to_include;

    if (determinizer_.GetLattice().NumStates() == 0)
      return determinizer_.GetLattice();   // Something went wrong, lattice is empty.
  }

  unordered_map<Token*, BaseFloat> token2final_cost;
  unordered_map<Label, BaseFloat> token_label2final_cost;
  if (use_final_probs) {
    ComputeFinalCosts(&token2final_cost, NULL, NULL);
    for (const auto &p: token2final_cost) {
      Token *tok = p.first;
      BaseFloat cost = p.second;
      auto iter = token2label_map_.find(tok);
      if (iter != token2label_map_.end()) {
        /* Some tokens may not have survived the pruned determinization. */
        Label token_label = iter->second;
        bool ret = token_label2final_cost.insert({token_label, cost}).second;
        KALDI_ASSERT(ret); /* Make sure it was inserted. */
      }
    }
  }
  /* Note: these final-probs won't affect the next chunk, only the lattice
     returned from GetLattice().  They are kind of temporaries. */
  determinizer_.SetFinalCosts(token_label2final_cost.empty() ? NULL :
                              &token_label2final_cost);

  return determinizer_.GetLattice();
}

GetNumToksForFrame()

int32 GetNumToksForFrame ( int32  frame )

protected

Definition at line 1094 of file lattice-incremental-decoder.cc.

                                                                              {
  int32 r = 0;
  for (Token *tok = active_toks_[frame].toks; tok; tok = tok->next) r++;
  return r;
}

GetOptions()

const LatticeIncrementalDecoderConfig& GetOptions ( ) const

inline

Definition at line 486 of file lattice-incremental-decoder.h.

{ return config_; }

InitDecoding()

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 61 of file lattice-incremental-decoder.cc.

                                                            {
  // clean up from last time:
  DeleteElems(toks_.Clear());
  cost_offsets_.clear();
  ClearActiveTokens();
  warned_ = false;
  num_toks_ = 0;
  decoding_finalized_ = false;
  final_costs_.clear();
  StateId start_state = fst_->Start();
  KALDI_ASSERT(start_state != fst::kNoStateId);
  active_toks_.resize(1);
  Token *start_tok = new Token(0.0, 0.0, NULL, NULL, NULL);
  active_toks_[0].toks = start_tok;
  toks_.Insert(start_state, start_tok);
  num_toks_++;

  determinizer_.Init();
  num_frames_in_lattice_ = 0;
  token2label_map_.clear();
  next_token_label_ = LatticeIncrementalDeterminizer::kTokenLabelOffset;
  ProcessNonemitting(config_.beam);
}

KALDI_DISALLOW_COPY_AND_ASSIGN()

KALDI_DISALLOW_COPY_AND_ASSIGN ( LatticeIncrementalDecoderTpl< FST, Token >  )

protected

NumFramesDecoded()

int32 NumFramesDecoded ( ) const

inline

Returns the number of frames decoded so far.

Definition at line 600 of file lattice-incremental-decoder.h.

Referenced by kaldi::DecodeUtteranceLatticeIncremental().

{ return active_toks_.size() - 1; }

NumFramesInLattice()

int NumFramesInLattice ( ) const

inline

Definition at line 569 of file lattice-incremental-decoder.h.

{ return num_frames_in_lattice_; }

PossiblyResizeHash()

void PossiblyResizeHash ( size_t  num_toks )

protected

Definition at line 151 of file lattice-incremental-decoder.cc.

                                                                                 {
  size_t new_sz =
      static_cast<size_t>(static_cast<BaseFloat>(num_toks) * config_.hash_ratio);
  if (new_sz > toks_.Size()) {
    toks_.SetSize(new_sz);
  }
}

ProcessEmitting()

BaseFloat ProcessEmitting ( DecodableInterface *  decodable )

protected

Definition at line 675 of file lattice-incremental-decoder.cc.

                                   {
  KALDI_ASSERT(active_toks_.size() > 0);
  int32 frame = active_toks_.size() - 1; // frame is the frame-index
                                         // (zero-based) used to get likelihoods
                                         // from the decodable object.
  active_toks_.resize(active_toks_.size() + 1);

  Elem *final_toks = toks_.Clear(); // analogous to swapping prev_toks_ / cur_toks_
                                    // in simple-decoder.h.   Removes the Elems from
                                    // being indexed in the hash in toks_.
  Elem *best_elem = NULL;
  BaseFloat adaptive_beam;
  size_t tok_cnt;
  BaseFloat cur_cutoff = GetCutoff(final_toks, &tok_cnt, &adaptive_beam, &best_elem);
  KALDI_VLOG(6) << "Adaptive beam on frame " << NumFramesDecoded() << " is "
                << adaptive_beam;

  PossiblyResizeHash(tok_cnt); // This makes sure the hash is always big enough.

  BaseFloat next_cutoff = std::numeric_limits<BaseFloat>::infinity();
  // pruning "online" before having seen all tokens

  BaseFloat cost_offset = 0.0; // Used to keep probabilities in a good
                               // dynamic range.

  // First process the best token to get a hopefully
  // reasonably tight bound on the next cutoff.  The only
  // products of the next block are "next_cutoff" and "cost_offset".
  if (best_elem) {
    StateId state = best_elem->key;
    Token *tok = best_elem->val;
    cost_offset = -tok->tot_cost;
    for (fst::ArcIterator<FST> aiter(*fst_, state); !aiter.Done(); aiter.Next()) {
      const Arc &arc = aiter.Value();
      if (arc.ilabel != 0) { // propagate..
        BaseFloat new_weight = arc.weight.Value() + cost_offset -
                               decodable->LogLikelihood(frame, arc.ilabel) +
                               tok->tot_cost;
        if (new_weight + adaptive_beam < next_cutoff)
          next_cutoff = new_weight + adaptive_beam;
      }
    }
  }

  // Store the offset on the acoustic likelihoods that we're applying.
  // Could just do cost_offsets_.push_back(cost_offset), but we
  // do it this way as it's more robust to future code changes.
  cost_offsets_.resize(frame + 1, 0.0);
  cost_offsets_[frame] = cost_offset;

  // the tokens are now owned here, in final_toks, and the hash is empty.
  // 'owned' is a complex thing here; the point is we need to call DeleteElem
  // on each elem 'e' to let toks_ know we're done with them.
  for (Elem *e = final_toks, *e_tail; e != NULL; e = e_tail) {
    // loop this way because we delete "e" as we go.
    StateId state = e->key;
    Token *tok = e->val;
    if (tok->tot_cost <= cur_cutoff) {
      for (fst::ArcIterator<FST> aiter(*fst_, state); !aiter.Done(); aiter.Next()) {
        const Arc &arc = aiter.Value();
        if (arc.ilabel != 0) { // propagate..
          BaseFloat ac_cost =
                        cost_offset - decodable->LogLikelihood(frame, arc.ilabel),
                    graph_cost = arc.weight.Value(), cur_cost = tok->tot_cost,
                    tot_cost = cur_cost + ac_cost + graph_cost;
          if (tot_cost >= next_cutoff)
            continue;
          else if (tot_cost + adaptive_beam < next_cutoff)
            next_cutoff = tot_cost + adaptive_beam; // prune by best current token
          // Note: the frame indexes into active_toks_ are one-based,
          // hence the + 1.
          Token *next_tok =
              FindOrAddToken(arc.nextstate, frame + 1, tot_cost, tok, NULL);
          // NULL: no change indicator needed

          // Add ForwardLink from tok to next_tok (put on head of list tok->links)
          tok->links = new ForwardLinkT(next_tok, arc.ilabel, arc.olabel, graph_cost,
                                        ac_cost, tok->links);
        }
      } // for all arcs
    }
    e_tail = e->tail;
    toks_.Delete(e); // delete Elem
  }
  return next_cutoff;
}

ProcessNonemitting()

void ProcessNonemitting ( BaseFloat  cost_cutoff )

protected

Definition at line 776 of file lattice-incremental-decoder.cc.

                                                                                  {
  KALDI_ASSERT(!active_toks_.empty());
  int32 frame = static_cast<int32>(active_toks_.size()) - 2;
  // Note: "frame" is the time-index we just processed, or -1 if
  // we are processing the nonemitting transitions before the
  // first frame (called from InitDecoding()).

  // Processes nonemitting arcs for one frame.  Propagates within toks_.
  // Note-- this queue structure is is not very optimal as
  // it may cause us to process states unnecessarily (e.g. more than once),
  // but in the baseline code, turning this vector into a set to fix this
  // problem did not improve overall speed.

  KALDI_ASSERT(queue_.empty());

  if (toks_.GetList() == NULL) {
    if (!warned_) {
      KALDI_WARN << "Error, no surviving tokens: frame is " << frame;
      warned_ = true;
    }
  }

  for (const Elem *e = toks_.GetList(); e != NULL; e = e->tail) {
    StateId state = e->key;
    if (fst_->NumInputEpsilons(state) != 0) queue_.push_back(state);
  }

  while (!queue_.empty()) {
    StateId state = queue_.back();
    queue_.pop_back();

    Token *tok =
        toks_.Find(state)
            ->val; // would segfault if state not in toks_ but this can't happen.
    BaseFloat cur_cost = tok->tot_cost;
    if (cur_cost >= cutoff) // Don't bother processing successors.
      continue;
    // If "tok" has any existing forward links, delete them,
    // because we're about to regenerate them.  This is a kind
    // of non-optimality (remember, this is the simple decoder),
    // but since most states are emitting it's not a huge issue.
    DeleteForwardLinks(tok); // necessary when re-visiting
    tok->links = NULL;
    for (fst::ArcIterator<FST> aiter(*fst_, state); !aiter.Done(); aiter.Next()) {
      const Arc &arc = aiter.Value();
      if (arc.ilabel == 0) { // propagate nonemitting only...
        BaseFloat graph_cost = arc.weight.Value(), tot_cost = cur_cost + graph_cost;
        if (tot_cost < cutoff) {
          bool changed;

          Token *new_tok =
              FindOrAddToken(arc.nextstate, frame + 1, tot_cost, tok, &changed);

          tok->links =
              new ForwardLinkT(new_tok, 0, arc.olabel, graph_cost, 0, tok->links);

          // "changed" tells us whether the new token has a different
          // cost from before, or is new [if so, add into queue].
          if (changed && fst_->NumInputEpsilons(arc.nextstate) != 0)
            queue_.push_back(arc.nextstate);
        }
      }
    } // for all arcs
  }   // while queue not empty
}

PruneActiveTokens()

void PruneActiveTokens ( BaseFloat  delta )

protected

Definition at line 451 of file lattice-incremental-decoder.cc.

                                                                                {
  int32 cur_frame_plus_one = NumFramesDecoded();
  int32 num_toks_begin = num_toks_;

  if (active_toks_[cur_frame_plus_one].num_toks == -1){
    // The current frame's tokens don't get pruned so they don't get counted
    // (the count is needed by the incremental determinization code).
    // Fix this.
    int this_frame_num_toks = 0;
    for (Token *t = active_toks_[cur_frame_plus_one].toks; t != NULL; t = t->next)
      this_frame_num_toks++;
    active_toks_[cur_frame_plus_one].num_toks = this_frame_num_toks;
 }

  // The index "f" below represents a "frame plus one", i.e. you'd have to subtract
  // one to get the corresponding index for the decodable object.
  for (int32 f = cur_frame_plus_one - 1; f >= 0; f--) {
    // Reason why we need to prune forward links in this situation:
    // (1) we have never pruned them (new TokenList)
    // (2) we have not yet pruned the forward links to the next f,
    // after any of those tokens have changed their extra_cost.
    if (active_toks_[f].must_prune_forward_links) {
      bool extra_costs_changed = false, links_pruned = false;
      PruneForwardLinks(f, &extra_costs_changed, &links_pruned, delta);
      if (extra_costs_changed && f > 0) // any token has changed extra_cost
        active_toks_[f - 1].must_prune_forward_links = true;
      if (links_pruned) // any link was pruned
        active_toks_[f].must_prune_tokens = true;
      active_toks_[f].must_prune_forward_links = false; // job done
    }
    if (f + 1 < cur_frame_plus_one && // except for last f (no forward links)
        active_toks_[f + 1].must_prune_tokens) {
      PruneTokensForFrame(f + 1);
      active_toks_[f + 1].must_prune_tokens = false;
    }
  }
  KALDI_VLOG(4) << "pruned tokens from " << num_toks_begin
                << " to " << num_toks_;
}

PruneForwardLinks()

void PruneForwardLinks ( int32  frame_plus_one, bool *  extra_costs_changed, bool *  links_pruned, BaseFloat  delta  )

protected

Definition at line 243 of file lattice-incremental-decoder.cc.

                     {
  // delta is the amount by which the extra_costs must change
  // If delta is larger,  we'll tend to go back less far
  //    toward the beginning of the file.
  // extra_costs_changed is set to true if extra_cost was changed for any token
  // links_pruned is set to true if any link in any token was pruned

  *extra_costs_changed = false;
  *links_pruned = false;
  KALDI_ASSERT(frame_plus_one >= 0 && frame_plus_one < active_toks_.size());
  if (active_toks_[frame_plus_one].toks == NULL) { // empty list; should not happen.
    if (!warned_) {
      KALDI_WARN << "No tokens alive [doing pruning].. warning first "
                    "time only for each utterance\n";
      warned_ = true;
    }
  }

  // We have to iterate until there is no more change, because the links
  // are not guaranteed to be in topological order.
  bool changed = true; // difference new minus old extra cost >= delta ?
  while (changed) {
    changed = false;
    for (Token *tok = active_toks_[frame_plus_one].toks; tok != NULL;
         tok = tok->next) {
      ForwardLinkT *link, *prev_link = NULL;
      // will recompute tok_extra_cost for tok.
      BaseFloat tok_extra_cost = std::numeric_limits<BaseFloat>::infinity();
      // tok_extra_cost is the best (min) of link_extra_cost of outgoing links
      for (link = tok->links; link != NULL;) {
        // See if we need to excise this link...
        Token *next_tok = link->next_tok;
        BaseFloat link_extra_cost =
            next_tok->extra_cost +
            ((tok->tot_cost + link->acoustic_cost + link->graph_cost) -
             next_tok->tot_cost); // difference in brackets is >= 0
        // link_exta_cost is the difference in score between the best paths
        // through link source state and through link destination state
        KALDI_ASSERT(link_extra_cost == link_extra_cost); // check for NaN
        if (link_extra_cost > config_.lattice_beam) {     // excise link
          ForwardLinkT *next_link = link->next;
          if (prev_link != NULL)
            prev_link->next = next_link;
          else
            tok->links = next_link;
          delete link;
          link = next_link; // advance link but leave prev_link the same.
          *links_pruned = true;
        } else { // keep the link and update the tok_extra_cost if needed.
          if (link_extra_cost < 0.0) { // this is just a precaution.
            if (link_extra_cost < -0.01)
              KALDI_WARN << "Negative extra_cost: " << link_extra_cost;
            link_extra_cost = 0.0;
          }
          if (link_extra_cost < tok_extra_cost) tok_extra_cost = link_extra_cost;
          prev_link = link; // move to next link
          link = link->next;
        }
      } // for all outgoing links
      if (fabs(tok_extra_cost - tok->extra_cost) > delta)
        changed = true; // difference new minus old is bigger than delta
      tok->extra_cost = tok_extra_cost;
      // will be +infinity or <= lattice_beam_.
      // infinity indicates, that no forward link survived pruning
    } // for all Token on active_toks_[frame]
    if (changed) *extra_costs_changed = true;

    // Note: it's theoretically possible that aggressive compiler
    // optimizations could cause an infinite loop here for small delta and
    // high-dynamic-range scores.
  } // while changed
}

PruneForwardLinksFinal()

void PruneForwardLinksFinal ( )

protected

Definition at line 322 of file lattice-incremental-decoder.cc.

                                                                      {
  KALDI_ASSERT(!active_toks_.empty());
  int32 frame_plus_one = active_toks_.size() - 1;

  if (active_toks_[frame_plus_one].toks == NULL) // empty list; should not happen.
    KALDI_WARN << "No tokens alive at end of file";

  typedef typename unordered_map<Token *, BaseFloat>::const_iterator IterType;
  ComputeFinalCosts(&final_costs_, &final_relative_cost_, &final_best_cost_);
  decoding_finalized_ = true;
  // We call DeleteElems() as a nicety, not because it's really necessary;
  // otherwise there would be a time, after calling PruneTokensForFrame() on the
  // final frame, when toks_.GetList() or toks_.Clear() would contain pointers
  // to nonexistent tokens.
  DeleteElems(toks_.Clear());

  // Now go through tokens on this frame, pruning forward links...  may have to
  // iterate a few times until there is no more change, because the list is not
  // in topological order.  This is a modified version of the code in
  // PruneForwardLinks, but here we also take account of the final-probs.
  bool changed = true;
  BaseFloat delta = 1.0e-05;
  while (changed) {
    changed = false;
    for (Token *tok = active_toks_[frame_plus_one].toks; tok != NULL;
         tok = tok->next) {
      ForwardLinkT *link, *prev_link = NULL;
      // will recompute tok_extra_cost.  It has a term in it that corresponds
      // to the "final-prob", so instead of initializing tok_extra_cost to infinity
      // below we set it to the difference between the (score+final_prob) of this
      // token,
      // and the best such (score+final_prob).
      BaseFloat final_cost;
      if (final_costs_.empty()) {
        final_cost = 0.0;
      } else {
        IterType iter = final_costs_.find(tok);
        if (iter != final_costs_.end())
          final_cost = iter->second;
        else
          final_cost = std::numeric_limits<BaseFloat>::infinity();
      }
      BaseFloat tok_extra_cost = tok->tot_cost + final_cost - final_best_cost_;
      // tok_extra_cost will be a "min" over either directly being final, or
      // being indirectly final through other links, and the loop below may
      // decrease its value:
      for (link = tok->links; link != NULL;) {
        // See if we need to excise this link...
        Token *next_tok = link->next_tok;
        BaseFloat link_extra_cost =
            next_tok->extra_cost +
            ((tok->tot_cost + link->acoustic_cost + link->graph_cost) -
             next_tok->tot_cost);
        if (link_extra_cost > config_.lattice_beam) { // excise link
          ForwardLinkT *next_link = link->next;
          if (prev_link != NULL)
            prev_link->next = next_link;
          else
            tok->links = next_link;
          delete link;
          link = next_link; // advance link but leave prev_link the same.
        } else {            // keep the link and update the tok_extra_cost if needed.
          if (link_extra_cost < 0.0) { // this is just a precaution.
            if (link_extra_cost < -0.01)
              KALDI_WARN << "Negative extra_cost: " << link_extra_cost;
            link_extra_cost = 0.0;
          }
          if (link_extra_cost < tok_extra_cost) tok_extra_cost = link_extra_cost;
          prev_link = link;
          link = link->next;
        }
      }
      // prune away tokens worse than lattice_beam above best path.  This step
      // was not necessary in the non-final case because then, this case
      // showed up as having no forward links.  Here, the tok_extra_cost has
      // an extra component relating to the final-prob.
      if (tok_extra_cost > config_.lattice_beam)
        tok_extra_cost = std::numeric_limits<BaseFloat>::infinity();
      // to be pruned in PruneTokensForFrame

      if (!ApproxEqual(tok->extra_cost, tok_extra_cost, delta)) changed = true;
      tok->extra_cost = tok_extra_cost; // will be +infinity or <= lattice_beam_.
    }
  } // while changed
}

PruneTokensForFrame()

void PruneTokensForFrame ( int32  frame_plus_one )

protected

Definition at line 420 of file lattice-incremental-decoder.cc.

                          {
  KALDI_ASSERT(frame_plus_one >= 0 && frame_plus_one < active_toks_.size());
  Token *&toks = active_toks_[frame_plus_one].toks;
  if (toks == NULL) KALDI_WARN << "No tokens alive [doing pruning]";
  Token *tok, *next_tok, *prev_tok = NULL;
  int32 num_toks = 0;
  for (tok = toks; tok != NULL; tok = next_tok, num_toks++) {
    next_tok = tok->next;
    if (tok->extra_cost == std::numeric_limits<BaseFloat>::infinity()) {
      // token is unreachable from end of graph; (no forward links survived)
      // excise tok from list and delete tok.
      if (prev_tok != NULL)
        prev_tok->next = tok->next;
      else
        toks = tok->next;
      delete tok;
      num_toks_--;
    } else { // fetch next Token
      prev_tok = tok;
    }
  }
  active_toks_[frame_plus_one].num_toks = num_toks;
}

ReachedFinal()

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 514 of file lattice-incremental-decoder.h.

Referenced by kaldi::DecodeUtteranceLatticeIncremental().

                            {
    return FinalRelativeCost() != std::numeric_limits<BaseFloat>::infinity();
  }

SetOptions()

void SetOptions ( const LatticeIncrementalDecoderConfig &  config )

inline

Definition at line 484 of file lattice-incremental-decoder.h.

{ config_ = config; }

UpdateLatticeDeterminization()

void UpdateLatticeDeterminization ( )

protected

UpdateLatticeDeterminization() ensures the work of determinization is kept up to date so that when you do need the lattice you can get it fast.

It uses the configuration values `determinize_delay`, `determinize_max_delay` and `determinize_min_chunk_size` to decide whether and when to call GetLattice(). You can safely call this as often as you want (e.g. after each time you call AdvanceDecoding(); it won't do subtantially more work if it is called frequently.

Definition at line 86 of file lattice-incremental-decoder.cc.

                                                                            {
  if (NumFramesDecoded() - num_frames_in_lattice_ <
      config_.determinize_max_delay)
    return;


  /* Make sure the token-pruning is active.  Note: PruneActiveTokens() has
     internal logic that prevents it from doing unnecessary work if you
     call it and then immediately call it again. */
  PruneActiveTokens(config_.lattice_beam * config_.prune_scale);

  int32 first = num_frames_in_lattice_ + config_.determinize_min_chunk_size,
      last = NumFramesDecoded(),
      fewest_tokens = std::numeric_limits<int32>::max(),
      best_frame = -1;
  for (int32 t = last; t >= first; t--) {
    /* Make sure PruneActiveTokens() has computed num_toks for all these
       frames... */
    KALDI_ASSERT(active_toks_[t].num_toks != -1);
    if (active_toks_[t].num_toks < fewest_tokens) {
      //  <= because we want the latest one in case of ties.
      fewest_tokens = active_toks_[t].num_toks;
      best_frame = t;
    }
  }
  /* OK, determinize the chunk that spans from num_frames_in_lattice_ to
     best_frame. */
  bool use_final_probs = false;
  GetLattice(best_frame, use_final_probs);
  return;
}

Member Data Documentation

active_toks_

std::vector<TokenList> active_toks_

protected

Definition at line 643 of file lattice-incremental-decoder.h.

config_

LatticeIncrementalDecoderConfig config_

protected

Definition at line 661 of file lattice-incremental-decoder.h.

cost_offsets_

std::vector<BaseFloat> cost_offsets_

protected

Definition at line 648 of file lattice-incremental-decoder.h.

decoding_finalized_

bool decoding_finalized_

protected

Definition at line 651 of file lattice-incremental-decoder.h.

delete_fst_

bool delete_fst_

protected

Definition at line 647 of file lattice-incremental-decoder.h.

determinizer_

LatticeIncrementalDeterminizer determinizer_

protected

Much of the the incremental determinization algorithm is encapsulated in the determinize_ object.

Definition at line 664 of file lattice-incremental-decoder.h.

final_best_cost_

BaseFloat final_best_cost_

protected

Definition at line 655 of file lattice-incremental-decoder.h.

final_costs_

unordered_map<Token *, BaseFloat> final_costs_

protected

Definition at line 653 of file lattice-incremental-decoder.h.

final_relative_cost_

BaseFloat final_relative_cost_

protected

Definition at line 654 of file lattice-incremental-decoder.h.

fst_

const FST* fst_

protected

Definition at line 646 of file lattice-incremental-decoder.h.

next_token_label_

Label next_token_label_

protected

Definition at line 682 of file lattice-incremental-decoder.h.

num_frames_in_lattice_

int32 num_frames_in_lattice_

protected

num_frames_in_lattice_ is the highest `num_frames_to_include_` argument for any prior call to GetLattice().

Definition at line 672 of file lattice-incremental-decoder.h.

num_toks_

int32 num_toks_

protected

Definition at line 649 of file lattice-incremental-decoder.h.

queue_

std::vector<StateId> queue_

protected

Definition at line 644 of file lattice-incremental-decoder.h.

temp_token_map_

unordered_map<Token*, StateId> temp_token_map_

protected

Definition at line 668 of file lattice-incremental-decoder.h.

tmp_array_

std::vector<BaseFloat> tmp_array_

protected

Definition at line 645 of file lattice-incremental-decoder.h.

token2label_map_

unordered_map<Token*, Label> token2label_map_

protected

Definition at line 676 of file lattice-incremental-decoder.h.

token2label_map_temp_

unordered_map<Token*, Label> token2label_map_temp_

protected

Definition at line 679 of file lattice-incremental-decoder.h.

toks_

HashList<StateId, Token *> toks_

protected

Definition at line 642 of file lattice-incremental-decoder.h.

warned_

bool warned_

protected

Definition at line 650 of file lattice-incremental-decoder.h.

---

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

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