PrunedCompactLatticeComposer implements an algorithm for pruned composition. More...

Collaboration diagram for PrunedCompactLatticeComposer:

[legend]

Classes
struct	ComposedStateInfo

struct	LatticeStateInfo

Public Member Functions
	PrunedCompactLatticeComposer (const ComposeLatticePrunedOptions &opts, const CompactLattice &clat, fst::DeterministicOnDemandFst< fst::StdArc > det_fst, CompactLattice composed_clat)

void	Compose ()

Private Types
typedef std::priority_queue< std::pair< BaseFloat, int32 >, std::vector< std::pair< BaseFloat, int32 > >, std::greater< std::pair< BaseFloat, int32 > > >	QueueType

Private Member Functions
int32	GetCurrentArcLimit () const

void	ComputeLatticeStateInfo ()

void	AddFirstState ()

void	ProcessQueueElement (int32 composed_state_to_expand)

void	ProcessTransition (int32 composed_src_state, int32 arc_index)

void	RecomputePruningInfo ()

void	GetTopsortedStateList (std::vector< int32 > *composed_states) const

void	ComputeForwardCosts (const std::vector< int32 > &composed_states)

void	ComputeBackwardCosts (const std::vector< int32 > &composed_states)

void	ComputeDeltaBackwardCosts (const std::vector< int32 > &composed_states)

Private Attributes
bool	output_reached_final_

float	depth_penalty_

const ComposeLatticePrunedOptions &	opts_

const CompactLattice &	clat_in_

fst::DeterministicOnDemandFst< fst::StdArc > *	det_fst_

CompactLattice *	clat_out_

int32	num_arcs_out_

std::vector< LatticeStateInfo >	lat_state_info_

double	lat_best_cost_

double	output_best_cost_

BaseFloat	current_cutoff_

QueueType	composed_state_queue_

std::vector< ComposedStateInfo >	composed_state_info_

unordered_map< std::pair< int32, int32 >, int32, PairHasher< int32 > >	pair_to_state_

std::set< int32 >	accessed_lat_states_

Detailed Description

PrunedCompactLatticeComposer implements an algorithm for pruned composition.

It uses a heuristic (like the heuristics used in A*) to estimate the cost to the end of a graph, of the best path that we might get if we expand a particular transition out of a particular state. This enables us to use a priority queue to expand arcs in the composed result in an order roughly from most promising to least promising.

Because some of the quantities used in the heuristic are hard to efficiently keep updated as the composed output is incrementally added to, we periodically recompute these quantities (c.f. RecomputePruningInfo()). In order to prevent this periodic recomputation from dominating the time taken to produce the lattice, we recompute these things on a schedule where, between each computation, we allow the size of the output to grow by a constant factor (default: 1.5). Since the time taken to do the recomputation of quantities used in the heuristic takes time linear in the size of the so-far existing composed output, doing so on this type of schedule will add no more than a constant factor to the runtime.

Definition at line 47 of file compose-lattice-pruned.cc.

Member Typedef Documentation

◆ QueueType

typedef std::priority_queue<std::pair<BaseFloat, int32>, std::vector<std::pair<BaseFloat, int32> >, std::greater<std::pair<BaseFloat, int32> > > QueueType

private

Definition at line 347 of file compose-lattice-pruned.cc.

Constructor & Destructor Documentation

◆ PrunedCompactLatticeComposer()

PrunedCompactLatticeComposer	(	const ComposeLatticePrunedOptions &	opts,
		const CompactLattice &	clat,
		fst::DeterministicOnDemandFst< fst::StdArc > *	det_fst,
		CompactLattice *	composed_clat
	)

Definition at line 621 of file compose-lattice-pruned.cc.

References PrunedCompactLatticeComposer::clat_out_, and PrunedCompactLatticeComposer::depth_penalty_.

                                     : output_reached_final_(false),
     opts_(opts), clat_in_(clat_in), det_fst_(det_fst),
     clat_out_(composed_clat),
     num_arcs_out_(0),
     output_best_cost_(std::numeric_limits<double>::infinity()),
     current_cutoff_(std::numeric_limits<double>::infinity()) {
   clat_out_->DeleteStates();
   depth_penalty_ = -1000;
 }

