CompactLatticeMinimizer< Weight, IntType > Class Template Reference

Collaboration diagram for CompactLatticeMinimizer< Weight, IntType >:

Classes
struct	EquivalenceSorter

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

Public Member Functions
	CompactLatticeMinimizer (MutableFst< CompactArc > *clat, float delta=fst::kDelta)
bool	Minimize ()
void	ComputeStateHashValues ()
bool	Equivalent (StateId s, StateId t) const
void	ComputeStateMap ()
void	ModifyModel ()

Static Public Member Functions
static HashType	ConvertStringToHashValue (const std::vector< IntType > &vec)
static void	InitHashValue (const CompactWeight &final_weight, HashType *h)
static void	UpdateHashValueForTransition (const CompactWeight &weight, Label label, HashType &next_state_hash, HashType *h)

Private Attributes
MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > *	clat_
float	delta_
std::vector< HashType >	state_hashes_
std::vector< StateId >	state_map_

Detailed Description

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

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

Member Typedef Documentation

CompactArc

typedef ArcTpl<CompactWeight> CompactArc

Definition at line 41 of file minimize-lattice.cc.

CompactWeight

typedef CompactLatticeWeightTpl<Weight, IntType> CompactWeight

Definition at line 40 of file minimize-lattice.cc.

HashType

typedef size_t HashType

Definition at line 44 of file minimize-lattice.cc.

Label

typedef CompactArc::Label Label

Definition at line 43 of file minimize-lattice.cc.

StateId

typedef CompactArc::StateId StateId

Definition at line 42 of file minimize-lattice.cc.

Constructor & Destructor Documentation

CompactLatticeMinimizer()

CompactLatticeMinimizer ( MutableFst< CompactArc > *  clat, float  delta = fst::kDelta  )

inline

Definition at line 46 of file minimize-lattice.cc.

                                                  :
      clat_(clat), delta_(delta) { }

Member Function Documentation

ComputeStateHashValues()

void ComputeStateHashValues ( )

inline

Definition at line 96 of file minimize-lattice.cc.

References CompactLatticeMinimizer< Weight, IntType >::clat_, CompactLatticeMinimizer< Weight, IntType >::InitHashValue(), KALDI_ASSERT, KALDI_WARN, CompactLatticeMinimizer< Weight, IntType >::state_hashes_, and CompactLatticeMinimizer< Weight, IntType >::UpdateHashValueForTransition().

Referenced by CompactLatticeMinimizer< Weight, IntType >::Minimize().

                                {
    // Note: clat_ is topologically sorted, and StateId is
    // signed.  Each state's hash value is only a function of toplogically-later
    // states' hash values.
    state_hashes_.resize(clat_->NumStates());
    for (StateId s = clat_->NumStates() - 1; s >= 0; s--) {
      HashType this_hash;
      InitHashValue(clat_->Final(s), &this_hash);
      for (ArcIterator<MutableFst<CompactArc> > aiter(*clat_, s);
           !aiter.Done(); aiter.Next()) {
        const CompactArc &arc = aiter.Value();
        HashType next_hash;
        if (arc.nextstate > s) {
          next_hash = state_hashes_[arc.nextstate];
        } else {
          KALDI_ASSERT(s == arc.nextstate &&
                       "Lattice not topologically sorted [code error]");
          next_hash = 1;
          KALDI_WARN << "Minimizing lattice with self-loops "
              "(lattices should not have self-loops)";
        }
        UpdateHashValueForTransition(arc.weight, arc.ilabel,
                                     next_hash, &this_hash);
      }
      state_hashes_[s] = this_hash;
    }
  }

ComputeStateMap()

void ComputeStateMap ( )

inline

Definition at line 190 of file minimize-lattice.cc.

References CompactLatticeMinimizer< Weight, IntType >::clat_, CompactLatticeMinimizer< Weight, IntType >::Equivalent(), rnnlm::i, KALDI_ASSERT, KALDI_WARN, CompactLatticeMinimizer< Weight, IntType >::state_hashes_, and CompactLatticeMinimizer< Weight, IntType >::state_map_.

