FasterDecoder Class Reference

#include <faster-decoder.h>

Inheritance diagram for FasterDecoder:

Collaboration diagram for FasterDecoder:

Classes
class	Token

Public Types
typedef fst::StdArc	Arc
typedef Arc::Label	Label
typedef Arc::StateId	StateId
typedef Arc::Weight	Weight

Public Member Functions
	FasterDecoder (const fst::Fst< fst::StdArc > &fst, const FasterDecoderOptions &config)
void	SetOptions (const FasterDecoderOptions &config)
	~FasterDecoder ()
void	Decode (DecodableInterface *decodable)
bool	ReachedFinal () const
	Returns true if a final state was active on the last frame. More...
bool	GetBestPath (fst::MutableFst< LatticeArc > *fst_out, bool use_final_probs=true)
	GetBestPath gets the decoding traceback. More...
void	InitDecoding ()
	As a new alternative to Decode(), you can call InitDecoding and then (possibly multiple times) 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, but if max_num_frames is >= 0 it will decode no more than that many frames. More...
int32	NumFramesDecoded () const
	Returns the number of frames already decoded. More...

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

Protected Member Functions
double	GetCutoff (Elem *list_head, size_t *tok_count, BaseFloat *adaptive_beam, Elem **best_elem)
	Gets the weight cutoff. Also counts the active tokens. More...
void	PossiblyResizeHash (size_t num_toks)
double	ProcessEmitting (DecodableInterface *decodable)
void	ProcessNonemitting (double cutoff)
void	ClearToks (Elem *list)
	KALDI_DISALLOW_COPY_AND_ASSIGN (FasterDecoder)

Protected Attributes
HashList< StateId, Token * >	toks_
const fst::Fst< fst::StdArc > &	fst_
FasterDecoderOptions	config_
std::vector< const Elem *>	queue_
std::vector< BaseFloat >	tmp_array_
int32	num_frames_decoded_

Detailed Description

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

Member Typedef Documentation

Arc

typedef fst::StdArc Arc

Definition at line 64 of file faster-decoder.h.

Elem

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

protected

Definition at line 150 of file faster-decoder.h.

Label

typedef Arc::Label Label

Definition at line 65 of file faster-decoder.h.

StateId

typedef Arc::StateId StateId

Definition at line 66 of file faster-decoder.h.

Weight

typedef Arc::Weight Weight

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

Constructor & Destructor Documentation

FasterDecoder()

FasterDecoder	(	const fst::Fst< fst::StdArc > &	fst,
		const FasterDecoderOptions &	config
	)

Definition at line 26 of file faster-decoder.cc.

References FasterDecoder::config_, FasterDecoderOptions::hash_ratio, KALDI_ASSERT, FasterDecoderOptions::max_active, FasterDecoderOptions::min_active, HashList< I, T >::SetSize(), and FasterDecoder::toks_.

                                                              :
    fst_(fst), config_(opts), num_frames_decoded_(-1) {
  KALDI_ASSERT(config_.hash_ratio >= 1.0);  // less doesn't make much sense.
  KALDI_ASSERT(config_.max_active > 1);
  KALDI_ASSERT(config_.min_active >= 0 && config_.min_active < config_.max_active);
  toks_.SetSize(1000);  // just so on the first frame we do something reasonable.
}

~FasterDecoder()

~FasterDecoder ( )

inline

Definition at line 74 of file faster-decoder.h.

{ ClearToks(toks_.Clear()); }

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, but if max_num_frames is >= 0 it will decode no more than that many frames.

Definition at line 53 of file faster-decoder.cc.

References KALDI_ASSERT, FasterDecoder::num_frames_decoded_, DecodableInterface::NumFramesReady(), FasterDecoder::ProcessEmitting(), and FasterDecoder::ProcessNonemitting().

