src/include/fst/state-table.h

   1 // See www.openfst.org for extensive documentation on this weighted
   2 // finite-state transducer library.
   3 //
   4 // Classes for representing the mapping between state tuples and state IDs.
   5
   6 #ifndef FST_LIB_STATE_TABLE_H_
   7 #define FST_LIB_STATE_TABLE_H_
   8
   9 #include <deque>
  10 #include <utility>
  11 #include <vector>
  12
  13 #include <fst/log.h>
  14
  15 #include <fst/bi-table.h>
  16 #include <fst/expanded-fst.h>
  17 #include <fst/filter-state.h>
  18
  19
  20 namespace fst {
  21
  22 // State tables determine the bijective mapping between state tuples (e.g., in
  23 // composition, triples of two FST states and a composition filter state) and
  24 // their corresponding state IDs. They are classes, templated on state tuples,
  25 // with the following interface:
  26 //
  27 // template <class T>
  28 // class StateTable {
  29 //  public:
  30 //   using StateTuple = T;
  31 //
  32 //   // Required constructors.
  33 //   StateTable();
  34 //
  35 //   StateTable(const StateTable &);
  36 //
  37 //   // Looks up state ID by tuple. If it doesn't exist, then add it.
  38 //   StateId FindState(const StateTuple &tuple);
  39 //
  40 //   // Looks up state tuple by state ID.
  41 //   const StateTuple<StateId> &Tuple(StateId s) const;
  42 //
  43 //   // # of stored tuples.
  44 //   StateId Size() const;
  45 // };
  46 //
  47 // A state tuple has the form:
  48 //
  49 // template <class S>
  50 // struct StateTuple {
  51 //   using StateId = S;
  52 //
  53 //   // Required constructors.
  54 //
  55 //   StateTuple();
  56 //
  57 //   StateTuple(const StateTuple &tuple);
  58 // };
  59
  60 // An implementation using a hash map for the tuple to state ID mapping. The
  61 // state tuple T must support operator==.
  62 template <class T, class H>
  63 class HashStateTable : public HashBiTable<typename T::StateId, T, H> {
  64  public:
  65   using StateTuple = T;
  66   using StateId = typename StateTuple::StateId;
  67
  68   using HashBiTable<StateId, StateTuple, H>::FindId;
  69   using HashBiTable<StateId, StateTuple, H>::FindEntry;
  70   using HashBiTable<StateId, StateTuple, H>::Size;
  71
  72   HashStateTable() : HashBiTable<StateId, StateTuple, H>() {}
  73
  74   explicit HashStateTable(size_t table_size)
  75       : HashBiTable<StateId, StateTuple, H>(table_size) {}
  76
  77   StateId FindState(const StateTuple &tuple) { return FindId(tuple); }
  78
  79   const StateTuple &Tuple(StateId s) const { return FindEntry(s); }
  80 };
  81
  82 // An implementation using a hash map for the tuple to state ID mapping. The
  83 // state tuple T must support operator==.
  84 template <class T, class H>
  85 class CompactHashStateTable
  86     : public CompactHashBiTable<typename T::StateId, T, H> {
  87  public:
  88   using StateTuple = T;
  89   using StateId = typename StateTuple::StateId;
  90
  91   using CompactHashBiTable<StateId, StateTuple, H>::FindId;
  92   using CompactHashBiTable<StateId, StateTuple, H>::FindEntry;
  93   using CompactHashBiTable<StateId, StateTuple, H>::Size;
  94
  95   CompactHashStateTable() : CompactHashBiTable<StateId, StateTuple, H>() {}
  96
  97   explicit CompactHashStateTable(size_t table_size)
  98       : CompactHashBiTable<StateId, StateTuple, H>(table_size) {}
  99
 100   StateId FindState(const StateTuple &tuple) { return FindId(tuple); }
 101
 102   const StateTuple &Tuple(StateId s) const { return FindEntry(s); }
 103 };
 104
 105 // An implementation using a vector for the tuple to state mapping. It is
 106 // passed a fingerprint functor that should fingerprint tuples uniquely to an
 107 // integer that can used as a vector index. Normally, VectorStateTable
 108 // constructs the fingerprint functor. Alternately, the user can pass this
 109 // objert, in which case the table takes ownership.
 110 template <class T, class FP>
 111 class VectorStateTable : public VectorBiTable<typename T::StateId, T, FP> {
 112  public:
 113   using StateTuple = T;
 114   using StateId = typename StateTuple::StateId;
 115
 116   using VectorBiTable<StateId, StateTuple, FP>::FindId;
 117   using VectorBiTable<StateId, StateTuple, FP>::FindEntry;
 118   using VectorBiTable<StateId, StateTuple, FP>::Size;
 119   using VectorBiTable<StateId, StateTuple, FP>::Fingerprint;
 120
 121   explicit VectorStateTable(FP *fingerprint = nullptr, size_t table_size = 0)
 122       : VectorBiTable<StateId, StateTuple, FP>(fingerprint, table_size) {}
 123
 124   StateId FindState(const StateTuple &tuple) { return FindId(tuple); }
 125
 126   const StateTuple &Tuple(StateId s) const { return FindEntry(s); }
 127 };
 128
 129 // An implementation using a vector and a compact hash table. The selection
 130 // functor returns true for tuples to be hashed in the vector. The fingerprint
 131 // functor should fingerprint tuples uniquely to an integer that can be used as
 132 // a vector index. A hash functor is used when hashing tuples into the compact
 133 // hash table.
 134 template <class T, class Select, class FP, class H>
 135 class VectorHashStateTable
 136     : public VectorHashBiTable<typename T::StateId, T, Select, FP, H> {
 137  public:
 138   using StateTuple = T;
 139   using StateId = typename StateTuple::StateId;
 140
 141   using VectorHashBiTable<StateId, StateTuple, Select, FP, H>::FindId;
 142   using VectorHashBiTable<StateId, StateTuple, Select, FP, H>::FindEntry;
 143   using VectorHashBiTable<StateId, StateTuple, Select, FP, H>::Size;
 144   using VectorHashBiTable<StateId, StateTuple, Select, FP, H>::Selector;
 145   using VectorHashBiTable<StateId, StateTuple, Select, FP, H>::Fingerprint;
 146   using VectorHashBiTable<StateId, StateTuple, Select, FP, H>::Hash;
 147
 148   VectorHashStateTable(Select *select, FP *fingerprint, H *hash,
 149                        size_t vector_size = 0, size_t tuple_size = 0)
 150       : VectorHashBiTable<StateId, StateTuple, Select, FP, H>(
 151             select, fingerprint, hash, vector_size, tuple_size) {}
 152
 153   StateId FindState(const StateTuple &tuple) { return FindId(tuple); }
 154
 155   const StateTuple &Tuple(StateId s) const { return FindEntry(s); }
 156 };
 157
 158 // An implementation using a hash map to map from tuples to state IDs. This
 159 // version permits erasing of states. The state tuple's default constructor
 160 // must produce a tuple that will never be seen and the table must suppor
 161 // operator==.
 162 template <class T, class H>
 163 class ErasableStateTable : public ErasableBiTable<typename T::StateId, T, H> {
 164  public:
 165   using StateTuple = T;
 166   using StateId = typename StateTuple::StateId;
 167
 168   using ErasableBiTable<StateId, StateTuple, H>::FindId;
 169   using ErasableBiTable<StateId, StateTuple, H>::FindEntry;
 170   using ErasableBiTable<StateId, StateTuple, H>::Size;
 171   using ErasableBiTable<StateId, StateTuple, H>::Erase;
 172
 173   ErasableStateTable() : ErasableBiTable<StateId, StateTuple, H>() {}
 174
 175   StateId FindState(const StateTuple &tuple) { return FindId(tuple); }
 176
 177   const StateTuple &Tuple(StateId s) const { return FindEntry(s); }
 178 };
 179
 180 // The composition state table has the form:
 181 //
 182 // template <class Arc, class FilterState>
 183 // class ComposeStateTable {
 184 //  public:
 185 //   using StateId = typename Arc::StateId;
 186 //
 187 //   // Required constructors.
 188 //
 189 //   ComposeStateTable(const Fst<Arc> &fst1, const Fst<Arc> &fst2);
 190 //   ComposeStateTable(const ComposeStateTable<Arc, FilterState> &table);
 191 //
 192 //   // Looks up a state ID by tuple, adding it if doesn't exist.
 193 //   StateId FindState(const StateTuple &tuple);
 194 //
 195 //   // Looks up a tuple by state ID.
 196 //   const ComposeStateTuple<StateId> &Tuple(StateId s) const;
 197 //
 198 //   // The number of of stored tuples.
 199 //   StateId Size() const;
 200 //
 201 //   // Return true if error was encountered.
 202 //   bool Error() const;
 203 // };
 204 //
 205 // The following interface is used to represent the composition state.
 206 //
 207 // template <class S, class FS>
 208 // class CompositionStateTuple {
 209 //  public:
 210 //   using StateId = typename StateId;
 211 //   using FS = FilterState;
 212 //
 213 //   // Required constructors.
 214 //   StateTuple();
 215 //   StateTuple(StateId s1, StateId s2, const FilterState &fs);
 216 //
 217 //   StateId StateId1() const;
 218 //   StateId StateId2() const;
 219 //
 220 //   FilterState GetFilterState() const;
 221 //
 222 //   std::pair<StateId, StateId> StatePair() const;
 223 //
 224 //   size_t Hash() const;
 225 //
 226 //   friend bool operator==(const StateTuple& x, const StateTuple &y);
 227 // }
 228 //
 229 template <typename S, typename FS>
 230 class DefaultComposeStateTuple {
 231  public:
 232   using StateId = S;
 233   using FilterState = FS;
 234
 235   DefaultComposeStateTuple()
 236       : state_pair_(kNoStateId, kNoStateId), fs_(FilterState::NoState()) {}
 237
 238   DefaultComposeStateTuple(StateId s1, StateId s2, const FilterState &fs)
 239       : state_pair_(s1, s2), fs_(fs) {}
 240
 241   StateId StateId1() const { return state_pair_.first; }
 242
 243   StateId StateId2() const { return state_pair_.second; }
 244
 245   FilterState GetFilterState() const { return fs_; }
 246
 247   const std::pair<StateId, StateId> &StatePair() const { return state_pair_; }
 248
 249   friend bool operator==(const DefaultComposeStateTuple &x,
 250                          const DefaultComposeStateTuple &y) {
 251     return (&x == &y) || (x.state_pair_ == y.state_pair_ && x.fs_ == y.fs_);
 252   }
 253
 254   size_t Hash() const {
 255     return StateId1() + StateId2() * 7853 + GetFilterState().Hash() * 7867;
 256   }
 257
 258  private:
 259   std::pair<StateId, StateId> state_pair_;
 260   FilterState fs_;  // State of composition filter.
 261 };
 262
 263 // Specialization for TrivialFilterState that does not explicitely store the
 264 // filter state since it is always the unique non-blocking state.
 265 template <typename S>
 266 class DefaultComposeStateTuple<S, TrivialFilterState> {
 267  public:
 268   using StateId = S;
 269   using FilterState = TrivialFilterState;
 270
 271   DefaultComposeStateTuple()
 272       : state_pair_(kNoStateId, kNoStateId) {}
 273
 274   DefaultComposeStateTuple(StateId s1, StateId s2, const FilterState &)
 275       : state_pair_(s1, s2) {}
 276
 277   StateId StateId1() const { return state_pair_.first; }
 278
 279   StateId StateId2() const { return state_pair_.second; }
 280
 281   FilterState GetFilterState() const { return FilterState(true); }
 282
 283   const std::pair<StateId, StateId> &StatePair() const { return state_pair_; }
 284
 285   friend bool operator==(const DefaultComposeStateTuple &x,
 286                          const DefaultComposeStateTuple &y) {
 287     return (&x == &y) || (x.state_pair_ == y.state_pair_);
 288   }
 289
 290   size_t Hash() const { return StateId1() + StateId2() * 7853; }
 291
 292  private:
 293   std::pair<StateId, StateId> state_pair_;
 294 };
 295
 296 // Hashing of composition state tuples.
 297 template <typename T>
 298 class ComposeHash {
 299  public:
 300   size_t operator()(const T &t) const { return t.Hash(); }
 301 };
 302
 303 // A HashStateTable over composition tuples.
 304 template <typename Arc, typename FilterState,
 305           typename StateTuple =
 306               DefaultComposeStateTuple<typename Arc::StateId, FilterState>,
 307           typename StateTable =
 308               CompactHashStateTable<StateTuple, ComposeHash<StateTuple>>>
 309 class GenericComposeStateTable : public StateTable {
 310  public:
 311   using StateId = typename Arc::StateId;
 312
 313   GenericComposeStateTable(const Fst<Arc> &fst1, const Fst<Arc> &fst2) {}
 314
 315   GenericComposeStateTable(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
 316                            size_t table_size)
 317       : StateTable(table_size) {}
 318
 319   constexpr bool Error() const { return false; }
 320
 321  private:
 322   GenericComposeStateTable &operator=(const GenericComposeStateTable &table) =
 323       delete;
 324 };
 325
 326 //  Fingerprint for general composition tuples.
 327 template <typename StateTuple>
 328 class ComposeFingerprint {
 329  public:
 330   using StateId = typename StateTuple::StateId;
 331
 332   // Required but suboptimal constructor.
 333   ComposeFingerprint() : mult1_(8192), mult2_(8192) {
 334     LOG(WARNING) << "TupleFingerprint: # of FST states should be provided.";
 335   }
 336
 337   // Constructor is provided the sizes of the input FSTs.
 338   ComposeFingerprint(StateId nstates1, StateId nstates2)
 339       : mult1_(nstates1), mult2_(nstates1 * nstates2) {}
 340
 341   size_t operator()(const StateTuple &tuple) {
 342     return tuple.StateId1() + tuple.StateId2() * mult1_ +
 343            tuple.GetFilterState().Hash() * mult2_;
 344   }
 345
 346  private:
 347   const ssize_t mult1_;
 348   const ssize_t mult2_;
 349 };
 350
 351 // Useful when the first composition state determines the tuple.
 352 template <typename StateTuple>
 353 class ComposeState1Fingerprint {
 354  public:
 355   size_t operator()(const StateTuple &tuple) { return tuple.StateId1(); }
 356 };
 357
 358 // Useful when the second composition state determines the tuple.
 359 template <typename StateTuple>
 360 class ComposeState2Fingerprint {
 361  public:
 362   size_t operator()(const StateTuple &tuple) { return tuple.StateId2(); }
 363 };
 364
 365 // A VectorStateTable over composition tuples. This can be used when the
 366 // product of number of states in FST1 and FST2 (and the composition filter
 367 // state hash) is manageable. If the FSTs are not expanded FSTs, they will
 368 // first have their states counted.
 369 template <typename Arc, typename StateTuple>
 370 class ProductComposeStateTable
 371     : public VectorStateTable<StateTuple, ComposeFingerprint<StateTuple>> {
 372  public:
 373   using StateId = typename Arc::StateId;
 374   using StateTable =
 375       VectorStateTable<StateTuple, ComposeFingerprint<StateTuple>>;
 376
 377   ProductComposeStateTable(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
 378                            size_t table_size = 0)
 379       : StateTable(new ComposeFingerprint<StateTuple>(CountStates(fst1),
 380                                                       CountStates(fst2)),
 381                    table_size) {}
 382
 383   ProductComposeStateTable(
 384       const ProductComposeStateTable<Arc, StateTuple> &table)
 385       : StateTable(new ComposeFingerprint<StateTuple>(table.Fingerprint())) {}
 386
 387   constexpr bool Error() const { return false; }
 388
 389  private:
 390   ProductComposeStateTable &operator=(const ProductComposeStateTable &table) =
 391       delete;
 392 };
 393
 394 // A vector-backed table over composition tuples which can be used when the
 395 // first FST is a string (i.e., satisfies kStringProperties) and the second is
 396 // deterministic and epsilon-free. It should be used with a composition filter
 397 // that creates at most one filter state per tuple under these conditions (e.g.,
 398 // SequenceComposeFilter or MatchComposeFilter).
 399 template <typename Arc, typename StateTuple>
 400 class StringDetComposeStateTable
 401     : public VectorStateTable<StateTuple,
 402                               ComposeState1Fingerprint<StateTuple>> {
 403  public:
 404   using StateId = typename Arc::StateId;
 405   using StateTable =
 406       VectorStateTable<StateTuple, ComposeState1Fingerprint<StateTuple>>;
 407
 408   StringDetComposeStateTable(const Fst<Arc> &fst1, const Fst<Arc> &fst2)
 409       : error_(false) {
 410     static constexpr auto props2 = kIDeterministic | kNoIEpsilons;
 411     if (fst1.Properties(kString, true) != kString) {
 412       FSTERROR() << "StringDetComposeStateTable: 1st FST is not a string";
 413       error_ = true;
 414     } else if (fst2.Properties(props2, true) != props2) {
 415       FSTERROR() << "StringDetComposeStateTable: 2nd FST is not deterministic "
 416                     "and epsilon-free";
 417       error_ = true;
 418     }
 419   }
 420
 421   StringDetComposeStateTable(
 422       const StringDetComposeStateTable<Arc, StateTuple> &table)
 423       : StateTable(table), error_(table.error_) {}
 424
 425   bool Error() const { return error_; }
 426
 427  private:
 428   bool error_;
 429
 430   StringDetComposeStateTable &operator=(const StringDetComposeStateTable &) =
 431       delete;
 432 };
 433
 434 // A vector-backed table over composition tuples which can be used when the
 435 // first FST is deterministic and epsilon-free and the second is a string (i.e.,
 436 // satisfies kString). It should be used with a composition filter that creates
 437 // at most one filter state per tuple under these conditions (e.g.,
 438 // SequenceComposeFilter or MatchComposeFilter).
 439 template <typename Arc, typename StateTuple>
 440 class DetStringComposeStateTable
 441     : public VectorStateTable<StateTuple,
 442                               ComposeState2Fingerprint<StateTuple>> {
 443  public:
 444   using StateId = typename Arc::StateId;
 445   using StateTable =
 446       VectorStateTable<StateTuple, ComposeState2Fingerprint<StateTuple>>;
 447
 448   DetStringComposeStateTable(const Fst<Arc> &fst1, const Fst<Arc> &fst2)
 449       : error_(false) {
 450     static constexpr auto props = kODeterministic | kNoOEpsilons;
 451     if (fst1.Properties(props, true) != props) {
 452       FSTERROR() << "StringDetComposeStateTable: 1st FST is not "
 453                  << "input-deterministic and epsilon-free";
 454       error_ = true;
 455     } else if (fst2.Properties(kString, true) != kString) {
 456       FSTERROR() << "DetStringComposeStateTable: 2nd FST is not a string";
 457       error_ = true;
 458     }
 459   }
 460
 461   DetStringComposeStateTable(
 462       const DetStringComposeStateTable<Arc, StateTuple> &table)
 463       : StateTable(table), error_(table.error_) {}
 464
 465   bool Error() const { return error_; }
 466
 467  private:
 468   bool error_;
 469
 470   DetStringComposeStateTable &operator=(const DetStringComposeStateTable &) =
 471       delete;
 472 };
 473
 474 // An erasable table over composition tuples. The Erase(StateId) method can be
 475 // called if the user either is sure that composition will never return to that
 476 // tuple or doesn't care that if it does, it is assigned a new state ID.
 477 template <typename Arc, typename StateTuple>
 478 class ErasableComposeStateTable
 479     : public ErasableStateTable<StateTuple, ComposeHash<StateTuple>> {
 480  public:
 481   ErasableComposeStateTable(const Fst<Arc> &fst1, const Fst<Arc> &fst2) {}
 482
 483   constexpr bool Error() const { return false; }
 484
 485  private:
 486   ErasableComposeStateTable &operator=(const ErasableComposeStateTable &table) =
 487       delete;
 488 };
 489
 490 }  // namespace fst
 491
 492 #endif  // FST_LIB_STATE_TABLE_H_