RemoveEpsLocalClass< Arc, ReweightPlus > Class Template Reference

#include <remove-eps-local-inl.h>

Collaboration diagram for RemoveEpsLocalClass< Arc, ReweightPlus >:

Public Member Functions
	RemoveEpsLocalClass (MutableFst< Arc > *fst)

Private Types
typedef Arc::StateId	StateId
typedef Arc::Label	Label
typedef Arc::Weight	Weight

Private Member Functions
bool	CanCombineArcs (const Arc &a, const Arc &b, Arc *c)
void	InitNumArcs ()
bool	CheckNumArcs ()
void	GetArc (StateId s, size_t pos, Arc *arc) const
void	SetArc (StateId s, size_t pos, const Arc &arc)
void	Reweight (StateId s, size_t pos, Weight reweight)
void	RemoveEpsPattern1 (StateId s, size_t pos, Arc arc)
void	RemoveEpsPattern2 (StateId s, size_t pos, Arc arc)
void	RemoveEps (StateId s, size_t pos)

Static Private Member Functions
static bool	CanCombineFinal (const Arc &a, Weight final_prob, Weight *final_prob_out)

Private Attributes
MutableFst< Arc > *	fst_
StateId	non_coacc_state_
std::vector< StateId >	num_arcs_in_
std::vector< StateId >	num_arcs_out_
ReweightPlus	reweight_plus_

Detailed Description

template<class Arc, class ReweightPlus = ReweightPlusDefault<typename Arc::Weight>>
class fst::RemoveEpsLocalClass< Arc, ReweightPlus >

Definition at line 46 of file remove-eps-local-inl.h.

Member Typedef Documentation

Label

typedef Arc::Label Label

private

Definition at line 48 of file remove-eps-local-inl.h.

StateId

typedef Arc::StateId StateId

private

Definition at line 47 of file remove-eps-local-inl.h.

Weight

typedef Arc::Weight Weight

private

Definition at line 49 of file remove-eps-local-inl.h.

Constructor & Destructor Documentation

RemoveEpsLocalClass()

RemoveEpsLocalClass ( MutableFst< Arc > *  fst )

inline

Definition at line 52 of file remove-eps-local-inl.h.

                                           :
      fst_(fst) {
    if (fst_->Start() == kNoStateId) return;  // empty.
    non_coacc_state_ = fst_->AddState();
    InitNumArcs();
    StateId num_states = fst_->NumStates();
    for (StateId s = 0; s < num_states; s++)
      for (size_t pos = 0; pos < fst_->NumArcs(s); pos++)
        RemoveEps(s, pos);
    assert(CheckNumArcs());
    Connect(fst);  // remove inaccessible states.
  }

Member Function Documentation

CanCombineArcs()

bool CanCombineArcs ( const Arc &  a, const Arc &  b, Arc *  c  )

inlineprivate

Definition at line 73 of file remove-eps-local-inl.h.

References fst::Times().

                                                          {
    if (a.ilabel != 0 && b.ilabel != 0) return false;
    if (a.olabel != 0 && b.olabel != 0) return false;
    c->weight = Times(a.weight, b.weight);
    c->ilabel = (a.ilabel != 0 ? a.ilabel : b.ilabel);
    c->olabel = (a.olabel != 0 ? a.olabel : b.olabel);
    c->nextstate = b.nextstate;
    return true;
  }

CanCombineFinal()

static bool CanCombineFinal ( const Arc &  a, Weight  final_prob, Weight *  final_prob_out  )

inlinestaticprivate

Definition at line 83 of file remove-eps-local-inl.h.

References fst::Times().

                                                                                       {
    if (a.ilabel != 0 || a.olabel != 0) return false;
    else {
      *final_prob_out = Times(a.weight, final_prob);
      return true;
    }
  }

CheckNumArcs()

bool CheckNumArcs ( )

inlineprivate

Definition at line 106 of file remove-eps-local-inl.h.

                      {  // check num arcs in/out of each state, at end.  Debug.
    num_arcs_in_[fst_->Start()]--;  // count start as trans in.
    StateId num_states =   fst_->NumStates();
    for (StateId s = 0; s < num_states; s++) {
      if (s == non_coacc_state_) continue;
      if (fst_->Final(s) != Weight::Zero())
        num_arcs_out_[s]--;  // count final as transition.
      for (ArcIterator<MutableFst<Arc> > aiter(*fst_, s); !aiter.Done(); aiter.Next()) {
        if (aiter.Value().nextstate == non_coacc_state_) continue;
        num_arcs_in_[aiter.Value().nextstate]--;
        num_arcs_out_[s]--;
      }
    }
    for (StateId s = 0; s < num_states; s++) {
      assert(num_arcs_in_[s] == 0);
      assert(num_arcs_out_[s] == 0);
    }
    return true;  // always does this.  so we can assert it w/o warnings.
  }

GetArc()

