GrammarFstPreparer Class Reference

Collaboration diagram for GrammarFstPreparer:

Classes
struct	ArcCategory

Public Types
using	FST = VectorFst< StdArc >
using	Arc = StdArc
using	StateId = Arc::StateId
using	Label = Arc::Label
using	Weight = Arc::Weight

Public Member Functions
	GrammarFstPreparer (int32 nonterm_phones_offset, VectorFst< StdArc > *fst)
void	Prepare ()

Private Member Functions
bool	IsSpecialState (StateId s) const
void	MaybeAddFinalProbToState (StateId s)
bool	NeedEpsilons (StateId s) const
bool	IsEntryState (StateId s) const
void	FixArcsToFinalStates (StateId s)
void	GetCategoryOfArc (const Arc &arc, ArcCategory *arc_category) const
void	InsertEpsilonsForState (StateId s)
int32	GetPhoneSymbolFor (enum NonterminalValues n) const

Private Attributes
int32	nonterm_phones_offset_
VectorFst< StdArc > *	fst_
StateId	orig_num_states_
StateId	simple_final_state_

Detailed Description

Definition at line 541 of file grammar-fst.cc.

Member Typedef Documentation

Arc

using Arc = StdArc

Definition at line 544 of file grammar-fst.cc.

FST

using FST = VectorFst<StdArc>

Definition at line 543 of file grammar-fst.cc.

Label

using Label = Arc::Label

Definition at line 546 of file grammar-fst.cc.

StateId

using StateId = Arc::StateId

Definition at line 545 of file grammar-fst.cc.

Weight

using Weight = Arc::Weight

Definition at line 547 of file grammar-fst.cc.

Constructor & Destructor Documentation

GrammarFstPreparer()

GrammarFstPreparer ( int32  nonterm_phones_offset, VectorFst< StdArc > *  fst  )

inline

Definition at line 549 of file grammar-fst.cc.

                                            :
      nonterm_phones_offset_(nonterm_phones_offset),
      fst_(fst), orig_num_states_(fst->NumStates()),
      simple_final_state_(kNoStateId) { }

Member Function Documentation

FixArcsToFinalStates()

void FixArcsToFinalStates ( StateId  s )

private

Definition at line 810 of file grammar-fst.cc.

References FasterDecoder::fst_, fst::GetEncodingMultiple(), KALDI_ASSERT, fst::kNontermBigNumber, fst::kNontermEnd, and fst::Times().

                                                       {
  int32 encoding_multiple = GetEncodingMultiple(nonterm_phones_offset_),
      big_number = kNontermBigNumber;
  for (MutableArcIterator<FST> aiter(fst_, s ); !aiter.Done(); aiter.Next()) {
    Arc arc = aiter.Value();
    if (arc.ilabel < big_number)
      continue;
    int32 nonterminal = (arc.ilabel - big_number) / encoding_multiple;
    if (nonterminal ==  GetPhoneSymbolFor(kNontermEnd)) {
      KALDI_ASSERT(fst_->NumArcs(arc.nextstate) == 0 &&
                   fst_->Final(arc.nextstate) != Weight::Zero());
      if (fst_->Final(arc.nextstate) == Weight::One())
        continue;  // There is no problem to fix.
      if (simple_final_state_ == kNoStateId) {
        simple_final_state_ = fst_->AddState();
        fst_->SetFinal(simple_final_state_, Weight::One());
      }
      arc.weight = Times(arc.weight, fst_->Final(arc.nextstate));
      arc.nextstate = simple_final_state_;
      aiter.SetValue(arc);
    }
  }
}

GetCategoryOfArc()

void GetCategoryOfArc ( const Arc &  arc, ArcCategory *  arc_category  ) const

private

Definition at line 855 of file grammar-fst.cc.

