All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
CompactLatticeMinimizer< Weight, IntType > Class Template Reference
Collaboration diagram for CompactLatticeMinimizer< Weight, IntType >:

Classes

struct  EquivalenceSorter
 

Public Types

typedef
CompactLatticeWeightTpl
< Weight, IntType > 
CompactWeight
 
typedef ArcTpl< CompactWeightCompactArc
 
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< HashTypestate_hashes_
 
std::vector< StateIdstate_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

typedef ArcTpl<CompactWeight> CompactArc

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

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

typedef size_t HashType

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

typedef CompactArc::Label Label

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

typedef CompactArc::StateId StateId

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

Constructor & Destructor Documentation

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

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

47  :
48  clat_(clat), delta_(delta) { }
MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > * clat_

Member Function Documentation

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().

96  {
97  // Note: clat_ is topologically sorted, and StateId is
98  // signed. Each state's hash value is only a function of toplogically-later
99  // states' hash values.
100  state_hashes_.resize(clat_->NumStates());
101  for (StateId s = clat_->NumStates() - 1; s >= 0; s--) {
102  HashType this_hash;
103  InitHashValue(clat_->Final(s), &this_hash);
104  for (ArcIterator<MutableFst<CompactArc> > aiter(*clat_, s);
105  !aiter.Done(); aiter.Next()) {
106  const CompactArc &arc = aiter.Value();
107  HashType next_hash;
108  if (arc.nextstate > s) {
109  next_hash = state_hashes_[arc.nextstate];
110  } else {
111  KALDI_ASSERT(s == arc.nextstate &&
112  "Lattice not topologically sorted [code error]");
113  next_hash = 1;
114  KALDI_WARN << "Minimizing lattice with self-loops "
115  "(lattices should not have self-loops)";
116  }
117  UpdateHashValueForTransition(arc.weight, arc.ilabel,
118  next_hash, &this_hash);
119  }
120  state_hashes_[s] = this_hash;
121  }
122  }
static void InitHashValue(const CompactWeight &final_weight, HashType *h)
static void UpdateHashValueForTransition(const CompactWeight &weight, Label label, HashType &next_state_hash, HashType *h)
#define KALDI_WARN
Definition: kaldi-error.h:130
ArcTpl< CompactWeight > CompactArc
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
std::vector< HashType > state_hashes_
MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > * clat_
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().

190  {
191  // We have to compute the state mapping in reverse topological order also,
192  // since the equivalence test relies on later states being already sorted
193  // out into equivalence classes (by state_map_).
194  StateId num_states = clat_->NumStates();
195  unordered_map<HashType, std::vector<StateId> > hash_groups_;
196 
197  for (StateId s = 0; s < num_states; s++)
198  hash_groups_[state_hashes_[s]].push_back(s);
199 
200  state_map_.resize(num_states);
201  for (StateId s = 0; s < num_states; s++)
202  state_map_[s] = s; // Default mapping.
203 
204 
205  { // This block is just diagnostic.
206  typedef typename unordered_map<HashType,
207  std::vector<StateId> >::const_iterator HashIter;
208  size_t max_size = 0;
209  for (HashIter iter = hash_groups_.begin(); iter != hash_groups_.end();
210  ++iter)
211  max_size = std::max(max_size, iter->second.size());
212  if (max_size > 1000) {
213  KALDI_WARN << "Largest equivalence group (using hash) is " << max_size
214  << ", minimization might be slow.";
215  }
216  }
217 
218  for (StateId s = num_states - 1; s >= 0; s--) {
219  HashType hash = state_hashes_[s];
220  const std::vector<StateId> &equivalence_class = hash_groups_[hash];
221  KALDI_ASSERT(!equivalence_class.empty());
222  for (size_t i = 0; i < equivalence_class.size(); i++) {
223  StateId t = equivalence_class[i];
224  // Below, there is no point doing the test if state_map_[t] != t, because
225  // in that case we will, before after this, be comparing with another state
226  // that is equivalent to t.
227  if (t > s && state_map_[t] == t && Equivalent(s, t)) {
228  state_map_[s] = t;
229  break;
230  }
231  }
232  }
233  }
bool Equivalent(StateId s, StateId t) const
std::vector< StateId > state_map_
#define KALDI_WARN
Definition: kaldi-error.h:130
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
std::vector< HashType > state_hashes_
MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > * clat_
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().

65  {
66  const HashType prime = 53281;
68  HashType ans = static_cast<HashType>(h(vec));
69  if (ans == 0) ans = prime;
70  // We don't allow a zero answer, as this can cause too many values to be the
71  // same.
72  return ans;
73  }
A hashing function-object for vectors.
Definition: stl-utils.h:218
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().