void GetArc ( StateId  s, size_t  pos, Arc *  arc  ) const

inlineprivate

Definition at line 126 of file remove-eps-local-inl.h.

                                                            {
    ArcIterator<MutableFst<Arc> > aiter(*fst_, s);
    aiter.Seek(pos);
    *arc = aiter.Value();
  }

InitNumArcs()

void InitNumArcs ( )

inlineprivate

Definition at line 91 of file remove-eps-local-inl.h.

                     {  // init num transitions in/out of each state.
    StateId num_states = fst_->NumStates();
    num_arcs_in_.resize(num_states);
    num_arcs_out_.resize(num_states);
    num_arcs_in_[fst_->Start()]++;  // count start as trans in.
    for (StateId s = 0; s < num_states; s++) {
      if (fst_->Final(s) != Weight::Zero())
        num_arcs_out_[s]++;  // count final as transition.
      for (ArcIterator<MutableFst<Arc> > aiter(*fst_, s); !aiter.Done(); aiter.Next()) {
        num_arcs_in_[aiter.Value().nextstate]++;
        num_arcs_out_[s]++;
      }
    }
  }

RemoveEps()

void RemoveEps ( StateId  s, size_t  pos  )

inlineprivate

Definition at line 290 of file remove-eps-local-inl.h.

                                        {
    // Tries to do local epsilon-removal for arc sequences starting with this arc
    Arc arc;
    GetArc(s, pos, &arc);
    StateId nextstate = arc.nextstate;
    if (nextstate == non_coacc_state_) return;  // deleted arc.
    if (nextstate == s) return;  // don't handle self-loops: too complex.

    if (num_arcs_in_[nextstate] == 1 && num_arcs_out_[nextstate] > 1) {
      RemoveEpsPattern1(s, pos, arc);
    } else if (num_arcs_out_[nextstate] == 1) {
      RemoveEpsPattern2(s, pos, arc);
    }
  }

RemoveEpsPattern1()

void RemoveEpsPattern1 ( StateId  s, size_t  pos, Arc  arc  )

inlineprivate

Definition at line 173 of file remove-eps-local-inl.h.

References fst::Divide(), rnnlm::i, and fst::Plus().

                                                         {
    const StateId nextstate = arc.nextstate;
    Weight total_removed = Weight::Zero(),
        total_kept = Weight::Zero();  // totals out of nextstate.
    std::vector<Arc> arcs_to_add;  // to add to state s.
    for (MutableArcIterator<MutableFst<Arc> > aiter_next(fst_, nextstate);
        !aiter_next.Done();
        aiter_next.Next()) {
      Arc nextarc = aiter_next.Value();
      if (nextarc.nextstate == non_coacc_state_) continue;  // deleted.
      Arc combined;
      if (CanCombineArcs(arc, nextarc, &combined)) {
        total_removed = reweight_plus_(total_removed, nextarc.weight);
        num_arcs_out_[nextstate]--;
        num_arcs_in_[nextarc.nextstate]--;
        nextarc.nextstate = non_coacc_state_;
        aiter_next.SetValue(nextarc);
        arcs_to_add.push_back(combined);
      } else {
        total_kept = reweight_plus_(total_kept, nextarc.weight);
      }
    }

    {  // now final-state.
      Weight next_final = fst_->Final(nextstate);
      if (next_final != Weight::Zero()) {
        Weight new_final;
        if (CanCombineFinal(arc, next_final, &new_final)) {
          total_removed = reweight_plus_(total_removed, next_final);
          if (fst_->Final(s) == Weight::Zero())
            num_arcs_out_[s]++;  // final is counted as arc.
          fst_->SetFinal(s, Plus(fst_->Final(s), new_final));
          num_arcs_out_[nextstate]--;
          fst_->SetFinal(nextstate, Weight::Zero());
        } else {
          total_kept = reweight_plus_(total_kept, next_final);
        }
      }
    }

    if (total_removed != Weight::Zero()) {  // did something...
      if (total_kept == Weight::Zero()) {  // removed everything: remove arc.
        num_arcs_out_[s]--;
        num_arcs_in_[arc.nextstate]--;
        arc.nextstate = non_coacc_state_;
        SetArc(s, pos, arc);
      } else {
        // Have to reweight.
        Weight total = reweight_plus_(total_removed, total_kept);
        Weight reweight = Divide(total_kept, total, DIVIDE_LEFT);  // <=1
        Reweight(s, pos, reweight);
      }
    }
    // Now add the arcs we were going to add.
    for (size_t i = 0; i < arcs_to_add.size(); i++) {
      num_arcs_out_[s]++;
      num_arcs_in_[arcs_to_add[i].nextstate]++;
      fst_->AddArc(s, arcs_to_add[i]);
    }
  }

RemoveEpsPattern2()

void RemoveEpsPattern2 ( StateId  s, size_t  pos, Arc  arc  )

inlineprivate

