Inheritance diagram for ArpaLmCompilerImpl< HistKey >:

Collaboration diagram for ArpaLmCompilerImpl< HistKey >:

[legend]

Public Member Functions
	ArpaLmCompilerImpl (ArpaLmCompiler parent, fst::StdVectorFst fst, Symbol sub_eps)

virtual void	ConsumeNGram (const NGram &ngram, bool is_highest)

Public Member Functions inherited from ArpaLmCompilerImplInterface
virtual	~ArpaLmCompilerImplInterface ()

Private Types
typedef unordered_map< HistKey, StateId, typename HistKey::HashType >	HistoryMap

Private Member Functions
StateId	AddStateWithBackoff (HistKey key, float backoff)

void	CreateBackoff (HistKey key, StateId state, float weight)

Private Attributes
ArpaLmCompiler *	parent_

fst::StdVectorFst *	fst_

Symbol	bos_symbol_

Symbol	eos_symbol_

Symbol	sub_eps_

StateId	eos_state_

HistoryMap	history_

Detailed Description

template<class HistKey>
class kaldi::ArpaLmCompilerImpl< HistKey >

Definition at line 114 of file arpa-lm-compiler.cc.

Member Typedef Documentation

◆ HistoryMap

typedef unordered_map<HistKey, StateId, typename HistKey::HashType> HistoryMap

private

Definition at line 133 of file arpa-lm-compiler.cc.

Constructor & Destructor Documentation

◆ ArpaLmCompilerImpl()

ArpaLmCompilerImpl	(	ArpaLmCompiler *	parent,
		fst::StdVectorFst *	fst,
		Symbol	sub_eps
	)

Definition at line 138 of file arpa-lm-compiler.cc.

References ArpaLmCompilerImpl< HistKey >::eos_state_, ArpaLmCompilerImpl< HistKey >::fst_, ArpaLmCompilerImpl< HistKey >::history_, and ArpaLmCompilerImpl< HistKey >::sub_eps_.

     : parent_(parent), fst_(fst), bos_symbol_(parent->Options().bos_symbol),
       eos_symbol_(parent->Options().eos_symbol), sub_eps_(sub_eps) {
   // The algorithm maintains state per history. The 0-gram is a special state
   // for empty history. All unigrams (including BOS) backoff into this state.
   StateId zerogram = fst_->AddState();
   history_[HistKey()] = zerogram;
 
   // Also, if </s> is not treated as epsilon, create a common end state for
   // all transitions accepting the </s>, since they do not back off. This small
   // optimization saves about 2% states in an average grammar.
   if (sub_eps_ == 0) {
     eos_state_ = fst_->AddState();
     fst_->SetFinal(eos_state_, 0);
   }
 }

Member Function Documentation

◆ AddStateWithBackoff()

StateId AddStateWithBackoff	(	HistKey	key,
		float	backoff
	)

private

Definition at line 245 of file arpa-lm-compiler.cc.

References backoff, ArpaLmCompilerImpl< HistKey >::CreateBackoff(), ArpaLmCompilerImpl< HistKey >::fst_, and ArpaLmCompilerImpl< HistKey >::history_.

Referenced by ArpaLmCompilerImpl< HistKey >::ConsumeNGram().

                                                                         {
   typename HistoryMap::iterator dest_it = history_.find(key);
   if (dest_it != history_.end()) {
     // Found an existing state in the history map. Invariant: if the state in
     // the map, then its backoff arc is in the FST. We are done.
     return dest_it->second;
   }
   // Otherwise create a new state and its backoff arc, and register in the map.
   StateId dest = fst_->AddState();
   history_[key] = dest;
   CreateBackoff(key.Tails(), dest, backoff);
   return dest;
 }

◆ ConsumeNGram()

void ConsumeNGram	(	const NGram &	ngram,
		bool	is_highest
	)

virtual

Implements ArpaLmCompilerImplInterface.

Definition at line 157 of file arpa-lm-compiler.cc.

