Collaboration diagram for LatticeLexiconWordAligner:

[legend]

Classes
class	ComputationState

struct	Tuple

struct	TupleEqual

struct	TupleHash

Public Types
enum	Freshness { kNotFresh, kFresh, kAllFresh }

typedef CompactLatticeArc::StateId	StateId

typedef CompactLatticeArc::Label	Label

typedef WordAlignLatticeLexiconInfo::ViabilityMap	ViabilityMap

typedef WordAlignLatticeLexiconInfo::LexiconMap	LexiconMap

typedef WordAlignLatticeLexiconInfo::NumPhonesMap	NumPhonesMap

typedef unordered_map< Tuple, StateId, TupleHash, TupleEqual >	MapType

Public Member Functions
StateId	GetStateForTuple (const Tuple &tuple)

void	ProcessTransition (StateId prev_output_state, const Tuple &next_tuple, CompactLatticeArc *arc)

void	ProcessEpsilonTransitions (const Tuple &tuple, StateId output_state)

void	ProcessWordTransitions (const Tuple &tuple, StateId output_state)

void	PossiblyAdvanceArc (const Tuple &tuple, StateId output_state)

bool	ProcessFinal ()
	Process all final-probs (normal case, no forcing-out). More...

bool	HasNonEpsArcsOut (StateId output_state)
	This function returns true if the state "output_state" in the output lattice has arcs out that have either a non-epsilon symbol or transition-ids in the string of the weight. More...

void	ProcessFinalForceOut ()
	Creates arcs from all the tuples that were final in the original lattice but have no arcs out of them in the output lattice that consume words or phones– does so by "forcing out" any words and phones there are pending in the computation states. More...

void	ProcessFinalWrapper ()

void	ProcessQueueElement ()

	LatticeLexiconWordAligner (const CompactLattice &lat, const TransitionModel &tmodel, const WordAlignLatticeLexiconInfo &lexicon_info, int32 max_states, int32 partial_word_label, CompactLattice *lat_out)

void	RemoveEpsilonsFromLattice ()

bool	AlignLattice ()

Static Public Member Functions
static void	AppendVectors (std::vector< std::vector< int32 > >::const_iterator input_begin, std::vector< std::vector< int32 > >::const_iterator input_end, std::vector< int32 > *output)

Public Attributes
CompactLattice	lat_in_

const TransitionModel &	tmodel_

const WordAlignLatticeLexiconInfo &	lexicon_info_

int32	max_states_

CompactLattice *	lat_out_

std::vector< std::pair< Tuple, StateId > >	queue_

std::vector< std::pair< Tuple, StateId > >	final_queue_

MapType	map_

int32	partial_word_label_

bool	error_

Detailed Description

Definition at line 35 of file word-align-lattice-lexicon.cc.

Member Typedef Documentation

◆ Label

typedef CompactLatticeArc::Label Label

Definition at line 38 of file word-align-lattice-lexicon.cc.

◆ LexiconMap

typedef WordAlignLatticeLexiconInfo::LexiconMap LexiconMap

Definition at line 40 of file word-align-lattice-lexicon.cc.

◆ MapType

typedef unordered_map<Tuple, StateId, TupleHash, TupleEqual> MapType

Definition at line 195 of file word-align-lattice-lexicon.cc.

◆ NumPhonesMap

typedef WordAlignLatticeLexiconInfo::NumPhonesMap NumPhonesMap

Definition at line 41 of file word-align-lattice-lexicon.cc.

◆ StateId

typedef CompactLatticeArc::StateId StateId

Definition at line 37 of file word-align-lattice-lexicon.cc.

◆ ViabilityMap

typedef WordAlignLatticeLexiconInfo::ViabilityMap ViabilityMap

Definition at line 39 of file word-align-lattice-lexicon.cc.

Member Enumeration Documentation

◆ Freshness

enum Freshness

Enumerator
kNotFresh
kFresh
kAllFresh

Definition at line 56 of file word-align-lattice-lexicon.cc.

                {
     kNotFresh,
     kFresh,
     kAllFresh
   } Freshness;

