closure.h revision f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2
1ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// closure.h 2ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 3ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Licensed under the Apache License, Version 2.0 (the "License"); 4ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// you may not use this file except in compliance with the License. 5ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// You may obtain a copy of the License at 6ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 7ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// http://www.apache.org/licenses/LICENSE-2.0 8ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 9ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Unless required by applicable law or agreed to in writing, software 10ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// distributed under the License is distributed on an "AS IS" BASIS, 11ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// See the License for the specific language governing permissions and 13ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// limitations under the License. 14ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 15ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Copyright 2005-2010 Google, Inc. 16ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Author: riley@google.com (Michael Riley) 17ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 18ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// \file 19ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Functions and classes to compute the concatenative closure of an Fst. 20ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 21ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifndef FST_LIB_CLOSURE_H__ 22ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define FST_LIB_CLOSURE_H__ 23ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 24ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <vector> 25ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownusing std::vector; 26ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <algorithm> 27ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 28ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <fst/mutable-fst.h> 29ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <fst/rational.h> 30ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 31ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 32ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownnamespace fst { 33ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 34ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Computes the concatenative closure. This version modifies its 35ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// MutableFst input. If FST transduces string x to y with weight a, 36ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// then the closure transduces x to y with weight a, xx to yy with 37ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// weight Times(a, a), xxx to yyy with with Times(Times(a, a), a), 38ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// etc. If closure_type == CLOSURE_STAR, then the empty string is 39ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// transduced to itself with weight Weight::One() as well. 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 41ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Complexity: 42ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// - Time: O(V) 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// - Space: O(V) 44ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// where V = # of states. 45ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntemplate<class Arc> 46ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid Closure(MutableFst<Arc> *fst, ClosureType closure_type) { 47ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown typedef typename Arc::StateId StateId; 48ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown typedef typename Arc::Label Label; 49ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown typedef typename Arc::Weight Weight; 50ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 51ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown uint64 props = fst->Properties(kFstProperties, false); 52ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown StateId start = fst->Start(); 53ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (StateIterator< MutableFst<Arc> > siter(*fst); 54ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown !siter.Done(); 55ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown siter.Next()) { 56ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown StateId s = siter.Value(); 57ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Weight final = fst->Final(s); 58ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (final != Weight::Zero()) 59ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fst->AddArc(s, Arc(0, 0, final, start)); 60ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 61ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (closure_type == CLOSURE_STAR) { 62ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fst->ReserveStates(fst->NumStates() + 1); 63ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown StateId nstart = fst->AddState(); 64ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fst->SetStart(nstart); 65ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fst->SetFinal(nstart, Weight::One()); 66ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (start != kNoLabel) 67ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fst->AddArc(nstart, Arc(0, 0, Weight::One(), start)); 68ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 69ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fst->SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR), 70ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown kFstProperties); 71ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 72ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 73ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Computes the concatenative closure. This version modifies its 74ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// RationalFst input. 75ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntemplate<class Arc> 76ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid Closure(RationalFst<Arc> *fst, ClosureType closure_type) { 77ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fst->GetImpl()->AddClosure(closure_type); 78ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 79ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 80ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 81ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstruct ClosureFstOptions : RationalFstOptions { 82ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ClosureType type; 83ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 84ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ClosureFstOptions(const RationalFstOptions &opts, ClosureType t) 85ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : RationalFstOptions(opts), type(t) {} 86ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown explicit ClosureFstOptions(ClosureType t) : type(t) {} 87ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ClosureFstOptions() : type(CLOSURE_STAR) {} 88ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown}; 89ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 90ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 91ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Computes the concatenative closure. This version is a delayed 92ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Fst. If FST transduces string x to y with weight a, then the 93ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// closure transduces x to y with weight a, xx to yy with weight 94ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Times(a, a), xxx to yyy with weight Times(Times(a, a), a), etc. If 95ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// closure_type == CLOSURE_STAR, then The empty string is transduced 96ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// to itself with weight Weight::One() as well. 97ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 98ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Complexity: 99ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// - Time: O(v) 100ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// - Space: O(v) 101ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// where v = # of states visited. Constant time and space to visit an 102ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// input state or arc is assumed and exclusive of caching. 103ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntemplate <class A> 104ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownclass ClosureFst : public RationalFst<A> { 105ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown public: 106ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown using ImplToFst< RationalFstImpl<A> >::GetImpl; 107ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 108ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown typedef A Arc; 109ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 110ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ClosureFst(const Fst<A> &fst, ClosureType closure_type) { 111ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown GetImpl()->InitClosure(fst, closure_type); 112ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 113ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 114ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ClosureFst(const Fst<A> &fst, const ClosureFstOptions &opts) 115ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : RationalFst<A>(opts) { 116ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown GetImpl()->InitClosure(fst, opts.type); 117ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // See Fst<>::Copy() for doc. 120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ClosureFst(const ClosureFst<A> &fst, bool safe = false) 121ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : RationalFst<A>(fst, safe) {} 122ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 123ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Get a copy of this ClosureFst. See Fst<>::Copy() for further doc. 124ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown virtual ClosureFst<A> *Copy(bool safe = false) const { 125ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return new ClosureFst<A>(*this, safe); 126ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 127ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown}; 128ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 129ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 130ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Specialization for ClosureFst. 131ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntemplate <class A> 132ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownclass StateIterator< ClosureFst<A> > : public StateIterator< RationalFst<A> > { 133ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown public: 134ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown explicit StateIterator(const ClosureFst<A> &fst) 135ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : StateIterator< RationalFst<A> >(fst) {} 136ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown}; 137ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 138ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 139ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Specialization for ClosureFst. 140ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntemplate <class A> 141ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownclass ArcIterator< ClosureFst<A> > : public ArcIterator< RationalFst<A> > { 142ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown public: 143ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown typedef typename A::StateId StateId; 144ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 145ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ArcIterator(const ClosureFst<A> &fst, StateId s) 146ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : ArcIterator< RationalFst<A> >(fst, s) {} 147ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown}; 148ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 149ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 150ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Useful alias when using StdArc. 151ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef ClosureFst<StdArc> StdClosureFst; 152ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 153ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} // namespace fst 154ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 155ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif // FST_LIB_CLOSURE_H__ 156ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown