LatticeStringRepository< IntType > Class Template Reference

#include <determinize-lattice-inl.h>

Collaboration diagram for LatticeStringRepository< IntType >:

Classes
struct	Entry
class	EntryEqual
class	EntryKey

Public Member Functions
const Entry *	EmptyString ()
const Entry *	Successor (const Entry *parent, IntType i)
const Entry *	Concatenate (const Entry *a, const Entry *b)
const Entry *	CommonPrefix (const Entry *a, const Entry *b)
void	ReduceToCommonPrefix (const Entry *a, std::vector< IntType > *b)
const Entry *	RemovePrefix (const Entry *a, size_t n)
bool	IsPrefixOf (const Entry *a, const Entry *b) const
size_t	Size (const Entry *entry) const
void	ConvertToVector (const Entry *entry, std::vector< IntType > *out) const
const Entry *	ConvertFromVector (const std::vector< IntType > &vec)
	LatticeStringRepository ()
void	Destroy ()
void	Rebuild (const std::vector< const Entry *> &to_keep)
	~LatticeStringRepository ()
int32	MemSize () const

Private Types
typedef std::unordered_set< const Entry *, EntryKey, EntryEqual >	SetType

Private Member Functions
void	RebuildHelper (const Entry *to_add, SetType *tmp_set)
	KALDI_DISALLOW_COPY_AND_ASSIGN (LatticeStringRepository)

Private Attributes
Entry *	new_entry_
SetType	set_

Detailed Description

template<class IntType>
class fst::LatticeStringRepository< IntType >

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

Member Typedef Documentation

SetType

typedef std::unordered_set<const Entry*, EntryKey, EntryEqual> SetType

private

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

Constructor & Destructor Documentation

LatticeStringRepository()

LatticeStringRepository ( )

inline

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

References LatticeStringRepository< IntType >::Entry::Entry(), and LatticeStringRepository< IntType >::new_entry_.

{ new_entry_ = new Entry; }

~LatticeStringRepository()

~LatticeStringRepository ( )

inline

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

References LatticeStringRepository< IntType >::Destroy().

{ Destroy(); }

Member Function Documentation

CommonPrefix()

const Entry* CommonPrefix ( const Entry *  a, const Entry *  b  )

inline

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

References LatticeStringRepository< IntType >::ConvertToVector(), LatticeStringRepository< IntType >::Entry::i, and LatticeStringRepository< IntType >::Successor().

Referenced by fst::TestLatticeStringRepository().

                                                             {
    std::vector<IntType> a_vec, b_vec;
    ConvertToVector(a, &a_vec);
    ConvertToVector(b, &b_vec);
    const Entry *ans = NULL;
    for(size_t i = 0; i < a_vec.size() && i < b_vec.size() &&
            a_vec[i] == b_vec[i]; i++)
      ans = Successor(ans, a_vec[i]);
    return ans;
  }

Concatenate()

const Entry* Concatenate ( const Entry *  a, const Entry *  b  )

inline

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

References LatticeStringRepository< IntType >::ConvertToVector(), LatticeStringRepository< IntType >::Entry::i, and LatticeStringRepository< IntType >::Successor().

                                                            {
    if (a == NULL) return b;
    else if (b == NULL) return a;
    std::vector<IntType> v;
    ConvertToVector(b, &v);
    const Entry *ans = a;
    for(size_t i = 0; i < v.size(); i++)
      ans = Successor(ans, v[i]);
    return ans;
  }

ConvertFromVector()

const Entry* ConvertFromVector ( const std::vector< IntType > &  vec )

inline

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

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

                                                                {
    const Entry *e = NULL;
    for(size_t i = 0; i < vec.size(); i++)
      e = Successor(e, vec[i]);
    return e;
  }

ConvertToVector()

void ConvertToVector ( const Entry *  entry, std::vector< IntType > *  out  ) const

inline

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

References LatticeStringRepository< IntType >::Entry::i, LatticeStringRepository< IntType >::Entry::parent, and LatticeStringRepository< IntType >::Size().

Referenced by LatticeStringRepository< IntType >::CommonPrefix(), LatticeStringRepository< IntType >::Concatenate(), LatticeStringRepository< IntType >::RemovePrefix(), and fst::TestLatticeStringRepository().

                                                                          {
    size_t length = Size(entry);
    out->resize(length);
    if (entry != NULL) {
      typename std::vector<IntType>::reverse_iterator iter = out->rbegin();
    while (entry != NULL) {
      *iter = entry->i;
      entry = entry->parent;
        ++iter;
    }
  }
  }

Destroy()

void Destroy ( )

inline

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

References LatticeStringRepository< IntType >::new_entry_, and LatticeStringRepository< IntType >::set_.

Referenced by LatticeStringRepository< IntType >::~LatticeStringRepository().

                 {
    for (typename SetType::iterator iter = set_.begin();
         iter != set_.end();
         ++iter)
      delete *iter;
    SetType tmp;
    tmp.swap(set_);
    if (new_entry_) {
      delete new_entry_;
      new_entry_ = NULL;
    }
  }

EmptyString()

const Entry* EmptyString ( )

inline

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

Referenced by fst::TestLatticeStringRepository().

{ return NULL; }

IsPrefixOf()

bool IsPrefixOf ( const Entry *  a, const Entry *  b  ) const

inline

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

References LatticeStringRepository< IntType >::Entry::parent.

Referenced by fst::TestLatticeStringRepository().

                                                        {
    if(a == NULL) return true; // empty string prefix of all.
    if (a == b) return true;
    if (b == NULL) return false;
    return IsPrefixOf(a, b->parent);
  }

KALDI_DISALLOW_COPY_AND_ASSIGN()

