LatticeDeterminizer< Weight, IntType > Class Template Reference

#include <determinize-lattice-inl.h>

Collaboration diagram for LatticeDeterminizer< Weight, IntType >:

Classes
struct	Element
class	PairComparator
class	SubsetEqual
class	SubsetEqualStates
class	SubsetKey
struct	TempArc

Public Types
typedef CompactLatticeWeightTpl< Weight, IntType >	CompactWeight
typedef ArcTpl< CompactWeight >	CompactArc
typedef ArcTpl< Weight >	Arc

Public Member Functions
void	Output (MutableFst< CompactArc > *ofst, bool destroy=true)
void	Output (MutableFst< Arc > *ofst, bool destroy=true)
	LatticeDeterminizer (const Fst< Arc > &ifst, DeterminizeLatticeOptions opts)
void	FreeMostMemory ()
	~LatticeDeterminizer ()
void	RebuildRepository ()
bool	CheckMemoryUsage ()
bool	Determinize (bool *debug_ptr)

Private Types
enum	IsymbolOrFinal { OSF_UNKNOWN = 0, OSF_NO = 1, OSF_YES = 2 }
typedef Arc::Label	Label
typedef Arc::StateId	StateId
typedef Arc::StateId	InputStateId
typedef Arc::StateId	OutputStateId
typedef LatticeStringRepository< IntType >	StringRepositoryType
typedef const StringRepositoryType::Entry *	StringId
typedef std::unordered_map< const std::vector< Element > *, OutputStateId, SubsetKey, SubsetEqual >	MinimalSubsetHash
typedef std::unordered_map< const std::vector< Element > *, Element, SubsetKey, SubsetEqual >	InitialSubsetHash

Private Member Functions
void	ConvertToMinimal (std::vector< Element > *subset)
OutputStateId	MinimalToStateId (const std::vector< Element > &subset)
OutputStateId	InitialToStateId (const std::vector< Element > &subset_in, Weight *remaining_weight, StringId *common_prefix)
int	Compare (const Weight &a_w, StringId a_str, const Weight &b_w, StringId b_str) const
void	EpsilonClosure (std::vector< Element > *subset)
void	ProcessFinal (OutputStateId output_state)
void	NormalizeSubset (std::vector< Element > *elems, Weight *tot_weight, StringId *common_str)
void	MakeSubsetUnique (std::vector< Element > *subset)
void	ProcessTransition (OutputStateId state, Label ilabel, std::vector< Element > *subset)
void	ProcessTransitions (OutputStateId output_state)
void	ProcessState (OutputStateId output_state)
void	Debug ()
bool	IsIsymbolOrFinal (InputStateId state)
void	InitializeDeterminization ()
	KALDI_DISALLOW_COPY_AND_ASSIGN (LatticeDeterminizer)

Private Attributes
std::vector< std::vector< Element > *>	output_states_
std::vector< std::vector< TempArc > >	output_arcs_
int	num_arcs_
int	num_elems_
const Fst< Arc > *	ifst_
DeterminizeLatticeOptions	opts_
SubsetKey	hasher_
SubsetEqual	equal_
bool	determinized_
MinimalSubsetHash	minimal_hash_
InitialSubsetHash	initial_hash_
std::vector< OutputStateId >	queue_
std::vector< std::pair< Label, Element > >	all_elems_tmp_
std::vector< char >	isymbol_or_final_
LatticeStringRepository< IntType >	repository_

Detailed Description

template<class Weight, class IntType>
class fst::LatticeDeterminizer< Weight, IntType >

Definition at line 258 of file determinize-lattice-inl.h.

Member Typedef Documentation

Arc

typedef ArcTpl<Weight> Arc

Definition at line 266 of file determinize-lattice-inl.h.

CompactArc

typedef ArcTpl<CompactWeight> CompactArc

Definition at line 265 of file determinize-lattice-inl.h.

CompactWeight

typedef CompactLatticeWeightTpl<Weight, IntType> CompactWeight

Definition at line 264 of file determinize-lattice-inl.h.

InitialSubsetHash

typedef std::unordered_map<const std::vector<Element>*, Element, SubsetKey, SubsetEqual> InitialSubsetHash

private

Definition at line 641 of file determinize-lattice-inl.h.

InputStateId

typedef Arc::StateId InputStateId

private

Definition at line 532 of file determinize-lattice-inl.h.

Label

typedef Arc::Label Label

private

Definition at line 530 of file determinize-lattice-inl.h.

MinimalSubsetHash

typedef std::unordered_map<const std::vector<Element>*, OutputStateId, SubsetKey, SubsetEqual> MinimalSubsetHash

private

Definition at line 633 of file determinize-lattice-inl.h.

OutputStateId

typedef Arc::StateId OutputStateId

private

Definition at line 533 of file determinize-lattice-inl.h.

StateId

typedef Arc::StateId StateId

private

Definition at line 531 of file determinize-lattice-inl.h.

StringId

typedef const StringRepositoryType::Entry* StringId

private

Definition at line 538 of file determinize-lattice-inl.h.

StringRepositoryType

typedef LatticeStringRepository<IntType> StringRepositoryType

private

Definition at line 537 of file determinize-lattice-inl.h.

Member Enumeration Documentation

IsymbolOrFinal

enum IsymbolOrFinal

private

Enumerator
OSF_UNKNOWN
OSF_NO
OSF_YES

Definition at line 1250 of file determinize-lattice-inl.h.

{ OSF_UNKNOWN = 0, OSF_NO = 1, OSF_YES = 2 };

Constructor & Destructor Documentation