References fst::GetEncodingMultiple(), KALDI_ERR, fst::kNontermBigNumber, fst::kNontermEnd, fst::kNontermUserDefined, GrammarFstPreparer::ArcCategory::nextstate, GrammarFstPreparer::ArcCategory::nonterminal, and GrammarFstPreparer::ArcCategory::olabel.

                                                     {
  int32 encoding_multiple = GetEncodingMultiple(nonterm_phones_offset_),
      big_number = kNontermBigNumber;

  int32 ilabel = arc.ilabel;
  if (ilabel < big_number) {
    arc_category->nonterminal = 0;
    arc_category->nextstate = kNoStateId;
    arc_category->olabel = 0;
  } else {
    int32 nonterminal = (ilabel - big_number) / encoding_multiple;
    arc_category->nonterminal = nonterminal;
    if (nonterminal <= nonterm_phones_offset_) {
      KALDI_ERR << "Problem decoding nonterminal symbol "
          "(wrong --nonterm-phones-offset option?), ilabel="
                << ilabel;
    }
    if (nonterminal >= GetPhoneSymbolFor(kNontermUserDefined)) {
      // This is a user-defined symbol.
      arc_category->nextstate = arc.nextstate;
      arc_category->olabel = arc.olabel;
    } else {
      arc_category->nextstate = kNoStateId;
      if (nonterminal == GetPhoneSymbolFor(kNontermEnd))
        arc_category->olabel = arc.olabel;
      else
        arc_category->olabel = 0;
    }
  }
}

GetPhoneSymbolFor()

int32 GetPhoneSymbolFor ( enum NonterminalValues  n ) const

inlineprivate

Definition at line 676 of file grammar-fst.cc.

References rnnlm::n.

                                                                 {
    return nonterm_phones_offset_ + static_cast<int32>(n);
  }

InsertEpsilonsForState()

void InsertEpsilonsForState ( StateId  s )

private

Definition at line 888 of file grammar-fst.cc.

References FasterDecoder::fst_, rnnlm::i, KALDI_ASSERT, KALDI_ERR, fst::kNontermBegin, fst::kNontermReenter, kaldi::LogAdd(), GrammarFstPreparer::ArcCategory::nonterminal, and GrammarFstPreparer::ArcCategory::olabel.

                                                         {
  // Maps from category of arc, to a pair:
  //  the StateId is the state corresponding to that category.
  //  the float is the cost on the arc leading to that state;
  //   we compute the value that corresponds to the sum of the probabilities
  //   of the leaving arcs, bearing in mind that p = exp(-cost).
  // We don't insert the arc-category whose 'nonterminal' is 0 here (i.e. the
  // category for normal arcs); those arcs stay at this state.
  std::map<ArcCategory, std::pair<StateId, float> > category_to_state;

  // This loop sets up 'category_to_state'.
  for (fst::ArcIterator<FST> aiter(*fst_, s); !aiter.Done(); aiter.Next()) {
    const Arc &arc = aiter.Value();
    ArcCategory category;
    GetCategoryOfArc(arc, &category);
    int32 nonterminal = category.nonterminal;
    if (nonterminal == 0)
      continue;
    if (nonterminal == GetPhoneSymbolFor(kNontermBegin) ||
        nonterminal == GetPhoneSymbolFor(kNontermReenter)) {
      KALDI_ERR << "Something went wrong; did not expect to insert epsilons "
          "for this type of state.";
    }
    auto iter = category_to_state.find(category);
    if (iter == category_to_state.end()) {
      StateId new_state = fst_->AddState();
      float cost = arc.weight.Value();
      category_to_state[category] = std::pair<StateId, float>(new_state, cost);
    } else {
      std::pair<StateId, float> &p = iter->second;
      p.second = -kaldi::LogAdd(-p.second, -arc.weight.Value());
    }
  }

  KALDI_ASSERT(!category_to_state.empty());  // would be a code error.

  // 'arcs_from_this_state' is a place to put arcs that will put on this state
  // after we delete all its existing arcs.
  std::vector<Arc> arcs_from_this_state;
  arcs_from_this_state.reserve(fst_->NumArcs(s) + category_to_state.size());

  // add arcs corresponding to transitions to the newly created states, to
  // 'arcs_from_this_state'
  for (std::map<ArcCategory, std::pair<StateId, float> >::const_iterator
           iter = category_to_state.begin(); iter != category_to_state.end();
       ++iter) {
    const ArcCategory &category = iter->first;
    StateId new_state = iter->second.first;
    float cost = iter->second.second;
    Arc arc;
    arc.ilabel = 0;
    arc.olabel = category.olabel;
    arc.weight = Weight(cost);
    arc.nextstate = new_state;
    arcs_from_this_state.push_back(arc);
  }

  // Now add to 'arcs_from_this_state', and to the newly created states,
  // arcs corresponding to each of the arcs that were originally leaving
  // this state.
  for (fst::ArcIterator<FST> aiter(*fst_, s); !aiter.Done(); aiter.Next()) {
    const Arc &arc = aiter.Value();
    ArcCategory category;
    GetCategoryOfArc(arc, &category);
    int32 nonterminal = category.nonterminal;
    if (nonterminal == 0) { // this arc remains unchanged; we'll put it back later.
      arcs_from_this_state.push_back(arc);
      continue;
    }
    auto iter = category_to_state.find(category);
    KALDI_ASSERT(iter != category_to_state.end());
    Arc new_arc;
    new_arc.ilabel = arc.ilabel;
    if (arc.olabel == category.olabel) {
      new_arc.olabel = 0;  // the olabel went on the epsilon-input arc.
    } else {
      KALDI_ASSERT(category.olabel == 0);
      new_arc.olabel = arc.olabel;
    }
    StateId new_state = iter->second.first;
    float epsilon_arc_cost = iter->second.second;
    new_arc.weight = Weight(arc.weight.Value() - epsilon_arc_cost);
    new_arc.nextstate = arc.nextstate;
    fst_->AddArc(new_state, new_arc);
  }

  fst_->DeleteArcs(s);
  for (size_t i = 0; i < arcs_from_this_state.size(); i++) {
    fst_->AddArc(s, arcs_from_this_state[i]);
  }
  // leave the final-prob on this state as it was before.
}

