SimpleDecoder Class Reference

Simplest possible decoder, included largely for didactic purposes and as a means to debug more highly optimized decoders. More...

#include <simple-decoder.h>

Collaboration diagram for SimpleDecoder:

Classes
class	Token

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

Public Member Functions
	SimpleDecoder (const fst::Fst< fst::StdArc > &fst, BaseFloat beam)
	~SimpleDecoder ()
bool	Decode (DecodableInterface *decodable)
	Decode this utterance. More...
bool	ReachedFinal () const
bool	GetBestPath (Lattice *fst_out, bool use_final_probs=true) const
BaseFloat	FinalRelativeCost () const
	*** The next functions are from the "new interface". *** 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, 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...

Private Member Functions
void	ProcessEmitting (DecodableInterface *decodable)
void	ProcessNonemitting ()
	KALDI_DISALLOW_COPY_AND_ASSIGN (SimpleDecoder)

Static Private Member Functions
static void	ClearToks (unordered_map< StateId, Token *> &toks)
static void	PruneToks (BaseFloat beam, unordered_map< StateId, Token *> *toks)

Private Attributes
unordered_map< StateId, Token * >	cur_toks_
unordered_map< StateId, Token * >	prev_toks_
const fst::Fst< fst::StdArc > &	fst_
BaseFloat	beam_
int32	num_frames_decoded_

Detailed Description

Simplest possible decoder, included largely for didactic purposes and as a means to debug more highly optimized decoders.

See SimpleDecoder: the simplest possible decoder for more information.

Definition at line 37 of file simple-decoder.h.

Member Typedef Documentation

Label

typedef StdArc::Label Label

Definition at line 41 of file simple-decoder.h.

StateId

typedef StdArc::StateId StateId

Definition at line 42 of file simple-decoder.h.

StdArc

typedef fst::StdArc StdArc

Definition at line 39 of file simple-decoder.h.

StdWeight

typedef StdArc::Weight StdWeight

Definition at line 40 of file simple-decoder.h.

Constructor & Destructor Documentation

SimpleDecoder()

SimpleDecoder ( const fst::Fst< fst::StdArc > &  fst, BaseFloat  beam  )

inline

Definition at line 44 of file simple-decoder.h.

References SimpleDecoder::AdvanceDecoding(), SimpleDecoder::Decode(), SimpleDecoder::FinalRelativeCost(), SimpleDecoder::GetBestPath(), SimpleDecoder::InitDecoding(), SimpleDecoder::ReachedFinal(), and SimpleDecoder::~SimpleDecoder().

: fst_(fst), beam_(beam) { }

~SimpleDecoder()

~SimpleDecoder

(

)

Definition at line 27 of file simple-decoder.cc.

References SimpleDecoder::ClearToks(), SimpleDecoder::cur_toks_, and SimpleDecoder::prev_toks_.

Referenced by SimpleDecoder::SimpleDecoder().

                              {
  ClearToks(cur_toks_);
  ClearToks(prev_toks_);
}

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.

If it returns false, then no tokens are alive, which is a kind of error state.

Definition at line 52 of file simple-decoder.cc.

References SimpleDecoder::beam_, SimpleDecoder::ClearToks(), SimpleDecoder::cur_toks_, KALDI_ASSERT, SimpleDecoder::num_frames_decoded_, DecodableInterface::NumFramesReady(), SimpleDecoder::prev_toks_, SimpleDecoder::ProcessEmitting(), SimpleDecoder::ProcessNonemitting(), and SimpleDecoder::PruneToks().

Referenced by SimpleDecoder::Decode(), and SimpleDecoder::SimpleDecoder().

                                                            {
  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_
    ClearToks(prev_toks_);
    cur_toks_.swap(prev_toks_);
    ProcessEmitting(decodable);
    ProcessNonemitting();
    PruneToks(beam_, &cur_toks_);
  }
}

ClearToks()

void ClearToks ( unordered_map< StateId, Token *> &  toks )

staticprivate

Definition at line 258 of file simple-decoder.cc.

References SimpleDecoder::Token::TokenDelete().

Referenced by SimpleDecoder::AdvanceDecoding(), SimpleDecoder::InitDecoding(), and SimpleDecoder::~SimpleDecoder().

                                                                  {
  for (unordered_map<StateId, Token*>::iterator iter = toks.begin();
       iter != toks.end(); ++iter) {
    Token::TokenDelete(iter->second);
  }
  toks.clear();
}

Decode()

bool Decode

(

DecodableInterface *

decodable

)

Decode this utterance.