Definition at line 234 of file remove-eps-local-inl.h.

References fst::Plus().

                                                         {

    // Pattern 2 is where "nextstate" has only one arc out, counting
    // being-the-final-state as an arc, but possibly multiple arcs in.
    // Also, nextstate != s.

    const StateId nextstate = arc.nextstate;
    bool can_delete_next = (num_arcs_in_[nextstate] == 1);  // if
    // we combine, can delete the corresponding out-arc/final-prob
    // of nextstate.
    bool delete_arc = false;  // set to true if this arc to be deleted.

    Weight next_final = fst_->Final(arc.nextstate);
    if (next_final != Weight::Zero()) {  // nextstate has no actual arcs out, only final-prob.
      Weight new_final;
      if (CanCombineFinal(arc, next_final, &new_final)) {
        if (fst_->Final(s) == Weight::Zero())
          num_arcs_out_[s]++;  // final is counted as arc.
        fst_->SetFinal(s, Plus(fst_->Final(s), new_final));
        delete_arc = true;  // will delete "arc".
        if (can_delete_next) {
          num_arcs_out_[nextstate]--;
          fst_->SetFinal(nextstate, Weight::Zero());
        }
      }
    } else {  // has an arc but no final prob.
      MutableArcIterator<MutableFst<Arc> > aiter_next(fst_, nextstate);
      assert(!aiter_next.Done());
      while (aiter_next.Value().nextstate == non_coacc_state_) {
        aiter_next.Next();
        assert(!aiter_next.Done());
      }
      // now aiter_next points to a real arc out of nextstate.
      Arc nextarc = aiter_next.Value();
      Arc combined;
      if (CanCombineArcs(arc, nextarc, &combined)) {
        delete_arc = true;
        if (can_delete_next) {  // do it before we invalidate iterators
          num_arcs_out_[nextstate]--;
          num_arcs_in_[nextarc.nextstate]--;
          nextarc.nextstate = non_coacc_state_;
          aiter_next.SetValue(nextarc);
        }
        num_arcs_out_[s]++;
        num_arcs_in_[combined.nextstate]++;
        fst_->AddArc(s, combined);
      }
    }
    if (delete_arc) {
      num_arcs_out_[s]--;
      num_arcs_in_[nextstate]--;
      arc.nextstate = non_coacc_state_;
      SetArc(s, pos, arc);
    }
  }

Reweight()

void Reweight ( StateId  s, size_t  pos, Weight  reweight  )

inlineprivate

Definition at line 139 of file remove-eps-local-inl.h.

References fst::Divide(), and fst::Times().

                                                        {
    // Reweight is called from RemoveEpsPattern1; it is a step we
    // do to preserve stochasticity.  This function multiplies the
    // arc at (s, pos) by reweight and divides all the arcs [+final-prob]
    // out of the next state by the same.  This is only valid if
    // the next state has only one arc in and is not the start state.
    assert(reweight != Weight::Zero());
    MutableArcIterator<MutableFst<Arc> > aiter(fst_, s);
    aiter.Seek(pos);
    Arc arc = aiter.Value();
    assert(num_arcs_in_[arc.nextstate] == 1);
    arc.weight = Times(arc.weight, reweight);
    aiter.SetValue(arc);

    for (MutableArcIterator<MutableFst<Arc> > aiter_next(fst_, arc.nextstate);
         !aiter_next.Done();
         aiter_next.Next()) {
      Arc nextarc = aiter_next.Value();
      if (nextarc.nextstate != non_coacc_state_) {
        nextarc.weight = Divide(nextarc.weight, reweight, DIVIDE_LEFT);
        aiter_next.SetValue(nextarc);
      }
    }
    Weight final = fst_->Final(arc.nextstate);
    if (final != Weight::Zero()) {
      fst_->SetFinal(arc.nextstate, Divide(final, reweight, DIVIDE_LEFT));
    }
  }

SetArc()

void SetArc ( StateId  s, size_t  pos, const Arc &  arc  )

inlineprivate

Definition at line 132 of file remove-eps-local-inl.h.

                                                            {
    MutableArcIterator<MutableFst<Arc> > aiter(fst_, s);
    aiter.Seek(pos);
    aiter.SetValue(arc);
  }

Member Data Documentation

fst_

MutableFst<Arc>* fst_

private

Definition at line 65 of file remove-eps-local-inl.h.

non_coacc_state_

StateId non_coacc_state_

private

Definition at line 66 of file remove-eps-local-inl.h.

num_arcs_in_

std::vector<StateId> num_arcs_in_

private

Definition at line 67 of file remove-eps-local-inl.h.

num_arcs_out_

std::vector<StateId> num_arcs_out_

private

Definition at line 69 of file remove-eps-local-inl.h.

reweight_plus_

ReweightPlus reweight_plus_

private

Definition at line 71 of file remove-eps-local-inl.h.

---

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

• fstext/remove-eps-local-inl.h