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

Public Types

typedef
CompactLatticeWeightTpl
< Weight, IntType > 
CompactWeight
 
typedef ArcTpl< CompactWeightCompactArc
 
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

typedef ArcTpl<CompactWeight> CompactArc

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

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

typedef CompactArc::StateId StateId

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

Constructor & Destructor Documentation

CompactLatticePusher ( MutableFst< CompactArc > *  clat)
inline

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

37 : clat_(clat) { }
MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > * clat_

Member Function Documentation

void ApplyShifts ( )
inline

Definition at line 165 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().

165  {
166  StateId num_states = clat_->NumStates();
167  for (StateId state = 0; state < num_states; state++) {
168  int32 shift = shift_vec_[state];
169  std::vector<IntType> string;
170  for (MutableArcIterator<MutableFst<CompactArc> > aiter(clat_, state);
171  !aiter.Done(); aiter.Next()) {
172  CompactArc arc(aiter.Value());
173  KALDI_ASSERT(arc.nextstate > state && "Cyclic lattice");
174 
175  string = arc.weight.String();
176  size_t orig_len = string.size(), next_shift = shift_vec_[arc.nextstate];
177  // extend "string" by next_shift.
178  string.resize(string.size() + next_shift);
179  // The next command sets the last "next_shift" elements of 'string' to
180  // the string starting from arc.nextstate (taking an arbitrary path).
181  GetString(*clat_, arc.nextstate, -1,
182  string.begin() + orig_len, string.end());
183  // Remove the first "shift" elements of this string and set the
184  // arc-weight string to this.
185  arc.weight.SetString(std::vector<IntType>(string.begin() + shift,
186  string.end()));
187  aiter.SetValue(arc);
188  }
189 
190  CompactWeight final = clat_->Final(state);
191  if (final != CompactWeight::Zero()) {
192  // Erase first "shift" elements of final-prob.
193  final.SetString(std::vector<IntType>(final.String().begin() + shift,
194  final.String().end()));
195  clat_->SetFinal(state, final);
196  }
197  }
198  }
CompactLatticeWeightTpl< Weight, IntType > CompactWeight
Definition: push-lattice.cc:33
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)
Definition: push-lattice.cc:55
MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > * clat_
std::vector< int32 > shift_vec_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
ArcTpl< CompactWeight > CompactArc
Definition: push-lattice.cc:34
static const CompactLatticeWeightTpl< WeightType, IntType > Zero()
CompactArc::StateId StateId
Definition: push-lattice.cc:35
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().

91  {
92  // At input, "shift" has the maximum value that we could shift back assuming
93  // there is no conflict between the values of the strings. We need to check
94  // if there is conflict, and if so, reduce the "shift".
95  bool is_final = (final != CompactWeight::Zero());
96  size_t num_arcs = clat_->NumArcs(state);
97  if (num_arcs + (is_final ? 1 : 0) > 1 && shift > 0) {
98  // There is potential for conflict between string values, because >1
99  // [arc or final-prob]. Find the longest shift up to and including the
100  // current shift, that gives no conflict.
101 
102  std::vector<IntType> string(*shift), compare_string(*shift);
103  size_t arc;
104  if (is_final) {
105  KALDI_ASSERT(final.String().size() >= *shift);
106  std::copy(final.String().begin(), final.String().begin() + *shift,
107  string.begin());
108  arc = 0;
109  } else {
110  // set "string" to string if we take 1st arc.
111  GetString(*clat_, state, 0, string.begin(), string.end());
112  arc = 1;
113  }
114  for (; arc < num_arcs; arc++) { // for the other arcs..
115  GetString(*clat_, state, arc,
116  compare_string.begin(), compare_string.end());
117  std::pair<typename std::vector<IntType>::iterator,
118  typename std::vector<IntType>::iterator> pr =
119  std::mismatch(string.begin(), string.end(),
120  compare_string.begin());
121  if (pr.first != string.end()) { // There was a mismatch. Reduce the shift
122  // to a value where they will match.
123  *shift = pr.first - string.begin();
124  string.resize(*shift);
125  compare_string.resize(*shift);
126  }
127  }
128  }
129  }
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)
Definition: push-lattice.cc:55
MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > * clat_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
static const CompactLatticeWeightTpl< WeightType, IntType > Zero()
void ComputeShifts ( )
inline

Definition at line 131 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().

