The class UnweightedNgramFst is a DeterministicOnDemandFst whose states encode an n-gram history. More...

#include <deterministic-fst.h>

Inheritance diagram for UnweightedNgramFst< Arc >:

Collaboration diagram for UnweightedNgramFst< Arc >:

Public Types
typedef Arc::Weight	Weight

typedef Arc::StateId	StateId

typedef Arc::Label	Label

Public Types inherited from DeterministicOnDemandFst< Arc >
typedef Arc::StateId	StateId

typedef Arc::Weight	Weight

typedef Arc::Label	Label

Public Member Functions
	UnweightedNgramFst (int n)

StateId	Start ()

Weight	Final (StateId s)

bool	GetArc (StateId s, Label ilabel, Arc *oarc)
	Note: ilabel must not be epsilon. More...

Public Member Functions inherited from DeterministicOnDemandFst< Arc >
virtual	~DeterministicOnDemandFst ()

Private Types
typedef unordered_map< std::vector< Label >, StateId, kaldi::VectorHasher< Label > >	MapType

Private Attributes
int	n_

MapType	state_map_

StateId	start_state_

std::vector< std::vector< Label > >	state_vec_

Detailed Description

template<class Arc>
class fst::UnweightedNgramFst< Arc >

The class UnweightedNgramFst is a DeterministicOnDemandFst whose states encode an n-gram history.

Conceptually, for n-gram order n and k labels, the FST is an unweighted acceptor with about k^(n-1) states (ignoring end effects). However, the FST is created on demand and doesn't need the label vocabulary; GetArc matches on any input label. This class is primarily used together with ComposeDeterministicOnDemandFst to expand the n-gram history of lattices, ensuring that each arc has a sufficiently long unique word history.

Definition at line 173 of file deterministic-fst.h.

Member Typedef Documentation

◆ Label

typedef Arc::Label Label

Definition at line 177 of file deterministic-fst.h.

◆ MapType

typedef unordered_map<std::vector<Label>, StateId, kaldi::VectorHasher<Label> > MapType

private

Definition at line 189 of file deterministic-fst.h.

◆ StateId

typedef Arc::StateId StateId

Definition at line 176 of file deterministic-fst.h.

◆ Weight

typedef Arc::Weight Weight

Definition at line 175 of file deterministic-fst.h.

Constructor & Destructor Documentation

◆ UnweightedNgramFst()

UnweightedNgramFst ( int n )

Definition at line 89 of file deterministic-fst-inl.h.

References UnweightedNgramFst< Arc >::start_state_, UnweightedNgramFst< Arc >::state_map_, and UnweightedNgramFst< Arc >::state_vec_.

                                                 : n_(n) {
   // Starting state is an empty vector
   std::vector<Label> start_state;
   state_vec_.push_back(start_state);
   start_state_ = 0;
   state_map_[start_state] = 0;
 }

Member Function Documentation

◆ Final()

Arc::Weight Final ( StateId s )

virtual

Implements DeterministicOnDemandFst< Arc >.

Definition at line 130 of file deterministic-fst-inl.h.

References KALDI_ASSERT, and UnweightedNgramFst< Arc >::state_vec_.

                                                                {
   KALDI_ASSERT(state < static_cast<StateId>(state_vec_.size()));
   return Weight::One();
 }

◆ GetArc()

bool GetArc	(	StateId	s,
		Label	ilabel,
		Arc *	oarc
	)

virtual

Note: ilabel must not be epsilon.

Implements DeterministicOnDemandFst< Arc >.

Definition at line 98 of file deterministic-fst-inl.h.

References KALDI_ASSERT, UnweightedNgramFst< Arc >::n_, UnweightedNgramFst< Arc >::state_map_, and UnweightedNgramFst< Arc >::state_vec_.

                                       {
 
   // The state ids increment with each state we encounter.
   // if the assert fails, then we are trying to access
   // unseen states that are not immediately traversable.
   KALDI_ASSERT(static_cast<size_t>(s) < state_vec_.size());
   std::vector<Label> seq = state_vec_[s];
   // Update state info.
   seq.push_back(ilabel);
   if (seq.size() > n_-1) {
     // Remove oldest word in the history.
     seq.erase(seq.begin());
   }
   std::pair<const std::vector<Label>, StateId> new_state(
     seq,
     static_cast<Label>(state_vec_.size()));
   // Now get state id for destination state.
   typedef typename MapType::iterator IterType;
   std::pair<IterType, bool> result = state_map_.insert(new_state);
   if (result.second == true) {
     state_vec_.push_back(seq);
   }
   oarc->weight = Weight::One(); // Because the FST is unweightd.
   oarc->ilabel = ilabel;
   oarc->olabel = ilabel;
   oarc->nextstate = result.first->second; // The next state id.
   // All arcs can be matched.
   return true;
 }