Returns true if any tokens reached the end of the file (regardless of whether they are in a final state); query ReachedFinal() after Decode() to see whether we reached a final state.

Definition at line 33 of file simple-decoder.cc.

References SimpleDecoder::AdvanceDecoding(), SimpleDecoder::cur_toks_, and SimpleDecoder::InitDecoding().

Referenced by main(), and SimpleDecoder::SimpleDecoder().

                                                        {
  InitDecoding();
  AdvanceDecoding(decodable);
  return (!cur_toks_.empty());
}

FinalRelativeCost()

BaseFloat FinalRelativeCost

(

)

const

*** The next functions are from the "new interface". ***

FinalRelativeCost() serves the same function 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.

Definition at line 87 of file simple-decoder.cc.

References SimpleDecoder::cur_toks_, SimpleDecoder::fst_, and KALDI_WARN.

Referenced by SimpleDecoder::SimpleDecoder().

                                                 {
  // as a special case, if there are no active tokens at all (e.g. some kind of
  // pruning failure), return infinity.
  double infinity = std::numeric_limits<double>::infinity();
  if (cur_toks_.empty())
    return infinity;
  double best_cost = infinity,
      best_cost_with_final = infinity;
  for (unordered_map<StateId, Token*>::const_iterator iter = cur_toks_.begin();
       iter != cur_toks_.end();
       ++iter) {
    // Note: Plus is taking the minimum cost, since we're in the tropical
    // semiring.
    best_cost = std::min(best_cost, iter->second->cost_);
    best_cost_with_final = std::min(best_cost_with_final,
                                    iter->second->cost_ +
                                    fst_.Final(iter->first).Value());
  }
  BaseFloat extra_cost = best_cost_with_final - best_cost;
  if (extra_cost != extra_cost) { // NaN.  This shouldn't happen; it indicates some
                                  // kind of error, most likely.
    KALDI_WARN << "Found NaN (likely search failure in decoding)";
    return infinity;
  }
  // Note: extra_cost will be infinity if no states were final.
  return extra_cost;
}

GetBestPath()

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

Definition at line 117 of file simple-decoder.cc.

References SimpleDecoder::Token::arc_, SimpleDecoder::Token::cost_, SimpleDecoder::cur_toks_, SimpleDecoder::fst_, rnnlm::i, KALDI_ASSERT, LatticeWeightTpl< BaseFloat >::One(), SimpleDecoder::Token::prev_, SimpleDecoder::ReachedFinal(), and fst::RemoveEpsLocal().

Referenced by main(), and SimpleDecoder::SimpleDecoder().

                                                                            {
  fst_out->DeleteStates();
  Token *best_tok = NULL;
  bool is_final = ReachedFinal();
  if (!is_final) {
    for (unordered_map<StateId, Token*>::const_iterator iter = cur_toks_.begin();
         iter != cur_toks_.end();
         ++iter)
      if (best_tok == NULL || *best_tok < *(iter->second) )
        best_tok = iter->second;
  } else {
    double infinity =std::numeric_limits<double>::infinity(),
        best_cost = infinity;
    for (unordered_map<StateId, Token*>::const_iterator iter = cur_toks_.begin();
         iter != cur_toks_.end();
         ++iter) {
      double this_cost = iter->second->cost_ + fst_.Final(iter->first).Value();
      if (this_cost != infinity && this_cost < best_cost) {
        best_cost = this_cost;
        best_tok = iter->second;
      }
    }
  }
  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_)
    arcs_reverse.push_back(tok->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)
    fst_out->SetFinal(cur_state,
                      LatticeWeight(fst_.Final(best_tok->arc_.nextstate).Value(),
                                    0.0));
  else
    fst_out->SetFinal(cur_state, LatticeWeight::One());
  fst::RemoveEpsLocal(fst_out);
  return true;
}

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 call InitDecoding if you have already decoded an utterance and want to start with a new utterance.

Definition at line 39 of file simple-decoder.cc.

References SimpleDecoder::ClearToks(), SimpleDecoder::cur_toks_, SimpleDecoder::fst_, KALDI_ASSERT, SimpleDecoder::num_frames_decoded_, SimpleDecoder::prev_toks_, and SimpleDecoder::ProcessNonemitting().

Referenced by SimpleDecoder::Decode(), and SimpleDecoder::SimpleDecoder().

                                 {
  // clean up from last time:
  ClearToks(cur_toks_);
  ClearToks(prev_toks_);
  // initialize decoding:
  StateId start_state = fst_.Start();
  KALDI_ASSERT(start_state != fst::kNoStateId);
  StdArc dummy_arc(0, 0, StdWeight::One(), start_state);
  cur_toks_[start_state] = new Token(dummy_arc, 0.0, NULL);
  num_frames_decoded_ = 0;
  ProcessNonemitting();
}

