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< Task >	queue_
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

InputStateId

typedef Arc::StateId InputStateId

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

Label

typedef Arc::Label Label

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

OutputStateId

typedef Arc::StateId OutputStateId

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

Weight

typedef Arc::Weight Weight

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

Constructor & Destructor Documentation

PruneSpecialClass()

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_.

                                      :
      ifst_(ifst), ofst_(ofst), beam_(beam), max_states_(max_states),
      best_weight_(Weight::Zero()) {
    KALDI_ASSERT(beam != Weight::One());
    KALDI_ASSERT(queue_.size() == 0);
    ofst_->DeleteStates(); // make sure it's empty.
    if (ifst_.Start() == kNoStateId)
      return;
    ofst_->SetStart(ProcessState(ifst_.Start(), Weight::One()));

    while (!queue_.empty()) {
      Task task = queue_.top();
      queue_.pop();
      if (Done(task)) break;
      else ProcessTask(task);
    }
    Connect(ofst);
    if (beam_ != Weight::One())
      Prune(ofst, beam_);
  }

Member Function Documentation

Done()

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

                              {
    if (beam_ != Weight::One() && best_weight_ != Weight::Zero() &&
        Compare(task.weight, Times(best_weight_, beam_)) < 0)
      return true;
    if (max_states_ > 0 &&
        static_cast<size_t>(ofst_->NumStates()) > max_states_)
      return true;
    return false;
  }

GetOutputStateId()

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

                                                              {
    typedef typename unordered_map<InputStateId, OutputStateId>::iterator IterType;
    IterType iter = state_map_.find(istate);
    if (iter == state_map_.end())
      return ProcessState(istate, weight);
    else 
      return iter->second;
  }

ProcessState()

OutputStateId ProcessState ( InputStateId  istate, const Weight &  weight  )

inline

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

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

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

                                                                               {
    OutputStateId ostate = ofst_->AddState();
    state_map_[istate] = ostate;
    for (ArcIterator<Fst<Arc> > aiter(ifst_, istate); !aiter.Done();
         aiter.Next()) {
      const Arc &arc = aiter.Value();
      Task new_task(istate, ostate, aiter.Position(),
                    Times(weight, arc.weight));
      KALDI_ASSERT(Compare(arc.weight, Weight::One()) != 1);
      queue_.push(new_task);
    }
    Weight final = ifst_.Final(istate);
    if (final != Weight::Zero()) {
      Task final_task(istate, ostate, static_cast<size_t>(-1),
                      Times(weight, final));
      KALDI_ASSERT(Compare(final, Weight::One()) != 1);
      queue_.push(final_task);
    }
    return ostate;
  }

ProcessTask()

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

                                     {
    if (task.position == static_cast<size_t>(-1)) {
      ofst_->SetFinal(task.ostate, ifst_.Final(task.istate));
      if (best_weight_ == Weight::Zero())
        best_weight_ = task.weight; // best-path cost through FST, used for
                                    // beam-pruning.
    } else {
      ArcIterator<Fst<Arc> > aiter(ifst_, task.istate);
      aiter.Seek(task.position); // if we spend most of our time here, we may
                                 // need to store the arc in the Task.
      const Arc &arc = aiter.Value();
      InputStateId next_istate = arc.nextstate;
      OutputStateId next_ostate = GetOutputStateId(next_istate, task.weight);
      Arc oarc(arc.ilabel, arc.olabel, arc.weight, next_ostate);
      ofst_->AddArc(task.ostate, oarc);
    }
  }

Member Data Documentation

beam_

Weight beam_

private

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

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

best_weight_

Weight best_weight_

private

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

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

ifst_

const Fst<Arc>& ifst_

private

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

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

max_states_

size_t max_states_

private

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

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

ofst_

VectorFst<Arc>* ofst_

private

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

Referenced by PruneSpecialClass< Arc >::Done(), PruneSpecialClass< Arc >::ProcessState(), PruneSpecialClass< Arc >::ProcessTask(), and PruneSpecialClass< Arc >::PruneSpecialClass().

queue_

std::priority_queue<Task> queue_

private

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

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

state_map_

unordered_map<InputStateId, OutputStateId> state_map_

private

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

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

---

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

• fstext/prune-special-inl.h