Referenced by FasterDecoder::Decode().

                                                            {
  KALDI_ASSERT(num_frames_decoded_ >= 0 &&
               "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 >= num_frames_decoded_);
  int32 target_frames_decoded = num_frames_ready;
  if (max_num_frames >= 0)
    target_frames_decoded = std::min(target_frames_decoded,
                                     num_frames_decoded_ + max_num_frames);
  while (num_frames_decoded_ < target_frames_decoded) {
    // note: ProcessEmitting() increments num_frames_decoded_
    double weight_cutoff = ProcessEmitting(decodable);
    ProcessNonemitting(weight_cutoff);
  }
}

ClearToks()

void ClearToks ( Elem *  list )

protected

Definition at line 343 of file faster-decoder.cc.

References HashList< I, T >::Delete(), FasterDecoder::Token::TokenDelete(), and FasterDecoder::toks_.

Referenced by FasterDecoder::InitDecoding(), and OnlineFasterDecoder::ResetDecoder().

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

Decode()

void Decode

(

DecodableInterface *

decodable

)

Definition at line 48 of file faster-decoder.cc.

References FasterDecoder::AdvanceDecoding(), and FasterDecoder::InitDecoding().

Referenced by kaldi::AlignUtteranceWrapper(), DecodeUtterance(), and main().

                                                        {
  InitDecoding();
  AdvanceDecoding(decodable);
}

GetBestPath()

bool GetBestPath	(	fst::MutableFst< LatticeArc > *	fst_out,
		bool	use_final_probs = true
	)

GetBestPath gets the decoding traceback.

If "use_final_probs" is true AND we reached a final state, it limits itself to final states; otherwise it gets the most likely token not taking into account final-probs. Returns true if the output best path was not the empty FST (will only return false in unusual circumstances where no tokens survived).

Definition at line 84 of file faster-decoder.cc.

References FasterDecoder::Token::arc_, FasterDecoder::Token::cost_, FasterDecoder::fst_, HashList< I, T >::GetList(), rnnlm::i, KALDI_ASSERT, LatticeWeightTpl< BaseFloat >::One(), FasterDecoder::Token::prev_, FasterDecoder::ReachedFinal(), fst::RemoveEpsLocal(), HashList< I, T >::Elem::tail, and FasterDecoder::toks_.

Referenced by kaldi::AlignUtteranceWrapper(), DecodeUtterance(), and main().

                                                      {
  // GetBestPath gets the decoding output.  If "use_final_probs" is true
  // AND we reached a final state, it limits itself to final states;
  // otherwise it gets the most likely token not taking into
  // account final-probs.  fst_out will be empty (Start() == kNoStateId) if
  // nothing was available.  It returns true if it got output (thus, fst_out
  // will be nonempty).
  fst_out->DeleteStates();
  Token *best_tok = NULL;
  bool is_final = ReachedFinal();
  if (!is_final) {
    for (const Elem *e = toks_.GetList(); e != NULL; e = e->tail)
      if (best_tok == NULL || *best_tok < *(e->val) )
        best_tok = e->val;
  } else {
    double infinity =  std::numeric_limits<double>::infinity(),
        best_cost = infinity;
    for (const Elem *e = toks_.GetList(); e != NULL; e = e->tail) {
      double this_cost = e->val->cost_ + fst_.Final(e->key).Value();
      if (this_cost < best_cost && this_cost != infinity) {
        best_cost = this_cost;
        best_tok = e->val;
      }
    }
  }
  if (best_tok == NULL) return false;  // No output.

  std::vector<LatticeArc> arcs_reverse;  // arcs in reverse order.

  for (Token *tok = best_tok; tok != NULL; tok = tok->prev_) {
    BaseFloat tot_cost = tok->cost_ -
        (tok->prev_ ? tok->prev_->cost_ : 0.0),
        graph_cost = tok->arc_.weight.Value(),
        ac_cost = tot_cost - graph_cost;
    LatticeArc l_arc(tok->arc_.ilabel,
                     tok->arc_.olabel,
                     LatticeWeight(graph_cost, ac_cost),
                     tok->arc_.nextstate);
    arcs_reverse.push_back(l_arc);
  }
  KALDI_ASSERT(arcs_reverse.back().nextstate == fst_.Start());
  arcs_reverse.pop_back();  // that was a "fake" token... gives no info.

  StateId cur_state = fst_out->AddState();
  fst_out->SetStart(cur_state);
  for (ssize_t i = static_cast<ssize_t>(arcs_reverse.size())-1; i >= 0; i--) {
    LatticeArc arc = arcs_reverse[i];
    arc.nextstate = fst_out->AddState();
    fst_out->AddArc(cur_state, arc);
    cur_state = arc.nextstate;
  }
  if (is_final && use_final_probs) {
    Weight final_weight = fst_.Final(best_tok->arc_.nextstate);
    fst_out->SetFinal(cur_state, LatticeWeight(final_weight.Value(), 0.0));
  } else {
    fst_out->SetFinal(cur_state, LatticeWeight::One());
  }
  RemoveEpsLocal(fst_out);
  return true;
}

GetCutoff()

double 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 148 of file faster-decoder.cc.

References FasterDecoderOptions::beam, FasterDecoderOptions::beam_delta, FasterDecoder::config_, count, FasterDecoderOptions::max_active, FasterDecoderOptions::min_active, HashList< I, T >::Elem::tail, and FasterDecoder::tmp_array_.

Referenced by FasterDecoder::ProcessEmitting().

                                                                            {
  double best_cost = std::numeric_limits<double>::infinity();
  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++) {
      double w = e->val->cost_;
      if (w < best_cost) {
        best_cost = w;
        if (best_elem) *best_elem = e;
      }
    }
    if (tok_count != NULL) *tok_count = count;
    if (adaptive_beam != NULL) *adaptive_beam = config_.beam;
    return best_cost + config_.beam;
  } else {
    tmp_array_.clear();
    for (Elem *e = list_head; e != NULL; e = e->tail, count++) {
      double w = e->val->cost_;
      tmp_array_.push_back(w);
      if (w < best_cost) {
        best_cost = w;
        if (best_elem) *best_elem = e;
      }
    }
    if (tok_count != NULL) *tok_count = count;
    double beam_cutoff = best_cost + config_.beam,
        min_active_cutoff = std::numeric_limits<double>::infinity(),
        max_active_cutoff = std::numeric_limits<double>::infinity();

    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_cost + 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_cost;
      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_cost + config_.beam_delta;
      return min_active_cutoff;
    } else {
      *adaptive_beam = config_.beam;
      return beam_cutoff;
    }
  }
}

