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