CompactLatticePusher< Weight, IntType > Class Template Reference

Collaboration diagram for CompactLatticePusher< Weight, IntType >:

Public Types
typedef CompactLatticeWeightTpl< Weight, IntType >	CompactWeight
typedef ArcTpl< CompactWeight >	CompactArc
typedef CompactArc::StateId	StateId

Public Member Functions
	CompactLatticePusher (MutableFst< CompactArc > *clat)
bool	Push ()
void	CheckForConflict (const CompactWeight &final, StateId state, int32 *shift)
void	ComputeShifts ()
void	ApplyShifts ()

Static Public Member Functions
static void	GetString (const ExpandedFst< CompactArc > &clat, StateId state, size_t arc_idx, typename std::vector< IntType >::iterator begin, typename std::vector< IntType >::iterator end)

Private Attributes
MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > *	clat_
std::vector< int32 >	shift_vec_

Detailed Description

template<class Weight, class IntType>
class fst::CompactLatticePusher< Weight, IntType >

Definition at line 31 of file push-lattice.cc.

Member Typedef Documentation

CompactArc

typedef ArcTpl<CompactWeight> CompactArc

Definition at line 34 of file push-lattice.cc.

CompactWeight

typedef CompactLatticeWeightTpl<Weight, IntType> CompactWeight

Definition at line 33 of file push-lattice.cc.

StateId

typedef CompactArc::StateId StateId

Definition at line 35 of file push-lattice.cc.

Constructor & Destructor Documentation

CompactLatticePusher()

CompactLatticePusher ( MutableFst< CompactArc > *  clat )

inline

Definition at line 37 of file push-lattice.cc.

: clat_(clat) { }

Member Function Documentation

ApplyShifts()

void ApplyShifts ( )

inline

Definition at line 166 of file push-lattice.cc.

References CompactLatticePusher< Weight, IntType >::clat_, CompactLatticePusher< Weight, IntType >::GetString(), KALDI_ASSERT, CompactLatticePusher< Weight, IntType >::shift_vec_, and CompactLatticeWeightTpl< WeightType, IntType >::Zero().

Referenced by CompactLatticePusher< Weight, IntType >::Push().

                     {
    StateId num_states = clat_->NumStates();
    for (StateId state = 0; state < num_states; state++) {
      int32 shift = shift_vec_[state];
      std::vector<IntType> string;
      for (MutableArcIterator<MutableFst<CompactArc> > aiter(clat_, state);
           !aiter.Done(); aiter.Next()) {
        CompactArc arc(aiter.Value());
        KALDI_ASSERT(arc.nextstate > state && "Cyclic lattice");

        string = arc.weight.String();
        size_t orig_len = string.size(), next_shift = shift_vec_[arc.nextstate];
        // extend "string" by next_shift.
        string.resize(string.size() + next_shift);
        // The next command sets the last "next_shift" elements of 'string' to
        // the string starting from arc.nextstate (taking an arbitrary path).
        GetString(*clat_, arc.nextstate, -1,
                  string.begin() + orig_len, string.end());
        // Remove the first "shift" elements of this string and set the
        // arc-weight string to this.
        arc.weight.SetString(std::vector<IntType>(string.begin() + shift,
                                                string.end()));
        aiter.SetValue(arc);
      }
      
      CompactWeight final = clat_->Final(state);
      if (final != CompactWeight::Zero()) {
        // Erase first "shift" elements of final-prob.
        final.SetString(std::vector<IntType>(final.String().begin() + shift,
                                           final.String().end()));
        clat_->SetFinal(state, final);
      }
    }
  }

CheckForConflict()

void CheckForConflict ( const CompactWeight &  final, StateId  state, int32 *  shift  )

inline

Definition at line 89 of file push-lattice.cc.

References CompactLatticePusher< Weight, IntType >::clat_, CompactLatticePusher< Weight, IntType >::GetString(), KALDI_ASSERT, and CompactLatticeWeightTpl< WeightType, IntType >::Zero().

Referenced by CompactLatticePusher< Weight, IntType >::ComputeShifts().

                                      {
    if (shift == NULL) return;
    // At input, "shift" has the maximum value that we could shift back assuming
    // there is no conflict between the values of the strings.  We need to check
    // if there is conflict, and if so, reduce the "shift".
    bool is_final = (final != CompactWeight::Zero());
    size_t num_arcs = clat_->NumArcs(state);
    if (num_arcs + (is_final ? 1 : 0) > 1 && *shift > 0) {
      // There is potential for conflict between string values, because >1
      // [arc or final-prob].  Find the longest shift up to and including the
      // current shift, that gives no conflict.

      std::vector<IntType> string(*shift), compare_string(*shift);
      size_t arc;
      if (is_final) {
        KALDI_ASSERT(final.String().size() >= *shift);
        std::copy(final.String().begin(), final.String().begin() + *shift,
                  string.begin());
        arc = 0;
      } else {
        // set "string" to string if we take 1st arc.
        GetString(*clat_, state, 0, string.begin(), string.end());
        arc = 1;
      }
      for (; arc < num_arcs; arc++) { // for the other arcs..
        GetString(*clat_, state, arc,
                  compare_string.begin(), compare_string.end());
        std::pair<typename std::vector<IntType>::iterator,
            typename std::vector<IntType>::iterator> pr =
                std::mismatch(string.begin(), string.end(),
                              compare_string.begin());
        if (pr.first != string.end()) { // There was a mismatch.  Reduce the shift
          // to a value where they will match.
          *shift = pr.first - string.begin();
          string.resize(*shift);
          compare_string.resize(*shift);
        }
      }
    }
  }