Member Function Documentation

◆ AddFirstState()

void AddFirstState ( )

private

Definition at line 636 of file compose-lattice-pruned.cc.

Referenced by PrunedCompactLatticeComposer::Compose().

                                                  {
   int32 state_id = clat_out_->AddState();
   clat_out_->SetStart(state_id);
   KALDI_ASSERT(state_id == 0);
   composed_state_info_.resize(1);
   ComposedStateInfo &composed_state = composed_state_info_[0];
   composed_state.lat_state = 0;
   composed_state.lm_state = det_fst_->Start();
   composed_state.depth = 0;
   composed_state.forward_cost = 0.0;
   composed_state.backward_cost = std::numeric_limits<double>::infinity();
   composed_state.delta_backward_cost = 0.0;
   composed_state.prev_composed_state = -1;
   composed_state.sorted_arc_index = 0;
   composed_state.arc_delta_cost = 0.0; // the first arc_delta_cost is always 0.0
                                        // due to sorting; no need to look it up.
   lat_state_info_[0].composed_states.push_back(state_id);
   accessed_lat_states_.insert(state_id);
   pair_to_state_[std::pair<int32, int32>(0, det_fst_->Start())] = state_id;
 
   BaseFloat expected_cost_offset = 0.0;  // the formula simplifies to zero
                                          // in this case.
   composed_state_queue_.push(
       std::pair<BaseFloat, int32>(expected_cost_offset,
                                   state_id));  // actually (0.0, 0).
 
 }

◆ Compose()

void Compose ( )

Definition at line 887 of file compose-lattice-pruned.cc.

Referenced by kaldi::ComposeCompactLatticePruned().

                                            {
   if (clat_in_.NumStates() == 0) {
     KALDI_WARN << "Input lattice to composition is empty.";
     return;
   }
   ComputeLatticeStateInfo();
   AddFirstState();
   // while (we have not reached final state  ||
   //        num-arcs produced < target num-arcs) { ...
   while (output_best_cost_ == std::numeric_limits<double>::infinity() ||
          num_arcs_out_ < opts_.max_arcs) {
     RecomputePruningInfo();
     int32 this_iter_arc_limit = GetCurrentArcLimit();
     while (num_arcs_out_ < this_iter_arc_limit &&
            !composed_state_queue_.empty()) {
       int32 src_composed_state = composed_state_queue_.top().second;
       composed_state_queue_.pop();
       ProcessQueueElement(src_composed_state);
     }
     if (composed_state_queue_.empty())
       break;
   }
 
   fst::Connect(clat_out_);
   TopSortCompactLatticeIfNeeded(clat_out_);
 
   if (GetVerboseLevel() >= 2) {
     int32 num_arcs_in = TotalNumArcs(clat_in_),
         orig_num_arcs_out = num_arcs_out_,
         num_arcs_out = TotalNumArcs(*clat_out_),
         num_states_in = clat_in_.NumStates(),
         orig_num_states_out = composed_state_info_.size(),
         num_states_out = clat_out_->NumStates();
     std::ostringstream os;
     os << "Input lattice had " << num_arcs_in << '/' << num_states_in
        << " arcs/states; output lattice has " << num_arcs_out << '/'
        << num_states_out;
     if (num_arcs_out != orig_num_arcs_out) {
       os << " (before pruning: " << orig_num_arcs_out << '/'
          << orig_num_states_out << ")";
     }
     if (!composed_state_queue_.empty()) {
       // Below, composed_state_queue_.top().first + lat_best_cost is an
       // expected-cost of the best path from the composed output that we *did
       // not* expand.  This, minus the best cost in the output compact lattice,
       // can be interpreted as the beam that we effecctively pruned the output
       // lattice to.
       BaseFloat effective_beam =
           composed_state_queue_.top().first + lat_best_cost_ - output_best_cost_;
       os << ". Effective beam was " << effective_beam;
     }
     KALDI_VLOG(2) << os.str();
   }
 
   if (clat_out_->NumStates() == 0) {
     KALDI_WARN << "Composed lattice has no states: something went wrong.";
   }
 }

◆ ComputeBackwardCosts()

void ComputeBackwardCosts ( const std::vector< int32 > & composed_states )