Constructor & Destructor Documentation

◆ LatticeLexiconWordAligner()

LatticeLexiconWordAligner	(	const CompactLattice &	lat,
		const TransitionModel &	tmodel,
		const WordAlignLatticeLexiconInfo &	lexicon_info,
		int32	max_states,
		int32	partial_word_label,
		CompactLattice *	lat_out
	)

inline

Definition at line 285 of file word-align-lattice-lexicon.cc.

References fst::CreateSuperFinal(), and LatticeLexiconWordAligner::lat_in_.

                                                     :
       lat_in_(lat), tmodel_(tmodel), lexicon_info_(lexicon_info),
       max_states_(max_states),
       lat_out_(lat_out),
       partial_word_label_(partial_word_label == 0 ?
                           kTemporaryEpsilon : partial_word_label),
       error_(false) {
     // lat_in_ is after PhoneAlignLattice, it is not deterministic and contains epsilons
 
     fst::CreateSuperFinal(&lat_in_); // Creates a super-final state, so the
     // only final-probs are One().  Note: the member lat_in_ is not a reference.
 
   }

Member Function Documentation

◆ AlignLattice()

bool AlignLattice ( )

inline

Definition at line 317 of file word-align-lattice-lexicon.cc.

References LatticeLexiconWordAligner::error_, LatticeLexiconWordAligner::GetStateForTuple(), KALDI_WARN, LatticeLexiconWordAligner::lat_in_, LatticeLexiconWordAligner::lat_out_, LatticeLexiconWordAligner::max_states_, LatticeLexiconWordAligner::ProcessFinalWrapper(), LatticeLexiconWordAligner::ProcessQueueElement(), LatticeLexiconWordAligner::queue_, and LatticeLexiconWordAligner::RemoveEpsilonsFromLattice().

Referenced by kaldi::WordAlignLatticeLexicon().

                       {
     lat_out_->DeleteStates();
     if (lat_in_.Start() == fst::kNoStateId) {
       KALDI_WARN << "Trying to word-align empty lattice.";
       return false;
     }
     ComputationState initial_comp_state;
     Tuple initial_tuple(lat_in_.Start(), initial_comp_state);
     StateId start_state = GetStateForTuple(initial_tuple);
     lat_out_->SetStart(start_state);
 
     while (!queue_.empty()) {
       if (max_states_ > 0 && lat_out_->NumStates() > max_states_) {
         KALDI_WARN << "Number of states in lattice exceeded max-states of "
                    << max_states_ << ", original lattice had "
                    << lat_in_.NumStates() << " states.  Returning empty lattice.";
         lat_out_->DeleteStates();
         return false;
       }
       ProcessQueueElement();
     }
     ProcessFinalWrapper();
 
     RemoveEpsilonsFromLattice();
 
     return !error_;
   }

◆ AppendVectors()

void AppendVectors	(	std::vector< std::vector< int32 > >::const_iterator	input_begin,
		std::vector< std::vector< int32 > >::const_iterator	input_end,
		std::vector< int32 > *	output
	)

static

Definition at line 363 of file word-align-lattice-lexicon.cc.

Referenced by LatticeLexiconWordAligner::ComputationState::TakeForcedTransition(), and LatticeLexiconWordAligner::ComputationState::TakeTransition().

                               {
   size_t size = 0;
   for (std::vector<std::vector<int32> >::const_iterator iter = input_begin;
        iter != input_end;
        ++iter)
     size += iter->size();
   output->clear();
   output->reserve(size);
   for (std::vector<std::vector<int32> >::const_iterator iter = input_begin;
        iter != input_end;
        ++iter)
     output->insert(output->end(), iter->begin(), iter->end());
 }

◆ GetStateForTuple()

StateId GetStateForTuple ( const Tuple & tuple )

inline

Definition at line 198 of file word-align-lattice-lexicon.cc.

References LatticeLexiconWordAligner::lat_out_, LatticeLexiconWordAligner::map_, and LatticeLexiconWordAligner::queue_.

