LatticeIncrementalDeterminizer Class Reference

This class is used inside LatticeIncrementalDecoderTpl; it handles some of the details of incremental determinization. More...

#include <lattice-incremental-decoder.h>

Collaboration diagram for LatticeIncrementalDeterminizer:

Public Types
enum	{ kStateLabelOffset = (int)1e8, kTokenLabelOffset = (int)2e8, kMaxTokenLabel = (int)3e8 }
using	Label = typename LatticeArc::Label

Public Member Functions
	LatticeIncrementalDeterminizer (const TransitionModel &trans_model, const LatticeIncrementalDecoderConfig &config)
void	Init ()
const CompactLattice &	GetDeterminizedLattice () const
void	InitializeRawLatticeChunk (Lattice *olat, unordered_map< Label, LatticeArc::StateId > *token_label2state)
	Starts the process of creating a raw lattice chunk. More...
bool	AcceptRawLatticeChunk (Lattice *raw_fst)
	This function accepts the raw FST (state-level lattice) corresponding to a single chunk of the lattice, determinizes it and appends it to this->clat_. More...
void	SetFinalCosts (const unordered_map< Label, BaseFloat > *token_label2final_cost=NULL)
const CompactLattice &	GetLattice ()

Private Member Functions
void	GetRawLatticeFinalCosts (const Lattice &raw_fst, std::unordered_map< Label, BaseFloat > *old_final_costs)
void	GetNonFinalRedetStates ()
bool	ProcessArcsFromChunkStartState (const CompactLattice &chunk_clat, std::unordered_map< CompactLattice::StateId, CompactLattice::StateId > *state_map)
	[called from AcceptRawLatticeChunk()] Processes arcs that leave the start-state of `chunk_clat` (if this is not the first chunk); does nothing if this is the first chunk. More...
void	TransferArcsToClat (const CompactLattice &chunk_clat, bool is_first_chunk, const std::unordered_map< CompactLattice::StateId, CompactLattice::StateId > &state_map, const std::unordered_map< CompactLattice::StateId, Label > &chunk_state_to_token, const std::unordered_map< Label, BaseFloat > &old_final_costs)
	This function, called from AcceptRawLatticeChunk(), transfers arcs from `chunk_clat` to clat_. More...
void	AddArcToClat (CompactLattice::StateId state, const CompactLatticeArc &arc)
	Adds one arc to `clat_`. More...
CompactLattice::StateId	AddStateToClat ()
void	IdentifyTokenFinalStates (const CompactLattice &chunk_clat, std::unordered_map< CompactLattice::StateId, CompactLatticeArc::Label > *token_map) const
	KALDI_DISALLOW_COPY_AND_ASSIGN (LatticeIncrementalDeterminizer)

Private Attributes
const TransitionModel &	trans_model_
const LatticeIncrementalDecoderConfig &	config_
std::unordered_set< CompactLattice::StateId >	non_final_redet_states_
CompactLattice	clat_
std::vector< std::vector< std::pair< CompactLattice::StateId, int32 > > >	arcs_in_
std::vector< CompactLatticeArc >	final_arcs_
std::vector< BaseFloat >	forward_costs_
std::unordered_set< int32 >	temp_

Detailed Description

This class is used inside LatticeIncrementalDecoderTpl; it handles some of the details of incremental determinization.

https://www.danielpovey.com/files/ *TBD*.pdf for the paper.

Definition at line 196 of file lattice-incremental-decoder.h.

Member Typedef Documentation

Label

using Label = typename LatticeArc::Label

Definition at line 198 of file lattice-incremental-decoder.h.

Member Enumeration Documentation

anonymous enum

anonymous enum

Enumerator
kStateLabelOffset
kTokenLabelOffset
kMaxTokenLabel

Definition at line 290 of file lattice-incremental-decoder.h.

{ kStateLabelOffset = (int)1e8,  kTokenLabelOffset = (int)2e8, kMaxTokenLabel = (int)3e8 };

Constructor & Destructor Documentation

LatticeIncrementalDeterminizer()

LatticeIncrementalDeterminizer ( const TransitionModel &  trans_model, const LatticeIncrementalDecoderConfig &  config  )

inline

Definition at line 203 of file lattice-incremental-decoder.h.

                                                    :
      trans_model_(trans_model), config_(config) { }

Member Function Documentation

AcceptRawLatticeChunk()

bool AcceptRawLatticeChunk

(

Lattice *

raw_fst

)

This function accepts the raw FST (state-level lattice) corresponding to a single chunk of the lattice, determinizes it and appends it to this->clat_.