KALDI_DISALLOW_COPY_AND_ASSIGN ( LatticeStringRepository< IntType >  )

private

Referenced by LatticeDeterminizer< Weight, IntType >::InitializeDeterminization(), and LatticeStringRepository< IntType >::RebuildHelper().

MemSize()

int32 MemSize ( ) const

inline

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

References LatticeStringRepository< IntType >::Entry::Entry(), and LatticeStringRepository< IntType >::set_.

                        {
    return set_.size() * sizeof(Entry) * 2; // this is a lower bound
    // on the size this structure might take.
  }

Rebuild()

void Rebuild ( const std::vector< const Entry *> &  to_keep )

inline

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

References LatticeStringRepository< IntType >::RebuildHelper(), and LatticeStringRepository< IntType >::set_.

                                                       {
    SetType tmp_set;
    for (typename std::vector<const Entry*>::const_iterator
             iter = to_keep.begin();
         iter != to_keep.end(); ++iter)
      RebuildHelper(*iter, &tmp_set);
    // Now delete all elems not in tmp_set.
    for (typename SetType::iterator iter = set_.begin();
         iter != set_.end(); ++iter) {
      if (tmp_set.count(*iter) == 0)
        delete (*iter); // delete the Entry; not needed.
    }
    set_.swap(tmp_set);
  }

RebuildHelper()

void RebuildHelper ( const Entry *  to_add, SetType *  tmp_set  )

inlineprivate

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

References LatticeStringRepository< IntType >::KALDI_DISALLOW_COPY_AND_ASSIGN(), and LatticeStringRepository< IntType >::Entry::parent.

Referenced by LatticeStringRepository< IntType >::Rebuild().

                                                            {
    while(true) {
      if (to_add == NULL) return;
      typename SetType::iterator iter = tmp_set->find(to_add);
      if (iter == tmp_set->end()) { // not in tmp_set.
        tmp_set->insert(to_add);
        to_add = to_add->parent; // and loop.
      } else {
        return;
      }
    }
  }

ReduceToCommonPrefix()

void ReduceToCommonPrefix ( const Entry *  a, std::vector< IntType > *  b  )

inline

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

References LatticeStringRepository< IntType >::Entry::i, LatticeStringRepository< IntType >::Entry::parent, and LatticeStringRepository< IntType >::Size().

Referenced by fst::TestLatticeStringRepository().

                                                   {
    size_t a_size = Size(a), b_size = b->size();
    while (a_size> b_size) {
      a = a->parent;
      a_size--;
    }
    if (b_size > a_size)
      b_size = a_size;
    typename std::vector<IntType>::iterator b_begin = b->begin();
    while (a_size != 0) {
      if (a->i != *(b_begin + a_size - 1))
        b_size = a_size - 1;
      a = a->parent;
      a_size--;
    }
    if (b_size != b->size())
      b->resize(b_size);
  }

RemovePrefix()

const Entry* RemovePrefix ( const Entry *  a, size_t  n  )

inline

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

References LatticeStringRepository< IntType >::ConvertToVector(), LatticeStringRepository< IntType >::Entry::i, rnnlm::n, and LatticeStringRepository< IntType >::Successor().

                                                      {
    if (n==0) return a;
    std::vector<IntType> a_vec;
    ConvertToVector(a, &a_vec);
    assert(a_vec.size() >= n);
    const Entry *ans = NULL;
    for(size_t i = n; i < a_vec.size(); i++)
      ans = Successor(ans, a_vec[i]);
    return ans;
  }

Size()

size_t Size ( const Entry *  entry ) const

inline

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

References LatticeStringRepository< IntType >::Entry::parent.

Referenced by LatticeStringRepository< IntType >::ConvertToVector(), and LatticeStringRepository< IntType >::ReduceToCommonPrefix().

                                               {
    size_t ans = 0;
    while (entry != NULL) {
      ans++;
      entry = entry->parent;
    }
    return ans;
  }

Successor()

const Entry* Successor ( const Entry *  parent, IntType  i  )

inline

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

References LatticeStringRepository< IntType >::Entry::Entry(), LatticeStringRepository< IntType >::Entry::i, LatticeStringRepository< IntType >::new_entry_, LatticeStringRepository< IntType >::Entry::parent, and LatticeStringRepository< IntType >::set_.

Referenced by LatticeStringRepository< IntType >::CommonPrefix(), LatticeStringRepository< IntType >::Concatenate(), LatticeStringRepository< IntType >::ConvertFromVector(), LatticeStringRepository< IntType >::RemovePrefix(), and fst::TestLatticeStringRepository().

                                                         {
    new_entry_->parent = parent;
    new_entry_->i = i;

    std::pair<typename SetType::iterator, bool> pr = set_.insert(new_entry_);
    if (pr.second) { // Was successfully inserted (was not there).  We need to
                     // replace the element we inserted, which resides on the
                     // stack, with one from the heap.
      const Entry *ans = new_entry_;
      new_entry_ = new Entry();
      return ans;
    } else { // Was not inserted because an equivalent Entry already
             // existed.
      return *pr.first;
    }
  }

Member Data Documentation

new_entry_

Entry* new_entry_

private

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

Referenced by LatticeStringRepository< IntType >::Destroy(), LatticeStringRepository< IntType >::LatticeStringRepository(), and LatticeStringRepository< IntType >::Successor().

set_

SetType set_

private

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

Referenced by LatticeStringRepository< IntType >::Destroy(), LatticeStringRepository< IntType >::MemSize(), LatticeStringRepository< IntType >::Rebuild(), and LatticeStringRepository< IntType >::Successor().

---

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

• fstext/determinize-lattice-inl.h