LatticeDeterminizer()

LatticeDeterminizer ( const Fst< Arc > &  ifst, DeterminizeLatticeOptions  opts  )

inline

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

References KALDI_ASSERT.

                                                     :
      num_arcs_(0), num_elems_(0), ifst_(ifst.Copy()), opts_(opts),
      equal_(opts_.delta), determinized_(false),
      minimal_hash_(3, hasher_, equal_), initial_hash_(3, hasher_, equal_) {
    KALDI_ASSERT(Weight::Properties() & kIdempotent); // this algorithm won't
    // work correctly otherwise.
  }

~LatticeDeterminizer()

~LatticeDeterminizer ( )

inline

Definition at line 431 of file determinize-lattice-inl.h.

                         {
    FreeMostMemory(); // rest is deleted by destructors.
  }

Member Function Documentation

CheckMemoryUsage()

bool CheckMemoryUsage ( )

inline

Definition at line 468 of file determinize-lattice-inl.h.

References KALDI_VLOG, and KALDI_WARN.

                          {
    int32 repo_size = repository_.MemSize(),
        arcs_size = num_arcs_ * sizeof(TempArc),
        elems_size = num_elems_ * sizeof(Element),
        total_size = repo_size + arcs_size + elems_size;
    if (opts_.max_mem > 0 && total_size > opts_.max_mem) { // We passed the memory threshold.
      // This is usually due to the repository getting large, so we
      // clean this out.
      RebuildRepository();
      int32 new_repo_size = repository_.MemSize(),
          new_total_size = new_repo_size + arcs_size + elems_size;

      KALDI_VLOG(2) << "Rebuilt repository in determinize-lattice: repository shrank from "
                    << repo_size << " to " << new_repo_size << " bytes (approximately)";

      if (new_total_size > static_cast<int32>(opts_.max_mem * 0.8)) {
        // Rebuilding didn't help enough-- we need a margin to stop
        // having to rebuild too often.
        KALDI_WARN << "Failure in determinize-lattice: size exceeds maximum "
                   << opts_.max_mem << " bytes; (repo,arcs,elems) = ("
                   << repo_size << "," << arcs_size << "," << elems_size
                   << "), after rebuilding, repo size was " << new_repo_size;
        return false;
      }
    }
    return true;
  }

Compare()

int Compare ( const Weight &  a_w, StringId  a_str, const Weight &  b_w, StringId  b_str  ) const

inlineprivate

Definition at line 733 of file determinize-lattice-inl.h.

References fst::Compare(), and LatticeStringRepository< IntType >::Entry::i.

                                                              {
    int weight_comp = fst::Compare(a_w, b_w);
    if (weight_comp != 0) return weight_comp;
    // now comparing strings.
    if (a_str == b_str) return 0;
    std::vector<IntType> a_vec, b_vec;
    repository_.ConvertToVector(a_str, &a_vec);
    repository_.ConvertToVector(b_str, &b_vec);
    // First compare their lengths.
    int a_len = a_vec.size(), b_len = b_vec.size();
    // use opposite order on the string lengths (c.f. Compare in
    // lattice-weight.h)
    if (a_len > b_len) return -1;
    else if (a_len < b_len) return 1;
    for(int i = 0; i < a_len; i++) {
      if (a_vec[i] < b_vec[i]) return -1;
      else if (a_vec[i] > b_vec[i]) return 1;
    }
    assert(0); // because we checked if a_str == b_str above, shouldn't reach here
    return 0;
  }

ConvertToMinimal()

void ConvertToMinimal ( std::vector< Element > *  subset )

inlineprivate

Definition at line 647 of file determinize-lattice-inl.h.

                                                    {
    assert(!subset->empty());
    typename std::vector<Element>::iterator cur_in = subset->begin(),
        cur_out = subset->begin(), end = subset->end();
    while (cur_in != end) {
      if(IsIsymbolOrFinal(cur_in->state)) {  // keep it...
        *cur_out = *cur_in;
        cur_out++;
      }
      cur_in++;
    }
    subset->resize(cur_out - subset->begin());
  }

Debug()

void Debug ( )

inlineprivate

Definition at line 1080 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::Entry::i, rnnlm::j, KALDI_ASSERT, KALDI_ERR, and KALDI_WARN.

               {  // this function called if you send a signal
    // SIGUSR1 to the process (and it's caught by the handler in
    // fstdeterminizestar).  It prints out some traceback
    // info and exits.

    KALDI_WARN << "Debug function called (probably SIGUSR1 caught)";
    // free up memory from the hash as we need a little memory
    { MinimalSubsetHash hash_tmp; hash_tmp.swap(minimal_hash_); }

    if (output_arcs_.size() <= 2) {
      KALDI_ERR << "Nothing to trace back";
    }
    size_t max_state = output_arcs_.size() - 2;  // Don't take the last
    // one as we might be halfway into constructing it.

    std::vector<OutputStateId> predecessor(max_state+1, kNoStateId);
    for (size_t i = 0; i < max_state; i++) {
      for (size_t j = 0; j < output_arcs_[i].size(); j++) {
        OutputStateId nextstate = output_arcs_[i][j].nextstate;
        // Always find an earlier-numbered predecessor; this
        // is always possible because of the way the algorithm
        // works.
        if (nextstate <= max_state && nextstate > i)
          predecessor[nextstate] = i;
      }
    }
    std::vector<std::pair<Label, StringId> > traceback;
    // 'traceback' is a pair of (ilabel, olabel-seq).
    OutputStateId cur_state = max_state;  // A recently constructed state.

    while (cur_state != 0 && cur_state != kNoStateId) {
      OutputStateId last_state = predecessor[cur_state];
      std::pair<Label, StringId> p;
      size_t i;
      for (i = 0; i < output_arcs_[last_state].size(); i++) {
        if (output_arcs_[last_state][i].nextstate == cur_state) {
          p.first = output_arcs_[last_state][i].ilabel;
          p.second = output_arcs_[last_state][i].string;
          traceback.push_back(p);
          break;
        }
      }
      KALDI_ASSERT(i != output_arcs_[last_state].size());  // Or fell off loop.
      cur_state = last_state;
    }
    if (cur_state == kNoStateId)
      KALDI_WARN << "Traceback did not reach start state "
                 << "(possibly debug-code error)";

    std::stringstream ss;
    ss << "Traceback follows in format "
       << "ilabel (olabel olabel) ilabel (olabel) ... :";
    for (ssize_t i = traceback.size() - 1; i >= 0; i--) {
      ss << ' ' << traceback[i].first << " ( ";
      std::vector<Label> seq;
      repository_.ConvertToVector(traceback[i].second, &seq);
      for (size_t j = 0; j < seq.size(); j++)
        ss << seq[j] << ' ';
      ss << ')';
    }
    KALDI_ERR << ss.str();
  }