Unless this was the

Note: final-probs in `raw_fst` are treated specially: they are used to guide the pruned determinization, but when you call GetLattice() it will be – except for pruning effects– as if all nonzero final-probs in `raw_fst` were: One() if final_costs == NULL; else the value present in `final_costs`.

Parameters

[in]

raw_fst

(Consumed destructively). The input raw (state-level) lattice. Would correspond to the FST A in the paper if first_frame == 0, and B otherwise.

Returns

returns false if determinization finished earlier than the beam or the determinized lattice was empty; true otherwise.

NOTE: if this is not the final chunk, you will probably want to call SetFinalCosts() directly after calling this.

Definition at line 1547 of file lattice-incremental-decoder.cc.

References fst::DeterminizeLatticePhonePrunedWrapper(), KALDI_ASSERT, KALDI_WARN, and kaldi::TopSortCompactLatticeIfNeeded().

                      {
  using Label = CompactLatticeArc::Label;
  using StateId = CompactLattice::StateId;

  // old_final_costs is a map from a `token-label` (see glossary) to the
  // associated final-prob in a final-state of `raw_fst`, that is associated
  // with that Token.  These are Tokens that were active at the end of the
  // chunk.  The final-probs may arise from beta (backward) costs, introduced
  // for pruning purposes, and/or from final-probs in HCLG.  Those costs will
  // not be included in anything we store permamently in this class; they used
  // only to guide pruned determinization, and we will use `old_final_costs`
  // later to cancel them out.
  std::unordered_map<Label, BaseFloat> old_final_costs;
  GetRawLatticeFinalCosts(*raw_fst, &old_final_costs);

  CompactLattice chunk_clat;
  bool determinized_till_beam = DeterminizeLatticePhonePrunedWrapper(
      trans_model_, raw_fst, config_.lattice_beam, &chunk_clat,
      config_.det_opts);

  TopSortCompactLatticeIfNeeded(&chunk_clat);

  std::unordered_map<StateId, Label> chunk_state_to_token;
  IdentifyTokenFinalStates(chunk_clat,
                           &chunk_state_to_token);

  StateId chunk_num_states = chunk_clat.NumStates();
  if (chunk_num_states == 0) {
    // This will be an error but user-level calling code can detect it from the
    // lattice being empty.
    KALDI_WARN << "Empty lattice, something went wrong.";
    clat_.DeleteStates();
    return false;
  }

  StateId start_state = chunk_clat.Start();  // would be 0.
  KALDI_ASSERT(start_state == 0);

  // Process arcs leaving the start state of chunk_clat. Unless this is the
  // first chunk in the lattice, all arcs leaving the start state of chunk_clat
  // will have `state labels` on them (identifying redeterminized-states in
  // clat_), and will transition to a state in `chunk_clat` that we can identify
  // with that redeterminized-state.

  // state_map maps from (non-initial, non-token-final state s in chunk_clat) to
  // a state in clat_.
  std::unordered_map<StateId, StateId> state_map;


  bool is_first_chunk = ProcessArcsFromChunkStartState(chunk_clat, &state_map);

  // Remove any existing arcs in clat_ that leave redeterminized-states, and
  // make those states non-final.  Below, we'll add arcs leaving those states
  // (and possibly new final-probs.)
  for (StateId clat_state: non_final_redet_states_) {
    clat_.DeleteArcs(clat_state);
    clat_.SetFinal(clat_state, CompactLatticeWeight::Zero());
  }

  // The previous final-arc info is no longer relevant; we'll recreate it below.
  final_arcs_.clear();

  // assume chunk_lat.Start() == 0; we asserted it above.  Allocate state-ids
  // for all remaining states in chunk_clat, except for token-final states.
  for (StateId state = (is_first_chunk ? 0 : 1);
       state < chunk_num_states; state++) {
    if (chunk_state_to_token.count(state) != 0)
      continue;  // these `token-final` states don't get a state allocated.

    StateId new_clat_state = clat_.NumStates();
    if (state_map.insert({state, new_clat_state}).second) {
      // If it was inserted then we need to actually allocate that state
      StateId s = AddStateToClat();
      KALDI_ASSERT(s == new_clat_state);
    }   // else do nothing; it would have been a redeterminized-state and no
  }     // allocation is needed since they already exist in clat_. and
        // in state_map.

  if (is_first_chunk) {
    auto iter = state_map.find(start_state);
    KALDI_ASSERT(iter != state_map.end());
    CompactLattice::StateId clat_start_state = iter->second;
    KALDI_ASSERT(clat_start_state == 0);  // topological order.
    clat_.SetStart(clat_start_state);
    forward_costs_[clat_start_state] = 0.0;
  }

  TransferArcsToClat(chunk_clat, is_first_chunk,
                     state_map, chunk_state_to_token, old_final_costs);

  GetNonFinalRedetStates();

  return determinized_till_beam;
}

