All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
PruneSpecialClass< Arc > Class Template Reference

This class is used to implement the function PruneSpecial. More...

#include <prune-special-inl.h>

Collaboration diagram for PruneSpecialClass< Arc >:

Classes

struct  Task
 

Public Types

typedef Arc::StateId InputStateId
 
typedef Arc::StateId OutputStateId
 
typedef Arc::Weight Weight
 
typedef Arc::Label Label
 

Public Member Functions

 PruneSpecialClass (const Fst< Arc > &ifst, VectorFst< Arc > *ofst, Weight beam, size_t max_states)
 
bool Done (const Task &task)
 
OutputStateId ProcessState (InputStateId istate, const Weight &weight)
 
OutputStateId GetOutputStateId (InputStateId istate, const Weight &weight)
 
void ProcessTask (const Task &task)
 

Private Attributes

const Fst< Arc > & ifst_
 
VectorFst< Arc > * ofst_
 
Weight beam_
 
size_t max_states_
 
unordered_map< InputStateId,
OutputStateId
state_map_
 
std::priority_queue< Taskqueue_
 
Weight best_weight_
 

Detailed Description

template<class Arc>
class fst::PruneSpecialClass< Arc >

This class is used to implement the function PruneSpecial.

Definition at line 32 of file prune-special-inl.h.

Member Typedef Documentation

typedef Arc::StateId InputStateId

Definition at line 34 of file prune-special-inl.h.

typedef Arc::Label Label

Definition at line 37 of file prune-special-inl.h.

typedef Arc::StateId OutputStateId

Definition at line 35 of file prune-special-inl.h.

typedef Arc::Weight Weight

Definition at line 36 of file prune-special-inl.h.

Constructor & Destructor Documentation

PruneSpecialClass ( const Fst< Arc > &  ifst,
VectorFst< Arc > *  ofst,
Weight  beam,
size_t  max_states 
)
inline

Definition at line 39 of file prune-special-inl.h.

References PruneSpecialClass< Arc >::beam_, PruneSpecialClass< Arc >::Done(), PruneSpecialClass< Arc >::ifst_, KALDI_ASSERT, PruneSpecialClass< Arc >::ofst_, PruneSpecialClass< Arc >::ProcessState(), PruneSpecialClass< Arc >::ProcessTask(), and PruneSpecialClass< Arc >::queue_.

42  :
43  ifst_(ifst), ofst_(ofst), beam_(beam), max_states_(max_states),
44  best_weight_(Weight::Zero()) {
45  KALDI_ASSERT(beam != Weight::One());
46  KALDI_ASSERT(queue_.size() == 0);
47  ofst_->DeleteStates(); // make sure it's empty.
48  if (ifst_.Start() == kNoStateId)
49  return;
50  ofst_->SetStart(ProcessState(ifst_.Start(), Weight::One()));
51 
52  while (!queue_.empty()) {
53  Task task = queue_.top();
54  queue_.pop();
55  if (Done(task)) break;
56  else ProcessTask(task);
57  }
58  Connect(ofst);
59  if (beam_ != Weight::One())
60  Prune(ofst, beam_);
61  }
void ProcessTask(const Task &task)
std::priority_queue< Task > queue_
VectorFst< Arc > * ofst_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
OutputStateId ProcessState(InputStateId istate, const Weight &weight)
bool Done(const Task &task)
const Fst< Arc > & ifst_

Member Function Documentation

bool Done ( const Task task)
inline

Definition at line 77 of file prune-special-inl.h.

References PruneSpecialClass< Arc >::beam_, PruneSpecialClass< Arc >::best_weight_, fst::Compare(), PruneSpecialClass< Arc >::max_states_, PruneSpecialClass< Arc >::ofst_, fst::Times(), and PruneSpecialClass< Arc >::Task::weight.

Referenced by PruneSpecialClass< Arc >::PruneSpecialClass().