Referenced by LatticeLexiconWordAligner::AlignLattice(), LatticeLexiconWordAligner::PossiblyAdvanceArc(), LatticeLexiconWordAligner::ProcessFinalForceOut(), and LatticeLexiconWordAligner::ProcessTransition().

                                                {
     MapType::iterator iter = map_.find(tuple);
     if (iter == map_.end()) { // not in map.
       StateId output_state = lat_out_->AddState();
       map_[tuple] = output_state;
       queue_.push_back(std::make_pair(tuple, output_state));
       return output_state;
     } else {
       return iter->second;
     }
   }

◆ HasNonEpsArcsOut()

bool HasNonEpsArcsOut ( StateId output_state )

This function returns true if the state "output_state" in the output lattice has arcs out that have either a non-epsilon symbol or transition-ids in the string of the weight.

Definition at line 531 of file word-align-lattice-lexicon.cc.

References LatticeLexiconWordAligner::lat_out_.

Referenced by LatticeLexiconWordAligner::ProcessFinalForceOut(), and LatticeLexiconWordAligner::ProcessTransition().

                                                                      {
   for (fst::ArcIterator<CompactLattice> aiter(*lat_out_, output_state);
        !aiter.Done(); aiter.Next()) {
     const CompactLatticeArc &arc = aiter.Value();
     if (arc.ilabel != 0 || arc.olabel != 0 || !arc.weight.String().empty())
       return true;
   }
   return false;
 }

◆ PossiblyAdvanceArc()

void PossiblyAdvanceArc	(	const Tuple &	tuple,
		StateId	output_state
	)

Definition at line 488 of file word-align-lattice-lexicon.cc.

References LatticeLexiconWordAligner::ComputationState::Advance(), LatticeLexiconWordAligner::Tuple::comp_state, LatticeLexiconWordAligner::GetStateForTuple(), LatticeLexiconWordAligner::Tuple::input_state, LatticeLexiconWordAligner::lat_in_, LatticeLexiconWordAligner::lat_out_, LatticeLexiconWordAligner::lexicon_info_, LatticeLexiconWordAligner::tmodel_, WordAlignLatticeLexiconInfo::viability_map_, and LatticeLexiconWordAligner::ComputationState::ViableIfAdvanced().

Referenced by LatticeLexiconWordAligner::ProcessQueueElement(), and LatticeLexiconWordAligner::ProcessTransition().

                                               {
   if (tuple.comp_state.ViableIfAdvanced(lexicon_info_.viability_map_)) {
     for(fst::ArcIterator<CompactLattice> aiter(lat_in_, tuple.input_state);
         !aiter.Done(); aiter.Next()) {
       const CompactLatticeArc &arc_in = aiter.Value();
       Tuple next_tuple(arc_in.nextstate, tuple.comp_state);
       LatticeWeight arc_weight;
       next_tuple.comp_state.Advance(arc_in, tmodel_, &arc_weight);
       // Note: GetStateForTuple will add the tuple to the queue,
       // if necessary.
 
       StateId next_output_state = GetStateForTuple(next_tuple);
       CompactLatticeArc arc_out(0, 0,
                                 CompactLatticeWeight(arc_weight,
                                                      std::vector<int32>()),
                                 next_output_state);
       lat_out_->AddArc(output_state,
                        arc_out);
     }
   }
 }

◆ ProcessEpsilonTransitions()

void ProcessEpsilonTransitions	(	const Tuple &	tuple,
		StateId	output_state
	)

Definition at line 380 of file word-align-lattice-lexicon.cc.