Determinize()

bool Determinize ( bool *  debug_ptr )

inline

Definition at line 498 of file determinize-lattice-inl.h.

References KALDI_WARN.

Referenced by fst::DeterminizeLattice().

                                    {
    assert(!determinized_);
    // This determinizes the input fst but leaves it in the "special format"
    // in "output_arcs_".  Must be called after Initialize().  To get the
    // output, call one of the Output routines.
    try {
      InitializeDeterminization(); // some start-up tasks.
      while (!queue_.empty()) {
        OutputStateId out_state = queue_.back();
        queue_.pop_back();
        ProcessState(out_state);
        if (debug_ptr && *debug_ptr) Debug();  // will exit.
        if (!CheckMemoryUsage()) return false;
      }
      return (determinized_ = true);
    } catch (const std::bad_alloc &) {
      int32 repo_size = repository_.MemSize(),
          arcs_size = num_arcs_ * sizeof(TempArc),
          elems_size = num_elems_ * sizeof(Element),
          total_size = repo_size + arcs_size + elems_size;
      KALDI_WARN << "Memory allocation error doing lattice determinization; using "
          << total_size << " bytes (max = " << opts_.max_mem
          << " (repo,arcs,elems) = ("
          << repo_size << "," << arcs_size << "," << elems_size << ")";
      return (determinized_ = false);
    } catch (const std::runtime_error &) {
      KALDI_WARN << "Caught exception doing lattice determinization";
      return (determinized_ = false);
    }
  }

EpsilonClosure()

void EpsilonClosure ( std::vector< Element > *  subset )

inlineprivate

Definition at line 762 of file determinize-lattice-inl.h.

References fst::Compare(), KALDI_ERR, LatticeDeterminizer< Weight, IntType >::Element::state, LatticeDeterminizer< Weight, IntType >::Element::string, fst::Times(), and LatticeDeterminizer< Weight, IntType >::Element::weight.

                                                  {
    // at input, subset must have only one example of each StateId.  [will still
    // be so at output].  This function follows input-epsilons, and augments the
    // subset accordingly.

    std::deque<Element> queue;
    std::unordered_map<InputStateId, Element> cur_subset;
    typedef typename std::unordered_map<InputStateId, Element>::iterator MapIter;
    typedef typename std::vector<Element>::const_iterator VecIter;

    for (VecIter iter = subset->begin(); iter != subset->end(); ++iter) {
      queue.push_back(*iter);
      cur_subset[iter->state] = *iter;
    }

    // find whether input fst is known to be sorted on input label.
    bool sorted = ((ifst_->Properties(kILabelSorted, false) & kILabelSorted) != 0);
    bool replaced_elems = false; // relates to an optimization, see below.
    int counter = 0; // stops infinite loops here for non-lattice-determinizable input;
    // useful in testing.
    while (queue.size() != 0) {
      Element elem = queue.front();
      queue.pop_front();

      // The next if-statement is a kind of optimization.  It's to prevent us
      // unnecessarily repeating the processing of a state.  "cur_subset" always
      // contains only one Element with a particular state.  The issue is that
      // whenever we modify the Element corresponding to that state in "cur_subset",
      // both the new (optimal) and old (less-optimal) Element will still be in
      // "queue".  The next if-statement stops us from wasting compute by
      // processing the old Element.
      if (replaced_elems && cur_subset[elem.state] != elem)
        continue;
      if (opts_.max_loop > 0 && counter++ > opts_.max_loop) {
        KALDI_ERR << "Lattice determinization aborted since looped more than "
                  << opts_.max_loop << " times during epsilon closure";
      }
      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
            && arc.weight != Weight::Zero()) {  // Epsilon transition.
          Element next_elem;
          next_elem.state = arc.nextstate;
          next_elem.weight = Times(elem.weight, arc.weight);
          // now must append strings
          if (arc.olabel == 0)
            next_elem.string = elem.string;
          else
            next_elem.string = repository_.Successor(elem.string, arc.olabel);

          MapIter iter = cur_subset.find(next_elem.state);
          if (iter == cur_subset.end()) {
            // was no such StateId: insert and add to queue.
            cur_subset[next_elem.state] = next_elem;
            queue.push_back(next_elem);
          } else {
            // was not inserted because one already there.  In normal determinization we'd
            // add the weights.  Here, we find which one has the better weight, and
            // keep its corresponding string.
            int comp = Compare(next_elem.weight, next_elem.string,
                               iter->second.weight, iter->second.string);
            if(comp == 1) { // next_elem is better, so use its (weight, string)
              iter->second.string = next_elem.string;
              iter->second.weight = next_elem.weight;
              queue.push_back(next_elem);
              replaced_elems = true;
            }
            // else it is the same or worse, so use original one.
          }
        }
      }
    }

    { // copy cur_subset to subset.
      subset->clear();
      subset->reserve(cur_subset.size());
      MapIter iter = cur_subset.begin(), end = cur_subset.end();
      for (; iter != end; ++iter) subset->push_back(iter->second);
      // sort by state ID, because the subset hash function is order-dependent(see SubsetKey)
      std::sort(subset->begin(), subset->end());
    }
  }

