All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
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 FSTGetFst () const
 
virtual ~TableMatcherImpl ()
 
virtual MatchType Type (bool test) const
 
void SetState (StateId s)
 
bool Find (Label match_label)
 
const ArcValue () const
 
void Next ()
 
bool Done () const
 
const ArcValue ()
 
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 ArcValue_ () const
 
virtual void Next_ ()
 

Private Attributes

MatchType match_type_
 
FSTfst_
 
bool current_loop_
 
Label match_label_
 
Arc loop_
 
ArcIterator< FST > * aiter_
 
StateId s_
 
vector< 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

typedef F::Arc Arc

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

typedef StateId ArcId

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

typedef F FST

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

typedef Arc::Label Label

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

typedef Arc::StateId StateId

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

typedef Arc::Weight Weight

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

Constructor & Destructor Documentation

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

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

References TableMatcherImpl< F, BackoffMatcher >::fst_, TableMatcherOptions::min_table_size, and TableMatcherImpl< F, BackoffMatcher >::opts_.

67  :
68  match_type_(match_type),
69  fst_(fst.Copy()),
70  loop_(match_type == MATCH_INPUT ?
71  Arc(kNoLabel, 0, Weight::One(), kNoStateId) :
72  Arc(0, kNoLabel, Weight::One(), kNoStateId)),
73  aiter_(NULL),
74  s_(kNoStateId), opts_(opts),
75  backoff_matcher_(fst, match_type)
76  {
77  assert(opts_.min_table_size > 0);
78  if (match_type == MATCH_INPUT)
79  assert(fst_->Properties(kILabelSorted, true) == kILabelSorted);
80  else if (match_type == MATCH_OUTPUT)
81  assert(fst_->Properties(kOLabelSorted, true) == kOLabelSorted);
82  else
83  assert(0 && "Invalid FST properties");
84  }
Definition: graph.dox:21
TableMatcherOptions opts_
ArcIterator< FST > * aiter_
BackoffMatcher backoff_matcher_
virtual ~TableMatcherImpl ( )
inlinevirtual

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

References TableMatcherImpl< F, BackoffMatcher >::aiter_, TableMatcherImpl< F, BackoffMatcher >::fst_, rnnlm::i, and TableMatcherImpl< F, BackoffMatcher >::tables_.

88  {
89  vector<ArcId> *const empty = ((vector<ArcId>*)(NULL)) + 1; // special marker.
90  for (size_t i = 0; i < tables_.size(); i++) {
91  if (tables_[i] != NULL && tables_[i] != empty)
92  delete tables_[i];
93  }
94  delete aiter_;
95  delete fst_;
96  }
vector< vector< ArcId > * > tables_
ArcIterator< FST > * aiter_

Member Function Documentation

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

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

212  {
213  assert(0); // shouldn't be called. This is not a "real" matcher,
214  // although we derive from MatcherBase for convenience.
215  return NULL;
216  }
bool Done ( ) const
inline

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

References TableMatcherImpl< F, BackoffMatcher >::aiter_, TableMatcherImpl< F, BackoffMatcher >::backoff_matcher_, TableMatcherImpl< F, BackoffMatcher >::current_loop_, TableMatcherImpl< F, BackoffMatcher >::match_label_, and TableMatcherImpl< F, BackoffMatcher >::match_type_.

Referenced by TableMatcherImpl< F, BackoffMatcher >::Done_().

193  {
194  if (aiter_ != NULL) {
195  if (current_loop_)
196  return false;
197  if (aiter_->Done())
198  return true;
199  Label label = (match_type_ == MATCH_OUTPUT ?
200  aiter_->Value().olabel : aiter_->Value().ilabel);
201  return (label != match_label_);
202  } else
203  return backoff_matcher_.Done();
204  }
ArcIterator< FST > * aiter_
BackoffMatcher backoff_matcher_
virtual bool Done_ ( ) const
inlineprivatevirtual

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

References TableMatcherImpl< F, BackoffMatcher >::Done().

224 { return Done(); }
bool Find ( Label  match_label)
inline

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

References TableMatcherImpl< F, BackoffMatcher >::aiter_, TableMatcherImpl< F, BackoffMatcher >::backoff_matcher_, TableMatcherImpl< F, BackoffMatcher >::current_loop_, TableMatcherImpl< F, BackoffMatcher >::match_label_, TableMatcherImpl< F, BackoffMatcher >::s_, and TableMatcherImpl< F, BackoffMatcher >::tables_.

Referenced by TableMatcherImpl< F, BackoffMatcher >::Find_().

160  {
161  if (!aiter_) return backoff_matcher_.Find(match_label);
162  else {
163  match_label_ = match_label;
164  current_loop_ = (match_label == 0);
165  // kNoLabel means the implicit loop on the other FST --
166  // matches real epsilons but not the self-loop.
167  match_label_ = (match_label_ == kNoLabel ? 0 : match_label_);
168  if (static_cast<size_t>(match_label_) < tables_[s_]->size() &&
169  (*(tables_[s_]))[match_label_] != kNoStateId) {
170  aiter_->Seek( (*(tables_[s_]))[match_label_] ); // label exists.
171  return true;
172  }
173  return current_loop_;
174  }
175  }
vector< vector< ArcId > * > tables_
ArcIterator< FST > * aiter_
BackoffMatcher backoff_matcher_
virtual bool Find_ ( Label  label)
inlineprivatevirtual

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

References TableMatcherImpl< F, BackoffMatcher >::Find().

223 { return Find(label); }
bool Find(Label match_label)
virtual const FST& GetFst ( ) const
inlinevirtual

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

References TableMatcherImpl< F, BackoffMatcher >::fst_.

86 { return *fst_; }
void Next ( )
inline

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

References TableMatcherImpl< F, BackoffMatcher >::aiter_, TableMatcherImpl< F, BackoffMatcher >::backoff_matcher_, and TableMatcherImpl< F, BackoffMatcher >::current_loop_.

Referenced by TableMatcherImpl< F, BackoffMatcher >::Next_().

183  {
184  if (aiter_) {
185  if (current_loop_)
186  current_loop_ = false;
187  else
188  aiter_->Next();
189  } else
190  backoff_matcher_.Next();
191  }
ArcIterator< FST > * aiter_
BackoffMatcher backoff_matcher_
virtual void Next_ ( )
inlineprivatevirtual

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

References TableMatcherImpl< F, BackoffMatcher >::Next().

226 { Next(); }
virtual uint64 Properties ( uint64  props) const
inlinevirtual

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

218 { return props; } // simple matcher that does
void SetState ( StateId  s)
inline

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

References TableMatcherImpl< F, BackoffMatcher >::aiter_, TableMatcherImpl< F, BackoffMatcher >::backoff_matcher_, TableMatcherImpl< F, BackoffMatcher >::fst_, TableMatcherImpl< F, BackoffMatcher >::loop_, TableMatcherImpl< F, BackoffMatcher >::match_type_, TableMatcherOptions::min_table_size, TableMatcherImpl< F, BackoffMatcher >::opts_, TableMatcherImpl< F, BackoffMatcher >::s_, TableMatcherOptions::table_ratio, and TableMatcherImpl< F, BackoffMatcher >::tables_.

Referenced by TableMatcherImpl< F, BackoffMatcher >::SetState_().

102  {
103  if (aiter_) {
104  delete aiter_;
105  aiter_ = NULL;
106  }
107  if (match_type_ == MATCH_NONE)
108  LOG(FATAL) << "TableMatcher: bad match type";
109  s_ = s;
110  vector<ArcId> *const empty = ((vector<ArcId>*)(NULL)) + 1; // special marker.
111  if (static_cast<size_t>(s) >= tables_.size()) {
112  assert(s>=0);
113  tables_.resize(s+1, NULL);
114  }
115  vector<ArcId>* &this_table_ = tables_[s]; // note: ref to ptr.
116  if (this_table_ == empty) {
117  backoff_matcher_.SetState(s);
118  return;
119  } else if (this_table_ == NULL) { // NULL means has not been set.
120  ArcId num_arcs = fst_->NumArcs(s);
121  if (num_arcs == 0 || num_arcs < opts_.min_table_size) {
122  this_table_ = empty;
123  backoff_matcher_.SetState(s);
124  return;
125  }
126  ArcIterator<FST> aiter(*fst_, s);
127  aiter.SetFlags(kArcNoCache|(match_type_ == MATCH_OUTPUT?kArcOLabelValue:kArcILabelValue),
128  kArcNoCache|kArcValueFlags);
129  // the statement above, says: "Don't cache stuff; and I only need the ilabel/olabel
130  // to be computed.
131  aiter.Seek(num_arcs - 1);
132  Label highest_label = (match_type_ == MATCH_OUTPUT ?
133  aiter.Value().olabel : aiter.Value().ilabel);
134  if ((highest_label+1) * opts_.table_ratio > num_arcs) {
135  this_table_ = empty;
136  backoff_matcher_.SetState(s);
137  return; // table would be too sparse.
138  }
139  // OK, now we are creating the table.
140  this_table_ = new vector<ArcId> (highest_label+1, kNoStateId);
141  ArcId pos = 0;
142  for (aiter.Seek(0); !aiter.Done(); aiter.Next(), pos++) {
143  Label label = (match_type_ == MATCH_OUTPUT ?
144  aiter.Value().olabel : aiter.Value().ilabel);
145  assert((size_t)label <= (size_t)highest_label); // also checks >= 0.
146  if ((*this_table_)[label] == kNoStateId) (*this_table_)[label] = pos;
147  // set this_table_[label] to first position where arc has this
148  // label.
149  }
150  }
151  // At this point in the code, this_table_ != NULL and != empty.
152  aiter_ = new ArcIterator<FST>(*fst_, s);
153  aiter_->SetFlags(kArcNoCache, kArcNoCache); // don't need to cache arcs as may only
154  // need a small subset.
155  loop_.nextstate = s;
156  // aiter_ = NULL;
157  // backoff_matcher_.SetState(s);
158  }
vector< vector< ArcId > * > tables_
TableMatcherOptions opts_
ArcIterator< FST > * aiter_
BackoffMatcher backoff_matcher_
virtual void SetState_ ( StateId  s)
inlineprivatevirtual

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

References TableMatcherImpl< F, BackoffMatcher >::SetState().

222 { SetState(s); }
void SetState(StateId s)
virtual MatchType Type ( bool  test) const
inlinevirtual

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

References TableMatcherImpl< F, BackoffMatcher >::match_type_.

98  {
99  return match_type_;
100  }
const Arc& Value ( )
inline
virtual const Arc& Value_ ( ) const
inlineprivatevirtual

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

References TableMatcherImpl< F, BackoffMatcher >::Value().

225 { return Value(); }
const Arc & Value() const

Member Data Documentation


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