private

Definition at line 475 of file compose-lattice-pruned.cc.

References PrunedCompactLatticeComposer::LatticeStateInfo::backward_cost, PrunedCompactLatticeComposer::ComposedStateInfo::backward_cost, PrunedCompactLatticeComposer::clat_out_, PrunedCompactLatticeComposer::composed_state_info_, fst::ConvertToCost(), PrunedCompactLatticeComposer::current_cutoff_, PrunedCompactLatticeComposer::lat_best_cost_, ComposeLatticePrunedOptions::lattice_compose_beam, PrunedCompactLatticeComposer::opts_, and PrunedCompactLatticeComposer::output_best_cost_.

Referenced by PrunedCompactLatticeComposer::RecomputePruningInfo().

                                              {
   // Access the composed states in reverse topological order from latest to
   // earliest.
   std::vector<int32>::const_reverse_iterator iter = composed_states.rbegin(),
       end = composed_states.rend();
   for (; iter != end; ++iter) {
     int32 composed_state_index = *iter;
     ComposedStateInfo &info = composed_state_info_[composed_state_index];
     double backward_cost =
         ConvertToCost(clat_out_->Final(composed_state_index));
     fst::ArcIterator<CompactLattice> aiter(*clat_out_,
                                            composed_state_index);
     for (; !aiter.Done(); aiter.Next()) {
       const CompactLatticeArc &arc = aiter.Value();
       double arc_cost = ConvertToCost(arc.weight),
          next_backward_cost = composed_state_info_[arc.nextstate].backward_cost,
          this_backward_cost = arc_cost + next_backward_cost;
       if (this_backward_cost < backward_cost)
         backward_cost = this_backward_cost;
     }
     // It's OK if at this point, backward_cost is still +infinity.  This means
     // that this state cannot reach the end yet, which means we have not yet
     // expanded any path from this state all the way to a final-state of the
     // output.
     info.backward_cost = backward_cost;
   }
   output_best_cost_ = composed_state_info_[0].backward_cost;
   // See the declaration of current_cutoff_ for more information.  Note: on
   // early iterations, before any path reaches a final state of the composed
   // lattice, current_cutoff_ may be +infinity, and this is OK.
   current_cutoff_ =
       output_best_cost_ - lat_best_cost_ + opts_.lattice_compose_beam;
 }

◆ ComputeDeltaBackwardCosts()

void ComputeDeltaBackwardCosts ( const std::vector< int32 > & composed_states )

private

Definition at line 510 of file compose-lattice-pruned.cc.

Referenced by PrunedCompactLatticeComposer::RecomputePruningInfo().

                                              {
 
   int32 num_states = clat_out_->NumStates();
   for (int32 composed_state_index = 0; composed_state_index < num_states;
        ++composed_state_index) {
     ComposedStateInfo &info = composed_state_info_[composed_state_index];
     int32 lat_state = info.lat_state;
     // Note: delta_backward_cost will be +infinity at this stage if the
     // backward_cost was +infinity.  This is OK; we'll set them all to
     // finite values later in this function.
     info.delta_backward_cost =
         info.backward_cost - lat_state_info_[lat_state].backward_cost + info.depth * depth_penalty_;
   }
 
   // 'queue_elements' is a list of items (expected_cost_offset,
   // composed_state_index) that we are going to add to composed_state_queue_,
   // after clearing it.  It's more efficient to accumulate them as a vector
   // and add them all at once, than adding them one by one (search online for
   // "heapify" if this seems confusing).
   std::vector<std::pair<BaseFloat, int32> > queue_elements;
   queue_elements.reserve(num_states);
 
   double lat_best_cost = lat_best_cost_;
   BaseFloat current_cutoff = current_cutoff_;
   std::vector<int32>::const_iterator iter = composed_states.begin(),
       end = composed_states.end();
   for (; iter != end; ++iter) {
     int32 composed_state_index = *iter;
     ComposedStateInfo &info = composed_state_info_[composed_state_index];
     if (info.delta_backward_cost - info.delta_backward_cost != 0) {
       // if info.delta_backward_cost is +infinity...
       int32 prev_composed_state = info.prev_composed_state;
       if (prev_composed_state < 0) {
         KALDI_ASSERT(composed_state_index == 0);
         info.delta_backward_cost = 0.0;
       } else {
         const ComposedStateInfo &prev_info =
             composed_state_info_[prev_composed_state];
         // Check that prev_info.delta_backward_cost is finite.
         KALDI_ASSERT(prev_info.delta_backward_cost -
                      prev_info.delta_backward_cost == 0.0);
         info.delta_backward_cost = prev_info.delta_backward_cost + depth_penalty_;
       }
     }
     double lat_backward_cost = lat_state_info_[info.lat_state].backward_cost;
     // See the formula by where expected_cost_offset is declared in the
     // struct for explanation.
     BaseFloat expected_cost_offset =
         info.forward_cost + lat_backward_cost + info.delta_backward_cost +
         info.arc_delta_cost - lat_best_cost;
     // If info.expected_cost_offset were real, we'd set it here:
     //info.expected_cost_offset = expected_cost_offset;
 
     // At this point expected_cost_offset may be infinite, if arc_delta_cost was
     // infinite (reflecting that we processed all the arcs, and the final-state
     // if applicable, of the lattice state corresponding to this composed state.
     if (expected_cost_offset < current_cutoff) {
       queue_elements.push_back(std::pair<BaseFloat, int32>(
           expected_cost_offset, composed_state_index));
     }
   }
 
   // Reinitialize composed_state_queue_ from 'queue_elements'.
   QueueType temp_queue(queue_elements.begin(), queue_elements.end());
   composed_state_queue_.swap(temp_queue);
 }