FreeMostMemory()

void FreeMostMemory ( )

inline

Definition at line 411 of file determinize-lattice-inl.h.

                        {
    if (ifst_) {
      delete ifst_;
      ifst_ = NULL;
    }
    for (typename MinimalSubsetHash::iterator iter = minimal_hash_.begin();
        iter != minimal_hash_.end(); ++iter)
      delete iter->first;
    { MinimalSubsetHash tmp; tmp.swap(minimal_hash_); }
    for (typename InitialSubsetHash::iterator iter = initial_hash_.begin();
        iter != initial_hash_.end(); ++iter)
      delete iter->first;
    { InitialSubsetHash tmp; tmp.swap(initial_hash_); }
    { std::vector<std::vector<Element>* > output_states_tmp;
      output_states_tmp.swap(output_states_); }
    { std::vector<char> tmp;  tmp.swap(isymbol_or_final_); }
    { std::vector<OutputStateId> tmp; tmp.swap(queue_); }
    { std::vector<std::pair<Label, Element> > tmp; tmp.swap(all_elems_tmp_); }
  }

InitializeDeterminization()

void InitializeDeterminization ( )

inlineprivate

Definition at line 1169 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::KALDI_DISALLOW_COPY_AND_ASSIGN(), LatticeDeterminizer< Weight, IntType >::Element::state, LatticeDeterminizer< Weight, IntType >::Element::string, and LatticeDeterminizer< Weight, IntType >::Element::weight.

                                   {
    if(ifst_->Properties(kExpanded, false) != 0) { // if we know the number of
      // states in ifst_, it might be a bit more efficient
      // to pre-size the hashes so we're not constantly rebuilding them.
#if !(__GNUC__ == 4 && __GNUC_MINOR__ == 0)
      StateId num_states =
          down_cast<const ExpandedFst<Arc>*, const Fst<Arc> >(ifst_)->NumStates();
      minimal_hash_.rehash(num_states/2 + 3);
      initial_hash_.rehash(num_states/2 + 3);
#endif
    }
    InputStateId start_id = ifst_->Start();
    if (start_id != kNoStateId) {
      /* Insert determinized-state corresponding to the start state into hash and
         queue.  Unlike all the other states, we don't "normalize" the representation
         of this determinized-state before we put it into minimal_hash_.  This is actually
         what we want, as otherwise we'd have problems dealing with any extra weight
         and string and might have to create a "super-initial" state which would make
         the output nondeterministic.  Normalization is only needed to make the
         determinized output more minimal anyway, it's not needed for correctness.
         Note, we don't put anything in the initial_hash_.  The initial_hash_ is only
         a lookaside buffer anyway, so this isn't a problem-- it will get populated
         later if it needs to be.
      */
      Element elem;
      elem.state = start_id;
      elem.weight = Weight::One();
      elem.string = repository_.EmptyString();  // Id of empty sequence.
      std::vector<Element> subset;
      subset.push_back(elem);
      EpsilonClosure(&subset); // follow through epsilon-inputs links
      ConvertToMinimal(&subset); // remove all but final states and
      // states with input-labels on arcs out of them.
      std::vector<Element> *subset_ptr = new std::vector<Element>(subset);
      assert(output_arcs_.empty() && output_states_.empty());
      // add the new state...
      output_states_.push_back(subset_ptr);
      output_arcs_.push_back(std::vector<TempArc>());
      OutputStateId initial_state = 0;
      minimal_hash_[subset_ptr] = initial_state;
      queue_.push_back(initial_state);
    }
  }

InitialToStateId()

OutputStateId InitialToStateId ( const std::vector< Element > &  subset_in, Weight *  remaining_weight, StringId *  common_prefix  )

inlineprivate

Definition at line 682 of file determinize-lattice-inl.h.

