Home | History | Annotate | Download | only in fst 
      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 // Copyright 2005-2010 Google, Inc.
     16 // Author: riley (at) google.com (Michael Riley)
     17 //
     18 // \file
     19 // Functions and classes to compute the concatenative closure of an Fst.
     20 
     21 #ifndef FST_LIB_CLOSURE_H__
     22 #define FST_LIB_CLOSURE_H__
     23 
     24 #include <vector>
     25 using std::vector;
     26 #include <algorithm>
     27 
     28 #include <fst/mutable-fst.h>
     29 #include <fst/rational.h>
     30 
     31 
     32 namespace fst {
     33 
     34 // Computes the concatenative closure. This version modifies its
     35 // MutableFst input. If FST transduces string x to y with weight a,
     36 // then the closure transduces x to y with weight a, xx to yy with
     37 // weight Times(a, a), xxx to yyy with with Times(Times(a, a), a),
     38 // etc. If closure_type == CLOSURE_STAR, then the empty string is
     39 // transduced to itself with weight Weight::One() as well.
     40 //
     41 // Complexity:
     42 // - Time: O(V)
     43 // - Space: O(V)
     44 // where V = # of states.
     45 template<class Arc>
     46 void Closure(MutableFst<Arc> *fst, ClosureType closure_type) {
     47   typedef typename Arc::StateId StateId;
     48   typedef typename Arc::Label Label;
     49   typedef typename Arc::Weight Weight;
     50 
     51   uint64 props = fst->Properties(kFstProperties, false);
     52   StateId start = fst->Start();
     53   for (StateIterator< MutableFst<Arc> > siter(*fst);
     54        !siter.Done();
     55        siter.Next()) {
     56     StateId s = siter.Value();
     57     Weight final = fst->Final(s);
     58     if (final != Weight::Zero())
     59       fst->AddArc(s, Arc(0, 0, final, start));
     60   }
     61   if (closure_type == CLOSURE_STAR) {
     62     fst->ReserveStates(fst->NumStates() + 1);
     63     StateId nstart = fst->AddState();
     64     fst->SetStart(nstart);
     65     fst->SetFinal(nstart, Weight::One());
     66     if (start != kNoLabel)
     67       fst->AddArc(nstart, Arc(0, 0, Weight::One(), start));
     68   }
     69   fst->SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR),
     70                      kFstProperties);
     71 }
     72 
     73 // Computes the concatenative closure. This version modifies its
     74 // RationalFst input.
     75 template<class Arc>
     76 void Closure(RationalFst<Arc> *fst, ClosureType closure_type) {
     77   fst->GetImpl()->AddClosure(closure_type);
     78 }
     79 
     80 
     81 struct ClosureFstOptions : RationalFstOptions {
     82   ClosureType type;
     83 
     84   ClosureFstOptions(const RationalFstOptions &opts, ClosureType t)
     85       : RationalFstOptions(opts), type(t) {}
     86   explicit ClosureFstOptions(ClosureType t) : type(t) {}
     87   ClosureFstOptions() : type(CLOSURE_STAR) {}
     88 };
     89 
     90 
     91 // Computes the concatenative closure. This version is a delayed
     92 // Fst. If FST transduces string x to y with weight a, then the
     93 // closure transduces x to y with weight a, xx to yy with weight
     94 // Times(a, a), xxx to yyy with weight Times(Times(a, a), a), etc. If
     95 // closure_type == CLOSURE_STAR, then The empty string is transduced
     96 // to itself with weight Weight::One() as well.
     97 //
     98 // Complexity:
     99 // - Time: O(v)
    100 // - Space: O(v)
    101 // where v = # of states visited. Constant time and space to visit an
    102 // input state or arc is assumed and exclusive of caching.
    103 template <class A>
    104 class ClosureFst : public RationalFst<A> {
    105  public:
    106   using ImplToFst< RationalFstImpl<A> >::GetImpl;
    107 
    108   typedef A Arc;
    109 
    110   ClosureFst(const Fst<A> &fst, ClosureType closure_type) {
    111     GetImpl()->InitClosure(fst, closure_type);
    112   }
    113 
    114   ClosureFst(const Fst<A> &fst, const ClosureFstOptions &opts)
    115       : RationalFst<A>(opts) {
    116     GetImpl()->InitClosure(fst, opts.type);
    117   }
    118 
    119   // See Fst<>::Copy() for doc.
    120   ClosureFst(const ClosureFst<A> &fst, bool safe = false)
    121       : RationalFst<A>(fst, safe) {}
    122 
    123   // Get a copy of this ClosureFst. See Fst<>::Copy() for further doc.
    124   virtual ClosureFst<A> *Copy(bool safe = false) const {
    125     return new ClosureFst<A>(*this, safe);
    126   }
    127 };
    128 
    129 
    130 // Specialization for ClosureFst.
    131 template <class A>
    132 class StateIterator< ClosureFst<A> > : public StateIterator< RationalFst<A> > {
    133  public:
    134   explicit StateIterator(const ClosureFst<A> &fst)
    135       : StateIterator< RationalFst<A> >(fst) {}
    136 };
    137 
    138 
    139 // Specialization for ClosureFst.
    140 template <class A>
    141 class ArcIterator< ClosureFst<A> > : public ArcIterator< RationalFst<A> > {
    142  public:
    143   typedef typename A::StateId StateId;
    144 
    145   ArcIterator(const ClosureFst<A> &fst, StateId s)
    146       : ArcIterator< RationalFst<A> >(fst, s) {}
    147 };
    148 
    149 
    150 // Useful alias when using StdArc.
    151 typedef ClosureFst<StdArc> StdClosureFst;
    152 
    153 }  // namespace fst
    154 
    155 #endif  // FST_LIB_CLOSURE_H__
    156