Home | History | Annotate | Download | only in lib 
      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 
     25 namespace 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.
     38 template<class Arc>
     39 void 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.
     67 template<class Arc>
     68 void Closure(RationalFst<Arc> *fst, ClosureType closure_type) {
     69   fst->Impl()->AddClosure(closure_type);
     70 }
     71 
     72 
     73 struct 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.
     95 template <class A>
     96 class 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.
    118 template <class A>
    119 class 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.
    127 template <class A>
    128 class 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.
    138 typedef ClosureFst<StdArc> StdClosureFst;
    139 
    140 }  // namespace fst
    141 
    142 #endif  // FST_LIB_CLOSURE_H__
    143