IsEntryState()

bool IsEntryState ( StateId  s ) const

private

Definition at line 705 of file grammar-fst.cc.

References FasterDecoder::fst_, fst::GetEncodingMultiple(), fst::kNontermBegin, and fst::kNontermBigNumber.

                                                     {
  int32 big_number = kNontermBigNumber,
      encoding_multiple = GetEncodingMultiple(nonterm_phones_offset_);

  for (ArcIterator<FST> aiter(*fst_, s ); !aiter.Done(); aiter.Next()) {
    const Arc &arc = aiter.Value();
    int32 nonterminal = (arc.ilabel - big_number) /
        encoding_multiple;
    // we check that at least one has label with nonterminal equal to #nonterm_begin...
    // in fact they will all have this value if at least one does, and this was checked
    // in NeedEpsilons().
    if (nonterminal == GetPhoneSymbolFor(kNontermBegin))
      return true;
  }
  return false;
}

IsSpecialState()

bool IsSpecialState ( StateId  s ) const

private

Definition at line 690 of file grammar-fst.cc.

References FasterDecoder::fst_, KALDI_GRAMMAR_FST_SPECIAL_WEIGHT, KALDI_WARN, and fst::kNontermBigNumber.

                                                       {
  if (fst_->Final(s).Value() == KALDI_GRAMMAR_FST_SPECIAL_WEIGHT) {
    // TODO: find a way to detect if it was a coincidence, or not make it an
    // error, because in principle a user-defined grammar could contain this
    // special cost.
    KALDI_WARN << "It looks like you are calling PrepareForGrammarFst twice.";
  }
  for (ArcIterator<FST> aiter(*fst_, s ); !aiter.Done(); aiter.Next()) {
    const Arc &arc = aiter.Value();
    if (arc.ilabel >= kNontermBigNumber) // 1 million
      return true;
  }
  return false;
}