AddArcToClat()

void AddArcToClat ( CompactLattice::StateId  state, const CompactLatticeArc &  arc  )

private

Adds one arc to `clat_`.

It's like clat_.AddArc(state, arc), except it also modifies arcs_in_ and forward_costs_.

Definition at line 1150 of file lattice-incremental-decoder.cc.

References fst::ConvertToCost().

                                  {
  BaseFloat forward_cost = forward_costs_[state] +
      ConvertToCost(arc.weight);
  if (forward_cost == std::numeric_limits<BaseFloat>::infinity())
    return;
  int32 arc_idx = clat_.NumArcs(state);
  clat_.AddArc(state, arc);
  arcs_in_[arc.nextstate].push_back({state, arc_idx});
  if (forward_cost < forward_costs_[arc.nextstate])
    forward_costs_[arc.nextstate] = forward_cost;
}

AddStateToClat()

CompactLattice::StateId AddStateToClat ( )

private

Definition at line 1142 of file lattice-incremental-decoder.cc.

References KALDI_ASSERT.

                                                                     {
  CompactLattice::StateId ans = clat_.AddState();
  forward_costs_.push_back(std::numeric_limits<BaseFloat>::infinity());
  KALDI_ASSERT(forward_costs_.size() == ans + 1);
  arcs_in_.resize(ans + 1);
  return ans;
}

GetDeterminizedLattice()

const CompactLattice& GetDeterminizedLattice ( ) const

inline

Definition at line 212 of file lattice-incremental-decoder.h.

{ return clat_; }

GetLattice()

const CompactLattice& GetLattice ( )

inline

Definition at line 284 of file lattice-incremental-decoder.h.

{ return clat_; }

GetNonFinalRedetStates()

void GetNonFinalRedetStates ( )

private

Definition at line 1190 of file lattice-incremental-decoder.cc.

                                                            {
  using StateId = CompactLattice::StateId;
  non_final_redet_states_.clear();
  non_final_redet_states_.reserve(final_arcs_.size());

  std::vector<StateId> state_queue;
  for (const CompactLatticeArc &arc: final_arcs_) {
    // Note: we abuse the .nextstate field to store the state which is really
    // the source of that arc.
    StateId redet_state = arc.nextstate;
    if (forward_costs_[redet_state] != std::numeric_limits<BaseFloat>::infinity()) {
      // if it is accessible..
      if (non_final_redet_states_.insert(redet_state).second) {
        // it was not already there
        state_queue.push_back(redet_state);
      }
    }
  }
  // Add any states that are reachable from the states above.
  while (!state_queue.empty()) {
    StateId s = state_queue.back();
    state_queue.pop_back();
    for (fst::ArcIterator<CompactLattice> aiter(clat_, s); !aiter.Done();
         aiter.Next()) {
      const CompactLatticeArc &arc = aiter.Value();
      StateId nextstate = arc.nextstate;
      if (non_final_redet_states_.insert(nextstate).second)
        state_queue.push_back(nextstate); // it was not already there
    }
  }
}

GetRawLatticeFinalCosts()

void GetRawLatticeFinalCosts ( const Lattice &  raw_fst, std::unordered_map< Label, BaseFloat > *  old_final_costs  )

private

Definition at line 1329 of file lattice-incremental-decoder.cc.

References KALDI_ERR, LatticeWeightTpl< FloatType >::Value1(), and LatticeWeightTpl< FloatType >::Value2().

                                                         {
  LatticeArc::StateId raw_fst_num_states = raw_fst.NumStates();
  for (LatticeArc::StateId s = 0; s < raw_fst_num_states; s++) {
    for (fst::ArcIterator<Lattice> aiter(raw_fst, s); !aiter.Done();
         aiter.Next()) {
      const LatticeArc &value = aiter.Value();
      if (value.olabel >= (Label)kTokenLabelOffset &&
          value.olabel < (Label)kMaxTokenLabel) {
        LatticeWeight final_weight = raw_fst.Final(value.nextstate);
        if (final_weight != LatticeWeight::Zero() &&
            final_weight.Value2() != 0) {
          KALDI_ERR << "Label " << value.olabel << " from state " << s
                    << " looks like a token-label but its next-state "
                    << value.nextstate <<
              " has unexpected final-weight " << final_weight.Value1() << ','
                    << final_weight.Value2();
        }
        auto r = old_final_costs->insert({value.olabel,
                final_weight.Value1()});
        if (!r.second && r.first->second != final_weight.Value1()) {
          // For any given token-label, all arcs in raw_fst with that
          // olabel should go to the same state, so this should be
          // impossible.
          KALDI_ERR << "Unexpected mismatch in final-costs for tokens, "
                    << r.first->second << " vs " << final_weight.Value1();
        }
      }
    }
  }
}

