1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// state-table.h 2f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 3f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Licensed under the Apache License, Version 2.0 (the "License"); 4f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// you may not use this file except in compliance with the License. 5f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// You may obtain a copy of the License at 6f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 7f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// http://www.apache.org/licenses/LICENSE-2.0 8f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 9f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Unless required by applicable law or agreed to in writing, software 10f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// distributed under the License is distributed on an "AS IS" BASIS, 11f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// See the License for the specific language governing permissions and 13f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// limitations under the License. 14f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 15f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Copyright 2005-2010 Google, Inc. 16f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Author: riley@google.com (Michael Riley) 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \file 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Classes for representing the mapping between state tuples and state Ids. 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_LIB_STATE_TABLE_H__ 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_LIB_STATE_TABLE_H__ 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <deque> 255b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkinusing std::deque; 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <vector> 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::vector; 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/bi-table.h> 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/expanded-fst.h> 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace fst { 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// STATE TABLES - these determine the bijective mapping between state 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// tuples (e.g. in composition triples of two FST states and a 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// composition filter state) and their corresponding state IDs. 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// They are classes, templated on state tuples, of the form: 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// template <class T> 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// class StateTable { 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// public: 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// typedef typename T StateTuple; 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // Required constructors. 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// StateTable(); 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // Lookup state ID by tuple. If it doesn't exist, then add it. 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// StateId FindState(const StateTuple &); 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // Lookup state tuple by state ID. 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// const StateTuple<StateId> &Tuple(StateId) const; 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // # of stored tuples. 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// StateId Size() const; 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// }; 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// A state tuple has the form: 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// template <class S> 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// struct StateTuple { 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// typedef typename S StateId; 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 625b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// // Required constructors. 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// StateTuple(); 645b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// StateTuple(const StateTuple &); 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// }; 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// An implementation using a hash map for the tuple to state ID mapping. 695b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// The state tuple T must have == defined. H is the hash function. 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class T, class H> 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass HashStateTable : public HashBiTable<typename T::StateId, T, H> { 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef T StateTuple; 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename StateTuple::StateId StateId; 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using HashBiTable<StateId, T, H>::FindId; 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using HashBiTable<StateId, T, H>::FindEntry; 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using HashBiTable<StateId, T, H>::Size; 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson HashStateTable() : HashBiTable<StateId, T, H>() {} 805b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin 815b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin // Reserves space for table_size elements. 825b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin explicit HashStateTable(size_t table_size) 835b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin : HashBiTable<StateId, T, H>(table_size) {} 845b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId FindState(const StateTuple &tuple) { return FindId(tuple); } 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StateTuple &Tuple(StateId s) const { return FindEntry(s); } 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 905b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// An implementation using a hash map for the tuple to state ID mapping. 915b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// The state tuple T must have == defined. H is the hash function. 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class T, class H> 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass CompactHashStateTable 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : public CompactHashBiTable<typename T::StateId, T, H> { 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef T StateTuple; 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename StateTuple::StateId StateId; 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using CompactHashBiTable<StateId, T, H>::FindId; 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using CompactHashBiTable<StateId, T, H>::FindEntry; 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using CompactHashBiTable<StateId, T, H>::Size; 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CompactHashStateTable() : CompactHashBiTable<StateId, T, H>() {} 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1045b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin // Reserves space for 'table_size' elements. 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson explicit CompactHashStateTable(size_t table_size) 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : CompactHashBiTable<StateId, T, H>(table_size) {} 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId FindState(const StateTuple &tuple) { return FindId(tuple); } 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StateTuple &Tuple(StateId s) const { return FindEntry(s); } 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// An implementation using a vector for the tuple to state mapping. 113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// It is passed a function object FP that should fingerprint tuples 114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// uniquely to an integer that can used as a vector index. Normally, 115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// VectorStateTable constructs the FP object. The user can instead 116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// pass in this object; in that case, VectorStateTable takes its 117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// ownership. 118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class T, class FP> 119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass VectorStateTable 120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : public VectorBiTable<typename T::StateId, T, FP> { 121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef T StateTuple; 123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename StateTuple::StateId StateId; 124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using VectorBiTable<StateId, T, FP>::FindId; 125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using VectorBiTable<StateId, T, FP>::FindEntry; 126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using VectorBiTable<StateId, T, FP>::Size; 127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using VectorBiTable<StateId, T, FP>::Fingerprint; 128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1295b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin // Reserves space for 'table_size' elements. 1305b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin explicit VectorStateTable(FP *fp = 0, size_t table_size = 0) 1315b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin : VectorBiTable<StateId, T, FP>(fp, table_size) {} 1325b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin 133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId FindState(const StateTuple &tuple) { return FindId(tuple); } 134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StateTuple &Tuple(StateId s) const { return FindEntry(s); } 135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// An implementation using a vector and a compact hash table. The 139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// selecting functor S returns true for tuples to be hashed in the 140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// vector. The fingerprinting functor FP returns a unique fingerprint 141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// for each tuple to be hashed in the vector (these need to be 142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// suitable for indexing in a vector). The hash functor H is used when 143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// hashing tuple into the compact hash table. 144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class T, class S, class FP, class H> 145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass VectorHashStateTable 146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : public VectorHashBiTable<typename T::StateId, T, S, FP, H> { 147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef T StateTuple; 149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename StateTuple::StateId StateId; 150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using VectorHashBiTable<StateId, T, S, FP, H>::FindId; 151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using VectorHashBiTable<StateId, T, S, FP, H>::FindEntry; 152f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using VectorHashBiTable<StateId, T, S, FP, H>::Size; 153f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using VectorHashBiTable<StateId, T, S, FP, H>::Selector; 154f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using VectorHashBiTable<StateId, T, S, FP, H>::Fingerprint; 155f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using VectorHashBiTable<StateId, T, S, FP, H>::Hash; 156f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 157f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorHashStateTable(S *s, FP *fp, H *h, 158f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t vector_size = 0, 159f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t tuple_size = 0) 160f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : VectorHashBiTable<StateId, T, S, FP, H>( 161f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson s, fp, h, vector_size, tuple_size) {} 162f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 163f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId FindState(const StateTuple &tuple) { return FindId(tuple); } 164f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StateTuple &Tuple(StateId s) const { return FindEntry(s); } 165f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 166f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 167f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 168f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// An implementation using a hash map for the tuple to state ID 169f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// mapping. This version permits erasing of states. The state tuple T 170f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// must have == defined and its default constructor must produce a 171f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// tuple that will never be seen. F is the hash function. 172f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class T, class F> 173f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass ErasableStateTable : public ErasableBiTable<typename T::StateId, T, F> { 174f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 175f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef T StateTuple; 176f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename StateTuple::StateId StateId; 177f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using ErasableBiTable<StateId, T, F>::FindId; 178f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using ErasableBiTable<StateId, T, F>::FindEntry; 179f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using ErasableBiTable<StateId, T, F>::Size; 180f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using ErasableBiTable<StateId, T, F>::Erase; 181f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 182f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ErasableStateTable() : ErasableBiTable<StateId, T, F>() {} 183f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId FindState(const StateTuple &tuple) { return FindId(tuple); } 184f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const StateTuple &Tuple(StateId s) const { return FindEntry(s); } 185f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 186f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 187f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 188f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// COMPOSITION STATE TUPLES AND TABLES 189f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 190f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// The composition state table has the form: 191f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 192f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// template <class A, class F> 193f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// class ComposeStateTable { 194f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// public: 195f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// typedef A Arc; 196f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// typedef F FilterState; 197f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// typedef typename A::StateId StateId; 198f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// typedef ComposeStateTuple<StateId> StateTuple; 199f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 200f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // Required constructors. Copy constructor does not copy state. 201f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// ComposeStateTable(const Fst<Arc> &fst1, const Fst<Arc> &fst2); 202f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// ComposeStateTable(const ComposeStateTable<A, F> &table); 203f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // Lookup state ID by tuple. If it doesn't exist, then add it. 204f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// StateId FindState(const StateTuple &); 205f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // Lookup state tuple by state ID. 206f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// const StateTuple<StateId> &Tuple(StateId) const; 207f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // # of stored tuples. 208f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// StateId Size() const; 209f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // Return true if error encountered 210f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// bool Error() const; 211f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// }; 212f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 213f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Represents the composition state. 214f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename S, typename F> 215f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonstruct ComposeStateTuple { 216f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef S StateId; 217f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef F FilterState; 218f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 219f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeStateTuple() 220f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : state_id1(kNoStateId), state_id2(kNoStateId), 221f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson filter_state(FilterState::NoState()) {} 222f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 223f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeStateTuple(StateId s1, StateId s2, const FilterState &f) 224f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : state_id1(s1), state_id2(s2), filter_state(f) {} 225f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 226f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId state_id1; // State Id on fst1 227f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId state_id2; // State Id on fst2 228f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FilterState filter_state; // State of composition filter 229f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 230f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 231f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Equality of composition state tuples. 232f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename S, typename F> 233f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline bool operator==(const ComposeStateTuple<S, F>& x, 234f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const ComposeStateTuple<S, F>& y) { 235f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (&x == &y) 236f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return true; 237f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return x.state_id1 == y.state_id1 && 238f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson x.state_id2 == y.state_id2 && 239f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson x.filter_state == y.filter_state; 240f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 241f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 242f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 243f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Hashing of composition state tuples. 244f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename S, typename F> 245f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass ComposeHash { 246f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 247f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t operator()(const ComposeStateTuple<S, F>& t) const { 248f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return t.state_id1 + t.state_id2 * kPrime0 + 249f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson t.filter_state.Hash() * kPrime1; 250f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 251f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 252f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const size_t kPrime0; 253f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const size_t kPrime1; 254f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 255f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 256f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename S, typename F> 257f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonconst size_t ComposeHash<S, F>::kPrime0 = 7853; 258f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 259f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename S, typename F> 260f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonconst size_t ComposeHash<S, F>::kPrime1 = 7867; 261f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 262f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 263f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// A HashStateTable over composition tuples. 264f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename A, 265f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename F, 266f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename H = 267f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CompactHashStateTable<ComposeStateTuple<typename A::StateId, F>, 268f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeHash<typename A::StateId, F> > > 269f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass GenericComposeStateTable : public H { 270f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 271f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef A Arc; 272f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::StateId StateId; 273f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef F FilterState; 274f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef ComposeStateTuple<StateId, F> StateTuple; 275f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 276f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson GenericComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2) {} 277f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 2785b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin // Reserves space for 'table_size' elements. 2795b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin GenericComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2, 2805b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin size_t table_size) : H(table_size) {} 281f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 282f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Error() const { return false; } 283f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 284f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 285f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void operator=(const GenericComposeStateTable<A, F> &table); // disallow 286f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 287f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 288f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 289f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Fingerprint for general composition tuples. 290f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename S, typename F> 291f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass ComposeFingerprint { 292f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 293f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef S StateId; 294f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef F FilterState; 295f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef ComposeStateTuple<S, F> StateTuple; 296f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 297f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Required but suboptimal constructor. 298f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFingerprint() : mult1_(8192), mult2_(8192) { 299f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson LOG(WARNING) << "TupleFingerprint: # of FST states should be provided."; 300f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 301f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 302f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Constructor is provided the sizes of the input FSTs 303f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFingerprint(StateId nstates1, StateId nstates2) 304f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : mult1_(nstates1), mult2_(nstates1 * nstates2) { } 305f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 306f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t operator()(const StateTuple &tuple) { 307f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return tuple.state_id1 + tuple.state_id2 * mult1_ + 308f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson tuple.filter_state.Hash() * mult2_; 309f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 310f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 311f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 312f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ssize_t mult1_; 313f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ssize_t mult2_; 314f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 315f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 316f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 317f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Useful when the first composition state determines the tuple. 318f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename S, typename F> 319f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass ComposeState1Fingerprint { 320f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 321f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef S StateId; 322f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef F FilterState; 323f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef ComposeStateTuple<S, F> StateTuple; 324f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 325f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t operator()(const StateTuple &tuple) { return tuple.state_id1; } 326f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 327f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 328f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 329f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Useful when the second composition state determines the tuple. 330f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename S, typename F> 331f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass ComposeState2Fingerprint { 332f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 333f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef S StateId; 334f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef F FilterState; 335f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef ComposeStateTuple<S, F> StateTuple; 336f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 337f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t operator()(const StateTuple &tuple) { return tuple.state_id2; } 338f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 339f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 340f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 341f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// A VectorStateTable over composition tuples. This can be used when 342f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// the product of number of states in FST1 and FST2 (and the 343f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// composition filter state hash) is manageable. If the FSTs are not 344f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// expanded Fsts, they will first have their states counted. 345f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename A, typename F> 346f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass ProductComposeStateTable : public 347f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonVectorStateTable<ComposeStateTuple<typename A::StateId, F>, 348f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFingerprint<typename A::StateId, F> > { 349f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 350f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef A Arc; 351f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::StateId StateId; 352f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef F FilterState; 353f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef ComposeStateTuple<StateId, F> StateTuple; 3545b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin typedef VectorStateTable<StateTuple, 3555b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin ComposeFingerprint<StateId, F> > StateTable; 356f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 3575b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin // Reserves space for 'table_size' elements. 3585b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin ProductComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2, 3595b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin size_t table_size = 0) 3605b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin : StateTable(new ComposeFingerprint<StateId, F>(CountStates(fst1), 3615b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin CountStates(fst2)), 3625b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin table_size) {} 363f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 364f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ProductComposeStateTable(const ProductComposeStateTable<A, F> &table) 3655b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin : StateTable(new ComposeFingerprint<StateId, F>(table.Fingerprint())) {} 366f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 367f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Error() const { return false; } 368f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 369f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 370f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void operator=(const ProductComposeStateTable<A, F> &table); // disallow 371f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 372f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 373f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// A VectorStateTable over composition tuples. This can be used when 374f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// FST1 is a string (satisfies kStringProperties) and FST2 is 375f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// epsilon-free and deterministic. It should be used with a 376f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// composition filter that creates at most one filter state per tuple 377f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// under these conditions (e.g. SequenceComposeFilter or 378f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// MatchComposeFilter). 379f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename A, typename F> 380f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass StringDetComposeStateTable : public 381f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonVectorStateTable<ComposeStateTuple<typename A::StateId, F>, 382f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeState1Fingerprint<typename A::StateId, F> > { 383f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 384f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef A Arc; 385f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::StateId StateId; 386f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef F FilterState; 387f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef ComposeStateTuple<StateId, F> StateTuple; 3885b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin typedef VectorStateTable<StateTuple, 3895b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin ComposeState1Fingerprint<StateId, F> > StateTable; 390f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 391f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringDetComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2) 392f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : error_(false) { 393f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props1 = kString; 394f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props2 = kIDeterministic | kNoIEpsilons; 395f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (fst1.Properties(props1, true) != props1 || 396f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst2.Properties(props2, true) != props2) { 397f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "StringDetComposeStateTable: fst1 not a string or" 398f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << " fst2 not input deterministic and epsilon-free"; 399f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson error_ = true; 400f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 401f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 402f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 403f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringDetComposeStateTable(const StringDetComposeStateTable<A, F> &table) 4045b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin : StateTable(table), error_(table.error_) {} 405f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 406f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Error() const { return error_; } 407f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 408f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 409f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool error_; 410f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 411f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void operator=(const StringDetComposeStateTable<A, F> &table); // disallow 412f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 413f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 414f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 415f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// A VectorStateTable over composition tuples. This can be used when 416f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// FST2 is a string (satisfies kStringProperties) and FST1 is 417f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// epsilon-free and deterministic. It should be used with a 418f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// composition filter that creates at most one filter state per tuple 419f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// under these conditions (e.g. SequenceComposeFilter or 420f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// MatchComposeFilter). 421f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename A, typename F> 422f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass DetStringComposeStateTable : public 423f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonVectorStateTable<ComposeStateTuple<typename A::StateId, F>, 4245b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin ComposeState2Fingerprint<typename A::StateId, F> > { 425f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 426f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef A Arc; 427f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::StateId StateId; 428f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef F FilterState; 429f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef ComposeStateTuple<StateId, F> StateTuple; 4305b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin typedef VectorStateTable<StateTuple, 4315b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin ComposeState2Fingerprint<StateId, F> > StateTable; 432f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 433f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DetStringComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2) 434f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson :error_(false) { 435f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props1 = kODeterministic | kNoOEpsilons; 436f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props2 = kString; 437f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (fst1.Properties(props1, true) != props1 || 438f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst2.Properties(props2, true) != props2) { 439f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "StringDetComposeStateTable: fst2 not a string or" 440f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << " fst1 not output deterministic and epsilon-free"; 441f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson error_ = true; 442f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 443f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 444f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 445f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DetStringComposeStateTable(const DetStringComposeStateTable<A, F> &table) 4465b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin : StateTable(table), error_(table.error_) {} 447f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 448f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Error() const { return error_; } 449f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 450f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 451f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool error_; 452f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 453f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void operator=(const DetStringComposeStateTable<A, F> &table); // disallow 454f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 455f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 456f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 457f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// An ErasableStateTable over composition tuples. The Erase(StateId) method 458f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// can be called if the user either is sure that composition will never return 459f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// to that tuple or doesn't care that if it does, it is assigned a new 460f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// state ID. 461f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename A, typename F> 462f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass ErasableComposeStateTable : public 463f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonErasableStateTable<ComposeStateTuple<typename A::StateId, F>, 464f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeHash<typename A::StateId, F> > { 465f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 466f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef A Arc; 467f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::StateId StateId; 468f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef F FilterState; 469f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef ComposeStateTuple<StateId, F> StateTuple; 470f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 471f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ErasableComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2) {} 472f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 473f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Error() const { return false; } 474f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 475f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 476f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void operator=(const ErasableComposeStateTable<A, F> &table); // disallow 477f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 478f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 479f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace fst 480f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 481f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // FST_LIB_STATE_TABLE_H__ 482