14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// concat.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// Functions and classes to compute the concat of two FSTs. 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_CONCAT_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_CONCAT_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <algorithm> 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/mutable-fst.h" 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/rational.h" 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes the concatenation (product) of two FSTs; this version 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// modifies its MutableFst argument. If FST1 transduces string x to y 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// with weight a and FST2 transduces string w to v with weight b, then 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// their concatenation transduces string xw to yv with Times(a, b). 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: O(V1 + V2 + E2) 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(V1 + V2 + E2) 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where Vi = # of states and Ei = # of arcs of the ith FST. 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc> 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Concat(MutableFst<Arc> *fst1, const Fst<Arc> &fst2) { 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Label Label; 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId start1 = fst1->Start(); 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (start1 == kNoStateId) 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return; 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props1 = fst1->Properties(kFstProperties, false); 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props2 = fst2.Properties(kFstProperties, false); 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId numstates1= fst1->NumStates(); 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateIterator< Fst<Arc> > siter2(fst2); 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !siter2.Done(); 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project siter2.Next()) { 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s1 = fst1->AddState(); 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s2 = siter2.Value(); 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst1->SetFinal(s1, fst2.Final(s2)); 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator< Fst<Arc> > aiter(fst2, s2); 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !aiter.Done(); 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter.Next()) { 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Arc arc = aiter.Value(); 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.nextstate += numstates1; 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst1->AddArc(s1, arc); 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId start2 = fst2.Start(); 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId s1 = 0; s1 < numstates1; ++s1) { 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight final = fst1->Final(s1); 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (final != Weight::Zero()) { 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst1->SetFinal(s1, Weight::Zero()); 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (start2 != kNoStateId) 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst1->AddArc(s1, Arc(0, 0, final, start2 + numstates1)); 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (start2 != kNoStateId) 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst1->SetProperties(ConcatProperties(props1, props2), kFstProperties); 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes the concatentation of two FSTs. This version modifies its 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// RationalFst input. 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc> 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Concat(RationalFst<Arc> *fst1, const Fst<Arc> &fst2) { 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst1->Impl()->AddConcat(fst2); 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef RationalFstOptions ConcatFstOptions; 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes the concatenation (product) of two FSTs; this version is a 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// delayed Fst. If FST1 transduces string x to y with weight a and FST2 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// transduces string w to v with weight b, then their concatenation 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// transduces string xw to yv with Times(a, b). 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: O(v1 + e1 + v2 + e2), 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(v1 + v2) 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where vi = # of states visited and ei = # of arcs visited of the 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// ith FST. Constant time and space to visit an input state or arc is 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// assumed and exclusive of caching. 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ConcatFst : public RationalFst<A> { 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using RationalFst<A>::Impl; 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ConcatFst(const Fst<A> &fst1, const Fst<A> &fst2) { 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Impl()->InitConcat(fst1, fst2); 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ConcatFst(const Fst<A> &fst1, const Fst<A> &fst2, 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const ConcatFstOptions &opts) : RationalFst<A>(opts) { 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Impl()->InitConcat(fst1, fst2); 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ConcatFst(const ConcatFst<A> &fst) : RationalFst<A>(fst) {} 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ConcatFst<A> *Copy() const { return new ConcatFst<A>(*this); } 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for ConcatFst. 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StateIterator< ConcatFst<A> > : public StateIterator< RationalFst<A> > { 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit StateIterator(const ConcatFst<A> &fst) 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : StateIterator< RationalFst<A> >(fst) {} 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for ConcatFst. 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcIterator< ConcatFst<A> > : public ArcIterator< RationalFst<A> > { 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator(const ConcatFst<A> &fst, StateId s) 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ArcIterator< RationalFst<A> >(fst, s) {} 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Useful alias when using StdArc. 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef ConcatFst<StdArc> StdConcatFst; 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_CONCAT_H__ 154