77  {
78  if (beam_ != Weight::One() && best_weight_ != Weight::Zero() &&
79  Compare(task.weight, Times(best_weight_, beam_)) < 0)
80  return true;
81  if (max_states_ > 0 &&
82  static_cast<size_t>(ofst_->NumStates()) > max_states_)
83  return true;
84  return false;
85  }
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
VectorFst< Arc > * ofst_
int Compare(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
Compare returns -1 if w1 < w2, +1 if w1 > w2, and 0 if w1 == w2.
OutputStateId GetOutputStateId ( InputStateId  istate,
const Weight weight 
)
inline

Definition at line 119 of file prune-special-inl.h.

References PruneSpecialClass< Arc >::ProcessState(), and PruneSpecialClass< Arc >::state_map_.

Referenced by PruneSpecialClass< Arc >::ProcessTask().

120  {
121  typedef typename unordered_map<InputStateId, OutputStateId>::iterator IterType;
122  IterType iter = state_map_.find(istate);
123  if (iter == state_map_.end())
124  return ProcessState(istate, weight);
125  else
126  return iter->second;
127  }
unordered_map< InputStateId, OutputStateId > state_map_
OutputStateId ProcessState(InputStateId istate, const Weight &weight)
OutputStateId ProcessState ( InputStateId  istate,
const Weight weight 
)
inline

Definition at line 92 of file prune-special-inl.h.

References fst::Compare(), PruneSpecialClass< Arc >::ifst_, KALDI_ASSERT, PruneSpecialClass< Arc >::ofst_, PruneSpecialClass< Arc >::queue_, PruneSpecialClass< Arc >::state_map_, and fst::Times().

Referenced by PruneSpecialClass< Arc >::GetOutputStateId(), and PruneSpecialClass< Arc >::PruneSpecialClass().

92  {
93  OutputStateId ostate = ofst_->AddState();
94  state_map_[istate] = ostate;
95  for (ArcIterator<Fst<Arc> > aiter(ifst_, istate); !aiter.Done();
96  aiter.Next()) {
97  const Arc &arc = aiter.Value();
98  Task new_task(istate, ostate, aiter.Position(),
99  Times(weight, arc.weight));
100  KALDI_ASSERT(Compare(arc.weight, Weight::One()) != 1);
101  queue_.push(new_task);
102  }
103  Weight final = ifst_.Final(istate);
104  if (final != Weight::Zero()) {
105  Task final_task(istate, ostate, static_cast<size_t>(-1),
106  Times(weight, final));
107  KALDI_ASSERT(Compare(final, Weight::One()) != 1);
108  queue_.push(final_task);
109  }
110  return ostate;
111  }
std::priority_queue< Task > queue_
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
unordered_map< InputStateId, OutputStateId > state_map_
VectorFst< Arc > * ofst_
int Compare(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
Compare returns -1 if w1 < w2, +1 if w1 > w2, and 0 if w1 == w2.
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
const Fst< Arc > & ifst_
void ProcessTask ( const Task task)
inline

Definition at line 129 of file prune-special-inl.h.

References PruneSpecialClass< Arc >::best_weight_, PruneSpecialClass< Arc >::GetOutputStateId(), PruneSpecialClass< Arc >::ifst_, PruneSpecialClass< Arc >::Task::istate, PruneSpecialClass< Arc >::ofst_, PruneSpecialClass< Arc >::Task::ostate, PruneSpecialClass< Arc >::Task::position, and PruneSpecialClass< Arc >::Task::weight.

Referenced by PruneSpecialClass< Arc >::PruneSpecialClass().

129  {
130  if (task.position == static_cast<size_t>(-1)) {
131  ofst_->SetFinal(task.ostate, ifst_.Final(task.istate));
132  if (best_weight_ == Weight::Zero())
133  best_weight_ = task.weight; // best-path cost through FST, used for
134  // beam-pruning.
135  } else {
136  ArcIterator<Fst<Arc> > aiter(ifst_, task.istate);
137  aiter.Seek(task.position); // if we spend most of our time here, we may
138  // need to store the arc in the Task.
139  const Arc &arc = aiter.Value();
140  InputStateId next_istate = arc.nextstate;
141  OutputStateId next_ostate = GetOutputStateId(next_istate, task.weight);
142  Arc oarc(arc.ilabel, arc.olabel, arc.weight, next_ostate);
143  ofst_->AddArc(task.ostate, oarc);
144  }
145  }
VectorFst< Arc > * ofst_
OutputStateId GetOutputStateId(InputStateId istate, const Weight &weight)
const Fst< Arc > & ifst_

Member Data Documentation

Weight best_weight_
private
size_t max_states_
private

Definition at line 151 of file prune-special-inl.h.

Referenced by PruneSpecialClass< Arc >::Done().

std::priority_queue<Task> queue_
private
unordered_map<InputStateId, OutputStateId> state_map_
private

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