131  {
132  StateId num_states = clat_->NumStates();
133  shift_vec_.resize(num_states, 0);
134 
135  // The for loop will only work if StateId is signed, so assert this.
136  KALDI_COMPILE_TIME_ASSERT(static_cast<StateId>(-1) < static_cast<StateId>(0));
137  // We rely on the topological sorting, so clat_->Start() should be zero or
138  // at least any preceding states should be non-accessible. We leave the
139  // shift at zero for the start state because we can't shift to before that.
140  for (StateId state = num_states - 1; state > clat_->Start(); state--) {
141  size_t num_arcs = clat_->NumArcs(state);
142  CompactWeight final = clat_->Final(state);
143  if (num_arcs == 0) {
144  // we can shift back by the number of transition-ids on the
145  // final-prob, if any.
146  shift_vec_[state] = final.String().size();
147  } else { // We have arcs ...
148  int32 shift = std::numeric_limits<int32>::max();
149  size_t num_arcs = 0;
150  bool is_final = (final != CompactWeight::Zero());
151  if (is_final)
152  shift = std::min(shift, static_cast<int32>(final.String().size()));
153  for (ArcIterator<MutableFst<CompactArc> > aiter(*clat_, state);
154  !aiter.Done(); aiter.Next(), num_arcs++) {
155  const CompactArc &arc (aiter.Value());
156  shift = std::min(shift, shift_vec_[arc.nextstate] +
157  static_cast<int32>(arc.weight.String().size()));
158  }
159  CheckForConflict(final, state, &shift);
160  shift_vec_[state] = shift;
161  }
162  }
163  }
CompactLatticeWeightTpl< Weight, IntType > CompactWeight
Definition: push-lattice.cc:33
void CheckForConflict(const CompactWeight &final, StateId state, int32 *shift)
Definition: push-lattice.cc:89
MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > * clat_
std::vector< int32 > shift_vec_
ArcTpl< CompactWeight > CompactArc
Definition: push-lattice.cc:34
static const CompactLatticeWeightTpl< WeightType, IntType > Zero()
CompactArc::StateId StateId
Definition: push-lattice.cc:35
#define KALDI_COMPILE_TIME_ASSERT(b)
Definition: kaldi-utils.h:127
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().

59  {
60  CompactWeight final = clat.Final(state);
61  size_t len = end - begin;
62  KALDI_ASSERT(len >= 0);
63  if (len == 0) return;
64  if (arc_idx == -1 && final != CompactWeight::Zero()) {
65  const std::vector<IntType> &string = final.String();
66  KALDI_ASSERT(string.size() >= len &&
67  "Either code error, or paths in lattice have inconsistent lengths");
68  std::copy(string.begin(), string.begin() + len, begin);
69  return;
70  }
71 
72  ArcIterator<ExpandedFst<CompactArc> > aiter(clat, state);
73  if (arc_idx != -1)
74  aiter.Seek(arc_idx);
75  KALDI_ASSERT(!aiter.Done() &&
76  "Either code error, or paths in lattice are inconsistent in length.");
77 
78  const CompactArc &arc = aiter.Value();
79  size_t arc_len = arc.weight.String().size();
80  if (arc_len >= len) {
81  std::copy(arc.weight.String().begin(), arc.weight.String().begin() + len, begin);
82  } else {
83  std::copy(arc.weight.String().begin(), arc.weight.String().end(), begin);
84  // Recurse.
85  GetString(clat, arc.nextstate, -1, begin + arc_len, end);
86  }
87  }
CompactLatticeWeightTpl< Weight, IntType > CompactWeight
Definition: push-lattice.cc:33
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)
Definition: push-lattice.cc:55
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
ArcTpl< CompactWeight > CompactArc
Definition: push-lattice.cc:34
static const CompactLatticeWeightTpl< WeightType, IntType > Zero()
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().

38  {
39  if (clat_->Properties(kTopSorted, true) == 0) {
40  if (!TopSort(clat_)) {
41  KALDI_WARN << "Topological sorting of state-level lattice failed "
42  "(probably your lexicon has empty words or your LM has epsilon cycles; this "
43  " is a bad idea.)";
44  return false;
45  }
46  }
47  ComputeShifts();
48  ApplyShifts();
49  return true;
50  }
MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > * clat_
#define KALDI_WARN
Definition: kaldi-error.h:130

Member Data Documentation

std::vector<int32> shift_vec_
private

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