KALDI_DISALLOW_COPY_AND_ASSIGN()

KALDI_DISALLOW_COPY_AND_ASSIGN ( SimpleDecoder  )

private

NumFramesDecoded()

int32 NumFramesDecoded ( ) const

inline

Returns the number of frames already decoded.

Definition at line 89 of file simple-decoder.h.

References SimpleDecoder::num_frames_decoded_.

{ return num_frames_decoded_; }

ProcessEmitting()

void ProcessEmitting ( DecodableInterface *  decodable )

private

Definition at line 167 of file simple-decoder.cc.

References SimpleDecoder::Token::arc_, SimpleDecoder::beam_, SimpleDecoder::Token::cost_, SimpleDecoder::cur_toks_, SimpleDecoder::fst_, KALDI_ASSERT, DecodableInterface::LogLikelihood(), SimpleDecoder::num_frames_decoded_, SimpleDecoder::prev_toks_, and SimpleDecoder::Token::TokenDelete().

Referenced by SimpleDecoder::AdvanceDecoding(), and SimpleDecoder::Token::TokenDelete().

                                                                 {
  int32 frame = num_frames_decoded_;
  // Processes emitting arcs for one frame.  Propagates from
  // prev_toks_ to cur_toks_.
  double cutoff = std::numeric_limits<BaseFloat>::infinity();
  for (unordered_map<StateId, Token*>::iterator iter = prev_toks_.begin();
       iter != prev_toks_.end();
       ++iter) {
    StateId state = iter->first;
    Token *tok = iter->second;
    KALDI_ASSERT(state == tok->arc_.nextstate);
    for (fst::ArcIterator<fst::Fst<StdArc> > aiter(fst_, state);
         !aiter.Done();
         aiter.Next()) {
      const StdArc &arc = aiter.Value();
      if (arc.ilabel != 0) {  // propagate..
        BaseFloat acoustic_cost = -decodable->LogLikelihood(frame, arc.ilabel);
        double total_cost = tok->cost_ + arc.weight.Value() + acoustic_cost;

        if (total_cost >= cutoff) continue;
        if (total_cost + beam_  < cutoff)
          cutoff = total_cost + beam_;
        Token *new_tok = new Token(arc, acoustic_cost, tok);
        unordered_map<StateId, Token*>::iterator find_iter
            = cur_toks_.find(arc.nextstate);
        if (find_iter == cur_toks_.end()) {
          cur_toks_[arc.nextstate] = new_tok;
        } else {
          if ( *(find_iter->second) < *new_tok ) {
            Token::TokenDelete(find_iter->second);
            find_iter->second = new_tok;
          } else {
            Token::TokenDelete(new_tok);
          }
        }
      }
    }
  }
  num_frames_decoded_++;
}

ProcessNonemitting()

void ProcessNonemitting ( )

private

Definition at line 208 of file simple-decoder.cc.

References SimpleDecoder::Token::arc_, SimpleDecoder::beam_, SimpleDecoder::Token::cost_, SimpleDecoder::cur_toks_, SimpleDecoder::fst_, KALDI_ASSERT, and SimpleDecoder::Token::TokenDelete().

Referenced by SimpleDecoder::AdvanceDecoding(), SimpleDecoder::InitDecoding(), and SimpleDecoder::Token::TokenDelete().

                                       {
  // Processes nonemitting arcs for one frame.  Propagates within
  // cur_toks_.
  std::vector<StateId> queue;
  double infinity = std::numeric_limits<double>::infinity();
  double best_cost = infinity;
  for (unordered_map<StateId, Token*>::iterator iter = cur_toks_.begin();
       iter != cur_toks_.end();
       ++iter) {
    queue.push_back(iter->first);
    best_cost = std::min(best_cost, iter->second->cost_);
  }
  double cutoff = best_cost + beam_;

  while (!queue.empty()) {
    StateId state = queue.back();
    queue.pop_back();
    Token *tok = cur_toks_[state];
    KALDI_ASSERT(tok != NULL && state == tok->arc_.nextstate);
    for (fst::ArcIterator<fst::Fst<StdArc> > aiter(fst_, state);
         !aiter.Done();
         aiter.Next()) {
      const StdArc &arc = aiter.Value();
      if (arc.ilabel == 0) {  // propagate nonemitting only...
        const BaseFloat acoustic_cost = 0.0;
        Token *new_tok = new Token(arc, acoustic_cost, tok);
        if (new_tok->cost_ > cutoff) {
          Token::TokenDelete(new_tok);
        } else {
          unordered_map<StateId, Token*>::iterator find_iter
              = cur_toks_.find(arc.nextstate);
          if (find_iter == cur_toks_.end()) {
            cur_toks_[arc.nextstate] = new_tok;
            queue.push_back(arc.nextstate);
          } else {
            if ( *(find_iter->second) < *new_tok ) {
              Token::TokenDelete(find_iter->second);
              find_iter->second = new_tok;
              queue.push_back(arc.nextstate);
            } else {
              Token::TokenDelete(new_tok);
            }
          }
        }
      }
    }
  }
}