Referenced by LatticeLexiconWordAligner::ProcessQueueElement(), and LatticeLexiconWordAligner::ProcessTransition().

                                               {
   const ComputationState &comp_state = tuple.comp_state;
   StateId input_state = tuple.input_state;
   StateId zero_word = 0;
   NumPhonesMap::const_iterator iter =
       lexicon_info_.num_phones_map_.find(zero_word);
   if (iter == lexicon_info_.num_phones_map_.end()) {
     return; // No epsilons to match; this can only happen if the lexicon
     // we were provided had no lines with 0 as the first entry, i.e.  no
     // optional silences or the like.
   }
   // Now decide what range of phone-lengths we must process.  This is all
   // about only getting a single opportunity to process any given sequence of
   // phones.
   int32 min_num_phones, max_num_phones;
 
   if (comp_state.PhoneFreshness() == kAllFresh) {
     // All sub-sequences of the phone sequence are fresh because we just
     // shifted some phones off, so we do this for all lengths.  We can limit
     // ourselves to the range of possible lengths for the epsilon symbol,
     // in the lexicon.
     min_num_phones = iter->second.first;
     max_num_phones = std::min(iter->second.second, comp_state.NumPhones());
   } else if (comp_state.PhoneFreshness() == kFresh) {
     // only last phone is "fresh", so only consider the sequence of all
     // phones including the last one.
     int32 num_phones = comp_state.NumPhones();
     if (num_phones >= iter->second.first &&
         num_phones <= iter->second.second) {
       min_num_phones = num_phones;
       max_num_phones = num_phones;
     } else {
       return;
     }
   } else { // kNotFresh
     return;
   }
 
   if (min_num_phones == 0)
     KALDI_ERR << "Lexicon error: epsilon transition that produces no output:";
 
   for (int32 num_phones = min_num_phones;
        num_phones <= max_num_phones;
        num_phones++) {
     Tuple next_tuple;
     next_tuple.input_state = input_state; // We're not taking a transition in the
     // input FST so this stays the same.
     CompactLatticeArc arc;
     if (comp_state.TakeTransition(lexicon_info_.lexicon_map_,
                                   zero_word,
                                   num_phones,
                                   &next_tuple.comp_state,
                                   &arc)) {
       ProcessTransition(output_state, next_tuple, &arc);
     }
   }
 }

◆ ProcessFinal()

bool ProcessFinal ( )

Process all final-probs (normal case, no forcing-out).

returns true if we had at least one final-prob.

Definition at line 511 of file word-align-lattice-lexicon.cc.

References LatticeLexiconWordAligner::Tuple::comp_state, LatticeLexiconWordAligner::final_queue_, LatticeLexiconWordAligner::ComputationState::FinalWeight(), rnnlm::i, LatticeLexiconWordAligner::Tuple::input_state, KALDI_ASSERT, LatticeLexiconWordAligner::lat_in_, LatticeLexiconWordAligner::lat_out_, CompactLatticeWeightTpl< WeightType, IntType >::One(), and LatticeWeightTpl< BaseFloat >::Zero().

Referenced by LatticeLexiconWordAligner::ProcessFinalWrapper(), and LatticeLexiconWordAligner::ProcessTransition().

                                              {
   bool saw_final = false;
   // Find final-states...
   for (size_t i = 0; i < final_queue_.size(); i++) {
     const Tuple &tuple = final_queue_[i].first;
     StateId output_state = final_queue_[i].second;
     KALDI_ASSERT(lat_in_.Final(tuple.input_state) == CompactLatticeWeight::One());
     LatticeWeight final_weight = tuple.comp_state.FinalWeight();
     if (final_weight != LatticeWeight::Zero()) {
       // note: final_weight is only nonzero if there are no
       // pending transition-ids, so there is no string component.
       std::vector<int32> empty_vec;
       lat_out_->SetFinal(output_state,
                          CompactLatticeWeight(final_weight, empty_vec));
       saw_final = true;
     }
   }
   return saw_final;
 }

◆ ProcessFinalForceOut()

void ProcessFinalForceOut ( )

Creates arcs from all the tuples that were final in the original lattice but have no arcs out of them in the output lattice that consume words or phones– does so by "forcing out" any words and phones there are pending in the computation states.

This function is only called if no states were "naturally" final; this will only happen for lattices that were forced out during decoding.

Definition at line 541 of file word-align-lattice-lexicon.cc.