MaybeAddFinalProbToState()

void MaybeAddFinalProbToState ( StateId  s )

private

Definition at line 834 of file grammar-fst.cc.

References FasterDecoder::fst_, fst::GetEncodingMultiple(), KALDI_ASSERT, KALDI_ERR, KALDI_GRAMMAR_FST_SPECIAL_WEIGHT, fst::kNontermBegin, fst::kNontermBigNumber, fst::kNontermEnd, and fst::kNontermUserDefined.

                                                           {
  if (fst_->Final(s) != Weight::Zero()) {
    // Something went wrong and it will require some debugging.  In Prepare(),
    // if we detected that the special state had a nonzero final-prob, we
    // would have inserted epsilons to remove it, so there may be a bug in
    // this class's code.
    KALDI_ERR << "State already final-prob.";
  }
  ArcIterator<FST> aiter(*fst_, s );
  KALDI_ASSERT(!aiter.Done());
  const Arc &arc = aiter.Value();
  int32 encoding_multiple = GetEncodingMultiple(nonterm_phones_offset_),
      big_number = kNontermBigNumber,
      nonterminal = (arc.ilabel - big_number) / encoding_multiple;
  KALDI_ASSERT(nonterminal >= GetPhoneSymbolFor(kNontermBegin));
  if (nonterminal == GetPhoneSymbolFor(kNontermEnd) ||
      nonterminal >= GetPhoneSymbolFor(kNontermUserDefined)) {
    fst_->SetFinal(s, Weight(KALDI_GRAMMAR_FST_SPECIAL_WEIGHT));
  }
}

NeedEpsilons()

bool NeedEpsilons ( StateId  s ) const

private

Definition at line 723 of file grammar-fst.cc.

References FasterDecoder::fst_, fst::GetEncodingMultiple(), KALDI_ERR, fst::kNontermBegin, fst::kNontermBigNumber, fst::kNontermEnd, fst::kNontermReenter, fst::kNontermUserDefined, GrammarFstPreparer::ArcCategory::nextstate, GrammarFstPreparer::ArcCategory::nonterminal, and GrammarFstPreparer::ArcCategory::olabel.

                                                     {

  // See the documentation for GetCategoryOfArc() for explanation of what these are.
  std::set<ArcCategory> categories;

  if (fst_->Final(s) != Weight::Zero()) {
    // A state having a final-prob is considered the same as it having
    // a non-nonterminal arc out of it.. this would be like a transition
    // within the same FST.
    ArcCategory category;
    category.nonterminal = 0;
    category.nextstate = kNoStateId;
    category.olabel = 0;
    categories.insert(category);
  }

  int32 big_number = kNontermBigNumber,
      encoding_multiple = GetEncodingMultiple(nonterm_phones_offset_);

  for (ArcIterator<FST> aiter(*fst_, s ); !aiter.Done(); aiter.Next()) {
    const Arc &arc = aiter.Value();
    ArcCategory category;
    GetCategoryOfArc(arc, &category);
    categories.insert(category);

    // the rest of this block is just checking.
    int32 nonterminal = category.nonterminal;

    if (nonterminal >= GetPhoneSymbolFor(kNontermUserDefined)) {
      // Check that the destination state of this arc has arcs with
      // kNontermReenter on them.  We'll separately check that such states
      // don't have other types of arcs leaving them (search for
      // kNontermReenter below), so it's sufficient to check the first arc.
      ArcIterator<FST> next_aiter(*fst_, arc.nextstate);
      if (next_aiter.Done())
        KALDI_ERR << "Destination state of a user-defined nonterminal "
            "has no arcs leaving it.";
      const Arc &next_arc = next_aiter.Value();
      int32 next_nonterminal = (next_arc.ilabel - big_number) /
          encoding_multiple;
      if (next_nonterminal != GetPhoneSymbolFor(kNontermReenter)) {
        KALDI_ERR << "Expected arcs with user-defined nonterminals to be "
            "followed by arcs with kNontermReenter.";
      }
    }
    if (nonterminal == GetPhoneSymbolFor(kNontermBegin) &&
        s != fst_->Start()) {
      KALDI_ERR << "#nonterm_begin symbol is present but this is not the "
          "first state.  Did you do fstdeterminizestar while compiling?";
    }
    if (nonterminal == GetPhoneSymbolFor(kNontermEnd)) {
      if (fst_->NumArcs(arc.nextstate) != 0 ||
          fst_->Final(arc.nextstate) == Weight::Zero()) {
        KALDI_ERR << "Arc with kNontermEnd is not the final arc.";
      }
    }
  }
  if (categories.size() > 1) {
    // This state has arcs leading to multiple FST instances.
    // Do some checking to see that there is nothing really unexpected in
    // there.
    for (std::set<ArcCategory>::const_iterator
             iter = categories.begin();
         iter != categories.end(); ++iter) {
      int32 nonterminal = iter->nonterminal;
      if (nonterminal == nonterm_phones_offset_ + kNontermBegin ||
          nonterminal == nonterm_phones_offset_ + kNontermReenter)
        // we don't expect any state which has symbols like (kNontermBegin:p1)
        // on arcs coming out of it, to also have other types of symbol.  The
        // same goes for kNontermReenter.
        KALDI_ERR << "We do not expect states with arcs of type "
            "kNontermBegin/kNontermReenter coming out of them, to also have "
            "other types of arc.";
    }
  }
  // the first half of the || below relates to olabels on arcs with either
  // user-defined nonterminals or #nonterm_end (which would become 'leaving_arc'
  // in the CombineArcs() function of GrammarFst).  That function does not allow
  // nonzero olabels on 'leaving_arc', which would be a problem if the
  // 'arriving' arc had nonzero olabels, so we solve this by introducing
  // input-epsilon arcs and putting the olabels on them instead.
  bool need_epsilons = (categories.size() == 1 &&
                        categories.begin()->olabel != 0) ||
      categories.size() > 1;
  return need_epsilons;
}

