DeterminizerStar< F >::EpsilonClosure Class Reference

Collaboration diagram for DeterminizerStar< F >::EpsilonClosure:

Classes
struct	EpsilonClosureInfo

Public Member Functions
	EpsilonClosure (const Fst< Arc > *ifst, int max_states, StringRepository< Label, StringId > *repository, float delta)
void	GetEpsilonClosure (const std::vector< Element > &input_subset, std::vector< Element > *output_subset)

Private Member Functions
void	AddOneElement (const Element &elem, const Weight &unprocessed_weight)
void	ExpandOneElement (const Element &elem, bool sorted, const Weight &unprocessed_weight, bool save_to_queue_2=false)

Private Attributes
std::deque< typename Arc::StateId >	queue_
std::vector< Element >	queue_2_
std::vector< int >	id_to_index_
std::vector< EpsilonClosureInfo >	ecinfo_
const Fst< Arc > *	ifst_
int	max_states_
StringRepository< Label, StringId > *	repository_
float	delta_

Detailed Description

template<class F>
class fst::DeterminizerStar< F >::EpsilonClosure

Definition at line 346 of file determinize-star-inl.h.

Constructor & Destructor Documentation

EpsilonClosure()

EpsilonClosure ( const Fst< Arc > *  ifst, int  max_states, StringRepository< Label, StringId > *  repository, float  delta  )

inline

Definition at line 348 of file determinize-star-inl.h.

                                                                   :
      ifst_(ifst), max_states_(max_states), repository_(repository),
      delta_(delta) {

    }

Member Function Documentation

AddOneElement()

void AddOneElement ( const Element &  elem, const Weight &  unprocessed_weight  )

private

Definition at line 746 of file determinize-star-inl.h.

References fst::ApproxEqual(), DeterminizerStar< F >::EpsilonClosure::EpsilonClosureInfo::element, rnnlm::i, DeterminizerStar< F >::EpsilonClosure::EpsilonClosureInfo::in_queue, KALDI_ERR, fst::Plus(), DeterminizerStar< F >::Element::state, DeterminizerStar< F >::Element::string, DeterminizerStar< F >::Element::weight, and DeterminizerStar< F >::EpsilonClosure::EpsilonClosureInfo::weight_to_process.

Referenced by DeterminizerStar< F >::EpsilonClosure::GetEpsilonClosure().

                                                                          {
  // first we try to find the element info in the ecinfo_ vector
  int index = -1;
  if (elem.state < id_to_index_.size()) {
    index = id_to_index_[elem.state];
  }
  if (index != -1) {
    if (index >= ecinfo_.size()) {
      index = -1;
    }
    // since ecinfo_ might store outdated information, we need to check
    else if (ecinfo_[index].element.state != elem.state) {
      index = -1;
    }
  }

  if (index == -1) {
    // was no such StateId: insert and add to queue.
    ecinfo_.push_back(EpsilonClosureInfo(elem, unprocessed_weight, true));
    size_t size = id_to_index_.size();
    if (size < elem.state + 1) {
      // double the size to reduce memory operations
      id_to_index_.resize(2 * elem.state + 1, -1);
    }
    id_to_index_[elem.state] = ecinfo_.size() - 1;
    queue_.push_back(elem.state);

  } else {  // one is already there.  Add weights.
    EpsilonClosureInfo &info = ecinfo_[index];
    if (info.element.string != elem.string) {
      // Non-functional FST.
      std::ostringstream ss;
      ss << "FST was not functional -> not determinizable.";
      { // Print some debugging information.  Can be helpful to debug
        // the inputs when FSTs are mysteriously non-functional.
        std::vector<Label> tmp_seq;
        repository_->SeqOfId(info.element.string, &tmp_seq);
        ss << "\nFirst string:";
        for (size_t i = 0; i < tmp_seq.size(); i++)
          ss << ' ' << tmp_seq[i];
        ss << "\nSecond string:";
        repository_->SeqOfId(elem.string, &tmp_seq);
        for (size_t i = 0; i < tmp_seq.size(); i++)
          ss << ' ' << tmp_seq[i];
      }
      KALDI_ERR << ss.str();
    }

    info.weight_to_process =
          Plus(info.weight_to_process, unprocessed_weight);

    if (!info.in_queue) {
      // this is because the code in "else" below: the
      // iter->second.weight_to_process might not be Zero()
      Weight weight = Plus(info.element.weight, info.weight_to_process);

      // What is done below is, we propagate the weight (by adding them
      // to the queue only when the change is big enough;
      // otherwise we just store the weight, until before returning
      // we add the element.weight and weight_to_process together
      if (! ApproxEqual(weight, info.element.weight, delta_)) {
        // add extra part of weight to queue.
        info.in_queue = true;
        queue_.push_back(elem.state);
      }
    }
  }
}

ExpandOneElement()

void ExpandOneElement ( const Element &  elem, bool  sorted, const Weight &  unprocessed_weight, bool  save_to_queue_2 = false  )

private

Definition at line 816 of file determinize-star-inl.h.