References KALDI_WARN, LatticeDeterminizer< Weight, IntType >::Element::state, LatticeDeterminizer< Weight, IntType >::Element::string, and LatticeDeterminizer< Weight, IntType >::Element::weight.

                                                          {
    typename InitialSubsetHash::const_iterator iter
        = initial_hash_.find(&subset_in);
    if (iter != initial_hash_.end()) { // Found a matching subset.
      const Element &elem = iter->second;
      *remaining_weight = elem.weight;
      *common_prefix = elem.string;
      if (elem.weight == Weight::Zero())
        KALDI_WARN << "Zero weight!"; // TEMP
      return elem.state;
    }
    // else no matching subset-- have to work it out.
    std::vector<Element> subset(subset_in);
    // Follow through epsilons.  Will add no duplicate states.  note: after
    // EpsilonClosure, it is the same as "canonical" subset, except not
    // normalized (actually we never compute the normalized canonical subset,
    // only the normalized minimal one).
    EpsilonClosure(&subset); // follow epsilons.
    ConvertToMinimal(&subset); // remove all but emitting and final states.

    Element elem; // will be used to store remaining weight and string, and
                 // OutputStateId, in initial_hash_;
    NormalizeSubset(&subset, &elem.weight, &elem.string); // normalize subset; put
    // common string and weight in "elem".  The subset is now a minimal,
    // normalized subset.

    OutputStateId ans = MinimalToStateId(subset);
    *remaining_weight = elem.weight;
    *common_prefix = elem.string;
    if (elem.weight == Weight::Zero())
      KALDI_WARN << "Zero weight!"; // TEMP

    // Before returning "ans", add the initial subset to the hash,
    // so that we can bypass the epsilon-closure etc., next time
    // we process the same initial subset.
    std::vector<Element> *initial_subset_ptr = new std::vector<Element>(subset_in);
    elem.state = ans;
    initial_hash_[initial_subset_ptr] = elem;
    num_elems_ += initial_subset_ptr->size(); // keep track of memory usage.
    return ans;
  }

IsIsymbolOrFinal()

bool IsIsymbolOrFinal ( InputStateId  state )

inlineprivate

Definition at line 1143 of file determinize-lattice-inl.h.

                                            { // returns true if this state
    // of the input FST either is final or has an osymbol on an arc out of it.
    // Uses the vector isymbol_or_final_ as a cache for this info.
    assert(state >= 0);
    if (isymbol_or_final_.size() <= state)
      isymbol_or_final_.resize(state+1, static_cast<char>(OSF_UNKNOWN));
    if (isymbol_or_final_[state] == static_cast<char>(OSF_NO))
      return false;
    else if (isymbol_or_final_[state] == static_cast<char>(OSF_YES))
      return true;
    // else work it out...
    isymbol_or_final_[state] = static_cast<char>(OSF_NO);
    if (ifst_->Final(state) != Weight::Zero())
      isymbol_or_final_[state] = static_cast<char>(OSF_YES);
    for (ArcIterator<Fst<Arc> > aiter(*ifst_, state);
         !aiter.Done();
         aiter.Next()) {
      const Arc &arc = aiter.Value();
      if (arc.ilabel != 0 && arc.weight != Weight::Zero()) {
        isymbol_or_final_[state] = static_cast<char>(OSF_YES);
        return true;
      }
    }
    return IsIsymbolOrFinal(state); // will only recurse once.
  }

KALDI_DISALLOW_COPY_AND_ASSIGN()

KALDI_DISALLOW_COPY_AND_ASSIGN ( LatticeDeterminizer< Weight, IntType >  )

private

MakeSubsetUnique()

void MakeSubsetUnique ( std::vector< Element > *  subset )

inlineprivate

Definition at line 924 of file determinize-lattice-inl.h.

References fst::Compare().

                                                    {
    typedef typename std::vector<Element>::iterator IterType;

    // This assert is designed to fail (usually) if the subset is not sorted on
    // state.
    assert(subset->size() < 2 || (*subset)[0].state <= (*subset)[1].state);

    IterType cur_in = subset->begin(), cur_out = cur_in, end = subset->end();
    size_t num_out = 0;
    // Merge elements with same state-id
    while (cur_in != end) {  // while we have more elements to process.
      // At this point, cur_out points to location of next place we want to put an element,
      // cur_in points to location of next element we want to process.
      if (cur_in != cur_out) *cur_out = *cur_in;
      cur_in++;
      while (cur_in != end && cur_in->state == cur_out->state) {
        if (Compare(cur_in->weight, cur_in->string,
                   cur_out->weight, cur_out->string) == 1) {
          // if *cur_in > *cur_out in semiring, then take *cur_in.
          cur_out->string = cur_in->string;
          cur_out->weight = cur_in->weight;
        }
        cur_in++;
      }
      cur_out++;
      num_out++;
    }
    subset->resize(num_out);
  }

MinimalToStateId()

OutputStateId MinimalToStateId ( const std::vector< Element > &  subset )

inlineprivate

Definition at line 664 of file determinize-lattice-inl.h.

                                                                   {
    typename MinimalSubsetHash::const_iterator iter
        = minimal_hash_.find(&subset);
    if (iter != minimal_hash_.end()) // Found a matching subset.
      return iter->second;
    OutputStateId ans = static_cast<OutputStateId>(output_arcs_.size());
    std::vector<Element> *subset_ptr = new std::vector<Element>(subset);
    output_states_.push_back(subset_ptr);
    num_elems_ += subset_ptr->size();
    output_arcs_.push_back(std::vector<TempArc>());
    minimal_hash_[subset_ptr] = ans;
    queue_.push_back(ans);
    return ans;
  }

NormalizeSubset()

void NormalizeSubset ( std::vector< Element > *  elems, Weight *  tot_weight, StringId *  common_str  )

inlineprivate

Definition at line 891 of file determinize-lattice-inl.h.