References LatticeLexiconWordAligner::Tuple::comp_state, LatticeLexiconWordAligner::final_queue_, LatticeLexiconWordAligner::GetStateForTuple(), LatticeLexiconWordAligner::HasNonEpsArcsOut(), rnnlm::i, LatticeLexiconWordAligner::Tuple::input_state, KALDI_ASSERT, LatticeLexiconWordAligner::lat_out_, LatticeLexiconWordAligner::partial_word_label_, LatticeLexiconWordAligner::queue_, kaldi::swap(), and LatticeLexiconWordAligner::ComputationState::TakeForcedTransition().

Referenced by LatticeLexiconWordAligner::ProcessFinalWrapper(), and LatticeLexiconWordAligner::ProcessTransition().

                                                      {
   KALDI_ASSERT(queue_.empty());
   std::vector<std::pair<Tuple, StateId> > new_final_queue_;
   new_final_queue_.reserve(final_queue_.size());
   for (size_t i = 0; i < final_queue_.size();i++) { // note: all the states will
     // be final in the orig. lattice
     const Tuple &tuple = final_queue_[i].first;
     StateId output_state = final_queue_[i].second;
 
     if (!HasNonEpsArcsOut(output_state)) { // This if-statement
       // avoids forcing things out too early, when they had words
       // that could naturally have been put out.  [without it,
       // we'd have multiple alternate paths at the end.]
 
       CompactLatticeArc arc;
       Tuple next_tuple;
       next_tuple.input_state = tuple.input_state;
       tuple.comp_state.TakeForcedTransition(partial_word_label_,
                                             &next_tuple.comp_state,
                                             &arc);
       // Note: the following call may add to queue_, but we'll clear it,
       // we don't want to process these states.
       StateId new_state = GetStateForTuple(next_tuple);
       arc.nextstate = new_state;
       lat_out_->AddArc(output_state, arc);
       new_final_queue_.push_back(std::make_pair(next_tuple, new_state));
     }
   }
   queue_.clear();
   std::swap(final_queue_, new_final_queue_);
 }

◆ ProcessFinalWrapper()

void ProcessFinalWrapper ( )

inline

Definition at line 250 of file word-align-lattice-lexicon.cc.

References LatticeLexiconWordAligner::error_, LatticeLexiconWordAligner::final_queue_, KALDI_WARN, LatticeLexiconWordAligner::ProcessFinal(), and LatticeLexiconWordAligner::ProcessFinalForceOut().

Referenced by LatticeLexiconWordAligner::AlignLattice().

                              {
     if (final_queue_.empty()) {
       KALDI_WARN << "No final-probs to process.";
       error_ = true;
       return;
     }
     if (ProcessFinal()) return;
     error_ = true;
     KALDI_WARN << "Word-aligning lattice: lattice was forced out, will have partial words at end.";
 
     ProcessFinalForceOut();
 
     if (ProcessFinal()) return;
     KALDI_WARN << "Word-aligning lattice: had no final-states even after forcing out "
                << "(result will be empty).  This probably indicates wrong input.";
     return;
   }

◆ ProcessQueueElement()

void ProcessQueueElement ( )

inline

Definition at line 268 of file word-align-lattice-lexicon.cc.

References LatticeLexiconWordAligner::final_queue_, KALDI_ASSERT, LatticeLexiconWordAligner::lat_in_, LatticeLexiconWordAligner::PossiblyAdvanceArc(), LatticeLexiconWordAligner::ProcessEpsilonTransitions(), LatticeLexiconWordAligner::ProcessWordTransitions(), LatticeLexiconWordAligner::queue_, and CompactLatticeWeightTpl< WeightType, IntType >::Zero().

Referenced by LatticeLexiconWordAligner::AlignLattice().

                              {
     KALDI_ASSERT(!queue_.empty());
     Tuple tuple = queue_.back().first;
     StateId output_state = queue_.back().second;
     queue_.pop_back();
 
     ProcessEpsilonTransitions(tuple, output_state);
     ProcessWordTransitions(tuple, output_state);
     PossiblyAdvanceArc(tuple, output_state);
 
     // Note: we'll do a bit more filtering in ProcessFinal(), meaning
     // that we won't necessarily give a final-prob to all of the things
     // that go onto final_queue_.
     if (lat_in_.Final(tuple.input_state) != CompactLatticeWeight::Zero())
       final_queue_.push_back(std::make_pair(tuple, output_state));
   }

◆ ProcessTransition()

void ProcessTransition	(	StateId	prev_output_state,
		const Tuple &	next_tuple,
		CompactLatticeArc *	arc
	)

inline

Definition at line 211 of file word-align-lattice-lexicon.cc.

References LatticeLexiconWordAligner::GetStateForTuple(), LatticeLexiconWordAligner::HasNonEpsArcsOut(), LatticeLexiconWordAligner::lat_out_, LatticeLexiconWordAligner::PossiblyAdvanceArc(), LatticeLexiconWordAligner::ProcessEpsilonTransitions(), LatticeLexiconWordAligner::ProcessFinal(), LatticeLexiconWordAligner::ProcessFinalForceOut(), and LatticeLexiconWordAligner::ProcessWordTransitions().

Referenced by LatticeLexiconWordAligner::ProcessEpsilonTransitions(), and LatticeLexiconWordAligner::ProcessWordTransitions().

                                                  { // arc to add (must first modify it by adding "nextstate")
     arc->nextstate = GetStateForTuple(next_tuple); // adds it to queue_ if new.
     lat_out_->AddArc(prev_output_state, *arc);
   }

◆ ProcessWordTransitions()

void ProcessWordTransitions	(	const Tuple &	tuple,
		StateId	output_state
	)

Definition at line 439 of file word-align-lattice-lexicon.cc.

Referenced by LatticeLexiconWordAligner::ProcessQueueElement(), and LatticeLexiconWordAligner::ProcessTransition().

                                               {
   const ComputationState &comp_state = tuple.comp_state;
   StateId input_state = tuple.input_state;
   if (comp_state.NumWords() > 0) {
     int32 min_num_phones, max_num_phones;
     int32 word_id = comp_state.PendingWord();
 
     if (comp_state.WordFreshness() == kFresh ||
         comp_state.PhoneFreshness() == kAllFresh) {
       // Just saw word, or shifted phones,
       // so 1st opportunity to process phone-sequences of all possible sizes,
       // with this word.
       NumPhonesMap::const_iterator iter =
           lexicon_info_.num_phones_map_.find(word_id);
       if (iter == lexicon_info_.num_phones_map_.end()) {
         KALDI_ERR << "Word " << word_id << " is not present in the lexicon.";
       }
       min_num_phones = iter->second.first;
       max_num_phones = std::min(iter->second.second,
                                 comp_state.NumPhones());
     } else if (comp_state.PhoneFreshness() == kFresh) {
       // just the latest phone is new -> just try to process the
       // phone-sequence of all the phones we have.
       min_num_phones = comp_state.NumPhones();
       max_num_phones = min_num_phones;
     } else {
       return; // Nothing to do, since neither the word nor the phones are fresh.
     }
 
     for (int32 num_phones = min_num_phones;
          num_phones <= max_num_phones;
          num_phones++) {
       Tuple next_tuple;
       next_tuple.input_state = input_state; // We're not taking a transition in the
       // input FST so this stays the same.
       CompactLatticeArc arc;
       if (comp_state.TakeTransition(lexicon_info_.lexicon_map_,
                                     word_id,
                                     num_phones,
                                     &next_tuple.comp_state,
                                     &arc)) {
         ProcessTransition(output_state, next_tuple, &arc);
       }
     }
   }
 }

◆ RemoveEpsilonsFromLattice()

void RemoveEpsilonsFromLattice ( )

inline

Definition at line 308 of file word-align-lattice-lexicon.cc.

References LatticeLexiconWordAligner::lat_out_, and fst::RemoveSomeInputSymbols().

Referenced by LatticeLexiconWordAligner::AlignLattice().

                                    {
     Connect(lat_out_);
     RmEpsilon(lat_out_, true); // true = connect.
     std::vector<int32> syms_to_remove;
     syms_to_remove.push_back(kTemporaryEpsilon);
     RemoveSomeInputSymbols(syms_to_remove, lat_out_);
     Project(lat_out_, fst::PROJECT_INPUT);
   }