Prepare()

void Prepare ( )

inline

Definition at line 555 of file grammar-fst.cc.

References FasterDecoder::fst_, fst::InputDeterminizeSingleState(), KALDI_ERR, and KALDI_LOG.

Referenced by fst::PrepareForGrammarFst().

                 {
    if (fst_->Start() == kNoStateId) {
      KALDI_ERR << "FST has no states.";
    }
    for (StateId s = 0; s < fst_->NumStates(); s++) {
      if (IsSpecialState(s)) {
        if (NeedEpsilons(s)) {
          InsertEpsilonsForState(s);
          // This state won't be treated as a 'special' state any more;
          // all 'special' arcs (arcs with ilabels >= kNontermBigNumber)
          // have been moved and now leave from newly created states that
          // this state transitions to via epsilons arcs.
        } else {
          // OK, state s is a special state.
          FixArcsToFinalStates(s);
          MaybeAddFinalProbToState(s);
          // The following ensures that the start-state of sub-FSTs only has
          // a single arc per left-context phone (the graph-building recipe can
          // end up creating more than one if there were disambiguation symbols,
          // e.g. for langauge model backoff).
          if (s == fst_->Start() && IsEntryState(s))
            InputDeterminizeSingleState(s, fst_);
        }
      }
    }
    StateId num_new_states = fst_->NumStates() - orig_num_states_;
    KALDI_LOG << "Added " << num_new_states << " new states while "
        "preparing for grammar FST.";
  }

Member Data Documentation

fst_

VectorFst<StdArc>* fst_

private

Definition at line 681 of file grammar-fst.cc.

nonterm_phones_offset_

int32 nonterm_phones_offset_

private

Definition at line 680 of file grammar-fst.cc.

orig_num_states_

StateId orig_num_states_

private

Definition at line 682 of file grammar-fst.cc.

simple_final_state_

StateId simple_final_state_

private

Definition at line 687 of file grammar-fst.cc.

---

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

• decoder/grammar-fst.cc