summaryrefslogtreecommitdiff
path: root/kaldi_io/src/tools/openfst/include/fst/state-table.h
diff options
context:
space:
mode:
Diffstat (limited to 'kaldi_io/src/tools/openfst/include/fst/state-table.h')
-rw-r--r--kaldi_io/src/tools/openfst/include/fst/state-table.h481
1 files changed, 481 insertions, 0 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/state-table.h b/kaldi_io/src/tools/openfst/include/fst/state-table.h
new file mode 100644
index 0000000..d8107a1
--- /dev/null
+++ b/kaldi_io/src/tools/openfst/include/fst/state-table.h
@@ -0,0 +1,481 @@
+// state-table.h
+
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Copyright 2005-2010 Google, Inc.
+// Author: [email protected] (Michael Riley)
+//
+// \file
+// Classes for representing the mapping between state tuples and state Ids.
+
+#ifndef FST_LIB_STATE_TABLE_H__
+#define FST_LIB_STATE_TABLE_H__
+
+#include <deque>
+using std::deque;
+#include <vector>
+using std::vector;
+
+#include <fst/bi-table.h>
+#include <fst/expanded-fst.h>
+
+
+namespace fst {
+
+// STATE TABLES - these determine the bijective mapping between state
+// tuples (e.g. in composition triples of two FST states and a
+// composition filter state) and their corresponding state IDs.
+// They are classes, templated on state tuples, of the form:
+//
+// template <class T>
+// class StateTable {
+// public:
+// typedef typename T StateTuple;
+//
+// // Required constructors.
+// StateTable();
+//
+// // Lookup state ID by tuple. If it doesn't exist, then add it.
+// StateId FindState(const StateTuple &);
+// // Lookup state tuple by state ID.
+// const StateTuple<StateId> &Tuple(StateId) const;
+// // # of stored tuples.
+// StateId Size() const;
+// };
+//
+// A state tuple has the form:
+//
+// template <class S>
+// struct StateTuple {
+// typedef typename S StateId;
+//
+// // Required constructors.
+// StateTuple();
+// StateTuple(const StateTuple &);
+// };
+
+
+// An implementation using a hash map for the tuple to state ID mapping.
+// The state tuple T must have == defined. H is the hash function.
+template <class T, class H>
+class HashStateTable : public HashBiTable<typename T::StateId, T, H> {
+ public:
+ typedef T StateTuple;
+ typedef typename StateTuple::StateId StateId;
+ using HashBiTable<StateId, T, H>::FindId;
+ using HashBiTable<StateId, T, H>::FindEntry;
+ using HashBiTable<StateId, T, H>::Size;
+
+ HashStateTable() : HashBiTable<StateId, T, H>() {}
+
+ // Reserves space for table_size elements.
+ explicit HashStateTable(size_t table_size)
+ : HashBiTable<StateId, T, H>(table_size) {}
+
+ StateId FindState(const StateTuple &tuple) { return FindId(tuple); }
+ const StateTuple &Tuple(StateId s) const { return FindEntry(s); }
+};
+
+
+// An implementation using a hash map for the tuple to state ID mapping.
+// The state tuple T must have == defined. H is the hash function.
+template <class T, class H>
+class CompactHashStateTable
+ : public CompactHashBiTable<typename T::StateId, T, H> {
+ public:
+ typedef T StateTuple;
+ typedef typename StateTuple::StateId StateId;
+ using CompactHashBiTable<StateId, T, H>::FindId;
+ using CompactHashBiTable<StateId, T, H>::FindEntry;
+ using CompactHashBiTable<StateId, T, H>::Size;
+
+ CompactHashStateTable() : CompactHashBiTable<StateId, T, H>() {}
+
+ // Reserves space for 'table_size' elements.
+ explicit CompactHashStateTable(size_t table_size)
+ : CompactHashBiTable<StateId, T, H>(table_size) {}
+
+ StateId FindState(const StateTuple &tuple) { return FindId(tuple); }
+ const StateTuple &Tuple(StateId s) const { return FindEntry(s); }
+};
+
+// An implementation using a vector for the tuple to state mapping.
+// It is passed a function object FP that should fingerprint tuples
+// uniquely to an integer that can used as a vector index. Normally,
+// VectorStateTable constructs the FP object. The user can instead
+// pass in this object; in that case, VectorStateTable takes its
+// ownership.
+template <class T, class FP>
+class VectorStateTable
+ : public VectorBiTable<typename T::StateId, T, FP> {
+ public:
+ typedef T StateTuple;
+ typedef typename StateTuple::StateId StateId;
+ using VectorBiTable<StateId, T, FP>::FindId;
+ using VectorBiTable<StateId, T, FP>::FindEntry;
+ using VectorBiTable<StateId, T, FP>::Size;
+ using VectorBiTable<StateId, T, FP>::Fingerprint;
+
+ // Reserves space for 'table_size' elements.
+ explicit VectorStateTable(FP *fp = 0, size_t table_size = 0)
+ : VectorBiTable<StateId, T, FP>(fp, table_size) {}
+
+ StateId FindState(const StateTuple &tuple) { return FindId(tuple); }
+ const StateTuple &Tuple(StateId s) const { return FindEntry(s); }
+};
+
+
+// An implementation using a vector and a compact hash table. The
+// selecting functor S returns true for tuples to be hashed in the
+// vector. The fingerprinting functor FP returns a unique fingerprint
+// for each tuple to be hashed in the vector (these need to be
+// suitable for indexing in a vector). The hash functor H is used when
+// hashing tuple into the compact hash table.
+template <class T, class S, class FP, class H>
+class VectorHashStateTable
+ : public VectorHashBiTable<typename T::StateId, T, S, FP, H> {
+ public:
+ typedef T StateTuple;
+ typedef typename StateTuple::StateId StateId;
+ using VectorHashBiTable<StateId, T, S, FP, H>::FindId;
+ using VectorHashBiTable<StateId, T, S, FP, H>::FindEntry;
+ using VectorHashBiTable<StateId, T, S, FP, H>::Size;
+ using VectorHashBiTable<StateId, T, S, FP, H>::Selector;
+ using VectorHashBiTable<StateId, T, S, FP, H>::Fingerprint;
+ using VectorHashBiTable<StateId, T, S, FP, H>::Hash;
+
+ VectorHashStateTable(S *s, FP *fp, H *h,
+ size_t vector_size = 0,
+ size_t tuple_size = 0)
+ : VectorHashBiTable<StateId, T, S, FP, H>(
+ s, fp, h, vector_size, tuple_size) {}
+
+ StateId FindState(const StateTuple &tuple) { return FindId(tuple); }
+ const StateTuple &Tuple(StateId s) const { return FindEntry(s); }
+};
+
+
+// An implementation using a hash map for the tuple to state ID
+// mapping. This version permits erasing of states. The state tuple T
+// must have == defined and its default constructor must produce a
+// tuple that will never be seen. F is the hash function.
+template <class T, class F>
+class ErasableStateTable : public ErasableBiTable<typename T::StateId, T, F> {
+ public:
+ typedef T StateTuple;
+ typedef typename StateTuple::StateId StateId;
+ using ErasableBiTable<StateId, T, F>::FindId;
+ using ErasableBiTable<StateId, T, F>::FindEntry;
+ using ErasableBiTable<StateId, T, F>::Size;
+ using ErasableBiTable<StateId, T, F>::Erase;
+
+ ErasableStateTable() : ErasableBiTable<StateId, T, F>() {}
+ StateId FindState(const StateTuple &tuple) { return FindId(tuple); }
+ const StateTuple &Tuple(StateId s) const { return FindEntry(s); }
+};
+
+//
+// COMPOSITION STATE TUPLES AND TABLES
+//
+// The composition state table has the form:
+//
+// template <class A, class F>
+// class ComposeStateTable {
+// public:
+// typedef A Arc;
+// typedef F FilterState;
+// typedef typename A::StateId StateId;
+// typedef ComposeStateTuple<StateId> StateTuple;
+//
+// // Required constructors. Copy constructor does not copy state.
+// ComposeStateTable(const Fst<Arc> &fst1, const Fst<Arc> &fst2);
+// ComposeStateTable(const ComposeStateTable<A, F> &table);
+// // Lookup state ID by tuple. If it doesn't exist, then add it.
+// StateId FindState(const StateTuple &);
+// // Lookup state tuple by state ID.
+// const StateTuple<StateId> &Tuple(StateId) const;
+// // # of stored tuples.
+// StateId Size() const;
+// // Return true if error encountered
+// bool Error() const;
+// };
+
+// Represents the composition state.
+template <typename S, typename F>
+struct ComposeStateTuple {
+ typedef S StateId;
+ typedef F FilterState;
+
+ ComposeStateTuple()
+ : state_id1(kNoStateId), state_id2(kNoStateId),
+ filter_state(FilterState::NoState()) {}
+
+ ComposeStateTuple(StateId s1, StateId s2, const FilterState &f)
+ : state_id1(s1), state_id2(s2), filter_state(f) {}
+
+ StateId state_id1; // State Id on fst1
+ StateId state_id2; // State Id on fst2
+ FilterState filter_state; // State of composition filter
+};
+
+// Equality of composition state tuples.
+template <typename S, typename F>
+inline bool operator==(const ComposeStateTuple<S, F>& x,
+ const ComposeStateTuple<S, F>& y) {
+ if (&x == &y)
+ return true;
+ return x.state_id1 == y.state_id1 &&
+ x.state_id2 == y.state_id2 &&
+ x.filter_state == y.filter_state;
+}
+
+
+// Hashing of composition state tuples.
+template <typename S, typename F>
+class ComposeHash {
+ public:
+ size_t operator()(const ComposeStateTuple<S, F>& t) const {
+ return t.state_id1 + t.state_id2 * kPrime0 +
+ t.filter_state.Hash() * kPrime1;
+ }
+ private:
+ static const size_t kPrime0;
+ static const size_t kPrime1;
+};
+
+template <typename S, typename F>
+const size_t ComposeHash<S, F>::kPrime0 = 7853;
+
+template <typename S, typename F>
+const size_t ComposeHash<S, F>::kPrime1 = 7867;
+
+
+// A HashStateTable over composition tuples.
+template <typename A,
+ typename F,
+ typename H =
+ CompactHashStateTable<ComposeStateTuple<typename A::StateId, F>,
+ ComposeHash<typename A::StateId, F> > >
+class GenericComposeStateTable : public H {
+ public:
+ typedef A Arc;
+ typedef typename A::StateId StateId;
+ typedef F FilterState;
+ typedef ComposeStateTuple<StateId, F> StateTuple;
+
+ GenericComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2) {}
+
+ // Reserves space for 'table_size' elements.
+ GenericComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2,
+ size_t table_size) : H(table_size) {}
+
+ bool Error() const { return false; }
+
+ private:
+ void operator=(const GenericComposeStateTable<A, F> &table); // disallow
+};
+
+
+// Fingerprint for general composition tuples.
+template <typename S, typename F>
+class ComposeFingerprint {
+ public:
+ typedef S StateId;
+ typedef F FilterState;
+ typedef ComposeStateTuple<S, F> StateTuple;
+
+ // Required but suboptimal constructor.
+ ComposeFingerprint() : mult1_(8192), mult2_(8192) {
+ LOG(WARNING) << "TupleFingerprint: # of FST states should be provided.";
+ }
+
+ // Constructor is provided the sizes of the input FSTs
+ ComposeFingerprint(StateId nstates1, StateId nstates2)
+ : mult1_(nstates1), mult2_(nstates1 * nstates2) { }
+
+ size_t operator()(const StateTuple &tuple) {
+ return tuple.state_id1 + tuple.state_id2 * mult1_ +
+ tuple.filter_state.Hash() * mult2_;
+ }
+
+ private:
+ ssize_t mult1_;
+ ssize_t mult2_;
+};
+
+
+// Useful when the first composition state determines the tuple.
+template <typename S, typename F>
+class ComposeState1Fingerprint {
+ public:
+ typedef S StateId;
+ typedef F FilterState;
+ typedef ComposeStateTuple<S, F> StateTuple;
+
+ size_t operator()(const StateTuple &tuple) { return tuple.state_id1; }
+};
+
+
+// Useful when the second composition state determines the tuple.
+template <typename S, typename F>
+class ComposeState2Fingerprint {
+ public:
+ typedef S StateId;
+ typedef F FilterState;
+ typedef ComposeStateTuple<S, F> StateTuple;
+
+ size_t operator()(const StateTuple &tuple) { return tuple.state_id2; }
+};
+
+
+// A VectorStateTable over composition tuples. This can be used when
+// the product of number of states in FST1 and FST2 (and the
+// composition filter state hash) is manageable. If the FSTs are not
+// expanded Fsts, they will first have their states counted.
+template <typename A, typename F>
+class ProductComposeStateTable : public
+VectorStateTable<ComposeStateTuple<typename A::StateId, F>,
+ ComposeFingerprint<typename A::StateId, F> > {
+ public:
+ typedef A Arc;
+ typedef typename A::StateId StateId;
+ typedef F FilterState;
+ typedef ComposeStateTuple<StateId, F> StateTuple;
+ typedef VectorStateTable<StateTuple,
+ ComposeFingerprint<StateId, F> > StateTable;
+
+ // Reserves space for 'table_size' elements.
+ ProductComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2,
+ size_t table_size = 0)
+ : StateTable(new ComposeFingerprint<StateId, F>(CountStates(fst1),
+ CountStates(fst2)),
+ table_size) {}
+
+ ProductComposeStateTable(const ProductComposeStateTable<A, F> &table)
+ : StateTable(new ComposeFingerprint<StateId, F>(table.Fingerprint())) {}
+
+ bool Error() const { return false; }
+
+ private:
+ void operator=(const ProductComposeStateTable<A, F> &table); // disallow
+};
+
+// A VectorStateTable over composition tuples. This can be used when
+// FST1 is a string (satisfies kStringProperties) and FST2 is
+// epsilon-free and deterministic. It should be used with a
+// composition filter that creates at most one filter state per tuple
+// under these conditions (e.g. SequenceComposeFilter or
+// MatchComposeFilter).
+template <typename A, typename F>
+class StringDetComposeStateTable : public
+VectorStateTable<ComposeStateTuple<typename A::StateId, F>,
+ ComposeState1Fingerprint<typename A::StateId, F> > {
+ public:
+ typedef A Arc;
+ typedef typename A::StateId StateId;
+ typedef F FilterState;
+ typedef ComposeStateTuple<StateId, F> StateTuple;
+ typedef VectorStateTable<StateTuple,
+ ComposeState1Fingerprint<StateId, F> > StateTable;
+
+ StringDetComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2)
+ : error_(false) {
+ uint64 props1 = kString;
+ uint64 props2 = kIDeterministic | kNoIEpsilons;
+ if (fst1.Properties(props1, true) != props1 ||
+ fst2.Properties(props2, true) != props2) {
+ FSTERROR() << "StringDetComposeStateTable: fst1 not a string or"
+ << " fst2 not input deterministic and epsilon-free";
+ error_ = true;
+ }
+ }
+
+ StringDetComposeStateTable(const StringDetComposeStateTable<A, F> &table)
+ : StateTable(table), error_(table.error_) {}
+
+ bool Error() const { return error_; }
+
+ private:
+ bool error_;
+
+ void operator=(const StringDetComposeStateTable<A, F> &table); // disallow
+};
+
+
+// A VectorStateTable over composition tuples. This can be used when
+// FST2 is a string (satisfies kStringProperties) and FST1 is
+// epsilon-free and deterministic. It should be used with a
+// composition filter that creates at most one filter state per tuple
+// under these conditions (e.g. SequenceComposeFilter or
+// MatchComposeFilter).
+template <typename A, typename F>
+class DetStringComposeStateTable : public
+VectorStateTable<ComposeStateTuple<typename A::StateId, F>,
+ ComposeState2Fingerprint<typename A::StateId, F> > {
+ public:
+ typedef A Arc;
+ typedef typename A::StateId StateId;
+ typedef F FilterState;
+ typedef ComposeStateTuple<StateId, F> StateTuple;
+ typedef VectorStateTable<StateTuple,
+ ComposeState2Fingerprint<StateId, F> > StateTable;
+
+ DetStringComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2)
+ :error_(false) {
+ uint64 props1 = kODeterministic | kNoOEpsilons;
+ uint64 props2 = kString;
+ if (fst1.Properties(props1, true) != props1 ||
+ fst2.Properties(props2, true) != props2) {
+ FSTERROR() << "StringDetComposeStateTable: fst2 not a string or"
+ << " fst1 not output deterministic and epsilon-free";
+ error_ = true;
+ }
+ }
+
+ DetStringComposeStateTable(const DetStringComposeStateTable<A, F> &table)
+ : StateTable(table), error_(table.error_) {}
+
+ bool Error() const { return error_; }
+
+ private:
+ bool error_;
+
+ void operator=(const DetStringComposeStateTable<A, F> &table); // disallow
+};
+
+
+// An ErasableStateTable over composition tuples. The Erase(StateId) method
+// can be called if the user either is sure that composition will never return
+// to that tuple or doesn't care that if it does, it is assigned a new
+// state ID.
+template <typename A, typename F>
+class ErasableComposeStateTable : public
+ErasableStateTable<ComposeStateTuple<typename A::StateId, F>,
+ ComposeHash<typename A::StateId, F> > {
+ public:
+ typedef A Arc;
+ typedef typename A::StateId StateId;
+ typedef F FilterState;
+ typedef ComposeStateTuple<StateId, F> StateTuple;
+
+ ErasableComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2) {}
+
+ bool Error() const { return false; }
+
+ private:
+ void operator=(const ErasableComposeStateTable<A, F> &table); // disallow
+};
+
+} // namespace fst
+
+#endif // FST_LIB_STATE_TABLE_H__