◆ ComputeForwardCosts()

void ComputeForwardCosts ( const std::vector< int32 > & composed_states )

private

Definition at line 428 of file compose-lattice-pruned.cc.

References PrunedCompactLatticeComposer::clat_out_, PrunedCompactLatticeComposer::composed_state_info_, fst::ConvertToCost(), PrunedCompactLatticeComposer::ComposedStateInfo::depth, PrunedCompactLatticeComposer::ComposedStateInfo::forward_cost, KALDI_ASSERT, and PrunedCompactLatticeComposer::ComposedStateInfo::prev_composed_state.

Referenced by PrunedCompactLatticeComposer::RecomputePruningInfo().

                                              {
   KALDI_ASSERT(composed_states[0] == 0);
 
   // Note: when we initialized composed_state_info_[0]
   // we set forward_cost = 0.0, prev_composed_state = -1.
 
   std::vector<ComposedStateInfo>::iterator
       state_iter = composed_state_info_.begin(),
       state_end = composed_state_info_.end();
 
   state_iter->depth = 0;  // start state has depth 0
   ++state_iter;  // Skip over the start state.
   // Set all other forward_cost fields to infinity and prev_composed_state to
   // -1.
   for (; state_iter != state_end; ++state_iter) {
     state_iter->forward_cost = std::numeric_limits<double>::infinity();
     state_iter->prev_composed_state = -1;
   }
 
   std::vector<int32>::const_iterator state_index_iter = composed_states.begin(),
       state_index_end = composed_states.end();
   for (; state_index_iter != state_index_end; ++state_index_iter) {
     int32 composed_state_index = *state_index_iter;
     const ComposedStateInfo &info = composed_state_info_[
         composed_state_index];
     double forward_cost = info.forward_cost;
     // The next line is a check for infinity.  If infinities have appeared, it
     // either means there is a bug in the algorithm or there were infinities or
     // NaN's in the lattice.
     KALDI_ASSERT(forward_cost - forward_cost == 0.0);
     fst::ArcIterator<CompactLattice> aiter(*clat_out_,
                                            composed_state_index);
     for (; !aiter.Done(); aiter.Next()) {
       const CompactLatticeArc &arc = aiter.Value();
       double arc_cost = ConvertToCost(arc.weight),
           next_forward_cost = forward_cost + arc_cost;
       ComposedStateInfo &next_info = composed_state_info_[arc.nextstate];
       if (next_info.forward_cost > next_forward_cost) {
         next_info.forward_cost = next_forward_cost;
         next_info.prev_composed_state = composed_state_index;
         next_info.depth = composed_state_info_[composed_state_index].depth + 1;
       }
     }
   }
 }