References fst::Divide(), LatticeStringRepository< IntType >::Entry::i, KALDI_WARN, and fst::Plus().

                                             {
    if(elems->empty()) { // just set common_str, tot_weight
      KALDI_WARN << "[empty subset]"; // TEMP
      // to defaults and return...
      *common_str = repository_.EmptyString();
      *tot_weight = Weight::Zero();
      return;
    }
    size_t size = elems->size();
    std::vector<IntType> common_prefix;
    repository_.ConvertToVector((*elems)[0].string, &common_prefix);
    Weight weight = (*elems)[0].weight;
    for (size_t i = 1; i < size; i++) {
      weight = Plus(weight, (*elems)[i].weight);
      repository_.ReduceToCommonPrefix((*elems)[i].string, &common_prefix);
    }
    assert(weight != Weight::Zero()); // we made sure to ignore arcs with zero
    // weights on them, so we shouldn't have zero here.
    size_t prefix_len = common_prefix.size();
    for (size_t i = 0; i < size; i++) {
      (*elems)[i].weight = Divide((*elems)[i].weight, weight, DIVIDE_LEFT);
      (*elems)[i].string =
          repository_.RemovePrefix((*elems)[i].string, prefix_len);
    }
    *common_str = repository_.ConvertFromVector(common_prefix);
    *tot_weight = weight;
  }

Output() [1/2]

void Output ( MutableFst< CompactArc > *  ofst, bool  destroy = true  )

inline

Definition at line 272 of file determinize-lattice-inl.h.

References LatticeDeterminizer< Weight, IntType >::TempArc::ilabel, LatticeDeterminizer< Weight, IntType >::TempArc::nextstate, LatticeDeterminizer< Weight, IntType >::TempArc::string, kaldi::swap(), and LatticeDeterminizer< Weight, IntType >::TempArc::weight.

Referenced by fst::DeterminizeLattice().

                                                                  {
    assert(determinized_);
    typedef typename Arc::StateId StateId;
    StateId nStates = static_cast<StateId>(output_arcs_.size());
    if (destroy)
      FreeMostMemory();
    ofst->DeleteStates();
    ofst->SetStart(kNoStateId);
    if (nStates == 0) {
      return;
    }
    for (StateId s = 0;s < nStates;s++) {
      OutputStateId news = ofst->AddState();
      assert(news == s);
    }
    ofst->SetStart(0);
    // now process transitions.
    for (StateId this_state = 0; this_state < nStates; this_state++) {
      std::vector<TempArc> &this_vec(output_arcs_[this_state]);
      typename std::vector<TempArc>::const_iterator iter = this_vec.begin(), end = this_vec.end();

      for (;iter != end; ++iter) {
        const TempArc &temp_arc(*iter);
        CompactArc new_arc;
        std::vector<Label> seq;
        repository_.ConvertToVector(temp_arc.string, &seq);
        CompactWeight weight(temp_arc.weight, seq);
        if (temp_arc.nextstate == kNoStateId) {  // is really final weight.
          ofst->SetFinal(this_state, weight);
        } else {  // is really an arc.
          new_arc.nextstate = temp_arc.nextstate;
          new_arc.ilabel = temp_arc.ilabel;
          new_arc.olabel = temp_arc.ilabel;  // acceptor.  input == output.
          new_arc.weight = weight;  // includes string and weight.
          ofst->AddArc(this_state, new_arc);
        }
      }
      // Free up memory.  Do this inside the loop as ofst is also allocating memory
      if (destroy) { std::vector<TempArc> temp; std::swap(temp, this_vec); }
    }
    if (destroy) { std::vector<std::vector<TempArc> > temp; std::swap(temp, output_arcs_); }
  }

Output() [2/2]

void Output ( MutableFst< Arc > *  ofst, bool  destroy = true  )

inline

Definition at line 318 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::Entry::i, LatticeDeterminizer< Weight, IntType >::TempArc::ilabel, LatticeDeterminizer< Weight, IntType >::TempArc::nextstate, LatticeDeterminizer< Weight, IntType >::TempArc::string, and LatticeDeterminizer< Weight, IntType >::TempArc::weight.

                                                           {
    // Outputs to standard fst.
    OutputStateId nStates = static_cast<OutputStateId>(output_arcs_.size());
    ofst->DeleteStates();
    if (nStates == 0) {
      ofst->SetStart(kNoStateId);
      return;
    }
    if (destroy)
      FreeMostMemory();
    // Add basic states-- but we will add extra ones to account for strings on output.
    for (OutputStateId s = 0;s < nStates;s++) {
      OutputStateId news = ofst->AddState();
      assert(news == s);
    }
    ofst->SetStart(0);
    for (OutputStateId this_state = 0; this_state < nStates; this_state++) {
      std::vector<TempArc> &this_vec(output_arcs_[this_state]);

      typename std::vector<TempArc>::const_iterator iter = this_vec.begin(), end = this_vec.end();
      for (; iter != end; ++iter) {
        const TempArc &temp_arc(*iter);
        std::vector<Label> seq;
        repository_.ConvertToVector(temp_arc.string, &seq);

        if (temp_arc.nextstate == kNoStateId) {  // Really a final weight.
          // Make a sequence of states going to a final state, with the strings
          // as labels.  Put the weight on the first arc.
          OutputStateId cur_state = this_state;
          for (size_t i = 0; i < seq.size(); i++) {
            OutputStateId next_state = ofst->AddState();
            Arc arc;
            arc.nextstate = next_state;
            arc.weight = (i == 0 ? temp_arc.weight : Weight::One());
            arc.ilabel = 0;  // epsilon.
            arc.olabel = seq[i];
            ofst->AddArc(cur_state, arc);
            cur_state = next_state;
          }
          ofst->SetFinal(cur_state, (seq.size() == 0 ? temp_arc.weight : Weight::One()));
        } else {  // Really an arc.
          OutputStateId cur_state = this_state;
          // Have to be careful with this integer comparison (i+1 < seq.size()) because unsigned.
          // i < seq.size()-1 could fail for zero-length sequences.
          for (size_t i = 0; i+1 < seq.size();i++) {
            // for all but the last element of seq, create new state.
            OutputStateId next_state = ofst->AddState();
            Arc arc;
            arc.nextstate = next_state;
            arc.weight = (i == 0 ? temp_arc.weight : Weight::One());
            arc.ilabel = (i == 0 ? temp_arc.ilabel : 0);  // put ilabel on first element of seq.
            arc.olabel = seq[i];
            ofst->AddArc(cur_state, arc);
            cur_state = next_state;
          }
          // Add the final arc in the sequence.
          Arc arc;
          arc.nextstate = temp_arc.nextstate;
          arc.weight = (seq.size() <= 1 ? temp_arc.weight : Weight::One());
          arc.ilabel = (seq.size() <= 1 ? temp_arc.ilabel : 0);
          arc.olabel = (seq.size() > 0 ? seq.back() : 0);
          ofst->AddArc(cur_state, arc);
        }
      }
      // Free up memory.  Do this inside the loop as ofst is also allocating memory
      if (destroy) {
        std::vector<TempArc> temp; temp.swap(this_vec);
      }
    }
    if (destroy) {
      std::vector<std::vector<TempArc> > temp;
      temp.swap(output_arcs_);
      repository_.Destroy();
    }
  }