References ArpaLmCompilerImpl< HistKey >::AddStateWithBackoff(), NGram::backoff, ArpaLmCompilerImpl< HistKey >::bos_symbol_, ArpaLmCompilerImpl< HistKey >::eos_state_, ArpaLmCompilerImpl< HistKey >::eos_symbol_, ArpaLmCompilerImpl< HistKey >::fst_, ArpaLmCompilerImpl< HistKey >::history_, KALDI_ERR, KALDI_WARN, ArpaFileParser::LineReference(), NGram::logprob, ArpaLmCompilerImpl< HistKey >::parent_, ArpaFileParser::ShouldWarn(), ArpaLmCompilerImpl< HistKey >::sub_eps_, and NGram::words.

                                                                 {
   // Generally, we do the following. Suppose we are adding an n-gram "A B
   // C". Then find the node for "A B", add a new node for "A B C", and connect
   // them with the arc accepting "C" with the specified weight. Also, add a
   // backoff arc from the new "A B C" node to its backoff state "B C".
   //
   // Two notable exceptions are the highest order n-grams, and final n-grams.
   //
   // When adding a highest order n-gram (e. g., our "A B C" is in a 3-gram LM),
   // the following optimization is performed. There is no point adding a node
   // for "A B C" with a "C" arc from "A B", since there will be no other
   // arcs ingoing to this node, and an epsilon backoff arc into the backoff
   // model "B C", with the weight of \bar{1}. To save a node, create an arc
   // accepting "C" directly from "A B" to "B C". This saves as many nodes
   // as there are the highest order n-grams, which is typically about half
   // the size of a large 3-gram model.
   //
   // Indeed, this does not apply to n-grams ending in EOS, since they do not
   // back off. These are special, as they do not have a back-off state, and
   // the node for "(..anything..) </s>" is always final. These are handled
   // in one of the two possible ways, If symbols <s> and </s> are being
   // replaced by epsilons, neither node nor arc is created, and the logprob
   // of the n-gram is applied to its source node as final weight. If <s> and
   // </s> are preserved, then a special final node for </s> is allocated and
   // used as the destination of the "</s>" acceptor arc.
   HistKey heads(ngram.words.begin(), ngram.words.end() - 1);
   typename HistoryMap::iterator source_it = history_.find(heads);
   if (source_it == history_.end()) {
     // There was no "A B", therefore the probability of "A B C" is zero.
     // Print a warning and discard current n-gram.
     if (parent_->ShouldWarn())
       KALDI_WARN << parent_->LineReference()
                  << " skipped: no parent (n-1)-gram exists";
     return;
   }
 
   StateId source = source_it->second;
   StateId dest;
   Symbol sym = ngram.words.back();
   float weight = -ngram.logprob;
   if (sym == sub_eps_ || sym == 0) {
     KALDI_ERR << " <eps> or disambiguation symbol " << sym << "found in the ARPA file. ";
   }
   if (sym == eos_symbol_) {
     if (sub_eps_ == 0) {
       // Keep </s> as a real symbol when not substituting.
       dest = eos_state_;
     } else {
       // Treat </s> as if it was epsilon: mark source final, with the weight
       // of the n-gram.
       fst_->SetFinal(source, weight);
       return;
     }
   } else {
     // For the highest order n-gram, this may find an existing state, for
     // non-highest, will create one (unless there are duplicate n-grams
     // in the grammar, which cannot be reliably detected if highest order,
     // so we better do not do that at all).
     dest = AddStateWithBackoff(
         HistKey(ngram.words.begin() + (is_highest ? 1 : 0),
                 ngram.words.end()),
         -ngram.backoff);
   }
 
   if (sym == bos_symbol_) {
     weight = 0;  // Accepting <s> is always free.
     if (sub_eps_ == 0) {
       // <s> is as a real symbol, only accepted in the start state.
       source = fst_->AddState();
       fst_->SetStart(source);
     } else {
       // The new state for <s> unigram history *is* the start state.
       fst_->SetStart(dest);
       return;
     }
   }
 
   // Add arc from source to dest, whichever way it was found.
   fst_->AddArc(source, fst::StdArc(sym, sym, weight, dest));
   return;
 }

◆ CreateBackoff()

void CreateBackoff	(	HistKey	key,
		StateId	state,
		float	weight
	)

inlineprivate

Definition at line 265 of file arpa-lm-compiler.cc.

References ArpaLmCompilerImpl< HistKey >::fst_, ArpaLmCompilerImpl< HistKey >::history_, and ArpaLmCompilerImpl< HistKey >::sub_eps_.

Referenced by ArpaLmCompilerImpl< HistKey >::AddStateWithBackoff().

                                               {
   typename HistoryMap::iterator dest_it = history_.find(key);
   while (dest_it == history_.end()) {
     key = key.Tails();
     dest_it = history_.find(key);
   }
 
   // The arc should transduce either <eos> or #0 to <eps>, depending on the
   // epsilon substitution mode. This is the only case when input and output
   // label may differ.
   fst_->AddArc(state, fst::StdArc(sub_eps_, 0, weight, dest_it->second));
 }