◆ ComputeLatticeStateInfo()

void ComputeLatticeStateInfo ( )

private

Definition at line 578 of file compose-lattice-pruned.cc.

References PrunedCompactLatticeComposer::LatticeStateInfo::arc_delta_costs, PrunedCompactLatticeComposer::LatticeStateInfo::backward_cost, PrunedCompactLatticeComposer::clat_in_, fst::ConvertToCost(), KALDI_ASSERT, PrunedCompactLatticeComposer::lat_best_cost_, and PrunedCompactLatticeComposer::lat_state_info_.

Referenced by PrunedCompactLatticeComposer::Compose().

                                                            {
   KALDI_ASSERT(clat_in_.Properties(fst::kTopSorted, true) ==
                fst::kTopSorted && clat_in_.NumStates() > 0 &&
                clat_in_.Start()  == 0);
   int32 num_lat_states = clat_in_.NumStates();
   lat_state_info_.resize(num_lat_states);
 
   for (int32 s = num_lat_states - 1; s >= 0; s--) {
     LatticeStateInfo &info = lat_state_info_[s];
     std::vector<std::pair<double, int32> > arc_costs;
     double backward_cost = ConvertToCost(clat_in_.Final(s));
     if (backward_cost != std::numeric_limits<double>::infinity())
       arc_costs.push_back(std::pair<BaseFloat,int32>(backward_cost, -1));
     fst::ArcIterator<CompactLattice> aiter(clat_in_, s);
     int32 arc_index = 0;
     for (; !aiter.Done(); aiter.Next(), ++arc_index)  {
       const CompactLatticeArc &arc = aiter.Value();
       KALDI_ASSERT(arc.nextstate > s);
       backward_cost = lat_state_info_[arc.nextstate].backward_cost +
           ConvertToCost(arc.weight);
       KALDI_ASSERT(backward_cost - backward_cost == 0.0 &&
                    "Possibly not all states of input lattice are co-accessible?");
       arc_costs.push_back(std::pair<BaseFloat,int32>(backward_cost, arc_index));
     }
     std::sort(arc_costs.begin(), arc_costs.end());
     KALDI_ASSERT(!arc_costs.empty() &&
                  "Possibly not all states of input lattice are co-accessible?");
     backward_cost = arc_costs[0].first;
     info.backward_cost = backward_cost;  // this is the state's backward_cost,
                                          // reflecting the best path to the end.
     info.arc_delta_costs.resize(arc_costs.size());
     std::vector<std::pair<double, int32> >::const_iterator
         src_iter = arc_costs.begin(), src_end = arc_costs.end();
     std::vector<std::pair<BaseFloat, int32> >::iterator
         dest_iter = info.arc_delta_costs.begin();
     for (; src_iter != src_end; ++src_iter, ++dest_iter) {
       dest_iter->first = BaseFloat(src_iter->first - backward_cost);
       dest_iter->second = src_iter->second;
     }
   }
   lat_best_cost_ = lat_state_info_[0].backward_cost;
 }

◆ GetCurrentArcLimit()

int32 GetCurrentArcLimit ( ) const

private

Definition at line 399 of file compose-lattice-pruned.cc.

References ComposeLatticePrunedOptions::growth_ratio, ComposeLatticePrunedOptions::initial_num_arcs, KALDI_ASSERT, ComposeLatticePrunedOptions::max_arcs, PrunedCompactLatticeComposer::num_arcs_out_, PrunedCompactLatticeComposer::opts_, and PrunedCompactLatticeComposer::output_best_cost_.

Referenced by PrunedCompactLatticeComposer::Compose().

                                                              {
   int32 current_num_arcs = num_arcs_out_;
   if (current_num_arcs == 0) {
     return opts_.initial_num_arcs;
   } else {
     KALDI_ASSERT(opts_.growth_ratio > 1.0);
     int32 ans = static_cast<int32>(current_num_arcs *
                                    opts_.growth_ratio);
     if (ans == current_num_arcs)  // make sure the target increases.
       ans = current_num_arcs + 1;
     // if we have already reached a final state, then
     // apply the max_arcs limit.
     if (output_best_cost_ - output_best_cost_ == 0.0 &&
         ans > opts_.max_arcs)
       ans = opts_.max_arcs;
     return ans;
   }
 
 }