IdentifyTokenFinalStates()

void IdentifyTokenFinalStates ( const CompactLattice &  chunk_clat, std::unordered_map< CompactLattice::StateId, CompactLatticeArc::Label > *  token_map  ) const

private

Definition at line 1165 of file lattice-incremental-decoder.cc.

References KALDI_ASSERT.

                                                                                      {
  token_map->clear();
  using StateId = CompactLattice::StateId;
  using Label = CompactLatticeArc::Label;

  StateId num_states = chunk_clat.NumStates();
  for (StateId state = 0; state < num_states; state++) {
    for (fst::ArcIterator<CompactLattice> aiter(chunk_clat, state);
       !aiter.Done(); aiter.Next()) {
      const CompactLatticeArc &arc = aiter.Value();
      if (arc.olabel >= kTokenLabelOffset && arc.olabel < kMaxTokenLabel) {
        StateId nextstate = arc.nextstate;
        auto r = token_map->insert({nextstate, arc.olabel});
        // Check consistency of labels on incoming arcs
        KALDI_ASSERT(r.first->second == arc.olabel);
      }
    }
  }
}

Init()

void Init

(

)

Definition at line 1134 of file lattice-incremental-decoder.cc.

                                          {
  non_final_redet_states_.clear();
  clat_.DeleteStates();
  final_arcs_.clear();
  forward_costs_.clear();
  arcs_in_.clear();
}

InitializeRawLatticeChunk()

void InitializeRawLatticeChunk	(	Lattice *	olat,
		unordered_map< Label, LatticeArc::StateId > *	token_label2state
	)

Starts the process of creating a raw lattice chunk.

(Search the glossary for "raw lattice chunk"). This just sets up the initial states and redeterminized-states in the chunk. Relates to sec. 5.2 in the paper, specifically the initial-state i and the redeterminized-states.

After calling this, the caller would add the remaining arcs and states to `olat` and then call AcceptRawLatticeChunk() with the result.

Parameters

[out]	olat	The lattice to be (partially) created
[out]	token_label2state	This function outputs to here a map from `token-label` to the state we created for it in *olat. See glossary for `token-label`. The keys actually correspond to the .nextstate fields in the arcs in final_arcs_; values are states in `olat`. See the last bullet point before Sec. 5.3 in the paper.

Definition at line 1223 of file lattice-incremental-decoder.cc.