ProcessFinal()

void ProcessFinal ( OutputStateId  output_state )

inlineprivate

Definition at line 852 of file determinize-lattice-inl.h.

References fst::Compare(), LatticeDeterminizer< Weight, IntType >::TempArc::ilabel, LatticeDeterminizer< Weight, IntType >::TempArc::nextstate, LatticeDeterminizer< Weight, IntType >::Element::state, LatticeDeterminizer< Weight, IntType >::Element::string, LatticeDeterminizer< Weight, IntType >::TempArc::string, fst::Times(), LatticeDeterminizer< Weight, IntType >::Element::weight, and LatticeDeterminizer< Weight, IntType >::TempArc::weight.

                                                {
    const std::vector<Element> &minimal_subset = *(output_states_[output_state]);
    // processes final-weights for this subset.

    // minimal_subset may be empty if the graphs is not connected/trimmed, I think,
    // do don't check that it's nonempty.
    bool is_final = false;
    StringId final_string = NULL;  // = NULL to keep compiler happy.
    Weight final_weight = Weight::Zero();
    typename std::vector<Element>::const_iterator iter = minimal_subset.begin(), end = minimal_subset.end();
    for (; iter != end; ++iter) {
      const Element &elem = *iter;
      Weight this_final_weight = Times(elem.weight, ifst_->Final(elem.state));
      StringId this_final_string = elem.string;
      if (this_final_weight != Weight::Zero() &&
         (!is_final || Compare(this_final_weight, this_final_string,
                               final_weight, final_string) == 1)) { // the new
        // (weight, string) pair is more in semiring than our current
        // one.
        is_final = true;
        final_weight = this_final_weight;
        final_string = this_final_string;
      }
    }
    if (is_final) {
      // store final weights in TempArc structure, just like a transition.
      TempArc temp_arc;
      temp_arc.ilabel = 0;
      temp_arc.nextstate = kNoStateId;  // special marker meaning "final weight".
      temp_arc.string = final_string;
      temp_arc.weight = final_weight;
      output_arcs_[output_state].push_back(temp_arc);
      num_arcs_++;
    }
  }

ProcessState()

void ProcessState ( OutputStateId  output_state )

inlineprivate

Definition at line 1074 of file determinize-lattice-inl.h.

                                                {
    ProcessFinal(output_state);
    ProcessTransitions(output_state);
  }

ProcessTransition()

void ProcessTransition ( OutputStateId  state, Label  ilabel, std::vector< Element > *  subset  )

inlineprivate

Definition at line 962 of file determinize-lattice-inl.h.

References LatticeDeterminizer< Weight, IntType >::TempArc::ilabel, LatticeDeterminizer< Weight, IntType >::TempArc::nextstate, LatticeDeterminizer< Weight, IntType >::TempArc::string, fst::Times(), and LatticeDeterminizer< Weight, IntType >::TempArc::weight.

                                                                                        {
    MakeSubsetUnique(subset); // remove duplicates with the same state.

    StringId common_str;
    Weight tot_weight;
    NormalizeSubset(subset, &tot_weight, &common_str);

    OutputStateId nextstate;
    {
      Weight next_tot_weight;
      StringId next_common_str;
      nextstate = InitialToStateId(*subset,
                                   &next_tot_weight,
                                   &next_common_str);
      common_str = repository_.Concatenate(common_str, next_common_str);
      tot_weight = Times(tot_weight, next_tot_weight);
    }

    // Now add an arc to the next state (would have been created if necessary by
    // InitialToStateId).
    TempArc temp_arc;
    temp_arc.ilabel = ilabel;
    temp_arc.nextstate = nextstate;
    temp_arc.string = common_str;
    temp_arc.weight = tot_weight;
    output_arcs_[state].push_back(temp_arc);  // record the arc.
    num_arcs_++;
  }

ProcessTransitions()

void ProcessTransitions ( OutputStateId  output_state )

inlineprivate

Definition at line 1018 of file determinize-lattice-inl.h.