PruneToks()

void PruneToks ( BaseFloat  beam, unordered_map< StateId, Token *> *  toks  )

staticprivate

Definition at line 267 of file simple-decoder.cc.

References rnnlm::i, KALDI_VLOG, and SimpleDecoder::Token::TokenDelete().

Referenced by SimpleDecoder::AdvanceDecoding().

                                                                                  {
  if (toks->empty()) {
    KALDI_VLOG(2) <<  "No tokens to prune.\n";
    return;
  }
  double best_cost = std::numeric_limits<double>::infinity();
  for (unordered_map<StateId, Token*>::iterator iter = toks->begin();
       iter != toks->end(); ++iter)
    best_cost = std::min(best_cost, iter->second->cost_);
  std::vector<StateId> retained;
  double cutoff = best_cost + beam;
  for (unordered_map<StateId, Token*>::iterator iter = toks->begin();
       iter != toks->end(); ++iter) {
    if (iter->second->cost_ < cutoff)
      retained.push_back(iter->first);
    else
      Token::TokenDelete(iter->second);
  }
  unordered_map<StateId, Token*> tmp;
  for (size_t i = 0; i < retained.size(); i++) {
    tmp[retained[i]] = (*toks)[retained[i]];
  }
  KALDI_VLOG(2) <<  "Pruned to " << (retained.size()) << " toks.\n";
  tmp.swap(*toks);
}

ReachedFinal()

bool ReachedFinal

(

)

const

Definition at line 76 of file simple-decoder.cc.

References SimpleDecoder::cur_toks_, and SimpleDecoder::fst_.

Referenced by SimpleDecoder::GetBestPath(), main(), and SimpleDecoder::SimpleDecoder().

                                       {
  for (unordered_map<StateId, Token*>::const_iterator iter = cur_toks_.begin();
       iter != cur_toks_.end();
       ++iter) {
    if (iter->second->cost_ != std::numeric_limits<BaseFloat>::infinity() &&
        fst_.Final(iter->first) != StdWeight::Zero())
      return true;
  }
  return false;
}

Member Data Documentation

beam_

BaseFloat beam_

private

Definition at line 141 of file simple-decoder.h.

Referenced by SimpleDecoder::AdvanceDecoding(), SimpleDecoder::ProcessEmitting(), and SimpleDecoder::ProcessNonemitting().

cur_toks_

unordered_map<StateId, Token*> cur_toks_

private

Definition at line 138 of file simple-decoder.h.

Referenced by SimpleDecoder::AdvanceDecoding(), SimpleDecoder::Decode(), SimpleDecoder::FinalRelativeCost(), SimpleDecoder::GetBestPath(), SimpleDecoder::InitDecoding(), SimpleDecoder::ProcessEmitting(), SimpleDecoder::ProcessNonemitting(), SimpleDecoder::ReachedFinal(), and SimpleDecoder::~SimpleDecoder().

fst_

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

private

Definition at line 140 of file simple-decoder.h.

Referenced by SimpleDecoder::FinalRelativeCost(), SimpleDecoder::GetBestPath(), SimpleDecoder::InitDecoding(), SimpleDecoder::ProcessEmitting(), SimpleDecoder::ProcessNonemitting(), and SimpleDecoder::ReachedFinal().

num_frames_decoded_

int32 num_frames_decoded_

private

Definition at line 143 of file simple-decoder.h.

Referenced by SimpleDecoder::AdvanceDecoding(), SimpleDecoder::InitDecoding(), SimpleDecoder::NumFramesDecoded(), and SimpleDecoder::ProcessEmitting().

prev_toks_

unordered_map<StateId, Token*> prev_toks_

private

Definition at line 139 of file simple-decoder.h.

Referenced by SimpleDecoder::AdvanceDecoding(), SimpleDecoder::InitDecoding(), SimpleDecoder::ProcessEmitting(), and SimpleDecoder::~SimpleDecoder().

---

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

• decoder/simple-decoder.h
• decoder/simple-decoder.cc