References kaldi::AddCompactLatticeArcToLattice(), and KALDI_ASSERT.

                                                                {
  using namespace fst;

  olat->DeleteStates();
  LatticeArc::StateId start_state = olat->AddState();
  olat->SetStart(start_state);
  token_label2state->clear();

  // redet_state_map maps from state-ids in clat_ to state-ids in olat.  This
  // will be the set of states from which the arcs to final-states in the
  // canonical appended lattice leave (physically, these are in the .nextstate
  // elements of arcs_, since we use that field for the source state), plus any
  // states reachable from those states.
  unordered_map<CompactLattice::StateId, LatticeArc::StateId> redet_state_map;

  for (CompactLattice::StateId redet_state: non_final_redet_states_)
    redet_state_map[redet_state] = olat->AddState();

  // First, process any arcs leaving the non-final redeterminized states that
  // are not to final-states.  (What we mean by "not to final states" is, not to
  // stats that are final in the `canonical appended lattice`.. they may
  // actually be physically final in clat_, because we make clat_ what we want
  // to return to the user.
  for (CompactLattice::StateId redet_state: non_final_redet_states_) {
    LatticeArc::StateId lat_state = redet_state_map[redet_state];

    for (ArcIterator<CompactLattice> aiter(clat_, redet_state);
         !aiter.Done(); aiter.Next()) {
      const CompactLatticeArc &arc = aiter.Value();
      CompactLattice::StateId nextstate = arc.nextstate;
      LatticeArc::StateId lat_nextstate = olat->NumStates();
      auto r = redet_state_map.insert({nextstate, lat_nextstate});
      if (r.second) {  // Was inserted.
        LatticeArc::StateId s = olat->AddState();
        KALDI_ASSERT(s == lat_nextstate);
      } else {
        // was not inserted -> was already there.
        lat_nextstate = r.first->second;
      }
      CompactLatticeArc clat_arc(arc);
      clat_arc.nextstate = lat_nextstate;
      AddCompactLatticeArcToLattice(clat_arc, lat_state, olat);
    }
    clat_.DeleteArcs(redet_state);
    clat_.SetFinal(redet_state, CompactLatticeWeight::Zero());
  }

  for (const CompactLatticeArc &arc: final_arcs_) {
    // We abuse the `nextstate` field to store the source state.
    CompactLattice::StateId src_state = arc.nextstate;
    auto iter = redet_state_map.find(src_state);
    if (forward_costs_[src_state] == std::numeric_limits<BaseFloat>::infinity())
      continue;  /* Unreachable state */
    KALDI_ASSERT(iter != redet_state_map.end());
    LatticeArc::StateId src_lat_state = iter->second;
    Label token_label = arc.ilabel;  // will be == arc.olabel.
    KALDI_ASSERT(token_label >= kTokenLabelOffset &&
                 token_label < kMaxTokenLabel);
    auto r = token_label2state->insert({token_label,
            olat->NumStates()});
    LatticeArc::StateId dest_lat_state = r.first->second;
    if (r.second) { // was inserted
      LatticeArc::StateId new_state = olat->AddState();
      KALDI_ASSERT(new_state == dest_lat_state);
    }
    CompactLatticeArc new_arc;
    new_arc.nextstate = dest_lat_state;
    /*  We convert the token-label to epsilon; it's not needed anymore. */
    new_arc.ilabel = new_arc.olabel = 0;
    new_arc.weight = arc.weight;
    AddCompactLatticeArcToLattice(new_arc, src_lat_state, olat);
  }

  // Now deal with the initial-probs.  Arcs from initial-states to
  // redeterminized-states in the raw lattice have an olabel that identifies the
  // id of that redeterminized-state in clat_, and a cost that is derived from
  // its entry in forward_costs_.  These forward-probs are used to get the
  // pruned lattice determinization to behave correctly, and will be canceled
  // out later on.
  //
  // In the paper this is the second-from-last bullet in Sec. 5.2.  NOTE: in the
  // paper we state that we only include such arcs for "each redeterminized
  // state that is either initial in det(A) or that has an arc entering it from
  // a state that is not a redeterminized state."  In fact, we include these
  // arcs for all redeterminized states.  I realized that it won't make a
  // difference to the outcome, and it's easier to do it this way.
  for (CompactLattice::StateId state_id: non_final_redet_states_) {
    BaseFloat forward_cost = forward_costs_[state_id];
    LatticeArc arc;
    arc.ilabel = 0;
    // The olabel (which appears where the word-id would) is what
    // we call a 'state-label'.  It identifies a state in clat_.
    arc.olabel = state_id + kStateLabelOffset;
    // It doesn't matter what field we put forward_cost in (or whether we
    // divide it among them both; the effect on pruning is the same, and
    // we will cancel it out later anyway.
    arc.weight = LatticeWeight(forward_cost, 0);
    auto iter = redet_state_map.find(state_id);
    KALDI_ASSERT(iter != redet_state_map.end());
    arc.nextstate = iter->second;
    olat->AddArc(start_state, arc);
  }
}

KALDI_DISALLOW_COPY_AND_ASSIGN()

KALDI_DISALLOW_COPY_AND_ASSIGN ( LatticeIncrementalDeterminizer  )

private

ProcessArcsFromChunkStartState()

bool ProcessArcsFromChunkStartState ( const CompactLattice &  chunk_clat, std::unordered_map< CompactLattice::StateId, CompactLattice::StateId > *  state_map  )

private

[called from AcceptRawLatticeChunk()] Processes arcs that leave the start-state of `chunk_clat` (if this is not the first chunk); does nothing if this is the first chunk.

This includes using the `state-labels` to work out which states in clat_ these states correspond to, and writing that mapping to `state_map`.

Also modifies forward_costs_, because it has to do a kind of reweighting of the clat states that are the values it puts in `state_map`, to take account of the probabilities on the arcs from the start state of chunk_clat to the states corresponding to those redeterminized-states (i.e. the states in clat corresponding to the values it puts in `*state_map`). It also modifies arcs_in_, mostly because there are rare cases when we end up `merging` sets of those redeterminized-states, because the determinization process mapped them to a single state, and that means we need to reroute the arcs into members of that set into one single member (which will appear as a value in `*state_map`).