◆ GetTopsortedStateList()

void GetTopsortedStateList ( std::vector< int32 > * composed_states ) const

private

Definition at line 381 of file compose-lattice-pruned.cc.

References PrunedCompactLatticeComposer::accessed_lat_states_, PrunedCompactLatticeComposer::clat_out_, PrunedCompactLatticeComposer::LatticeStateInfo::composed_states, KALDI_ASSERT, and PrunedCompactLatticeComposer::lat_state_info_.

Referenced by PrunedCompactLatticeComposer::RecomputePruningInfo().

                                              {
   composed_states->clear();
   composed_states->reserve(clat_out_->NumStates());
   std::set<int32>::const_iterator iter = accessed_lat_states_.begin(),
       end = accessed_lat_states_.end();
   for (; iter != end; ++iter) {
     int32 lat_state = *iter;
     const LatticeStateInfo &input_lat_info = lat_state_info_[lat_state];
     composed_states->insert(composed_states->end(),
                             input_lat_info.composed_states.begin(),
                             input_lat_info.composed_states.end());
   }
   KALDI_ASSERT((*composed_states)[0] == 0 &&
                static_cast<int32>(composed_states->size()) ==
                clat_out_->NumStates());
 }

◆ ProcessQueueElement()

void ProcessQueueElement ( int32 composed_state_to_expand )

private

Definition at line 665 of file compose-lattice-pruned.cc.

Referenced by PrunedCompactLatticeComposer::Compose().

                               {
   KALDI_ASSERT(static_cast<size_t>(src_composed_state) <
                composed_state_info_.size());
 
   ComposedStateInfo &src_composed_state_info = composed_state_info_[
       src_composed_state];
   int32 lat_state = src_composed_state_info.lat_state;
   const LatticeStateInfo &lat_state_info =
       lat_state_info_[lat_state];
 
   int32 sorted_arc_index = src_composed_state_info.sorted_arc_index,
       num_sorted_arcs = lat_state_info.arc_delta_costs.size();
   // note: num_sorted_arcs will be the number of arcs from this
   // lattice state; plus one if there is a final-prob.
   KALDI_ASSERT(sorted_arc_index >= 0);
 
   { // this block update the state's 'sorted_arc_index', 'arc_delta_cost' and
     // 'expected_cost_offset' to reflect the fact that (by the time we exit from
     // this function) we will have processed this arc (or the final-prob);
     // it also re-inserts this state into the queue, if appropriate.
     BaseFloat expected_cost_offset;
     if (sorted_arc_index + 1 == num_sorted_arcs) {
       src_composed_state_info.sorted_arc_index = -1;
       src_composed_state_info.arc_delta_cost =
           std::numeric_limits<BaseFloat>::infinity();
       expected_cost_offset =
           std::numeric_limits<BaseFloat>::infinity();
     } else {
       src_composed_state_info.sorted_arc_index = sorted_arc_index + 1;
       src_composed_state_info.arc_delta_cost =
           lat_state_info.arc_delta_costs[sorted_arc_index+1].first;
       expected_cost_offset =
           (src_composed_state_info.forward_cost +
            lat_state_info.backward_cost +
            src_composed_state_info.delta_backward_cost +
            src_composed_state_info.arc_delta_cost - lat_best_cost_);
     }
     // We do '<' here rather than '<=', so that if current_cutoff_ is infinity
     // and expected_cost_offset is infinity (because we've exhausted all the
     // transitions from this state, and sorted_arc_index is now -1), we don't
     // add this element to the queue.
     if (expected_cost_offset < current_cutoff_) {
       // this state has another exit arc (or final prob) that is good
       // enough to re-enter into the queue.  Note: if we are processing
       // an arc out of this state and the destination state is new,
       // we may also add something new to the queue at that time.
 
       // the following call should be equivalent to
       // composed_state_queue_.push(std::pair<BaseFloat,int32>(...)) with
       // the same pair of args.
       composed_state_queue_.emplace(
           expected_cost_offset, src_composed_state);
     }
   }
 
   int32 arc_index = lat_state_info.arc_delta_costs[sorted_arc_index].second;
   if (arc_index < 0) {  // This (arc_index == -1) means it is not really an arc
                         // index; it's a final-prob.
     int32 lm_state = src_composed_state_info.lm_state;
     BaseFloat lm_final_cost = det_fst_->Final(lm_state).Value();
     if (lm_final_cost != std::numeric_limits<BaseFloat>::infinity()) {
       // If there is a final-prob on this LM state (note: there always will be
       // for conventional language models), then add the final-prob of this
       // state...
       CompactLattice::Weight final_weight = clat_in_.Final(lat_state);
       // assume 'final_weight' is not Zero(); otherwise the final-prob should
       // not have been present in 'arc_delta_costs'.
       Lattice::Weight final_lat_weight = final_weight.Weight();
       final_lat_weight.SetValue1(final_lat_weight.Value1() +
                                  lm_final_cost);
       final_weight.SetWeight(final_lat_weight);
       clat_out_->SetFinal(src_composed_state, final_weight);
       double final_cost = ConvertToCost(final_lat_weight);
       if (final_cost < src_composed_state_info.backward_cost)
         src_composed_state_info.backward_cost = final_cost;
       if (!output_reached_final_) {
         output_reached_final_ = true;
         depth_penalty_ = 0.0;
         RecomputePruningInfo();
       }
     }
   } else {
     // It really was an arc.  This code is very complicated, so we make it its
     // own function.
     ProcessTransition(src_composed_state, arc_index);
   }
 }