InitDecoding()

void InitDecoding

(

)

As a new alternative to Decode(), you can call InitDecoding and then (possibly multiple times) AdvanceDecoding().

Definition at line 36 of file faster-decoder.cc.

References HashList< I, T >::Clear(), FasterDecoder::ClearToks(), FasterDecoder::fst_, HashList< I, T >::Insert(), KALDI_ASSERT, FasterDecoder::num_frames_decoded_, FasterDecoder::ProcessNonemitting(), and FasterDecoder::toks_.

Referenced by FasterDecoder::Decode(), and main().

                                 {
  // clean up from last time:
  ClearToks(toks_.Clear());
  StateId start_state = fst_.Start();
  KALDI_ASSERT(start_state != fst::kNoStateId);
  Arc dummy_arc(0, 0, Weight::One(), start_state);
  toks_.Insert(start_state, new Token(dummy_arc, NULL));
  ProcessNonemitting(std::numeric_limits<float>::max());
  num_frames_decoded_ = 0;
}

KALDI_DISALLOW_COPY_AND_ASSIGN()

KALDI_DISALLOW_COPY_AND_ASSIGN ( FasterDecoder  )

protected

NumFramesDecoded()

int32 NumFramesDecoded ( ) const

inline

Returns the number of frames already decoded.

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

{ return num_frames_decoded_; }

PossiblyResizeHash()

void PossiblyResizeHash ( size_t  num_toks )

protected

Definition at line 212 of file faster-decoder.cc.

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