Parameters

[in]	chunk_clat	The determinized chunk of lattice we are processing
[out]	state_map	Mapping from states in chunk_clat to the state in clat_ they correspond to.

Returns

Returns true if this is the first chunk.

Definition at line 1363 of file lattice-incremental-decoder.cc.

References fst::ConvertToCost(), KALDI_ASSERT, CompactLatticeWeightTpl< WeightType, IntType >::SetWeight(), fst::Times(), and CompactLatticeWeightTpl< WeightType, IntType >::Weight().

                                                                               {
  using StateId = CompactLattice::StateId;
  StateId clat_num_states = clat_.NumStates();

  // Process arcs leaving the start state of chunk_clat.  These arcs will have
  // state-labels on them (unless this is the first chunk).
  // For destination-states of those arcs, work out which states in
  // clat_ they correspond to and update their forward_costs.
  for (fst::ArcIterator<CompactLattice> aiter(chunk_clat, chunk_clat.Start());
       !aiter.Done(); aiter.Next()) {
    const CompactLatticeArc &arc = aiter.Value();
    Label label = arc.ilabel;  // ilabel == olabel; would be the olabel
                               // in a Lattice.
    if (!(label >= kStateLabelOffset &&
          label - kStateLabelOffset < clat_num_states)) {
      // The label was not a state-label.  This should only be possible on the
      // first chunk.
      KALDI_ASSERT(state_map->empty());
      return true;  // this is the first chunk.
    }
    StateId clat_state = label - kStateLabelOffset;
    StateId chunk_state = arc.nextstate;
    auto p = state_map->insert({chunk_state, clat_state});
    StateId dest_clat_state = p.first->second;
    // We deleted all its arcs in InitializeRawLatticeChunk
    KALDI_ASSERT(clat_.NumArcs(clat_state) == 0);
    /*
      In almost all cases, dest_clat_state and clat_state will be the same state;
      but there may be situations where two arcs with different state-labels
      left the start state and entered the same next-state in chunk_clat; and in
      these cases, they will be different.

      We didn't address this issue in the paper (or actually realize it could be
      a problem).  What we do is pick one of the clat_states as the "canonical"
      one, and redirect all incoming transitions of the others to enter the
      "canonical" one.  (Search below for new_in_arc.nextstate =
      dest_clat_state).
     */
    if (clat_state != dest_clat_state) {
      // Check that the start state isn't getting merged with any other state.
      // If this were possible, we'd need to deal with it specially, but it
      // can't be, because to be merged, 2 states must have identical arcs
      // leaving them with identical weights, so we'd need to have another state
      // on frame 0 identical to the start state, which is not possible if the
      // lattice is deterministic and epsilon-free.
      KALDI_ASSERT(clat_state != 0 && dest_clat_state != 0);
    }

    // in_weight is an extra weight that we'll include on arcs entering this
    // state from the previous chunk.  We need to cancel out
    // `forward_costs[clat_state]`, which was included in the corresponding arc
    // in the raw lattice for pruning purposes; and we need to include the
    // weight on the arc from the start-state of `chunk_clat` to this state.
    CompactLatticeWeight extra_weight_in = arc.weight;
    extra_weight_in.SetWeight(
        fst::Times(extra_weight_in.Weight(),
                   LatticeWeight(-forward_costs_[clat_state], 0.0)));

    // We don't allow state 0 to be a redeterminized-state; calling code assures
    // this.  Search for `determinizer_.GetLattice().Final(0) !=
    // CompactLatticeWeight::Zero())` to find that calling code.
    KALDI_ASSERT(clat_state != 0);

    // Note: 0 is the start state of clat_.  This was checked.
    forward_costs_[clat_state] = (clat_state == 0 ? 0 :
                                  std::numeric_limits<BaseFloat>::infinity());
    std::vector<std::pair<StateId, int32> > arcs_in;
    arcs_in.swap(arcs_in_[clat_state]);
    for (auto p: arcs_in) {
      // Note: we'll be doing `continue` below if this input arc came from
      // another redeterminized-state, because we did DeleteArcs() for them in
      // InitializeRawLatticeChunk().  Those arcs will be transferred
      // from chunk_clat later on.
      CompactLattice::StateId src_state = p.first;
      int32 arc_pos = p.second;

      if (arc_pos >= (int32)clat_.NumArcs(src_state))
        continue;
      fst::MutableArcIterator<CompactLattice> aiter(&clat_, src_state);
      aiter.Seek(arc_pos);
      if (aiter.Value().nextstate != clat_state)
        continue;  // This arc record has become invalidated.
      CompactLatticeArc new_in_arc(aiter.Value());
      // In most cases we will have dest_clat_state == clat_state, so the next
      // line won't change the value of .nextstate
      new_in_arc.nextstate = dest_clat_state;
      new_in_arc.weight = fst::Times(new_in_arc.weight, extra_weight_in);
      aiter.SetValue(new_in_arc);

      BaseFloat new_forward_cost = forward_costs_[src_state] +
          ConvertToCost(new_in_arc.weight);
      if (new_forward_cost < forward_costs_[dest_clat_state])
        forward_costs_[dest_clat_state] = new_forward_cost;
      arcs_in_[dest_clat_state].push_back(p);
    }
  }
  return false;  // this is not the first chunk.
}

