Home | History | Annotate | Download | only in fst 
      1 // rational.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 // An Fst implementation and base interface for delayed unions,
     20 // concatenations and closures.
     21 
     22 #ifndef FST_LIB_RATIONAL_H__
     23 #define FST_LIB_RATIONAL_H__
     24 
     25 #include <algorithm>
     26 #include <string>
     27 #include <vector>
     28 using std::vector;
     29 
     30 #include <fst/mutable-fst.h>
     31 #include <fst/replace.h>
     32 #include <fst/test-properties.h>
     33 
     34 
     35 namespace fst {
     36 
     37 typedef CacheOptions RationalFstOptions;
     38 
     39 // This specifies whether to add the empty string.
     40 enum ClosureType { CLOSURE_STAR = 0,    // T* -> add the empty string
     41                    CLOSURE_PLUS = 1 };  // T+ -> don't add the empty string
     42 
     43 template <class A> class RationalFst;
     44 template <class A> void Union(RationalFst<A> *fst1, const Fst<A> &fst2);
     45 template <class A> void Concat(RationalFst<A> *fst1, const Fst<A> &fst2);
     46 template <class A> void Concat(const Fst<A> &fst1, RationalFst<A> *fst2);
     47 template <class A> void Closure(RationalFst<A> *fst, ClosureType closure_type);
     48 
     49 
     50 // Implementation class for delayed unions, concatenations and closures.
     51 template<class A>
     52 class RationalFstImpl : public FstImpl<A> {
     53  public:
     54   using FstImpl<A>::SetType;
     55   using FstImpl<A>::SetProperties;
     56   using FstImpl<A>::WriteHeader;
     57   using FstImpl<A>::SetInputSymbols;
     58   using FstImpl<A>::SetOutputSymbols;
     59 
     60   typedef A Arc;
     61   typedef typename A::Weight Weight;
     62   typedef typename A::StateId StateId;
     63   typedef typename A::Label Label;
     64 
     65   explicit RationalFstImpl(const RationalFstOptions &opts)
     66       : nonterminals_(0),
     67         replace_(0),
     68         replace_options_(opts, 0) {
     69     SetType("rational");
     70     fst_tuples_.push_back(pair<Label, const Fst<A>*>(0, 0));
     71   }
     72 
     73   RationalFstImpl(const RationalFstImpl<A> &impl)
     74       : rfst_(impl.rfst_),
     75         nonterminals_(impl.nonterminals_),
     76 
     77         replace_(impl.replace_ ? impl.replace_->Copy(true) : 0),
     78         replace_options_(impl.replace_options_) {
     79     SetType("rational");
     80     fst_tuples_.reserve(impl.fst_tuples_.size());
     81     for (size_t i = 0; i < impl.fst_tuples_.size(); ++i)
     82       fst_tuples_.push_back(make_pair(impl.fst_tuples_[i].first,
     83                                       impl.fst_tuples_[i].second
     84                                       ? impl.fst_tuples_[i].second->Copy(true)
     85                                       : 0));
     86   }
     87 
     88   virtual ~RationalFstImpl() {
     89     for (size_t i = 0; i < fst_tuples_.size(); ++i)
     90       if (fst_tuples_[i].second)
     91         delete fst_tuples_[i].second;
     92     if (replace_)
     93       delete replace_;
     94   }
     95 
     96   StateId Start() { return Replace()->Start(); }
     97 
     98   Weight Final(StateId s) { return Replace()->Final(s); }
     99 
    100   size_t NumArcs(StateId s) { return Replace()->NumArcs(s); }
    101 
    102   size_t NumInputEpsilons(StateId s) {
    103     return Replace()->NumInputEpsilons(s);
    104   }
    105 
    106   size_t NumOutputEpsilons(StateId s) {
    107     return Replace()->NumOutputEpsilons(s);
    108   }
    109 
    110   uint64 Properties() const { return Properties(kFstProperties); }
    111 
    112   // Set error if found; return FST impl properties.
    113   uint64 Properties(uint64 mask) const {
    114     if ((mask & kError) && Replace()->Properties(kError, false))
    115       SetProperties(kError, kError);
    116     return FstImpl<Arc>::Properties(mask);
    117   }
    118 
    119   // Implementation of UnionFst(fst1,fst2)
    120   void InitUnion(const Fst<A> &fst1, const Fst<A> &fst2) {
    121     if (replace_)
    122       delete replace_;
    123     uint64 props1 = fst1.Properties(kFstProperties, false);
    124     uint64 props2 = fst2.Properties(kFstProperties, false);
    125     SetInputSymbols(fst1.InputSymbols());
    126     SetOutputSymbols(fst1.OutputSymbols());
    127     rfst_.AddState();
    128     rfst_.AddState();
    129     rfst_.SetStart(0);
    130     rfst_.SetFinal(1, Weight::One());
    131     rfst_.SetInputSymbols(fst1.InputSymbols());
    132     rfst_.SetOutputSymbols(fst1.OutputSymbols());
    133     nonterminals_ = 2;
    134     rfst_.AddArc(0, A(0, -1, Weight::One(), 1));
    135     rfst_.AddArc(0, A(0, -2, Weight::One(), 1));
    136     fst_tuples_.push_back(make_pair(-1, fst1.Copy()));
    137     fst_tuples_.push_back(make_pair(-2, fst2.Copy()));
    138     SetProperties(UnionProperties(props1, props2, true), kCopyProperties);
    139   }
    140 
    141   // Implementation of ConcatFst(fst1,fst2)
    142   void InitConcat(const Fst<A> &fst1, const Fst<A> &fst2) {
    143     if (replace_)
    144       delete replace_;
    145     uint64 props1 = fst1.Properties(kFstProperties, false);
    146     uint64 props2 = fst2.Properties(kFstProperties, false);
    147     SetInputSymbols(fst1.InputSymbols());
    148     SetOutputSymbols(fst1.OutputSymbols());
    149     rfst_.AddState();
    150     rfst_.AddState();
    151     rfst_.AddState();
    152     rfst_.SetStart(0);
    153     rfst_.SetFinal(2, Weight::One());
    154     rfst_.SetInputSymbols(fst1.InputSymbols());
    155     rfst_.SetOutputSymbols(fst1.OutputSymbols());
    156     nonterminals_ = 2;
    157     rfst_.AddArc(0, A(0, -1, Weight::One(), 1));
    158     rfst_.AddArc(1, A(0, -2, Weight::One(), 2));
    159     fst_tuples_.push_back(make_pair(-1, fst1.Copy()));
    160     fst_tuples_.push_back(make_pair(-2, fst2.Copy()));
    161     SetProperties(ConcatProperties(props1, props2, true), kCopyProperties);
    162   }
    163 
    164   // Implementation of ClosureFst(fst, closure_type)
    165   void InitClosure(const Fst<A> &fst, ClosureType closure_type) {
    166     if (replace_)
    167       delete replace_;
    168     uint64 props = fst.Properties(kFstProperties, false);
    169     SetInputSymbols(fst.InputSymbols());
    170     SetOutputSymbols(fst.OutputSymbols());
    171     if (closure_type == CLOSURE_STAR) {
    172       rfst_.AddState();
    173       rfst_.SetStart(0);
    174       rfst_.SetFinal(0, Weight::One());
    175       rfst_.AddArc(0, A(0, -1, Weight::One(), 0));
    176     } else {
    177       rfst_.AddState();
    178       rfst_.AddState();
    179       rfst_.SetStart(0);
    180       rfst_.SetFinal(1, Weight::One());
    181       rfst_.AddArc(0, A(0, -1, Weight::One(), 1));
    182       rfst_.AddArc(1, A(0, 0, Weight::One(), 0));
    183     }
    184     rfst_.SetInputSymbols(fst.InputSymbols());
    185     rfst_.SetOutputSymbols(fst.OutputSymbols());
    186     fst_tuples_.push_back(make_pair(-1, fst.Copy()));
    187     nonterminals_ = 1;
    188     SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR, true),
    189                   kCopyProperties);
    190   }
    191 
    192   // Implementation of Union(Fst &, RationalFst *)
    193   void AddUnion(const Fst<A> &fst) {
    194     if (replace_)
    195       delete replace_;
    196     uint64 props1 = FstImpl<A>::Properties();
    197     uint64 props2 = fst.Properties(kFstProperties, false);
    198     VectorFst<A> afst;
    199     afst.AddState();
    200     afst.AddState();
    201     afst.SetStart(0);
    202     afst.SetFinal(1, Weight::One());
    203     ++nonterminals_;
    204     afst.AddArc(0, A(0, -nonterminals_, Weight::One(), 1));
    205     Union(&rfst_, afst);
    206     fst_tuples_.push_back(make_pair(-nonterminals_, fst.Copy()));
    207     SetProperties(UnionProperties(props1, props2, true), kCopyProperties);
    208   }
    209 
    210   // Implementation of Concat(Fst &, RationalFst *)
    211   void AddConcat(const Fst<A> &fst, bool append) {
    212     if (replace_)
    213       delete replace_;
    214     uint64 props1 = FstImpl<A>::Properties();
    215     uint64 props2 = fst.Properties(kFstProperties, false);
    216     VectorFst<A> afst;
    217     afst.AddState();
    218     afst.AddState();
    219     afst.SetStart(0);
    220     afst.SetFinal(1, Weight::One());
    221     ++nonterminals_;
    222     afst.AddArc(0, A(0, -nonterminals_, Weight::One(), 1));
    223     if (append)
    224       Concat(&rfst_, afst);
    225     else
    226       Concat(afst, &rfst_);
    227     fst_tuples_.push_back(make_pair(-nonterminals_, fst.Copy()));
    228     SetProperties(ConcatProperties(props1, props2, true), kCopyProperties);
    229   }
    230 
    231   // Implementation of Closure(RationalFst *, closure_type)
    232   void AddClosure(ClosureType closure_type) {
    233     if (replace_)
    234       delete replace_;
    235     uint64 props = FstImpl<A>::Properties();
    236     Closure(&rfst_, closure_type);
    237     SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR, true),
    238                   kCopyProperties);
    239   }
    240 
    241   // Returns the underlying ReplaceFst.
    242   ReplaceFst<A> *Replace() const {
    243     if (!replace_) {
    244       fst_tuples_[0].second = rfst_.Copy();
    245       replace_ = new ReplaceFst<A>(fst_tuples_, replace_options_);
    246     }
    247     return replace_;
    248   }
    249 
    250  private:
    251   VectorFst<A> rfst_;   // rational topology machine; uses neg. nonterminals
    252   Label nonterminals_;  // # of nonterminals used
    253   // Contains the nonterminals and their corresponding FSTs.
    254   mutable vector<pair<Label, const Fst<A>*> > fst_tuples_;
    255   mutable ReplaceFst<A> *replace_;        // Underlying ReplaceFst
    256   ReplaceFstOptions<A> replace_options_;  // Options for creating 'replace_'
    257 
    258   void operator=(const RationalFstImpl<A> &impl);    // disallow
    259 };
    260 
    261 // Parent class for the delayed rational operations - delayed union,
    262 // concatenation, and closure.
    263 //
    264 // This class attaches interface to implementation and handles
    265 // reference counting, delegating most methods to ImplToFst.
    266 template <class A>
    267 class RationalFst : public ImplToFst< RationalFstImpl<A> > {
    268  public:
    269   friend class StateIterator< RationalFst<A> >;
    270   friend class ArcIterator< RationalFst<A> >;
    271   friend void Union<>(RationalFst<A> *fst1, const Fst<A> &fst2);
    272   friend void Concat<>(RationalFst<A> *fst1, const Fst<A> &fst2);
    273   friend void Concat<>(const Fst<A> &fst1, RationalFst<A> *fst2);
    274   friend void Closure<>(RationalFst<A> *fst, ClosureType closure_type);
    275 
    276   typedef A Arc;
    277   typedef typename A::StateId StateId;
    278   typedef RationalFstImpl<A> Impl;
    279 
    280   virtual void InitStateIterator(StateIteratorData<A> *data) const {
    281     GetImpl()->Replace()->InitStateIterator(data);
    282   }
    283 
    284   virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const {
    285     GetImpl()->Replace()->InitArcIterator(s, data);
    286   }
    287 
    288  protected:
    289   RationalFst()
    290       : ImplToFst<Impl>(new Impl(RationalFstOptions())) {}
    291 
    292   explicit RationalFst(const RationalFstOptions &opts)
    293       : ImplToFst<Impl>(new Impl(opts)) {}
    294 
    295   // See Fst<>::Copy() for doc.
    296   RationalFst(const RationalFst<A> &fst , bool safe = false)
    297       : ImplToFst<Impl>(fst, safe) {}
    298 
    299  private:
    300   // Makes visible to friends.
    301   Impl *GetImpl() const { return ImplToFst<Impl>::GetImpl(); }
    302 
    303   void operator=(const RationalFst<A> &fst);  // disallow
    304 };
    305 
    306 
    307 // Specialization for RationalFst.
    308 template <class A>
    309 class StateIterator< RationalFst<A> >
    310     : public StateIterator< ReplaceFst<A> > {
    311  public:
    312   explicit StateIterator(const RationalFst<A> &fst)
    313       : StateIterator< ReplaceFst<A> >(*(fst.GetImpl()->Replace())) {}
    314 };
    315 
    316 
    317 // Specialization for RationalFst.
    318 template <class A>
    319 class ArcIterator< RationalFst<A> >
    320     : public CacheArcIterator< ReplaceFst<A> > {
    321  public:
    322   typedef typename A::StateId StateId;
    323 
    324   ArcIterator(const RationalFst<A> &fst, StateId s)
    325       : ArcIterator< ReplaceFst<A> >(*(fst.GetImpl()->Replace()), s) {}
    326 };
    327 
    328 }  // namespace fst
    329 
    330 #endif  // FST_LIB_RATIONAL_H__
    331