Referenced by FasterDecoder::ProcessEmitting().

                                                      {
  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()

double ProcessEmitting ( DecodableInterface *  decodable )

protected

Definition at line 221 of file faster-decoder.cc.

References FasterDecoder::Token::arc_, HashList< I, T >::Clear(), FasterDecoder::Token::cost_, HashList< I, T >::Delete(), FasterDecoder::fst_, FasterDecoder::GetCutoff(), HashList< I, T >::Insert(), KALDI_ASSERT, KALDI_VLOG, HashList< I, T >::Elem::key, DecodableInterface::LogLikelihood(), FasterDecoder::num_frames_decoded_, FasterDecoder::PossiblyResizeHash(), FasterDecoder::Token::TokenDelete(), FasterDecoder::toks_, and HashList< I, T >::Elem::val.

Referenced by FasterDecoder::AdvanceDecoding(), and OnlineFasterDecoder::Decode().

                                                                   {
  int32 frame = num_frames_decoded_;
  Elem *last_toks = toks_.Clear();
  size_t tok_cnt;
  BaseFloat adaptive_beam;
  Elem *best_elem = NULL;
  double weight_cutoff = GetCutoff(last_toks, &tok_cnt,
                                   &adaptive_beam, &best_elem);
  KALDI_VLOG(3) << tok_cnt << " tokens active.";
  PossiblyResizeHash(tok_cnt);  // This makes sure the hash is always big enough.

  // This is the cutoff we use after adding in the log-likes (i.e.
  // for the next frame).  This is a bound on the cutoff we will use
  // on the next frame.
  double next_weight_cutoff = std::numeric_limits<double>::infinity();

  // First process the best token to get a hopefully
  // reasonably tight bound on the next cutoff.
  if (best_elem) {
    StateId state = best_elem->key;
    Token *tok = best_elem->val;
    for (fst::ArcIterator<fst::Fst<Arc> > aiter(fst_, state);
         !aiter.Done();
         aiter.Next()) {
      const Arc &arc = aiter.Value();
      if (arc.ilabel != 0) {  // we'd propagate..
        BaseFloat ac_cost = - decodable->LogLikelihood(frame, arc.ilabel);
        double new_weight = arc.weight.Value() + tok->cost_ + ac_cost;
        if (new_weight + adaptive_beam < next_weight_cutoff)
          next_weight_cutoff = new_weight + adaptive_beam;
      }
    }
  }

  // int32 n = 0, np = 0;

  // the tokens are now owned here, in last_toks, and the hash is empty.
  // 'owned' is a complex thing here; the point is we need to call TokenDelete
  // on each elem 'e' to let toks_ know we're done with them.
  for (Elem *e = last_toks, *e_tail; e != NULL; e = e_tail) {  // loop this way
    // n++;
    // because we delete "e" as we go.
    StateId state = e->key;
    Token *tok = e->val;
    if (tok->cost_ < weight_cutoff) {  // not pruned.
      // np++;
      KALDI_ASSERT(state == tok->arc_.nextstate);
      for (fst::ArcIterator<fst::Fst<Arc> > aiter(fst_, state);
           !aiter.Done();
           aiter.Next()) {
        Arc arc = aiter.Value();
        if (arc.ilabel != 0) {  // propagate..
          BaseFloat ac_cost =  - decodable->LogLikelihood(frame, arc.ilabel);
          double new_weight = arc.weight.Value() + tok->cost_ + ac_cost;
          if (new_weight < next_weight_cutoff) {  // not pruned..
            Token *new_tok = new Token(arc, ac_cost, tok);
            Elem *e_found = toks_.Insert(arc.nextstate, new_tok);
            if (new_weight + adaptive_beam < next_weight_cutoff)
              next_weight_cutoff = new_weight + adaptive_beam;
            if (e_found->val != new_tok) {
              if (*(e_found->val) < *new_tok) {
                Token::TokenDelete(e_found->val);
                e_found->val = new_tok;
              } else {
                Token::TokenDelete(new_tok);
              }
            }
          }
        }
      }
    }
    e_tail = e->tail;
    Token::TokenDelete(e->val);
    toks_.Delete(e);
  }
  num_frames_decoded_++;
  return next_weight_cutoff;
}

ProcessNonemitting()

void ProcessNonemitting ( double  cutoff )

protected

Definition at line 301 of file faster-decoder.cc.

References FasterDecoder::Token::arc_, FasterDecoder::Token::cost_, FasterDecoder::fst_, HashList< I, T >::GetList(), HashList< I, T >::Insert(), KALDI_ASSERT, HashList< I, T >::Elem::key, FasterDecoder::queue_, HashList< I, T >::Elem::tail, FasterDecoder::Token::TokenDelete(), FasterDecoder::toks_, and HashList< I, T >::Elem::val.

Referenced by FasterDecoder::AdvanceDecoding(), OnlineFasterDecoder::Decode(), and FasterDecoder::InitDecoding().

                                                    {
  // Processes nonemitting arcs for one frame.
  KALDI_ASSERT(queue_.empty());
  for (const Elem *e = toks_.GetList(); e != NULL;  e = e->tail)
    queue_.push_back(e);
  while (!queue_.empty()) {
    const Elem* e = queue_.back();
    queue_.pop_back();
    StateId state = e->key;
    Token *tok = e->val;  // would segfault if state not
    // in toks_ but this can't happen.
    if (tok->cost_ > cutoff) { // Don't bother processing successors.
      continue;
    }
    KALDI_ASSERT(tok != NULL && state == tok->arc_.nextstate);
    for (fst::ArcIterator<fst::Fst<Arc> > aiter(fst_, state);
         !aiter.Done();
         aiter.Next()) {
      const Arc &arc = aiter.Value();
      if (arc.ilabel == 0) {  // propagate nonemitting only...
        Token *new_tok = new Token(arc, tok);
        if (new_tok->cost_ > cutoff) {  // prune
          Token::TokenDelete(new_tok);
        } else {
          Elem *e_found = toks_.Insert(arc.nextstate, new_tok);
          if (e_found->val == new_tok) {
            queue_.push_back(e_found);
          } else {
            if (*(e_found->val) < *new_tok) {
              Token::TokenDelete(e_found->val);
              e_found->val = new_tok;
              queue_.push_back(e_found);
            } else {
              Token::TokenDelete(new_tok);
            }
          }
        }
      }
    }
  }
}

ReachedFinal()

bool ReachedFinal

(

)

const

Returns true if a final state was active on the last frame.

Definition at line 75 of file faster-decoder.cc.

References FasterDecoder::fst_, HashList< I, T >::GetList(), HashList< I, T >::Elem::tail, and FasterDecoder::toks_.

Referenced by kaldi::AlignUtteranceWrapper(), DecodeUtterance(), OnlineFasterDecoder::FinishTraceBack(), FasterDecoder::GetBestPath(), and main().

                                       {
  for (const Elem *e = toks_.GetList(); e != NULL; e = e->tail) {
    if (e->val->cost_ != std::numeric_limits<double>::infinity() &&
        fst_.Final(e->key) != Weight::Zero())
      return true;
  }
  return false;
}

SetOptions()

void SetOptions ( const FasterDecoderOptions &  config )

inline

Definition at line 72 of file faster-decoder.h.

Referenced by kaldi::AlignUtteranceWrapper().

{ config_ = config; }

Member Data Documentation

config_

FasterDecoderOptions config_

protected

Definition at line 172 of file faster-decoder.h.

Referenced by FasterDecoder::FasterDecoder(), FasterDecoder::GetCutoff(), and FasterDecoder::PossiblyResizeHash().

fst_

const fst::Fst<fst::StdArc>& fst_

protected

Definition at line 171 of file faster-decoder.h.

Referenced by OnlineFasterDecoder::FinishTraceBack(), GrammarFstPreparer::FixArcsToFinalStates(), FasterDecoder::GetBestPath(), FasterDecoder::InitDecoding(), GrammarFstPreparer::InsertEpsilonsForState(), GrammarFstPreparer::IsEntryState(), GrammarFstPreparer::IsSpecialState(), OnlineFasterDecoder::MakeLattice(), GrammarFstPreparer::MaybeAddFinalProbToState(), GrammarFstPreparer::NeedEpsilons(), GrammarFstPreparer::Prepare(), FasterDecoder::ProcessEmitting(), FasterDecoder::ProcessNonemitting(), FasterDecoder::ReachedFinal(), OnlineFasterDecoder::ResetDecoder(), and OnlineFasterDecoder::TracebackNFrames().

num_frames_decoded_

int32 num_frames_decoded_

protected

Definition at line 178 of file faster-decoder.h.

Referenced by FasterDecoder::AdvanceDecoding(), FasterDecoder::InitDecoding(), and FasterDecoder::ProcessEmitting().

queue_

std::vector<const Elem* > queue_

protected

Definition at line 173 of file faster-decoder.h.

Referenced by FasterDecoder::ProcessNonemitting().

tmp_array_

std::vector<BaseFloat> tmp_array_

protected

Definition at line 174 of file faster-decoder.h.

Referenced by FasterDecoder::GetCutoff().

toks_

HashList<StateId, Token*> toks_

protected

Definition at line 170 of file faster-decoder.h.

Referenced by FasterDecoder::ClearToks(), FasterDecoder::FasterDecoder(), OnlineFasterDecoder::FinishTraceBack(), FasterDecoder::GetBestPath(), FasterDecoder::InitDecoding(), FasterDecoder::PossiblyResizeHash(), FasterDecoder::ProcessEmitting(), FasterDecoder::ProcessNonemitting(), FasterDecoder::ReachedFinal(), OnlineFasterDecoder::ResetDecoder(), OnlineFasterDecoder::TracebackNFrames(), and OnlineFasterDecoder::UpdateImmortalToken().

---

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

• decoder/faster-decoder.h
• decoder/faster-decoder.cc