compose.h revision 4a68b3365c8c50aa93505e99ead2565ab73dcdb0
14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// compose.h 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License"); 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License. 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// http://www.apache.org/licenses/LICENSE-2.0 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS, 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License. 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Class to compute the composition of two FSTs 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_COMPOSE_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_COMPOSE_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <algorithm> 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <ext/hash_map> 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectusing __gnu_cxx::hash_map; 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/cache.h" 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/test-properties.h" 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Enumeration of uint64 bits used to represent the user-defined 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// properties of FST composition (in the template parameter to 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// ComposeFstOptions<T>). The bits stand for extensions of generic FST 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// composition. ComposeFstOptions<> (all the bits unset) is the "plain" 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// compose without any extra extensions. 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectenum ComposeTypes { 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // RHO: flags dealing with a special "rest" symbol in the FSTs. 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // NB: at most one of the bits COMPOSE_FST1_RHO, COMPOSE_FST2_RHO 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // may be set. 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_FST1_RHO = 1ULL<<0, // "Rest" symbol on the output side of fst1. 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_FST2_RHO = 1ULL<<1, // "Rest" symbol on the input side of fst2. 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_FST1_PHI = 1ULL<<2, // "Failure" symbol on the output 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // side of fst1. 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_FST2_PHI = 1ULL<<3, // "Failure" symbol on the input side 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // of fst2. 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_FST1_SIGMA = 1ULL<<4, // "Any" symbol on the output side of 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // fst1. 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_FST2_SIGMA = 1ULL<<5, // "Any" symbol on the input side of 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // fst2. 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Optimization related bits. 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_GENERIC = 1ULL<<32, // Disables optimizations, applies 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // the generic version of the 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // composition algorithm. This flag 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // is used for internal testing 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // only. 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // ----------------------------------------------------------------- 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Auxiliary enum values denoting specific combinations of 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // bits. Internal use only. 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_RHO = COMPOSE_FST1_RHO | COMPOSE_FST2_RHO, 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_PHI = COMPOSE_FST1_PHI | COMPOSE_FST2_PHI, 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_SIGMA = COMPOSE_FST1_SIGMA | COMPOSE_FST2_SIGMA, 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_SPECIAL_SYMBOLS = COMPOSE_RHO | COMPOSE_PHI | COMPOSE_SIGMA, 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // ----------------------------------------------------------------- 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // The following bits, denoting specific optimizations, are 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // typically set *internally* by the composition algorithm. 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_FST1_STRING = 1ULL<<33, // fst1 is a string 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_FST2_STRING = 1ULL<<34, // fst2 is a string 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_FST1_DET = 1ULL<<35, // fst1 is deterministic 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_FST2_DET = 1ULL<<36, // fst2 is deterministic 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project COMPOSE_INTERNAL_MASK = 0xffffffff00000000ULL 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <uint64 T = 0ULL> 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct ComposeFstOptions : public CacheOptions { 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit ComposeFstOptions(const CacheOptions &opts) : CacheOptions(opts) {} 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeFstOptions() { } 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Abstract base for the implementation of delayed ComposeFst. The 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// concrete specializations are templated on the (uint64-valued) 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// properties of the FSTs being composed. 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ComposeFstImplBase : public CacheImpl<A> { 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetType; 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetProperties; 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::Properties; 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetInputSymbols; 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetOutputSymbols; 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using CacheBaseImpl< CacheState<A> >::HasStart; 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using CacheBaseImpl< CacheState<A> >::HasFinal; 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using CacheBaseImpl< CacheState<A> >::HasArcs; 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Label Label; 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef CacheState<A> State; 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeFstImplBase(const Fst<A> &fst1, 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A> &fst2, 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const CacheOptions &opts) 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project :CacheImpl<A>(opts), fst1_(fst1.Copy()), fst2_(fst2.Copy()) { 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetType("compose"); 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props1 = fst1.Properties(kFstProperties, false); 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props2 = fst2.Properties(kFstProperties, false); 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetProperties(ComposeProperties(props1, props2), kCopyProperties); 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!CompatSymbols(fst2.InputSymbols(), fst1.OutputSymbols())) 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "ComposeFst: output symbol table of 1st argument " 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << "does not match input symbol table of 2nd argument"; 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetInputSymbols(fst1.InputSymbols()); 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetOutputSymbols(fst2.OutputSymbols()); 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ~ComposeFstImplBase() { 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete fst1_; 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete fst2_; 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId Start() { 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasStart()) { 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId start = ComputeStart(); 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (start != kNoStateId) { 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetStart(start); 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::Start(); 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight Final(StateId s) { 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasFinal(s)) { 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight final = ComputeFinal(s); 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetFinal(s, final); 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::Final(s); 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Expand(StateId s) = 0; 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumArcs(StateId s) { 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::NumArcs(s); 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumInputEpsilons(StateId s) { 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::NumInputEpsilons(s); 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumOutputEpsilons(StateId s) { 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::NumOutputEpsilons(s); 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void InitArcIterator(StateId s, ArcIteratorData<A> *data) { 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CacheImpl<A>::InitArcIterator(s, data); 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Access to flags encoding compose options/optimizations etc. (for 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // debugging). 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual uint64 ComposeFlags() const = 0; 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project protected: 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId ComputeStart() = 0; 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual Weight ComputeFinal(StateId s) = 0; 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A> *fst1_; // first input Fst 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A> *fst2_; // second input Fst 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The following class encapsulates implementation-dependent details 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// of state tuple lookup, i.e. a bijective mapping from triples of two 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// FST states and an epsilon filter state to the corresponding state 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// IDs of the fst resulting from composition. The mapping must 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// implement the [] operator in the style of STL associative 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// containers (map, hash_map), i.e. table[x] must return a reference 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// to the value associated with x. If x is an unassigned tuple, the 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// operator must automatically associate x with value 0. 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// NB: "table[x] == 0" for unassigned tuples x is required by the 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// following off-by-one device used in the implementation of 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// ComposeFstImpl. The value stored in the table is equal to tuple ID 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// plus one, i.e. it is always a strictly positive number. Therefore, 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// table[x] is equal to 0 if and only if x is an unassigned tuple (in 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// which the algorithm assigns a new ID to x, and sets table[x] - 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// stored in a reference - to "new ID + 1"). This form of lookup is 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// more efficient than calling "find(x)" and "insert(make_pair(x, new 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// ID))" if x is an unassigned tuple. 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The generic implementation is a wrapper around a hash_map. 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A, uint64 T> 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ComposeStateTable { 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project struct StateTuple { 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateTuple() {} 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateTuple(StateId s1, StateId s2, int f) 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : state_id1(s1), state_id2(s2), filt(f) {} 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId state_id1; // state Id on fst1 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId state_id2; // state Id on fst2 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int filt; // epsilon filter state 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeStateTable() { 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateTuple empty_tuple(kNoStateId, kNoStateId, 0); 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // NB: if 'tuple' is not in 'table_', the pair (tuple, StateId()) is 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // inserted into 'table_' (standard STL container semantics). Since 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // StateId is a built-in type, the explicit default constructor call 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // StateId() returns 0. 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId &operator[](const StateTuple &tuple) { 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return table_[tuple]; 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Comparison object for hashing StateTuple(s). 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project class StateTupleEqual { 2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool operator()(const StateTuple& x, const StateTuple& y) const { 2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return x.state_id1 == y.state_id1 && 2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project x.state_id2 == y.state_id2 && 2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project x.filt == y.filt; 2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const int kPrime0 = 7853; 2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const int kPrime1 = 7867; 2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Hash function for StateTuple to Fst states. 2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project class StateTupleKey { 2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t operator()(const StateTuple& x) const { 2484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return static_cast<size_t>(x.state_id1 + 2494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project x.state_id2 * kPrime0 + 2504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project x.filt * kPrime1); 2514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 2534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Lookup table mapping state tuples to state IDs. 2554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef hash_map<StateTuple, 2564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId, 2574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateTupleKey, 2584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateTupleEqual> StateTable; 2594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Actual table data. 2604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateTable table_; 2614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(ComposeStateTable); 2634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 2644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// State tuple lookup table for the composition of a string FST with a 2674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// deterministic FST. The class maps state tuples to their unique IDs 2684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// (i.e. states of the ComposeFst). Main optimization: due to the 2694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1-to-1 correspondence between the states of the input string FST 2704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// and those of the resulting (string) FST, a state tuple (s1, s2) is 2714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// simply mapped to StateId s1. Hence, we use an STL vector as a 2724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// lookup table. Template argument Fst1IsString specifies which FST is 2734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// a string (this determines whether or not we index the lookup table 2744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// by the first or by the second state). 2754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A, bool Fst1IsString> 2764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StringDetComposeStateTable { 2774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 2794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project struct StateTuple { 2814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 2824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateTuple() {} 2834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateTuple(StateId s1, StateId s2, int /* f */) 2844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : state_id1(s1), state_id2(s2) {} 2854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId state_id1; // state Id on fst1 2864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId state_id2; // state Id on fst2 2874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const int filt = 0; // 'fake' epsilon filter - only needed 2884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // for API compatibility 2894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 2904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringDetComposeStateTable() {} 2924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Subscript operator. Behaves in a way similar to its map/hash_map 2944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // counterpart, i.e. returns a reference to the value associated 2954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // with 'tuple', inserting a 0 value if 'tuple' is unassigned. 2964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId &operator[](const StateTuple &tuple) { 2974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId index = Fst1IsString ? tuple.state_id1 : tuple.state_id2; 2984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (index >= (StateId)data_.size()) { 2994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // NB: all values in [old_size; index] are initialized to 0. 3004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data_.resize(index + 1); 3014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return data_[index]; 3034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 3064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> data_; 3074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(StringDetComposeStateTable); 3094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 3104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specializations of ComposeStateTable for the string/det case. 3134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Both inherit from StringDetComposeStateTable. 3144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 3154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ComposeStateTable<A, COMPOSE_FST1_STRING | COMPOSE_FST2_DET> 3164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public StringDetComposeStateTable<A, true> { }; 3174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 3194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ComposeStateTable<A, COMPOSE_FST2_STRING | COMPOSE_FST1_DET> 3204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public StringDetComposeStateTable<A, false> { }; 3214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Parameterized implementation of FST composition for a pair of FSTs 3244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// matching the property bit vector T. If possible, 3254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// instantiation-specific switches in the code are based on the values 3264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// of the bits in T, which are known at compile time, so unused code 3274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// should be optimized away by the compiler. 3284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A, uint64 T> 3294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ComposeFstImpl : public ComposeFstImplBase<A> { 3304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 3314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Label Label; 3324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 3334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetType; 3344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetProperties; 3354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enum FindType { FIND_INPUT = 1, // find input label on fst2 3374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FIND_OUTPUT = 2, // find output label on fst1 3384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FIND_BOTH = 3 }; // find choice state dependent 3394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef ComposeStateTable<A, T & COMPOSE_INTERNAL_MASK> StateTupleTable; 3414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename StateTupleTable::StateTuple StateTuple; 3424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 3444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeFstImpl(const Fst<A> &fst1, 3454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A> &fst2, 3464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const CacheOptions &opts) 3474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project :ComposeFstImplBase<A>(fst1, fst2, opts) { 3484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool osorted = fst1.Properties(kOLabelSorted, false); 3504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool isorted = fst2.Properties(kILabelSorted, false); 3514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project switch (T & COMPOSE_SPECIAL_SYMBOLS) { 3534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project case COMPOSE_FST1_RHO: 3544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project case COMPOSE_FST1_PHI: 3554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project case COMPOSE_FST1_SIGMA: 3564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!osorted || FLAGS_fst_verify_properties) 3574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project osorted = fst1.Properties(kOLabelSorted, true); 3584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!osorted) 3594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "ComposeFst: 1st argument not output label " 3604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << "sorted (special symbols present)"; 3614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 3624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project case COMPOSE_FST2_RHO: 3634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project case COMPOSE_FST2_PHI: 3644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project case COMPOSE_FST2_SIGMA: 3654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!isorted || FLAGS_fst_verify_properties) 3664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project isorted = fst2.Properties(kILabelSorted, true); 3674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!isorted) 3684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "ComposeFst: 2nd argument not input label " 3694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << "sorted (special symbols present)"; 3704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 3714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project case 0: 3724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!isorted && !osorted || FLAGS_fst_verify_properties) { 3734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project osorted = fst1.Properties(kOLabelSorted, true); 3744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!osorted) 3754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project isorted = fst2.Properties(kILabelSorted, true); 3764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 3784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project default: 3794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) 3804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << "ComposeFst: More than one special symbol used in composition"; 3814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (isorted && (T & COMPOSE_FST2_SIGMA)) { 3844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project find_type_ = FIND_INPUT; 3854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (osorted && (T & COMPOSE_FST1_SIGMA)) { 3864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project find_type_ = FIND_OUTPUT; 3874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (isorted && (T & COMPOSE_FST2_PHI)) { 3884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project find_type_ = FIND_INPUT; 3894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (osorted && (T & COMPOSE_FST1_PHI)) { 3904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project find_type_ = FIND_OUTPUT; 3914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (isorted && (T & COMPOSE_FST2_RHO)) { 3924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project find_type_ = FIND_INPUT; 3934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (osorted && (T & COMPOSE_FST1_RHO)) { 3944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project find_type_ = FIND_OUTPUT; 3954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (isorted && (T & COMPOSE_FST1_STRING)) { 3964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project find_type_ = FIND_INPUT; 3974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if(osorted && (T & COMPOSE_FST2_STRING)) { 3984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project find_type_ = FIND_OUTPUT; 3994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (isorted && osorted) { 4004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project find_type_ = FIND_BOTH; 4014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (isorted) { 4024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project find_type_ = FIND_INPUT; 4034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (osorted) { 4044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project find_type_ = FIND_OUTPUT; 4054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 4064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "ComposeFst: 1st argument not output label sorted " 4074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << "and 2nd argument is not input label sorted"; 4084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Finds/creates an Fst state given a StateTuple. Only creates a new 4124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // state if StateTuple is not found in the state hash. 4134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // 4144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // The method exploits the following device: all pairs stored in the 4154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // associative container state_tuple_table_ are of the form (tuple, 4164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // id(tuple) + 1), i.e. state_tuple_table_[tuple] > 0 if tuple has 4174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // been stored previously. For unassigned tuples, the call to 4184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // state_tuple_table_[tuple] creates a new pair (tuple, 0). As a 4194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // result, state_tuple_table_[tuple] == 0 iff tuple is new. 4204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId FindState(const StateTuple& tuple) { 4214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId &assoc_value = state_tuple_table_[tuple]; 4224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (assoc_value == 0) { // tuple wasn't present in lookup table: 4234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // assign it a new ID. 4244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_tuples_.push_back(tuple); 4254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project assoc_value = state_tuples_.size(); 4264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return assoc_value - 1; // NB: assoc_value = ID + 1 4284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Generates arc for composition state s from matched input Fst arcs. 4314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void AddArc(StateId s, const A &arca, const A &arcb, int f, 4324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool find_input) { 4334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project A arc; 4344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (find_input) { 4354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.ilabel = arcb.ilabel; 4364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.olabel = arca.olabel; 4374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.weight = Times(arcb.weight, arca.weight); 4384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateTuple tuple(arcb.nextstate, arca.nextstate, f); 4394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.nextstate = FindState(tuple); 4404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 4414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.ilabel = arca.ilabel; 4424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.olabel = arcb.olabel; 4434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.weight = Times(arca.weight, arcb.weight); 4444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateTuple tuple(arca.nextstate, arcb.nextstate, f); 4454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.nextstate = FindState(tuple); 4464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CacheImpl<A>::AddArc(s, arc); 4484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Arranges it so that the first arg to OrderedExpand is the Fst 4514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // that will be passed to FindLabel. 4524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Expand(StateId s) { 4534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateTuple &tuple = state_tuples_[s]; 4544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s1 = tuple.state_id1; 4554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s2 = tuple.state_id2; 4564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int f = tuple.filt; 4574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (find_type_ == FIND_INPUT) 4584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project OrderedExpand(s, ComposeFstImplBase<A>::fst2_, s2, 4594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeFstImplBase<A>::fst1_, s1, f, true); 4604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 4614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project OrderedExpand(s, ComposeFstImplBase<A>::fst1_, s1, 4624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeFstImplBase<A>::fst2_, s2, f, false); 4634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Access to flags encoding compose options/optimizations etc. (for 4664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // debugging). 4674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual uint64 ComposeFlags() const { return T; } 4684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 4704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // This does that actual matching of labels in the composition. The 4714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // arguments are ordered so FindLabel is called with state SA of 4724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // FSTA for each arc leaving state SB of FSTB. The FIND_INPUT arg 4734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // determines whether the input or output label of arcs at SB is 4744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // the one to match on. 4754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void OrderedExpand(StateId s, const Fst<A> *fsta, StateId sa, 4764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A> *fstb, StateId sb, int f, bool find_input) { 4774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t numarcsa = fsta->NumArcs(sa); 4794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t numepsa = find_input ? fsta->NumInputEpsilons(sa) : 4804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fsta->NumOutputEpsilons(sa); 4814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool finala = fsta->Final(sa) != Weight::Zero(); 4824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator< Fst<A> > aitera(*fsta, sa); 4834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // First handle special epsilons and sigmas on FSTA 4844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (; !aitera.Done(); aitera.Next()) { 4854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const A &arca = aitera.Value(); 4864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Label match_labela = find_input ? arca.ilabel : arca.olabel; 4874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (match_labela > 0) { 4884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 4894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((T & COMPOSE_SIGMA) != 0 && match_labela == kSigmaLabel) { 4914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Found a sigma? Match it against all (non-special) symbols 4924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // on side b. 4934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator< Fst<A> > aiterb(*fstb, sb); 4944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !aiterb.Done(); 4954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiterb.Next()) { 4964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const A &arcb = aiterb.Value(); 4974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Label labelb = find_input ? arcb.olabel : arcb.ilabel; 4984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (labelb <= 0) continue; 4994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AddArc(s, arca, arcb, 0, find_input); 5004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (f == 0 && match_labela == 0) { 5024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project A earcb(0, 0, Weight::One(), sb); 5034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AddArc(s, arca, earcb, 0, find_input); // move forward on epsilon 5044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Next handle non-epsilon matches, rho labels, and epsilons on FSTB 5074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator< Fst<A> > aiterb(*fstb, sb); 5084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !aiterb.Done(); 5094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiterb.Next()) { 5104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const A &arcb = aiterb.Value(); 5114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Label match_labelb = find_input ? arcb.olabel : arcb.ilabel; 5124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (match_labelb) { // Consider non-epsilon match 5134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (FindLabel(&aitera, numarcsa, match_labelb, find_input)) { 5144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (; !aitera.Done(); aitera.Next()) { 5154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const A &arca = aitera.Value(); 5164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Label match_labela = find_input ? arca.ilabel : arca.olabel; 5174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (match_labela != match_labelb) 5184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 5194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AddArc(s, arca, arcb, 0, find_input); // move forward on match 5204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if ((T & COMPOSE_SPECIAL_SYMBOLS) != 0) { 5224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // If there is no transition labelled 'match_labelb' in 5234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // fsta, try matching 'match_labelb' against special symbols 5244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // (Phi, Rho,...). 5254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (aitera.Reset(); !aitera.Done(); aitera.Next()) { 5264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project A arca = aitera.Value(); 5274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Label labela = find_input ? arca.ilabel : arca.olabel; 5284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (labela >= 0) { 5294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 5304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (((T & COMPOSE_PHI) != 0) && (labela == kPhiLabel)) { 5314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Case 1: if a failure transition exists, follow its 5324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // transitive closure until a) a transition labelled 5334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // 'match_labelb' is found, or b) the initial state of 5344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // fsta is reached. 5354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId sf = sa; // Start of current failure transition. 5374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (labela == kPhiLabel && sf != arca.nextstate) { 5384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sf = arca.nextstate; 5394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t numarcsf = fsta->NumArcs(sf); 5414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator< Fst<A> > aiterf(*fsta, sf); 5424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (FindLabel(&aiterf, numarcsf, match_labelb, find_input)) { 5434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Sub-case 1a: there exists a transition starting 5444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // in sf and consuming symbol 'match_labelb'. 5454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AddArc(s, aiterf.Value(), arcb, 0, find_input); 5464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 5474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 5484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // No transition labelled 'match_labelb' found: try 5494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // next failure transition (starting at 'sf'). 5504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (aiterf.Reset(); !aiterf.Done(); aiterf.Next()) { 5514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arca = aiterf.Value(); 5524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project labela = find_input ? arca.ilabel : arca.olabel; 5534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (labela >= kPhiLabel) break; 5544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (labela == kPhiLabel && sf == arca.nextstate) { 5584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Sub-case 1b: failure transitions lead to start 5594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // state without finding a matching 5604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // transition. Therefore, we generate a loop in start 5614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // state of fsta. 5624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project A loop(match_labelb, match_labelb, Weight::One(), sf); 5634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AddArc(s, loop, arcb, 0, find_input); 5644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (((T & COMPOSE_RHO) != 0) && (labela == kRhoLabel)) { 5664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Case 2: 'match_labelb' can be matched against a 5674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // "rest" (rho) label in fsta. 5684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (find_input) { 5694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arca.ilabel = match_labelb; 5704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (arca.olabel == kRhoLabel) 5714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arca.olabel = match_labelb; 5724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 5734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arca.olabel = match_labelb; 5744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (arca.ilabel == kRhoLabel) 5754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arca.ilabel = match_labelb; 5764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AddArc(s, arca, arcb, 0, find_input); // move fwd on match 5784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (numepsa != numarcsa || finala) { // Handle FSTB epsilon 5824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project A earca(0, 0, Weight::One(), sa); 5834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AddArc(s, earca, arcb, numepsa > 0, find_input); // move on epsilon 5844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetArcs(s); 5874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Finds matches to MATCH_LABEL in arcs given by AITER 5914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // using FIND_INPUT to determine whether to look on input or output. 5924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool FindLabel(ArcIterator< Fst<A> > *aiter, size_t numarcs, 5934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Label match_label, bool find_input) { 5944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // binary search for match 5954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t low = 0; 5964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t high = numarcs; 5974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (low < high) { 5984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t mid = (low + high) / 2; 5994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter->Seek(mid); 6004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Label label = find_input ? 6014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter->Value().ilabel : aiter->Value().olabel; 6024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (label > match_label) { 6034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project high = mid; 6044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (label < match_label) { 6054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project low = mid + 1; 6064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 6074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // find first matching label (when non-determinism) 6084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (size_t i = mid; i > low; --i) { 6094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter->Seek(i - 1); 6104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project label = find_input ? aiter->Value().ilabel : aiter->Value().olabel; 6114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (label != match_label) { 6124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter->Seek(i); 6134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 6144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 6174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 6204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId ComputeStart() { 6234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s1 = ComposeFstImplBase<A>::fst1_->Start(); 6244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s2 = ComposeFstImplBase<A>::fst2_->Start(); 6254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s1 == kNoStateId || s2 == kNoStateId) 6264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return kNoStateId; 6274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateTuple tuple(s1, s2, 0); 6284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return FindState(tuple); 6294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight ComputeFinal(StateId s) { 6324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateTuple &tuple = state_tuples_[s]; 6334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight final = Times(ComposeFstImplBase<A>::fst1_->Final(tuple.state_id1), 6344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeFstImplBase<A>::fst2_->Final(tuple.state_id2)); 6354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return final; 6364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FindType find_type_; // find label on which side? 6404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Maps from StateId to StateTuple. 6424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateTuple> state_tuples_; 6434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Maps from StateTuple to StateId. 6454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateTupleTable state_tuple_table_; 6464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(ComposeFstImpl); 6484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 6494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes the composition of two transducers. This version is a 6524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// delayed Fst. If FST1 transduces string x to y with weight a and FST2 6534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// transduces y to z with weight b, then their composition transduces 6544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// string x to z with weight Times(x, z). 6554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 6564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The output labels of the first transducer or the input labels of 6574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the second transducer must be sorted. The weights need to form a 6584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// commutative semiring (valid for TropicalWeight and LogWeight). 6594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 6604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 6614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Assuming the first FST is unsorted and the second is sorted: 6624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: O(v1 v2 d1 (log d2 + m2)), 6634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(v1 v2) 6644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where vi = # of states visited, di = maximum out-degree, and mi the 6654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// maximum multiplicity of the states visited for the ith 6664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// FST. Constant time and space to visit an input state or arc is 6674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// assumed and exclusive of caching. 6684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 6694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Caveats: 6704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - ComposeFst does not trim its output (since it is a delayed operation). 6714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - The efficiency of composition can be strongly affected by several factors: 6724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - the choice of which tnansducer is sorted - prefer sorting the FST 6734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// that has the greater average out-degree. 6744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - the amount of non-determinism 6754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - the presence and location of epsilon transitions - avoid epsilon 6764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// transitions on the output side of the first transducer or 6774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the input side of the second transducer or prefer placing 6784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// them later in a path since they delay matching and can 6794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// introduce non-coaccessible states and transitions. 6804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 6814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ComposeFst : public Fst<A> { 6824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 6834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class ArcIterator< ComposeFst<A> >; 6844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class CacheStateIterator< ComposeFst<A> >; 6854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class CacheArcIterator< ComposeFst<A> >; 6864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 6884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 6894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 6904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef CacheState<A> State; 6914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeFst(const Fst<A> &fst1, const Fst<A> &fst2) 6934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : impl_(Init(fst1, fst2, ComposeFstOptions<>())) { } 6944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project template <uint64 T> 6964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeFst(const Fst<A> &fst1, 6974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A> &fst2, 6984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const ComposeFstOptions<T> &opts) 6994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : impl_(Init(fst1, fst2, opts)) { } 7004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeFst(const ComposeFst<A> &fst) : Fst<A>(fst), impl_(fst.impl_) { 7024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->IncrRefCount(); 7034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 7044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ~ComposeFst() { if (!impl_->DecrRefCount()) delete impl_; } 7064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Start() const { return impl_->Start(); } 7084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual Weight Final(StateId s) const { return impl_->Final(s); } 7104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumArcs(StateId s) const { return impl_->NumArcs(s); } 7124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumInputEpsilons(StateId s) const { 7144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->NumInputEpsilons(s); 7154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 7164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumOutputEpsilons(StateId s) const { 7184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->NumOutputEpsilons(s); 7194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 7204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual uint64 Properties(uint64 mask, bool test) const { 7224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (test) { 7234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 known, test = TestProperties(*this, mask, &known); 7244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->SetProperties(test, known); 7254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return test & mask; 7264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 7274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->Properties(mask); 7284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 7294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 7304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const string& Type() const { return impl_->Type(); } 7324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ComposeFst<A> *Copy() const { 7344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return new ComposeFst<A>(*this); 7354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 7364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const SymbolTable* InputSymbols() const { 7384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->InputSymbols(); 7394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 7404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const SymbolTable* OutputSymbols() const { 7424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->OutputSymbols(); 7434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 7444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual inline void InitStateIterator(StateIteratorData<A> *data) const; 7464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const { 7484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->InitArcIterator(s, data); 7494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 7504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Access to flags encoding compose options/optimizations etc. (for 7524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // debugging). 7534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 ComposeFlags() const { return impl_->ComposeFlags(); } 7544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project protected: 7564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeFstImplBase<A> *Impl() { return impl_; } 7574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 7594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeFstImplBase<A> *impl_; 7604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Auxiliary method encapsulating the creation of a ComposeFst 7624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // implementation that is appropriate for the properties of fst1 and 7634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // fst2. 7644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project template <uint64 T> 7654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static ComposeFstImplBase<A> *Init( 7664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A> &fst1, 7674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A> &fst2, 7684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const ComposeFstOptions<T> &opts) { 7694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Filter for sort properties (forces a property check). 7714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 sort_props_mask = kILabelSorted | kOLabelSorted; 7724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Filter for optimization-related properties (does not force a 7734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // property-check). 7744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 opt_props_mask = 7754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kString | kIDeterministic | kODeterministic | kNoIEpsilons | 7764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kNoOEpsilons; 7774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props1 = fst1.Properties(sort_props_mask, true); 7794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props2 = fst2.Properties(sort_props_mask, true); 7804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project props1 |= fst1.Properties(opt_props_mask, false); 7824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project props2 |= fst2.Properties(opt_props_mask, false); 7834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!(Weight::Properties() & kCommutative)) { 7854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project props1 |= fst1.Properties(kUnweighted, true); 7864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project props2 |= fst2.Properties(kUnweighted, true); 7874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!(props1 & kUnweighted) && !(props2 & kUnweighted)) 7884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "ComposeFst: Weight needs to be a commutative semiring: " 7894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << Weight::Type(); 7904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 7914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Case 1: flag COMPOSE_GENERIC disables optimizations. 7934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (T & COMPOSE_GENERIC) { 7944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return new ComposeFstImpl<A, T>(fst1, fst2, opts); 7954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 7964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const uint64 kStringDetOptProps = 7984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kIDeterministic | kILabelSorted | kNoIEpsilons; 7994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const uint64 kDetStringOptProps = 8004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kODeterministic | kOLabelSorted | kNoOEpsilons; 8014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Case 2: fst1 is a string, fst2 is deterministic and epsilon-free. 8034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((props1 & kString) && 8044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !(T & (COMPOSE_FST1_RHO | COMPOSE_FST1_PHI | COMPOSE_FST1_SIGMA)) && 8054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ((props2 & kStringDetOptProps) == kStringDetOptProps)) { 8064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return new ComposeFstImpl<A, T | COMPOSE_FST1_STRING | COMPOSE_FST2_DET>( 8074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst1, fst2, opts); 8084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 8094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Case 3: fst1 is deterministic and epsilon-free, fst2 is string. 8104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((props2 & kString) && 8114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !(T & (COMPOSE_FST1_RHO | COMPOSE_FST1_PHI | COMPOSE_FST1_SIGMA)) && 8124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ((props1 & kDetStringOptProps) == kDetStringOptProps)) { 8134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return new ComposeFstImpl<A, T | COMPOSE_FST2_STRING | COMPOSE_FST1_DET>( 8144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst1, fst2, opts); 8154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 8164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Default case: no optimizations. 8184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return new ComposeFstImpl<A, T>(fst1, fst2, opts); 8194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 8204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void operator=(const ComposeFst<A> &fst); // disallow 8224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 8234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for ComposeFst. 8264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class A> 8274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StateIterator< ComposeFst<A> > 8284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public CacheStateIterator< ComposeFst<A> > { 8294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 8304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit StateIterator(const ComposeFst<A> &fst) 8314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheStateIterator< ComposeFst<A> >(fst) {} 8324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 8334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for ComposeFst. 8364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 8374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcIterator< ComposeFst<A> > 8384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public CacheArcIterator< ComposeFst<A> > { 8394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 8404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 8414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator(const ComposeFst<A> &fst, StateId s) 8434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheArcIterator< ComposeFst<A> >(fst, s) { 8444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!fst.impl_->HasArcs(s)) 8454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst.impl_->Expand(s); 8464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 8474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 8494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(ArcIterator); 8504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 8514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> inline 8534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid ComposeFst<A>::InitStateIterator(StateIteratorData<A> *data) const { 8544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data->base = new StateIterator< ComposeFst<A> >(*this); 8554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 8564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Useful alias when using StdArc. 8584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef ComposeFst<StdArc> StdComposeFst; 8594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct ComposeOptions { 8624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool connect; // Connect output 8634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeOptions(bool c) : connect(c) {} 8654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeOptions() : connect(true) { } 8664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 8674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes the composition of two transducers. This version writes 8704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the composed FST into a MurableFst. If FST1 transduces string x to 8714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// y with weight a and FST2 transduces y to z with weight b, then 8724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// their composition transduces string x to z with weight 8734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Times(x, z). 8744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 8754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The output labels of the first transducer or the input labels of 8764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the second transducer must be sorted. The weights need to form a 8774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// commutative semiring (valid for TropicalWeight and LogWeight). 8784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 8794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 8804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Assuming the first FST is unsorted and the second is sorted: 8814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: O(V1 V2 D1 (log D2 + M2)), 8824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(V1 V2 D1 M2) 8834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where Vi = # of states, Di = maximum out-degree, and Mi is 8844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the maximum multiplicity for the ith FST. 8854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 8864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Caveats: 8874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Compose trims its output. 8884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - The efficiency of composition can be strongly affected by several factors: 8894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - the choice of which tnansducer is sorted - prefer sorting the FST 8904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// that has the greater average out-degree. 8914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - the amount of non-determinism 8924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - the presence and location of epsilon transitions - avoid epsilon 8934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// transitions on the output side of the first transducer or 8944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the input side of the second transducer or prefer placing 8954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// them later in a path since they delay matching and can 8964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// introduce non-coaccessible states and transitions. 8974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc> 8984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Compose(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2, 8994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project MutableFst<Arc> *ofst, 9004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const ComposeOptions &opts = ComposeOptions()) { 9014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeFstOptions<> nopts; 9024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project nopts.gc_limit = 0; // Cache only the last state for fastest copy. 9034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *ofst = ComposeFst<Arc>(ifst1, ifst2, nopts); 9044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (opts.connect) 9054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Connect(ofst); 9064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 9074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 9084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 9094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 9104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_COMPOSE_H__ 911