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

166  {
167  StateId num_states = clat_->NumStates();
168  for (StateId state = 0; state < num_states; state++) {
169  int32 shift = shift_vec_[state];
170  std::vector<IntType> string;
171  for (MutableArcIterator<MutableFst<CompactArc> > aiter(clat_, state);
172  !aiter.Done(); aiter.Next()) {
173  CompactArc arc(aiter.Value());
174  KALDI_ASSERT(arc.nextstate > state && "Cyclic lattice");
175 
176  string = arc.weight.String();
177  size_t orig_len = string.size(), next_shift = shift_vec_[arc.nextstate];
178  // extend "string" by next_shift.
179  string.resize(string.size() + next_shift);
180  // The next command sets the last "next_shift" elements of 'string' to
181  // the string starting from arc.nextstate (taking an arbitrary path).
182  GetString(*clat_, arc.nextstate, -1,
183  string.begin() + orig_len, string.end());
184  // Remove the first "shift" elements of this string and set the
185  // arc-weight string to this.
186  arc.weight.SetString(std::vector<IntType>(string.begin() + shift,
187  string.end()));
188  aiter.SetValue(arc);
189  }
190 
191  CompactWeight final = clat_->Final(state);
192  if (final != CompactWeight::Zero()) {
193  // Erase first "shift" elements of final-prob.
194  final.SetString(std::vector<IntType>(final.String().begin() + shift,
195  final.String().end()));
196  clat_->SetFinal(state, final);
197  }
198  }
199  }
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  if (shift == NULL) return;
93  // At input, "shift" has the maximum value that we could shift back assuming
94  // there is no conflict between the values of the strings. We need to check
95  // if there is conflict, and if so, reduce the "shift".
96  bool is_final = (final != CompactWeight::Zero());
97  size_t num_arcs = clat_->NumArcs(state);
98  if (num_arcs + (is_final ? 1 : 0) > 1 && *shift > 0) {
99  // There is potential for conflict between string values, because >1
100  // [arc or final-prob]. Find the longest shift up to and including the
101  // current shift, that gives no conflict.
102 
103  std::vector<IntType> string(*shift), compare_string(*shift);
104  size_t arc;
105  if (is_final) {
106  KALDI_ASSERT(final.String().size() >= *shift);
107  std::copy(final.String().begin(), final.String().begin() + *shift,
108  string.begin());
109  arc = 0;
110  } else {
111  // set "string" to string if we take 1st arc.
112  GetString(*clat_, state, 0, string.begin(), string.end());
113  arc = 1;
114  }
115  for (; arc < num_arcs; arc++) { // for the other arcs..
116  GetString(*clat_, state, arc,
117  compare_string.begin(), compare_string.end());
118  std::pair<typename std::vector<IntType>::iterator,
119  typename std::vector<IntType>::iterator> pr =
120  std::mismatch(string.begin(), string.end(),
121  compare_string.begin());
122  if (pr.first != string.end()) { // There was a mismatch. Reduce the shift
123  // to a value where they will match.
124  *shift = pr.first - string.begin();
125  string.resize(*shift);
126  compare_string.resize(*shift);
127  }
128  }
129  }
130  }
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 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().

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