SetFinalCosts()

void SetFinalCosts

(

const unordered_map< Label, BaseFloat > *

token_label2final_cost = NULL

)

Definition at line 1645 of file lattice-incremental-decoder.cc.

References KALDI_WARN, fst::Plus(), and fst::Times().

                                                                   {
  if (final_arcs_.empty()) {
    KALDI_WARN << "SetFinalCosts() called when final_arcs_.empty()... possibly "
        "means you are calling this after Finalize()?  Not allowed: could "
        "indicate a code error.  Or possibly decoding failed somehow.";
  }

  /*
    prefinal states a terminology that does not appear in the paper.  What it
    means is: the set of states that have an arc with a Token-label as the label
    leaving them in the canonical appended lattice.
  */
  std::unordered_set<int32> &prefinal_states(temp_);
  prefinal_states.clear();
  for (const auto &arc: final_arcs_) {
    /* Caution: `state` is actually the state the arc would
       leave from in the canonical appended lattice; we just store
       that in the .nextstate field. */
    CompactLattice::StateId state = arc.nextstate;
    prefinal_states.insert(state);
  }

  for (int32 state: prefinal_states)
    clat_.SetFinal(state, CompactLatticeWeight::Zero());


  for (const CompactLatticeArc &arc: final_arcs_) {
    Label token_label = arc.ilabel;
    /* Note: we store the source state in the .nextstate field. */
    CompactLattice::StateId src_state = arc.nextstate;
    BaseFloat graph_final_cost;
    if (token_label2final_cost == NULL) {
      graph_final_cost = 0.0;
    } else {
      auto iter = token_label2final_cost->find(token_label);
      if (iter == token_label2final_cost->end())
        continue;
      else
        graph_final_cost = iter->second;
    }
    /* It might seem odd to set a final-prob on the src-state of the arc..
       the point is that the symbol on the arc is a token-label, which should not
       appear in the lattice the user sees, so after that token-label is removed
       the arc would just become a final-prob.
    */
    clat_.SetFinal(src_state,
                   fst::Plus(clat_.Final(src_state),
                             fst::Times(arc.weight,
                                        CompactLatticeWeight(
                                            LatticeWeight(graph_final_cost, 0), {}))));
  }
}

TransferArcsToClat()

void TransferArcsToClat ( const CompactLattice &  chunk_clat, bool  is_first_chunk, const std::unordered_map< CompactLattice::StateId, CompactLattice::StateId > &  state_map, const std::unordered_map< CompactLattice::StateId, Label > &  chunk_state_to_token, const std::unordered_map< Label, BaseFloat > &  old_final_costs  )

private

This function, called from AcceptRawLatticeChunk(), transfers arcs from `chunk_clat` to clat_.

For those arcs that have `token-labels` on them, they don't get written to clat_ but instead are stored in the arcs_ array.

Parameters

[in]	chunk_clat	The determinized lattice for the chunk we are processing; this is the source of the arcs we are moving.
[in]	is_first_chunk	True if this is the first chunk in the utterance; it's needed because if it is, we will also transfer arcs from the start state of chunk_clat.
[in]	state_map	Map from state-ids in chunk_clat to state-ids in clat_.
[in]	chunk_state_to_token	Map from `token-final states` (see glossary) in chunk_clat, to the token-label on arcs entering those states.
[in]	old_final_costs	Map from token-label to the final-costs that were on the corresponding token-final states in the undeterminized lattice; these final-costs need to be removed when we record the weights in final_arcs_, because they were just temporary.

Definition at line 1464 of file lattice-incremental-decoder.cc.

