TableMatcherImpl< F, BackoffMatcher > Class Template Reference

#include <table-matcher.h>

Inheritance diagram for TableMatcherImpl< F, BackoffMatcher >:

Collaboration diagram for TableMatcherImpl< F, BackoffMatcher >:

Public Types
typedef F	FST
typedef F::Arc	Arc
typedef Arc::Label	Label
typedef Arc::StateId	StateId
typedef StateId	ArcId
typedef Arc::Weight	Weight

Public Member Functions
	TableMatcherImpl (const FST &fst, MatchType match_type, const TableMatcherOptions &opts=TableMatcherOptions())
virtual const FST &	GetFst () const
virtual	~TableMatcherImpl ()
virtual MatchType	Type (bool test) const
void	SetState (StateId s)
bool	Find (Label match_label)
const Arc &	Value () const
void	Next ()
bool	Done () const
const Arc &	Value ()
virtual TableMatcherImpl< FST > *	Copy (bool safe=false) const
virtual uint64	Properties (uint64 props) const

Private Member Functions
virtual void	SetState_ (StateId s)
virtual bool	Find_ (Label label)
virtual bool	Done_ () const
virtual const Arc &	Value_ () const
virtual void	Next_ ()

Private Attributes
MatchType	match_type_
FST *	fst_
bool	current_loop_
Label	match_label_
Arc	loop_
ArcIterator< FST > *	aiter_
StateId	s_
std::vector< std::vector< ArcId > * >	tables_
TableMatcherOptions	opts_
BackoffMatcher	backoff_matcher_

Detailed Description

template<class F, class BackoffMatcher = SortedMatcher<F>>
class fst::TableMatcherImpl< F, BackoffMatcher >

Definition at line 53 of file table-matcher.h.

Member Typedef Documentation

Arc

typedef F::Arc Arc

Definition at line 56 of file table-matcher.h.

ArcId

typedef StateId ArcId

Definition at line 59 of file table-matcher.h.

FST

typedef F FST

Definition at line 55 of file table-matcher.h.

Label

typedef Arc::Label Label

Definition at line 57 of file table-matcher.h.

StateId

typedef Arc::StateId StateId

Definition at line 58 of file table-matcher.h.

Weight

typedef Arc::Weight Weight

Definition at line 61 of file table-matcher.h.

Constructor & Destructor Documentation

TableMatcherImpl()

TableMatcherImpl ( const FST &  fst, MatchType  match_type, const TableMatcherOptions &  opts = TableMatcherOptions()  )

inline

Definition at line 66 of file table-matcher.h.

                                                                           :
      match_type_(match_type),
      fst_(fst.Copy()),
      loop_(match_type == MATCH_INPUT ?
            Arc(kNoLabel, 0, Weight::One(), kNoStateId) :
            Arc(0, kNoLabel, Weight::One(), kNoStateId)),
      aiter_(NULL),
      s_(kNoStateId), opts_(opts),
      backoff_matcher_(fst, match_type)
  {
    assert(opts_.min_table_size > 0);
    if (match_type == MATCH_INPUT)
      assert(fst_->Properties(kILabelSorted, true) == kILabelSorted);
    else if (match_type == MATCH_OUTPUT)
      assert(fst_->Properties(kOLabelSorted, true) == kOLabelSorted);
    else
      assert(0 && "Invalid FST properties");
  }

~TableMatcherImpl()

virtual ~TableMatcherImpl ( )

inlinevirtual

Definition at line 88 of file table-matcher.h.

References rnnlm::i.

                              {
    std::vector<ArcId> *const empty = ((std::vector<ArcId>*)(NULL)) + 1;  // special marker.
    for (size_t i = 0; i < tables_.size(); i++) {
      if (tables_[i] != NULL && tables_[i] != empty)
        delete tables_[i];
    }
    delete aiter_;
    delete fst_;
  }

Member Function Documentation

Copy()

virtual TableMatcherImpl<FST>* Copy ( bool  safe = false ) const

inlinevirtual

Definition at line 212 of file table-matcher.h.

                                                               {
    assert(0);  // shouldn't be called.  This is not a "real" matcher,
    // although we derive from MatcherBase for convenience.
    return NULL;
  }

Done()

bool Done ( ) const

inline

Definition at line 193 of file table-matcher.h.

                    {
    if (aiter_ != NULL) {
      if (current_loop_)
        return false;
      if (aiter_->Done())
        return true;
      Label label = (match_type_ == MATCH_OUTPUT ?
                     aiter_->Value().olabel : aiter_->Value().ilabel);
      return (label != match_label_);
    } else
      return backoff_matcher_.Done();
  }

Done_()

virtual bool Done_ ( ) const

inlineprivatevirtual

Definition at line 224 of file table-matcher.h.

{ return Done(); }

Find()

bool Find ( Label  match_label )

inline

Definition at line 160 of file table-matcher.h.

                               {
    if (!aiter_) return backoff_matcher_.Find(match_label);
    else {
      match_label_ = match_label;
      current_loop_ = (match_label == 0);
      // kNoLabel means the implicit loop on the other FST --
      // matches real epsilons but not the self-loop.
      match_label_ = (match_label_ == kNoLabel ? 0 : match_label_);
      if (static_cast<size_t>(match_label_) < tables_[s_]->size() &&
         (*(tables_[s_]))[match_label_] != kNoStateId) {
        aiter_->Seek( (*(tables_[s_]))[match_label_] );  // label exists.
        return true;
      }
      return current_loop_;
    }
  }

Find_()

virtual bool Find_ ( Label  label )

inlineprivatevirtual