ComputeShifts()

void ComputeShifts ( )

inline

Definition at line 132 of file push-lattice.cc.

References CompactLatticePusher< Weight, IntType >::CheckForConflict(), CompactLatticePusher< Weight, IntType >::clat_, KALDI_COMPILE_TIME_ASSERT, CompactLatticePusher< Weight, IntType >::shift_vec_, and CompactLatticeWeightTpl< WeightType, IntType >::Zero().

Referenced by CompactLatticePusher< Weight, IntType >::Push().

                       {
    StateId num_states = clat_->NumStates();
    shift_vec_.resize(num_states, 0);
    
    // The for loop will only work if StateId is signed, so assert this.
    KALDI_COMPILE_TIME_ASSERT(static_cast<StateId>(-1) < static_cast<StateId>(0));
    // We rely on the topological sorting, so clat_->Start() should be zero or
    // at least any preceding states should be non-accessible.  We leave the
    // shift at zero for the start state because we can't shift to before that.
    for (StateId state = num_states - 1; state > clat_->Start(); state--) {
      size_t num_arcs = clat_->NumArcs(state);
      CompactWeight final = clat_->Final(state);
      if (num_arcs == 0) {
        // we can shift back by the number of transition-ids on the
        // final-prob, if any.
        shift_vec_[state] = final.String().size();
      } else { // We have arcs ...
        int32 shift = std::numeric_limits<int32>::max();
        size_t num_arcs = 0;
        bool is_final = (final != CompactWeight::Zero());
        if (is_final)
          shift = std::min(shift, static_cast<int32>(final.String().size()));
        for (ArcIterator<MutableFst<CompactArc> > aiter(*clat_, state);
             !aiter.Done(); aiter.Next(), num_arcs++) {
          const CompactArc &arc (aiter.Value());
          shift = std::min(shift, shift_vec_[arc.nextstate] +
                           static_cast<int32>(arc.weight.String().size()));
        }
        CheckForConflict(final, state, &shift);
        shift_vec_[state] = shift;
      }
    }
  }

GetString()

static void GetString ( const ExpandedFst< CompactArc > &  clat, StateId  state, size_t  arc_idx, typename std::vector< IntType >::iterator  begin, typename std::vector< IntType >::iterator  end  )

inlinestatic

Definition at line 55 of file push-lattice.cc.

References KALDI_ASSERT, and CompactLatticeWeightTpl< WeightType, IntType >::Zero().

Referenced by CompactLatticePusher< Weight, IntType >::ApplyShifts(), and CompactLatticePusher< Weight, IntType >::CheckForConflict().

                                                                 {
    CompactWeight final = clat.Final(state);
    size_t len = end - begin;
    KALDI_ASSERT(len >= 0);
    if (len == 0) return;
    if (arc_idx == -1 && final != CompactWeight::Zero()) {
      const std::vector<IntType> &string = final.String();
      KALDI_ASSERT(string.size() >= len &&
                   "Either code error, or paths in lattice have inconsistent lengths");
      std::copy(string.begin(), string.begin() + len, begin);
      return;
    }

    ArcIterator<ExpandedFst<CompactArc> > aiter(clat, state);
    if (arc_idx != -1)
      aiter.Seek(arc_idx);
    KALDI_ASSERT(!aiter.Done() &&
                 "Either code error, or paths in lattice are inconsistent in length.");

    const CompactArc &arc = aiter.Value();
    size_t arc_len = arc.weight.String().size();
    if (arc_len >= len) {
      std::copy(arc.weight.String().begin(), arc.weight.String().begin() + len, begin);
    } else {
      std::copy(arc.weight.String().begin(), arc.weight.String().end(), begin);
      // Recurse.
      GetString(clat, arc.nextstate, -1, begin + arc_len, end);
    }
  }

Push()

bool Push ( )

inline

Definition at line 38 of file push-lattice.cc.

References CompactLatticePusher< Weight, IntType >::ApplyShifts(), CompactLatticePusher< Weight, IntType >::clat_, CompactLatticePusher< Weight, IntType >::ComputeShifts(), and KALDI_WARN.

Referenced by fst::PushCompactLatticeStrings().

              {
    if (clat_->Properties(kTopSorted, true) == 0) {
      if (!TopSort(clat_)) {
        KALDI_WARN << "Topological sorting of state-level lattice failed "
            "(probably your lexicon has empty words or your LM has epsilon cycles; this "
            " is a bad idea.)";
        return false;
      }
    }
    ComputeShifts();
    ApplyShifts();
    return true;
  }

Member Data Documentation

clat_

MutableFst<ArcTpl<CompactLatticeWeightTpl<Weight, IntType> > >* clat_

private

Definition at line 202 of file push-lattice.cc.

Referenced by CompactLatticePusher< Weight, IntType >::ApplyShifts(), CompactLatticePusher< Weight, IntType >::CheckForConflict(), CompactLatticePusher< Weight, IntType >::ComputeShifts(), and CompactLatticePusher< Weight, IntType >::Push().

shift_vec_

std::vector<int32> shift_vec_

private

Definition at line 206 of file push-lattice.cc.

Referenced by CompactLatticePusher< Weight, IntType >::ApplyShifts(), and CompactLatticePusher< Weight, IntType >::ComputeShifts().

---

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

• lat/push-lattice.cc