14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// closure.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 concatenative closure of an Fst. 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_CLOSURE_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_CLOSURE_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/mutable-fst.h" 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/rational.h" 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes the concatenative closure. This version modifies its 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// MutableFst input. If FST transduces string x to y with weight a, 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// then the closure transduces x to y with weight a, xx to yy with 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// weight Times(a, a), xxx to yyy with with Times(Times(a, a), a), 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// etc. If closure_type == CLOSURE_STAR, then the empty string is 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// transduced to itself with weight Weight::One() as well. 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: O(V) 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(V) 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where V = # of states. 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc> 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Closure(MutableFst<Arc> *fst, ClosureType closure_type) { 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 uint64 props = fst->Properties(kFstProperties, false); 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId start = fst->Start(); 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateIterator< MutableFst<Arc> > siter(*fst); 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !siter.Done(); 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project siter.Next()) { 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s = siter.Value(); 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight final = fst->Final(s); 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (final != Weight::Zero()) 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->AddArc(s, Arc(0, 0, final, start)); 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (closure_type == CLOSURE_STAR) { 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId nstart = fst->AddState(); 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->SetStart(nstart); 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->SetFinal(nstart, Weight::One()); 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (start != kNoLabel) 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->AddArc(nstart, Arc(0, 0, Weight::One(), start)); 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR), 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kFstProperties); 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes the concatenative closure. This version modifies its 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// RationalFst input. 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc> 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Closure(RationalFst<Arc> *fst, ClosureType closure_type) { 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->Impl()->AddClosure(closure_type); 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct ClosureFstOptions : RationalFstOptions { 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ClosureType type; 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ClosureFstOptions(const RationalFstOptions &opts, ClosureType t) 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : RationalFstOptions(opts), type(t) {} 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit ClosureFstOptions(ClosureType t) : type(t) {} 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ClosureFstOptions() : type(CLOSURE_STAR) {} 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes the concatenative closure. This version is a delayed 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Fst. If FST transduces string x to y with weight a, then the 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// closure transduces x to y with weight a, xx to yy with weight 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Times(a, a), xxx to yyy with weight Times(Times(a, a), a), etc. If 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// closure_type == CLOSURE_STAR, then The empty string is transduced 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// to itself with weight Weight::One() as well. 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: O(v) 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(v) 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where v = # of states visited. Constant time and space to visit an 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// input state or arc is assumed and exclusive of caching. 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ClosureFst : public RationalFst<A> { 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using RationalFst<A>::Impl; 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ClosureFst(const Fst<A> &fst, ClosureType closure_type) { 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Impl()->InitClosure(fst, closure_type); 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ClosureFst(const Fst<A> &fst, const ClosureFstOptions &opts) 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : RationalFst<A>(opts) { 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Impl()->InitClosure(fst, opts.type); 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ClosureFst(const ClosureFst<A> &fst) : RationalFst<A>(fst) {} 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ClosureFst<A> *Copy() const { return new ClosureFst<A>(*this); } 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for ClosureFst. 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StateIterator< ClosureFst<A> > : public StateIterator< RationalFst<A> > { 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit StateIterator(const ClosureFst<A> &fst) 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : StateIterator< RationalFst<A> >(fst) {} 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for ClosureFst. 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcIterator< ClosureFst<A> > : public ArcIterator< RationalFst<A> > { 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator(const ClosureFst<A> &fst, StateId s) 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ArcIterator< RationalFst<A> >(fst, s) {} 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Useful alias when using StdArc. 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef ClosureFst<StdArc> StdClosureFst; 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_CLOSURE_H__ 143