148  {
149  if (!ApproxEqual(clat_->Final(s), clat_->Final(t), delta_))
150  return false;
151  if (clat_->NumArcs(s) != clat_->NumArcs(t))
152  return false;
153  std::vector<CompactArc> s_arcs;
154  std::vector<CompactArc> t_arcs;
155  for (int32 iter = 0; iter <= 1; iter++) {
156  StateId state = (iter == 0 ? s : t);
157  std::vector<CompactArc> &arcs = (iter == 0 ? s_arcs : t_arcs);
158  arcs.reserve(clat_->NumArcs(s));
159  for (ArcIterator<MutableFst<CompactArc> > aiter(*clat_, state);
160  !aiter.Done(); aiter.Next()) {
161  CompactArc arc = aiter.Value();
162  if (arc.nextstate == state) {
163  // This is a special case for states that have self-loops. If two
164  // states have an identical self-loop arc, they may be equivalent.
165  arc.nextstate = kNoStateId;
166  } else {
167  KALDI_ASSERT(arc.nextstate > state);
168  //while (state_map_[arc.nextstate] != arc.nextstate)
169  arc.nextstate = state_map_[arc.nextstate];
170  arcs.push_back(arc);
171  }
172  }
173  EquivalenceSorter s;
174  std::sort(arcs.begin(), arcs.end(), s);
175  }
176  KALDI_ASSERT(s_arcs.size() == t_arcs.size());
177  for (size_t i = 0; i < s_arcs.size(); i++) {
178  if (s_arcs[i].nextstate != t_arcs[i].nextstate) return false;
179  KALDI_ASSERT(s_arcs[i].ilabel == s_arcs[i].olabel); // CompactLattices are
180  // supposed to be
181  // acceptors.
182  if (s_arcs[i].ilabel != t_arcs[i].ilabel) return false;
183  // We've already mapped to equivalence classes.
184  if (s_arcs[i].nextstate != t_arcs[i].nextstate) return false;
185  if (!ApproxEqual(s_arcs[i].weight, t_arcs[i].weight)) return false;
186  }
187  return true;
188  }
bool ApproxEqual(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2, float delta=kDelta)
std::vector< StateId > state_map_
ArcTpl< CompactWeight > CompactArc
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > * clat_
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().

75  {
76  const HashType prime1 = 33317, prime2 = 607; // it's pretty random.
77  if (final_weight == CompactWeight::Zero()) *h = prime1;
78  else *h = prime2 * ConvertStringToHashValue(final_weight.String());
79  }
static HashType ConvertStringToHashValue(const std::vector< IntType > &vec)
static const CompactLatticeWeightTpl< WeightType, IntType > Zero()
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().

50  {
51  if (clat_->Properties(kTopSorted, true) == 0) {
52  if (!TopSort(clat_)) {
53  KALDI_WARN << "Topological sorting of state-level lattice failed "
54  "(probably your lexicon has empty words or your LM has epsilon cycles; this "
55  " is a bad idea.)";
56  return false;
57  }
58  }
61  ModifyModel();
62  return true;
63  }
#define KALDI_WARN
Definition: kaldi-error.h:130
MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > * clat_
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().

235  {
236  // Modifies the model according to state_map_;
237 
238  StateId num_removed = 0;
239  StateId num_states = clat_->NumStates();
240  for (StateId s = 0; s < num_states; s++)
241  if (state_map_[s] != s)
242  num_removed++;
243  KALDI_VLOG(3) << "Removing " << num_removed << " of "
244  << num_states << " states.";
245  if (num_removed == 0) return; // Nothing to do.
246 
247  clat_->SetStart(state_map_[clat_->Start()]);
248 
249  for (StateId s = 0; s < num_states; s++) {
250  if (state_map_[s] != s)
251  continue; // There is no point modifying states we're removing.
252  for (MutableArcIterator<MutableFst<CompactArc> > aiter(clat_, s);
253  !aiter.Done(); aiter.Next()) {
254  CompactArc arc = aiter.Value();
255  StateId mapped_nextstate = state_map_[arc.nextstate];
256  if (mapped_nextstate != arc.nextstate) {
257  arc.nextstate = mapped_nextstate;
258  aiter.SetValue(arc);
259  }
260  }
261  }
262  fst::Connect(clat_);
263  }
std::vector< StateId > state_map_
ArcTpl< CompactWeight > CompactArc
#define KALDI_VLOG(v)
Definition: kaldi-error.h:136
MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > * clat_
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().

87  {
88  const HashType prime1 = 1447, prime2 = 51907;
89  if (label == 0) label = prime2; // Zeros will cause problems.
90  *h += prime1 * label *
91  (1 + ConvertStringToHashValue(weight.String()) * next_state_hash);
92  // Above, the "1 +" is to ensure that if somehow we get zeros due to
93  // weird word sequences, they don't propagate.
94  }
static HashType ConvertStringToHashValue(const std::vector< IntType > &vec)

Member Data Documentation

float delta_
private

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