Referenced by CompactLatticeMinimizer< Weight, IntType >::Minimize().

                         {
    // We have to compute the state mapping in reverse topological order also,
    // since the equivalence test relies on later states being already sorted
    // out into equivalence classes (by state_map_).
    StateId num_states = clat_->NumStates();
    unordered_map<HashType, std::vector<StateId> > hash_groups_;
    
    for (StateId s = 0; s < num_states; s++)
      hash_groups_[state_hashes_[s]].push_back(s);

    state_map_.resize(num_states);
    for (StateId s = 0; s < num_states; s++)
      state_map_[s] = s; // Default mapping.
    

    { // This block is just diagnostic.
      typedef typename unordered_map<HashType,
              std::vector<StateId> >::const_iterator HashIter;
      size_t max_size = 0;
      for (HashIter iter = hash_groups_.begin(); iter != hash_groups_.end();
           ++iter)
        max_size = std::max(max_size, iter->second.size());
      if (max_size > 1000) {
        KALDI_WARN << "Largest equivalence group (using hash) is " << max_size
                   << ", minimization might be slow.";
      }
    }

    for (StateId s = num_states - 1; s >= 0; s--) {
      HashType hash = state_hashes_[s];
      const std::vector<StateId> &equivalence_class = hash_groups_[hash];
      KALDI_ASSERT(!equivalence_class.empty());
      for (size_t i = 0; i < equivalence_class.size(); i++) {
        StateId t = equivalence_class[i];
        // Below, there is no point doing the test if state_map_[t] != t, because
        // in that case we will, before after this, be comparing with another state
        // that is equivalent to t.
        if (t > s && state_map_[t] == t && Equivalent(s, t)) {
          state_map_[s] = t;
          break;
        }
      }
    }
  }

ConvertStringToHashValue()

static HashType ConvertStringToHashValue ( const std::vector< IntType > &  vec )

inlinestatic

Definition at line 65 of file minimize-lattice.cc.

Referenced by CompactLatticeMinimizer< Weight, IntType >::InitHashValue(), and CompactLatticeMinimizer< Weight, IntType >::UpdateHashValueForTransition().

                                                                          {
    const HashType prime = 53281;
    kaldi::VectorHasher<IntType> h;
    HashType ans = static_cast<HashType>(h(vec));
    if (ans == 0)  ans = prime;
    // We don't allow a zero answer, as this can cause too many values to be the
    // same.
    return ans;
  }

Equivalent()

bool Equivalent ( StateId  s, StateId  t  ) const

inline

Definition at line 148 of file minimize-lattice.cc.

References fst::ApproxEqual(), CompactLatticeMinimizer< Weight, IntType >::clat_, CompactLatticeMinimizer< Weight, IntType >::delta_, rnnlm::i, KALDI_ASSERT, and CompactLatticeMinimizer< Weight, IntType >::state_map_.

Referenced by CompactLatticeMinimizer< Weight, IntType >::ComputeStateMap().

                                              {
    if (!ApproxEqual(clat_->Final(s), clat_->Final(t), delta_))
      return false;
    if (clat_->NumArcs(s) != clat_->NumArcs(t))
      return false;
    std::vector<CompactArc> s_arcs;
    std::vector<CompactArc> t_arcs;
    for (int32 iter = 0; iter <= 1; iter++) {
      StateId state = (iter == 0 ? s : t);
      std::vector<CompactArc> &arcs = (iter == 0 ? s_arcs : t_arcs);
      arcs.reserve(clat_->NumArcs(s));
      for (ArcIterator<MutableFst<CompactArc> > aiter(*clat_, state);
           !aiter.Done(); aiter.Next()) {
        CompactArc arc = aiter.Value();
        if (arc.nextstate == state) {
          // This is a special case for states that have self-loops.  If two
          // states have an identical self-loop arc, they may be equivalent.
          arc.nextstate = kNoStateId;
        } else {
          KALDI_ASSERT(arc.nextstate > state);
          //while (state_map_[arc.nextstate] != arc.nextstate)
          arc.nextstate = state_map_[arc.nextstate];
          arcs.push_back(arc);
        }
      }
      EquivalenceSorter s;
      std::sort(arcs.begin(), arcs.end(), s);
    }
    KALDI_ASSERT(s_arcs.size() == t_arcs.size());
    for (size_t i = 0; i < s_arcs.size(); i++) {
      if (s_arcs[i].nextstate != t_arcs[i].nextstate) return false;
      KALDI_ASSERT(s_arcs[i].ilabel == s_arcs[i].olabel); // CompactLattices are
                                                          // supposed to be
                                                          // acceptors.
      if (s_arcs[i].ilabel != t_arcs[i].ilabel) return false;
      // We've already mapped to equivalence classes.
      if (s_arcs[i].nextstate != t_arcs[i].nextstate) return false;
      if (!ApproxEqual(s_arcs[i].weight, t_arcs[i].weight)) return false;
    }
    return true;
  }

InitHashValue()

static void InitHashValue ( const CompactWeight &  final_weight, HashType *  h  )

inlinestatic

Definition at line 75 of file minimize-lattice.cc.

References CompactLatticeMinimizer< Weight, IntType >::ConvertStringToHashValue(), CompactLatticeWeightTpl< WeightType, IntType >::String(), and CompactLatticeWeightTpl< WeightType, IntType >::Zero().