Definition at line 223 of file table-matcher.h.

{ return Find(label); }

GetFst()

virtual const FST& GetFst ( ) const

inlinevirtual

Definition at line 86 of file table-matcher.h.

{ return *fst_; }

Next()

void Next ( )

inline

Definition at line 183 of file table-matcher.h.

              {
    if (aiter_) {
      if (current_loop_)
        current_loop_ = false;
      else
        aiter_->Next();
    } else
      backoff_matcher_.Next();
  }

Next_()

virtual void Next_ ( )

inlineprivatevirtual

Definition at line 226 of file table-matcher.h.

{ Next(); }

Properties()

virtual uint64 Properties ( uint64  props ) const

inlinevirtual

Definition at line 218 of file table-matcher.h.

{ return props; } // simple matcher that does

SetState()

void SetState ( StateId  s )

inline

Definition at line 102 of file table-matcher.h.

                           {
    if (aiter_) {
      delete aiter_;
      aiter_ = NULL;
    }
    if (match_type_ == MATCH_NONE)
      LOG(FATAL) << "TableMatcher: bad match type";
    s_ = s;
    std::vector<ArcId> *const empty = ((std::vector<ArcId>*)(NULL)) + 1;  // special marker.
    if (static_cast<size_t>(s) >= tables_.size()) {
      assert(s>=0);
      tables_.resize(s+1, NULL);
    }
    std::vector<ArcId>* &this_table_ = tables_[s];  // note: ref to ptr.
    if (this_table_ == empty) {
      backoff_matcher_.SetState(s);
      return;
    } else if (this_table_ == NULL) {  // NULL means has not been set.
      ArcId num_arcs = fst_->NumArcs(s);
      if (num_arcs == 0 || num_arcs < opts_.min_table_size) {
        this_table_ = empty;
        backoff_matcher_.SetState(s);
        return;
      }
      ArcIterator<FST> aiter(*fst_, s);
      aiter.SetFlags(kArcNoCache|(match_type_ == MATCH_OUTPUT?kArcOLabelValue:kArcILabelValue),
                     kArcNoCache|kArcValueFlags);
      // the statement above, says: "Don't cache stuff; and I only need the ilabel/olabel
      // to be computed.
      aiter.Seek(num_arcs - 1);
      Label highest_label = (match_type_ == MATCH_OUTPUT ?
                             aiter.Value().olabel : aiter.Value().ilabel);
      if ((highest_label+1) * opts_.table_ratio > num_arcs) {
        this_table_ = empty;
        backoff_matcher_.SetState(s);
        return;  // table would be too sparse.
      }
      // OK, now we are creating the table.
      this_table_ = new std::vector<ArcId> (highest_label+1, kNoStateId);
      ArcId pos = 0;
      for (aiter.Seek(0); !aiter.Done(); aiter.Next(), pos++) {
        Label label = (match_type_ == MATCH_OUTPUT ?
                       aiter.Value().olabel : aiter.Value().ilabel);
        assert((size_t)label <= (size_t)highest_label);  // also checks >= 0.
        if ((*this_table_)[label] == kNoStateId) (*this_table_)[label] = pos;
        // set this_table_[label] to first position where arc has this
        // label.
      }
    }
    // At this point in the code, this_table_ != NULL and != empty.
    aiter_ = new ArcIterator<FST>(*fst_, s);
    aiter_->SetFlags(kArcNoCache, kArcNoCache);  // don't need to cache arcs as may only
    // need a small subset.
    loop_.nextstate = s;
    // aiter_ = NULL;
    // backoff_matcher_.SetState(s);
  }

SetState_()

virtual void SetState_ ( StateId  s )

inlineprivatevirtual

Definition at line 222 of file table-matcher.h.

{ SetState(s); }

Type()

virtual MatchType Type ( bool  test ) const

inlinevirtual

Definition at line 98 of file table-matcher.h.

                                          {
    return match_type_;
  }

Value() [1/2]

const Arc& Value ( ) const

inline

Definition at line 176 of file table-matcher.h.

                           {
    if (aiter_)
      return current_loop_ ? loop_ : aiter_->Value();
    else
      return backoff_matcher_.Value();
  }

Value() [2/2]

const Arc& Value ( )

inline

Definition at line 205 of file table-matcher.h.

                     {
    if (aiter_ != NULL) {
      return (current_loop_ ?  loop_ : aiter_->Value() );
    } else
      return backoff_matcher_.Value();
  }

Value_()

virtual const Arc& Value_ ( ) const

inlineprivatevirtual

Definition at line 225 of file table-matcher.h.

{ return Value(); }

Member Data Documentation

aiter_

ArcIterator<FST>* aiter_

private

Definition at line 233 of file table-matcher.h.

backoff_matcher_

BackoffMatcher backoff_matcher_

private

Definition at line 237 of file table-matcher.h.

current_loop_

bool current_loop_

private

Definition at line 230 of file table-matcher.h.

fst_

FST* fst_

private

Definition at line 229 of file table-matcher.h.

loop_

Arc loop_

private

Definition at line 232 of file table-matcher.h.

match_label_

Label match_label_

private

Definition at line 231 of file table-matcher.h.

match_type_

MatchType match_type_

private

Definition at line 228 of file table-matcher.h.

opts_

TableMatcherOptions opts_

private

Definition at line 236 of file table-matcher.h.

s_

StateId s_

private

Definition at line 234 of file table-matcher.h.

tables_

std::vector<std::vector<ArcId> *> tables_

private

Definition at line 235 of file table-matcher.h.

---

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

• fstext/table-matcher.h