References KALDI_ASSERT, and fst::Times().

                                                               {
  using StateId = CompactLattice::StateId;
  StateId chunk_num_states = chunk_clat.NumStates();

  // Now transfer arcs from chunk_clat to clat_.
  for (StateId chunk_state = (is_first_chunk ? 0 : 1);
       chunk_state < chunk_num_states; chunk_state++) {
    auto iter = state_map.find(chunk_state);
    if (iter == state_map.end()) {
      KALDI_ASSERT(chunk_state_to_token.count(chunk_state) != 0);
      // Don't process token-final states.  Anyway they have no arcs leaving
      // them.
      continue;
    }
    StateId clat_state = iter->second;

    // We know that this point that `clat_state` is not a token-final state
    // (see glossary for definition) as if it were, we would have done
    // `continue` above.
    //
    // Only in the last chunk of the lattice would be there be a final-prob on
    // states that are not `token-final states`; these final-probs would
    // normally all be Zero() at this point.  So in almost all cases the following
    // call will do nothing.
    clat_.SetFinal(clat_state, chunk_clat.Final(chunk_state));

    // Process arcs leaving this state.
    for (fst::ArcIterator<CompactLattice> aiter(chunk_clat, chunk_state);
         !aiter.Done(); aiter.Next()) {
      CompactLatticeArc arc(aiter.Value());

      auto next_iter = state_map.find(arc.nextstate);
      if (next_iter != state_map.end()) {
        // The normal case (when the .nextstate has a corresponding
        // state in clat_) is very simple.  Just copy the arc over.
        arc.nextstate = next_iter->second;
        KALDI_ASSERT(arc.ilabel < kTokenLabelOffset ||
                     arc.ilabel > kMaxTokenLabel);
        AddArcToClat(clat_state, arc);
      } else {
        // This is the case when the arc is to a `token-final` state (see
        // glossary.)

        // TODO: remove the following slightly excessive assertion?
        KALDI_ASSERT(chunk_clat.Final(arc.nextstate) != CompactLatticeWeight::Zero() &&
                     arc.olabel >= (Label)kTokenLabelOffset &&
                     arc.olabel < (Label)kMaxTokenLabel &&
                     chunk_state_to_token.count(arc.nextstate) != 0 &&
                     old_final_costs.count(arc.olabel) != 0);

        // Include the final-cost of the next state (which should be final)
        // in arc.weight.
        arc.weight = fst::Times(arc.weight,
                                chunk_clat.Final(arc.nextstate));

        auto cost_iter = old_final_costs.find(arc.olabel);
        KALDI_ASSERT(cost_iter != old_final_costs.end());
        BaseFloat old_final_cost = cost_iter->second;

        // `arc` is going to become an element of final_arcs_.  These
        // contain information about transitions from states in clat_ to
        // `token-final` states (i.e. states that have a token-label on the arc
        // to them and that are final in the canonical compact lattice).
        // We subtract the old_final_cost as it was just a temporary cost
        // introduced for pruning purposes.
        arc.weight.SetWeight(fst::Times(arc.weight.Weight(),
                                        LatticeWeight{-old_final_cost, 0.0}));
        // In a slight abuse of the Arc data structure, the nextstate is set to
        // the source state.  The label (ilabel == olabel) indicates the
        // token it is associated with.
        arc.nextstate = clat_state;
        final_arcs_.push_back(arc);
      }
    }
  }

}

Member Data Documentation

arcs_in_

std::vector<std::vector<std::pair<CompactLattice::StateId, int32> > > arcs_in_

private

Definition at line 420 of file lattice-incremental-decoder.h.

clat_

CompactLattice clat_

private

Definition at line 411 of file lattice-incremental-decoder.h.

config_

const LatticeIncrementalDecoderConfig& config_

private

Definition at line 395 of file lattice-incremental-decoder.h.

final_arcs_

std::vector<CompactLatticeArc> final_arcs_

private

Definition at line 429 of file lattice-incremental-decoder.h.

forward_costs_

std::vector<BaseFloat> forward_costs_

private

Definition at line 435 of file lattice-incremental-decoder.h.

non_final_redet_states_

std::unordered_set<CompactLattice::StateId> non_final_redet_states_

private

Definition at line 403 of file lattice-incremental-decoder.h.

temp_

std::unordered_set<int32> temp_

private

Definition at line 438 of file lattice-incremental-decoder.h.

trans_model_

const TransitionModel& trans_model_

private

Definition at line 392 of file lattice-incremental-decoder.h.

---

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

• decoder/lattice-incremental-decoder.h
• decoder/lattice-incremental-decoder.cc