15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// state-table.h 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Licensed under the Apache License, Version 2.0 (the "License"); 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// you may not use this file except in compliance with the License. 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// You may obtain a copy of the License at 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// http://www.apache.org/licenses/LICENSE-2.0 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Unless required by applicable law or agreed to in writing, software 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// distributed under the License is distributed on an "AS IS" BASIS, 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// See the License for the specific language governing permissions and 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// limitations under the License. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright 2005-2010 Google, Inc. 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Author: riley@google.com (Michael Riley) 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// \file 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Classes for representing the mapping between state tuples and state Ids. 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef FST_LIB_STATE_TABLE_H__ 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define FST_LIB_STATE_TABLE_H__ 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <deque> 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::deque; 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <vector> 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::vector; 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <fst/bi-table.h> 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <fst/expanded-fst.h> 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace fst { 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// STATE TABLES - these determine the bijective mapping between state 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// tuples (e.g. in composition triples of two FST states and a 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// composition filter state) and their corresponding state IDs. 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// They are classes, templated on state tuples, of the form: 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// template <class T> 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// class StateTable { 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// public: 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// typedef typename T StateTuple; 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// // Required constructors. 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// StateTable(); 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// // Lookup state ID by tuple. If it doesn't exist, then add it. 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// StateId FindState(const StateTuple &); 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// // Lookup state tuple by state ID. 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// const StateTuple<StateId> &Tuple(StateId) const; 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// // # of stored tuples. 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// StateId Size() const; 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// }; 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A state tuple has the form: 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// template <class S> 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// struct StateTuple { 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// typedef typename S StateId; 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// // Required constructors. 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// StateTuple(); 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// StateTuple(const StateTuple &); 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// }; 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// An implementation using a hash map for the tuple to state ID mapping. 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The state tuple T must have == defined. H is the hash function. 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class T, class H> 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class HashStateTable : public HashBiTable<typename T::StateId, T, H> { 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef T StateTuple; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef typename StateTuple::StateId StateId; 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using HashBiTable<StateId, T, H>::FindId; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using HashBiTable<StateId, T, H>::FindEntry; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using HashBiTable<StateId, T, H>::Size; 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HashStateTable() : HashBiTable<StateId, T, H>() {} 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Reserves space for table_size elements. 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit HashStateTable(size_t table_size) 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : HashBiTable<StateId, T, H>(table_size) {} 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StateId FindState(const StateTuple &tuple) { return FindId(tuple); } 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StateTuple &Tuple(StateId s) const { return FindEntry(s); } 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// An implementation using a hash map for the tuple to state ID mapping. 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The state tuple T must have == defined. H is the hash function. 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class T, class H> 93c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)class CompactHashStateTable 94c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) : public CompactHashBiTable<typename T::StateId, T, H> { 95c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) public: 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef T StateTuple; 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef typename StateTuple::StateId StateId; 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using CompactHashBiTable<StateId, T, H>::FindId; 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using CompactHashBiTable<StateId, T, H>::FindEntry; 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using CompactHashBiTable<StateId, T, H>::Size; 101c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CompactHashStateTable() : CompactHashBiTable<StateId, T, H>() {} 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 104424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // Reserves space for 'table_size' elements. 105424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) explicit CompactHashStateTable(size_t table_size) 106424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) : CompactHashBiTable<StateId, T, H>(table_size) {} 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StateId FindState(const StateTuple &tuple) { return FindId(tuple); } 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StateTuple &Tuple(StateId s) const { return FindEntry(s); } 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// An implementation using a vector for the tuple to state mapping. 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// It is passed a function object FP that should fingerprint tuples 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// uniquely to an integer that can used as a vector index. Normally, 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// VectorStateTable constructs the FP object. The user can instead 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// pass in this object; in that case, VectorStateTable takes its 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ownership. 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class T, class FP> 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class VectorStateTable 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : public VectorBiTable<typename T::StateId, T, FP> { 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef T StateTuple; 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef typename StateTuple::StateId StateId; 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using VectorBiTable<StateId, T, FP>::FindId; 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using VectorBiTable<StateId, T, FP>::FindEntry; 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using VectorBiTable<StateId, T, FP>::Size; 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using VectorBiTable<StateId, T, FP>::Fingerprint; 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Reserves space for 'table_size' elements. 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit VectorStateTable(FP *fp = 0, size_t table_size = 0) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : VectorBiTable<StateId, T, FP>(fp, table_size) {} 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StateId FindState(const StateTuple &tuple) { return FindId(tuple); } 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StateTuple &Tuple(StateId s) const { return FindEntry(s); } 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// An implementation using a vector and a compact hash table. The 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// selecting functor S returns true for tuples to be hashed in the 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// vector. The fingerprinting functor FP returns a unique fingerprint 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// for each tuple to be hashed in the vector (these need to be 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// suitable for indexing in a vector). The hash functor H is used when 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// hashing tuple into the compact hash table. 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class T, class S, class FP, class H> 1452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class VectorHashStateTable 1462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) : public VectorHashBiTable<typename T::StateId, T, S, FP, H> { 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef T StateTuple; 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef typename StateTuple::StateId StateId; 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using VectorHashBiTable<StateId, T, S, FP, H>::FindId; 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using VectorHashBiTable<StateId, T, S, FP, H>::FindEntry; 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using VectorHashBiTable<StateId, T, S, FP, H>::Size; 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using VectorHashBiTable<StateId, T, S, FP, H>::Selector; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using VectorHashBiTable<StateId, T, S, FP, H>::Fingerprint; 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using VectorHashBiTable<StateId, T, S, FP, H>::Hash; 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VectorHashStateTable(S *s, FP *fp, H *h, 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t vector_size = 0, 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t tuple_size = 0) 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : VectorHashBiTable<StateId, T, S, FP, H>( 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s, fp, h, vector_size, tuple_size) {} 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StateId FindState(const StateTuple &tuple) { return FindId(tuple); } 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StateTuple &Tuple(StateId s) const { return FindEntry(s); } 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// An implementation using a hash map for the tuple to state ID 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// mapping. This version permits erasing of states. The state tuple T 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// must have == defined and its default constructor must produce a 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// tuple that will never be seen. F is the hash function. 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class T, class F> 1732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class ErasableStateTable : public ErasableBiTable<typename T::StateId, T, F> { 1742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public: 1752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef T StateTuple; 1762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef typename StateTuple::StateId StateId; 1772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) using ErasableBiTable<StateId, T, F>::FindId; 1782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) using ErasableBiTable<StateId, T, F>::FindEntry; 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using ErasableBiTable<StateId, T, F>::Size; 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) using ErasableBiTable<StateId, T, F>::Erase; 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ErasableStateTable() : ErasableBiTable<StateId, T, F>() {} 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StateId FindState(const StateTuple &tuple) { return FindId(tuple); } 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StateTuple &Tuple(StateId s) const { return FindEntry(s); } 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// COMPOSITION STATE TUPLES AND TABLES 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The composition state table has the form: 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// template <class A, class F> 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// class ComposeStateTable { 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// public: 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// typedef A Arc; 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// typedef F FilterState; 197// typedef typename A::StateId StateId; 198// typedef ComposeStateTuple<StateId> StateTuple; 199// 200// // Required constructors. Copy constructor does not copy state. 201// ComposeStateTable(const Fst<Arc> &fst1, const Fst<Arc> &fst2); 202// ComposeStateTable(const ComposeStateTable<A, F> &table); 203// // Lookup state ID by tuple. If it doesn't exist, then add it. 204// StateId FindState(const StateTuple &); 205// // Lookup state tuple by state ID. 206// const StateTuple<StateId> &Tuple(StateId) const; 207// // # of stored tuples. 208// StateId Size() const; 209// // Return true if error encountered 210// bool Error() const; 211// }; 212 213// Represents the composition state. 214template <typename S, typename F> 215struct ComposeStateTuple { 216 typedef S StateId; 217 typedef F FilterState; 218 219 ComposeStateTuple() 220 : state_id1(kNoStateId), state_id2(kNoStateId), 221 filter_state(FilterState::NoState()) {} 222 223 ComposeStateTuple(StateId s1, StateId s2, const FilterState &f) 224 : state_id1(s1), state_id2(s2), filter_state(f) {} 225 226 StateId state_id1; // State Id on fst1 227 StateId state_id2; // State Id on fst2 228 FilterState filter_state; // State of composition filter 229}; 230 231// Equality of composition state tuples. 232template <typename S, typename F> 233inline bool operator==(const ComposeStateTuple<S, F>& x, 234 const ComposeStateTuple<S, F>& y) { 235 if (&x == &y) 236 return true; 237 return x.state_id1 == y.state_id1 && 238 x.state_id2 == y.state_id2 && 239 x.filter_state == y.filter_state; 240} 241 242 243// Hashing of composition state tuples. 244template <typename S, typename F> 245class ComposeHash { 246 public: 247 size_t operator()(const ComposeStateTuple<S, F>& t) const { 248 return t.state_id1 + t.state_id2 * kPrime0 + 249 t.filter_state.Hash() * kPrime1; 250 } 251 private: 252 static const size_t kPrime0; 253 static const size_t kPrime1; 254}; 255 256template <typename S, typename F> 257const size_t ComposeHash<S, F>::kPrime0 = 7853; 258 259template <typename S, typename F> 260const size_t ComposeHash<S, F>::kPrime1 = 7867; 261 262 263// A HashStateTable over composition tuples. 264template <typename A, 265 typename F, 266 typename H = 267 CompactHashStateTable<ComposeStateTuple<typename A::StateId, F>, 268 ComposeHash<typename A::StateId, F> > > 269class GenericComposeStateTable : public H { 270 public: 271 typedef A Arc; 272 typedef typename A::StateId StateId; 273 typedef F FilterState; 274 typedef ComposeStateTuple<StateId, F> StateTuple; 275 276 GenericComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2) {} 277 278 // Reserves space for 'table_size' elements. 279 GenericComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2, 280 size_t table_size) : H(table_size) {} 281 282 bool Error() const { return false; } 283 284 private: 285 void operator=(const GenericComposeStateTable<A, F> &table); // disallow 286}; 287 288 289// Fingerprint for general composition tuples. 290template <typename S, typename F> 291class ComposeFingerprint { 292 public: 293 typedef S StateId; 294 typedef F FilterState; 295 typedef ComposeStateTuple<S, F> StateTuple; 296 297 // Required but suboptimal constructor. 298 ComposeFingerprint() : mult1_(8192), mult2_(8192) { 299 LOG(WARNING) << "TupleFingerprint: # of FST states should be provided."; 300 } 301 302 // Constructor is provided the sizes of the input FSTs 303 ComposeFingerprint(StateId nstates1, StateId nstates2) 304 : mult1_(nstates1), mult2_(nstates1 * nstates2) { } 305 306 size_t operator()(const StateTuple &tuple) { 307 return tuple.state_id1 + tuple.state_id2 * mult1_ + 308 tuple.filter_state.Hash() * mult2_; 309 } 310 311 private: 312 ssize_t mult1_; 313 ssize_t mult2_; 314}; 315 316 317// Useful when the first composition state determines the tuple. 318template <typename S, typename F> 319class ComposeState1Fingerprint { 320 public: 321 typedef S StateId; 322 typedef F FilterState; 323 typedef ComposeStateTuple<S, F> StateTuple; 324 325 size_t operator()(const StateTuple &tuple) { return tuple.state_id1; } 326}; 327 328 329// Useful when the second composition state determines the tuple. 330template <typename S, typename F> 331class ComposeState2Fingerprint { 332 public: 333 typedef S StateId; 334 typedef F FilterState; 335 typedef ComposeStateTuple<S, F> StateTuple; 336 337 size_t operator()(const StateTuple &tuple) { return tuple.state_id2; } 338}; 339 340 341// A VectorStateTable over composition tuples. This can be used when 342// the product of number of states in FST1 and FST2 (and the 343// composition filter state hash) is manageable. If the FSTs are not 344// expanded Fsts, they will first have their states counted. 345template <typename A, typename F> 346class ProductComposeStateTable : public 347VectorStateTable<ComposeStateTuple<typename A::StateId, F>, 348 ComposeFingerprint<typename A::StateId, F> > { 349 public: 350 typedef A Arc; 351 typedef typename A::StateId StateId; 352 typedef F FilterState; 353 typedef ComposeStateTuple<StateId, F> StateTuple; 354 typedef VectorStateTable<StateTuple, 355 ComposeFingerprint<StateId, F> > StateTable; 356 357 // Reserves space for 'table_size' elements. 358 ProductComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2, 359 size_t table_size = 0) 360 : StateTable(new ComposeFingerprint<StateId, F>(CountStates(fst1), 361 CountStates(fst2)), 362 table_size) {} 363 364 ProductComposeStateTable(const ProductComposeStateTable<A, F> &table) 365 : StateTable(new ComposeFingerprint<StateId, F>(table.Fingerprint())) {} 366 367 bool Error() const { return false; } 368 369 private: 370 void operator=(const ProductComposeStateTable<A, F> &table); // disallow 371}; 372 373// A VectorStateTable over composition tuples. This can be used when 374// FST1 is a string (satisfies kStringProperties) and FST2 is 375// epsilon-free and deterministic. It should be used with a 376// composition filter that creates at most one filter state per tuple 377// under these conditions (e.g. SequenceComposeFilter or 378// MatchComposeFilter). 379template <typename A, typename F> 380class StringDetComposeStateTable : public 381VectorStateTable<ComposeStateTuple<typename A::StateId, F>, 382 ComposeState1Fingerprint<typename A::StateId, F> > { 383 public: 384 typedef A Arc; 385 typedef typename A::StateId StateId; 386 typedef F FilterState; 387 typedef ComposeStateTuple<StateId, F> StateTuple; 388 typedef VectorStateTable<StateTuple, 389 ComposeState1Fingerprint<StateId, F> > StateTable; 390 391 StringDetComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2) 392 : error_(false) { 393 uint64 props1 = kString; 394 uint64 props2 = kIDeterministic | kNoIEpsilons; 395 if (fst1.Properties(props1, true) != props1 || 396 fst2.Properties(props2, true) != props2) { 397 FSTERROR() << "StringDetComposeStateTable: fst1 not a string or" 398 << " fst2 not input deterministic and epsilon-free"; 399 error_ = true; 400 } 401 } 402 403 StringDetComposeStateTable(const StringDetComposeStateTable<A, F> &table) 404 : StateTable(table), error_(table.error_) {} 405 406 bool Error() const { return error_; } 407 408 private: 409 bool error_; 410 411 void operator=(const StringDetComposeStateTable<A, F> &table); // disallow 412}; 413 414 415// A VectorStateTable over composition tuples. This can be used when 416// FST2 is a string (satisfies kStringProperties) and FST1 is 417// epsilon-free and deterministic. It should be used with a 418// composition filter that creates at most one filter state per tuple 419// under these conditions (e.g. SequenceComposeFilter or 420// MatchComposeFilter). 421template <typename A, typename F> 422class DetStringComposeStateTable : public 423VectorStateTable<ComposeStateTuple<typename A::StateId, F>, 424 ComposeState2Fingerprint<typename A::StateId, F> > { 425 public: 426 typedef A Arc; 427 typedef typename A::StateId StateId; 428 typedef F FilterState; 429 typedef ComposeStateTuple<StateId, F> StateTuple; 430 typedef VectorStateTable<StateTuple, 431 ComposeState2Fingerprint<StateId, F> > StateTable; 432 433 DetStringComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2) 434 :error_(false) { 435 uint64 props1 = kODeterministic | kNoOEpsilons; 436 uint64 props2 = kString; 437 if (fst1.Properties(props1, true) != props1 || 438 fst2.Properties(props2, true) != props2) { 439 FSTERROR() << "StringDetComposeStateTable: fst2 not a string or" 440 << " fst1 not output deterministic and epsilon-free"; 441 error_ = true; 442 } 443 } 444 445 DetStringComposeStateTable(const DetStringComposeStateTable<A, F> &table) 446 : StateTable(table), error_(table.error_) {} 447 448 bool Error() const { return error_; } 449 450 private: 451 bool error_; 452 453 void operator=(const DetStringComposeStateTable<A, F> &table); // disallow 454}; 455 456 457// An ErasableStateTable over composition tuples. The Erase(StateId) method 458// can be called if the user either is sure that composition will never return 459// to that tuple or doesn't care that if it does, it is assigned a new 460// state ID. 461template <typename A, typename F> 462class ErasableComposeStateTable : public 463ErasableStateTable<ComposeStateTuple<typename A::StateId, F>, 464 ComposeHash<typename A::StateId, F> > { 465 public: 466 typedef A Arc; 467 typedef typename A::StateId StateId; 468 typedef F FilterState; 469 typedef ComposeStateTuple<StateId, F> StateTuple; 470 471 ErasableComposeStateTable(const Fst<A> &fst1, const Fst<A> &fst2) {} 472 473 bool Error() const { return false; } 474 475 private: 476 void operator=(const ErasableComposeStateTable<A, F> &table); // disallow 477}; 478 479} // namespace fst 480 481#endif // FST_LIB_STATE_TABLE_H__ 482