References DeterminizerStar< F >::Element::state, DeterminizerStar< F >::Element::string, fst::Times(), and DeterminizerStar< F >::Element::weight.

                                                                {
  StringId str = elem.string; // copy it here because there is an iterator-
                // - invalidation problem (it really happens for some FSTs)

  // now we are going to propagate the "unprocessed_weight"
  for (ArcIterator<Fst<Arc> > aiter(*ifst_, elem.state);
       !aiter.Done(); aiter.Next()) {
    const Arc &arc = aiter.Value();
    if (sorted && arc.ilabel > 0) {
      break;
      // Break from the loop: due to sorting there will be no
      // more transitions with epsilons as input labels.
    }
    if (arc.ilabel != 0) {
      continue;  // we only process epsilons here
    }
    Element next_elem;
    next_elem.state = arc.nextstate;
    next_elem.weight = Weight::Zero();
    Weight next_unprocessed_weight
                   = Times(unprocessed_weight, arc.weight);

    // now must append strings
    if (arc.olabel == 0) {
      next_elem.string = str;
    } else {
      std::vector<Label> seq;
      repository_->SeqOfId(str, &seq);
      if (arc.olabel != 0)
        seq.push_back(arc.olabel);
      next_elem.string = repository_->IdOfSeq(seq);
    }
    if (save_to_queue_2) {
      next_elem.weight = next_unprocessed_weight;
      queue_2_.push_back(next_elem);
    } else {
      AddOneElement(next_elem, next_unprocessed_weight);
    }
  }
}

GetEpsilonClosure()

void GetEpsilonClosure	(	const std::vector< Element > &	input_subset,
		std::vector< Element > *	output_subset
	)

Definition at line 652 of file determinize-star-inl.h.

References DeterminizerStar< F >::EpsilonClosure::AddOneElement(), DeterminizerStar< F >::EpsilonClosure::EpsilonClosureInfo::element, rnnlm::i, DeterminizerStar< F >::EpsilonClosure::EpsilonClosureInfo::in_queue, KALDI_ERR, fst::Plus(), DeterminizerStar< F >::Element::state, DeterminizerStar< F >::Element::string, DeterminizerStar< F >::Element::weight, and DeterminizerStar< F >::EpsilonClosure::EpsilonClosureInfo::weight_to_process.

Referenced by fst::DeterminizeStar().

                                                                          {
  ecinfo_.resize(0);
  size_t size = input_subset.size();
  // find whether input fst is known to be sorted in input label.
  bool sorted =
          ((ifst_->Properties(kILabelSorted, false) & kILabelSorted) != 0);

  // size is still the input_subset.size()
  for (size_t i = 0; i < size; i++) {
    ExpandOneElement(input_subset[i], sorted, input_subset[i].weight, true);
  }

  size_t s = queue_2_.size();
  if (s == 0) {
    *output_subset = input_subset;
    return;
  } else {
    // queue_2 not empty. Need to create the vector<info>
    for (size_t i = 0; i < size; i++) {
      // the weight has not been processed yet,
      // so put all of them in the "weight_to_process"
      ecinfo_.push_back(EpsilonClosureInfo(input_subset[i],
                                           input_subset[i].weight,
                                           false));
      ecinfo_.back().element.weight = Weight::Zero(); // clear the weight

      if (id_to_index_.size() < input_subset[i].state + 1) {
        id_to_index_.resize(2 * input_subset[i].state + 1, -1);
      }
      id_to_index_[input_subset[i].state] = ecinfo_.size() - 1;
    }
  }

  {
    Element elem;
    elem.weight = Weight::Zero();
    for (size_t i = 0; i < s; i++) {
      elem.state = queue_2_[i].state;
      elem.string = queue_2_[i].string;
      AddOneElement(elem, queue_2_[i].weight);
    }
    queue_2_.resize(0);
  }

  int counter = 0; // relates to max-states option, used for test.
  while (!queue_.empty()) {
    InputStateId id = queue_.front();

    // no need to check validity of the index
    // since anything in the queue we are sure they're in the "virtual set"
    int index = id_to_index_[id];
    EpsilonClosureInfo &info = ecinfo_[index];
    Element &elem = info.element;
    Weight unprocessed_weight = info.weight_to_process;

    elem.weight = Plus(elem.weight, unprocessed_weight);
    info.weight_to_process = Weight::Zero();

    info.in_queue = false;
    queue_.pop_front();

    if (max_states_ > 0 && counter++ > max_states_) {
      KALDI_ERR << "Determinization aborted since looped more than "
                << max_states_ << " times during epsilon closure";
    }

    // generally we need to be careful about iterator-invalidation problem
    // here we pass a reference (elem), which could be an issue.
    // In the beginning of ExpandOneElement, we make a copy of elem.string
    // to avoid that issue
    ExpandOneElement(elem, sorted, unprocessed_weight);
  }

  {
    // this sorting is based on StateId
    sort(ecinfo_.begin(), ecinfo_.end());

    output_subset->clear();

    size = ecinfo_.size();
    output_subset->reserve(size);
    for (size_t i = 0; i < size; i++) {
      EpsilonClosureInfo& info = ecinfo_[i];
      if (info.weight_to_process != Weight::Zero()) {
        info.element.weight = Plus(info.element.weight, info.weight_to_process);
      }
      output_subset->push_back(info.element);
    }
  }
}

Member Data Documentation

delta_

float delta_

private

Definition at line 427 of file determinize-star-inl.h.

ecinfo_

std::vector<EpsilonClosureInfo> ecinfo_

private

Definition at line 405 of file determinize-star-inl.h.

id_to_index_

std::vector<int> id_to_index_

private

Definition at line 400 of file determinize-star-inl.h.

ifst_

const Fst<Arc>* ifst_

private

Definition at line 424 of file determinize-star-inl.h.

max_states_

int max_states_

private

Definition at line 425 of file determinize-star-inl.h.

queue_

std::deque<typename Arc::StateId> queue_

private

Definition at line 390 of file determinize-star-inl.h.

queue_2_

std::vector<Element> queue_2_

private

Definition at line 391 of file determinize-star-inl.h.

repository_

StringRepository<Label, StringId>* repository_

private

Definition at line 426 of file determinize-star-inl.h.

---

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

• fstext/determinize-star-inl.h