References LatticeDeterminizer< Weight, IntType >::Element::state, LatticeDeterminizer< Weight, IntType >::Element::string, fst::Times(), and LatticeDeterminizer< Weight, IntType >::Element::weight.

                                                      {
    const std::vector<Element> &minimal_subset = *(output_states_[output_state]);
    // it's possible that minimal_subset could be empty if there are
    // unreachable parts of the graph, so don't check that it's nonempty.
    std::vector<std::pair<Label, Element> > &all_elems(all_elems_tmp_); // use class member
    // to avoid memory allocation/deallocation.
    {
      // Push back into "all_elems", elements corresponding to all
      // non-epsilon-input transitions out of all states in "minimal_subset".
      typename std::vector<Element>::const_iterator iter = minimal_subset.begin(), end = minimal_subset.end();
      for (;iter != end; ++iter) {
        const Element &elem = *iter;
        for (ArcIterator<Fst<Arc> > aiter(*ifst_, elem.state); ! aiter.Done(); aiter.Next()) {
          const Arc &arc = aiter.Value();
          if (arc.ilabel != 0
              && arc.weight != Weight::Zero()) {  // Non-epsilon transition -- ignore epsilons here.
            std::pair<Label, Element> this_pr;
            this_pr.first = arc.ilabel;
            Element &next_elem(this_pr.second);
            next_elem.state = arc.nextstate;
            next_elem.weight = Times(elem.weight, arc.weight);
            if (arc.olabel == 0) // output epsilon
              next_elem.string = elem.string;
            else
              next_elem.string = repository_.Successor(elem.string, arc.olabel);
            all_elems.push_back(this_pr);
          }
        }
      }
    }
    PairComparator pc;
    std::sort(all_elems.begin(), all_elems.end(), pc);
    // now sorted first on input label, then on state.
    typedef typename std::vector<std::pair<Label, Element> >::const_iterator PairIter;
    PairIter cur = all_elems.begin(), end = all_elems.end();
    std::vector<Element> this_subset;
    while (cur != end) {
      // Process ranges that share the same input symbol.
      Label ilabel = cur->first;
      this_subset.clear();
      while (cur != end && cur->first == ilabel) {
        this_subset.push_back(cur->second);
        cur++;
      }
      // We now have a subset for this ilabel.
      assert(!this_subset.empty()); // temp.
      ProcessTransition(output_state, ilabel, &this_subset);
    }
    all_elems.clear(); // as it's a class variable-- want it to stay
    // emtpy.
  }

RebuildRepository()

void RebuildRepository ( )

inline

Definition at line 434 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::Entry::i, rnnlm::j, and LatticeDeterminizer< Weight, IntType >::Element::string.

                           { // rebuild the string repository,
    // freeing stuff we don't need.. we call this when memory usage
    // passes a supplied threshold.  We need to accumulate all the
    // strings we need the repository to "remember", then tell it
    // to clean the repository.
    std::vector<StringId> needed_strings;
    for (size_t i = 0; i < output_arcs_.size(); i++)
      for (size_t j = 0; j < output_arcs_[i].size(); j++)
        needed_strings.push_back(output_arcs_[i][j].string);

    // the following loop covers strings present in minimal_hash_
    // which are also accessible via output_states_.
    for (size_t i = 0; i < output_states_.size(); i++)
      for (size_t j = 0; j < output_states_[i]->size(); j++)
        needed_strings.push_back((*(output_states_[i]))[j].string);

    // the following loop covers strings present in initial_hash_.
    for (typename InitialSubsetHash::const_iterator
             iter = initial_hash_.begin();
         iter != initial_hash_.end(); ++iter) {
      const std::vector<Element> &vec = *(iter->first);
      Element elem = iter->second;
      for (size_t i = 0; i < vec.size(); i++)
        needed_strings.push_back(vec[i].string);
      needed_strings.push_back(elem.string);
    }

    std::sort(needed_strings.begin(), needed_strings.end());
    needed_strings.erase(std::unique(needed_strings.begin(),
                                     needed_strings.end()),
                         needed_strings.end()); // uniq the strings.
    repository_.Rebuild(needed_strings);
  }

Member Data Documentation

all_elems_tmp_

std::vector<std::pair<Label, Element> > all_elems_tmp_

private

Definition at line 1248 of file determinize-lattice-inl.h.

determinized_

bool determinized_

private

Definition at line 1229 of file determinize-lattice-inl.h.

equal_

SubsetEqual equal_

private

Definition at line 1228 of file determinize-lattice-inl.h.

hasher_

SubsetKey hasher_

private

Definition at line 1227 of file determinize-lattice-inl.h.

ifst_

const Fst<Arc>* ifst_

private

Definition at line 1225 of file determinize-lattice-inl.h.

initial_hash_

InitialSubsetHash initial_hash_

private

Definition at line 1235 of file determinize-lattice-inl.h.

isymbol_or_final_

std::vector<char> isymbol_or_final_

private

Definition at line 1252 of file determinize-lattice-inl.h.

minimal_hash_

MinimalSubsetHash minimal_hash_

private

Definition at line 1231 of file determinize-lattice-inl.h.

num_arcs_

int num_arcs_

private

Definition at line 1222 of file determinize-lattice-inl.h.

num_elems_

int num_elems_

private

Definition at line 1223 of file determinize-lattice-inl.h.

opts_

DeterminizeLatticeOptions opts_

private

Definition at line 1226 of file determinize-lattice-inl.h.

output_arcs_

std::vector<std::vector<TempArc> > output_arcs_

private

Definition at line 1220 of file determinize-lattice-inl.h.

output_states_

std::vector<std::vector<Element>* > output_states_

private

Definition at line 1216 of file determinize-lattice-inl.h.

queue_

std::vector<OutputStateId> queue_

private

Definition at line 1244 of file determinize-lattice-inl.h.

repository_

LatticeStringRepository<IntType> repository_

private

Definition at line 1256 of file determinize-lattice-inl.h.

---

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

• fstext/determinize-lattice-inl.h