◆ ProcessTransition()

void ProcessTransition	(	int32	composed_src_state,
		int32	arc_index
	)

private

Definition at line 754 of file compose-lattice-pruned.cc.

Referenced by PrunedCompactLatticeComposer::ProcessQueueElement().

                                                                       {
   // Make src_composed_state a const pointer not a reference, as we may have to
   // modify the pointer if composed_state_info_ is resized.
   const ComposedStateInfo *src_info = &(composed_state_info_[
       src_composed_state]);
   int32 src_lat_state = src_info->lat_state;
   // Get the arc we are going to expand.
   fst::ArcIterator<CompactLattice> aiter(clat_in_, src_lat_state);
   aiter.Seek(arc_index);
   const CompactLatticeArc &lat_arc = aiter.Value();
   // Note: this code is for CompactLatticeArc, in which the ilabel and olabel
   // are the same, but we're writing it in such a way that it will naturally
   // generalize to LatticeArc, so there are separate variables for the ilabel
   // and the olabel.
   int32 dest_lat_state = lat_arc.nextstate,
       ilabel = lat_arc.ilabel,
       olabel = lat_arc.olabel;
   // Note: we expect that ilabel == olabel, since this is a CompactLattice, but this
   // may not be so if we extend this to work with Lattice.
   fst::StdArc lm_arc;
 
   // the input lattice might have epsilons
   if (olabel == 0) {
     lm_arc.ilabel = 0;
     lm_arc.olabel = 0;
     lm_arc.nextstate = src_info->lm_state;
     lm_arc.weight = fst::StdArc::Weight(0.0);
   } else if (!det_fst_->GetArc(src_info->lm_state, olabel, &lm_arc)) {
     // for normal language models we don't expect this to happen, but the
     // appropriate behavior is to do nothing; the composed arc does not exist,
     // so there is no arc to add and no new state to create.
     return;
   }
   int32 dest_lm_state = lm_arc.nextstate;
   // The following assertion is necessary because CompactLattice cannot support
   // different ilabel vs. olabel; and also it's an expectation about
   // language-models.
   KALDI_ASSERT(lm_arc.ilabel == lm_arc.olabel);
 
   LatticeStateInfo &dest_lat_state_info =
       lat_state_info_[dest_lat_state];
 
   int32 dest_composed_state;
   ComposedStateInfo *dest_info;
 
   { // The next block works out 'dest_composed_state' and
     // 'dest_info', and if the destination state did not already
     // exist, creates a new composed state.
     typedef std::unordered_map<std::pair<int32,int32>, int32,
         PairHasher<int32> > MapType;
     int32 new_composed_state = clat_out_->NumStates();
     std::pair<const std::pair<int32,int32>, int32> value(
         std::pair<int32,int32>(dest_lat_state, dest_lm_state), new_composed_state);
     std::pair<MapType::iterator, bool> ret =
         pair_to_state_.insert(value);
     if (ret.second) {
       // Successfully inserted: this dest-state did not already exist.  Most of
       // the rest of this block deals with the consequences of adding a new
       // state.
       int32 ans = clat_out_->AddState();
       KALDI_ASSERT(ans == new_composed_state);
       dest_composed_state = new_composed_state;
       composed_state_info_.resize(dest_composed_state + 1);
       dest_info = &(composed_state_info_[dest_composed_state]);
       // Re-assign src_composed_state as the vector might have been reallocated.
       src_info = &(composed_state_info_[src_composed_state]);
       if (dest_lat_state_info.composed_states.empty())
         accessed_lat_states_.insert(dest_lat_state);
       dest_lat_state_info.composed_states.push_back(new_composed_state);
       dest_info->lat_state = dest_lat_state;
       dest_info->lm_state = dest_lm_state;
       dest_info->depth = src_info->depth + 1;
       dest_info->forward_cost =
           src_info->forward_cost +
           ConvertToCost(lat_arc.weight) + lm_arc.weight.Value();
       dest_info->backward_cost =
           std::numeric_limits<double>::infinity();
       dest_info->delta_backward_cost =
           src_info->delta_backward_cost + dest_info->depth * depth_penalty_;
       // The 'prev_composed_state' field will not be read again until after it's
       // overwritten; we set it as below only for debugging purposes (the
       // negation is also for debugging purposes).
       dest_info->prev_composed_state = -src_composed_state;
       dest_info->sorted_arc_index = 0;
       dest_info->arc_delta_cost = 0.0;
       // Note: in the expression below, which can be understood with reference
       // to the comment by the declaration of the phantom variable
       // 'expected_cost_offset', 'arc_delta_cost' is known to equal 0.0 so it
       // has been removed.
       BaseFloat expected_cost_offset =
           (dest_info->forward_cost +
            dest_lat_state_info.backward_cost +
            dest_info->delta_backward_cost -
            lat_best_cost_);
       if (expected_cost_offset < current_cutoff_) {
         // the following call should be equivalent to
         // composed_state_queue_.push(std::pair<BaseFloat,int32>(...)) with
         // the same pair of args.
         composed_state_queue_.emplace(expected_cost_offset,
                                       dest_composed_state);
       }
     } else { // the destination composed state already existed.
       dest_composed_state = ret.first->second;
       dest_info = &(composed_state_info_[dest_composed_state]);
     }
   }
   // Add the arc from the src to dest state in the composed output.
   CompactLatticeArc new_arc;
   new_arc.nextstate = dest_composed_state;
   // Actually the ilabel and olabel are the same, but writing it this way will
   // generalize better to type Lattice if we need that later.
   new_arc.ilabel = ilabel;
   new_arc.olabel = olabel;
   new_arc.weight = lat_arc.weight;
   // 'weight' is the weight part, as opposed to the string part.
   LatticeArc::Weight weight = new_arc.weight.Weight();
   // include the LM-arc's weight in the weight of the new arc.
   weight.SetValue1(fst::Times(weight.Value1(), lm_arc.weight).Value());
   new_arc.weight.SetWeight(weight);
   clat_out_->AddArc(src_composed_state, new_arc);
   num_arcs_out_++;
 }

◆ RecomputePruningInfo()

void RecomputePruningInfo ( )

private

Definition at line 420 of file compose-lattice-pruned.cc.

References PrunedCompactLatticeComposer::ComputeBackwardCosts(), PrunedCompactLatticeComposer::ComputeDeltaBackwardCosts(), PrunedCompactLatticeComposer::ComputeForwardCosts(), and PrunedCompactLatticeComposer::GetTopsortedStateList().

Referenced by PrunedCompactLatticeComposer::Compose(), and PrunedCompactLatticeComposer::ProcessQueueElement().

                                                         {
   std::vector<int32> all_composed_states;
   GetTopsortedStateList(&all_composed_states);
   ComputeForwardCosts(all_composed_states);
   ComputeBackwardCosts(all_composed_states);
   ComputeDeltaBackwardCosts(all_composed_states);
 }