Referenced by CompactLatticeMinimizer< Weight, IntType >::ComputeStateHashValues().

                                                                            {
    const HashType prime1 = 33317, prime2 = 607; // it's pretty random.
    if (final_weight == CompactWeight::Zero()) *h = prime1;
    else *h = prime2 * ConvertStringToHashValue(final_weight.String());
  }

Minimize()

bool Minimize ( )

inline

Definition at line 50 of file minimize-lattice.cc.

References CompactLatticeMinimizer< Weight, IntType >::clat_, CompactLatticeMinimizer< Weight, IntType >::ComputeStateHashValues(), CompactLatticeMinimizer< Weight, IntType >::ComputeStateMap(), KALDI_WARN, and CompactLatticeMinimizer< Weight, IntType >::ModifyModel().

Referenced by fst::MinimizeCompactLattice().

                  {
    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;
      }
    }
    ComputeStateHashValues();
    ComputeStateMap();
    ModifyModel();
    return true;
  }

ModifyModel()

void ModifyModel ( )

inline

Definition at line 235 of file minimize-lattice.cc.

References CompactLatticeMinimizer< Weight, IntType >::clat_, KALDI_VLOG, and CompactLatticeMinimizer< Weight, IntType >::state_map_.

Referenced by CompactLatticeMinimizer< Weight, IntType >::Minimize().

                     {    
    // Modifies the model according to state_map_;

    StateId num_removed = 0;
    StateId num_states = clat_->NumStates();
    for (StateId s = 0; s < num_states; s++)
      if (state_map_[s] != s)
        num_removed++;
    KALDI_VLOG(3) << "Removing " << num_removed << " of "
                  << num_states << " states.";
    if (num_removed == 0) return; // Nothing to do.
    
    clat_->SetStart(state_map_[clat_->Start()]);

    for (StateId s = 0; s < num_states; s++) {
      if (state_map_[s] != s)
        continue; // There is no point modifying states we're removing.
      for (MutableArcIterator<MutableFst<CompactArc> > aiter(clat_, s);
           !aiter.Done(); aiter.Next()) {
        CompactArc arc = aiter.Value();
        StateId mapped_nextstate = state_map_[arc.nextstate];
        if (mapped_nextstate != arc.nextstate) {
          arc.nextstate = mapped_nextstate;
          aiter.SetValue(arc);
        }
      }
    }
    fst::Connect(clat_);
  }

UpdateHashValueForTransition()

static void UpdateHashValueForTransition ( const CompactWeight &  weight, Label  label, HashType &  next_state_hash, HashType *  h  )

inlinestatic

Definition at line 84 of file minimize-lattice.cc.

References CompactLatticeMinimizer< Weight, IntType >::ConvertStringToHashValue(), and CompactLatticeWeightTpl< WeightType, IntType >::String().

Referenced by CompactLatticeMinimizer< Weight, IntType >::ComputeStateHashValues().

                                                        {
    const HashType prime1 = 1447, prime2 = 51907;
    if (label == 0) label = prime2; // Zeros will cause problems.
    *h += prime1 * label *
        (1 + ConvertStringToHashValue(weight.String()) * next_state_hash);
    // Above, the "1 +" is to ensure that if somehow we get zeros due to
    // weird word sequences, they don't propagate.
  }

Member Data Documentation

clat_

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

private

Definition at line 265 of file minimize-lattice.cc.

Referenced by CompactLatticeMinimizer< Weight, IntType >::ComputeStateHashValues(), CompactLatticeMinimizer< Weight, IntType >::ComputeStateMap(), CompactLatticeMinimizer< Weight, IntType >::Equivalent(), CompactLatticeMinimizer< Weight, IntType >::Minimize(), and CompactLatticeMinimizer< Weight, IntType >::ModifyModel().

delta_

float delta_

private

Definition at line 266 of file minimize-lattice.cc.

Referenced by CompactLatticeMinimizer< Weight, IntType >::Equivalent().

state_hashes_

std::vector<HashType> state_hashes_

private

Definition at line 267 of file minimize-lattice.cc.

Referenced by CompactLatticeMinimizer< Weight, IntType >::ComputeStateHashValues(), and CompactLatticeMinimizer< Weight, IntType >::ComputeStateMap().

state_map_

std::vector<StateId> state_map_

private

Definition at line 268 of file minimize-lattice.cc.

Referenced by CompactLatticeMinimizer< Weight, IntType >::ComputeStateMap(), CompactLatticeMinimizer< Weight, IntType >::Equivalent(), and CompactLatticeMinimizer< Weight, IntType >::ModifyModel().

---

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

• lat/minimize-lattice.cc