Home | History | Annotate | Download | only in lib 
      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 //
     16 // \file
     17 // An Fst implementation and base interface for delayed unions,
     18 // concatenations and closures.
     19 
     20 #ifndef FST_LIB_RATIONAL_H__
     21 #define FST_LIB_RATIONAL_H__
     22 
     23 #include "fst/lib/map.h"
     24 #include "fst/lib/mutable-fst.h"
     25 #include "fst/lib/replace.h"
     26 #include "fst/lib/test-properties.h"
     27 
     28 namespace fst {
     29 
     30 typedef CacheOptions RationalFstOptions;
     31 
     32 // This specifies whether to add the empty string.
     33 enum ClosureType { CLOSURE_STAR = 0,    // T* -> add the empty string
     34                    CLOSURE_PLUS = 1 };  // T+ -> don't add the empty string
     35 
     36 template <class A> class RationalFst;
     37 template <class A> void Union(RationalFst<A> *fst1, const Fst<A> &fst2);
     38 template <class A> void Concat(RationalFst<A> *fst1, const Fst<A> &fst2);
     39 template <class A> void Closure(RationalFst<A> *fst, ClosureType closure_type);
     40 
     41 
     42 // Implementation class for delayed unions, concatenations and closures.
     43 template<class A>
     44 class RationalFstImpl : public ReplaceFstImpl<A> {
     45  public:
     46   using FstImpl<A>::SetType;
     47   using FstImpl<A>::SetProperties;
     48   using FstImpl<A>::Properties;
     49   using FstImpl<A>::SetInputSymbols;
     50   using FstImpl<A>::SetOutputSymbols;
     51   using ReplaceFstImpl<A>::SetRoot;
     52 
     53   typedef typename A::Weight Weight;
     54   typedef typename A::Label Label;
     55 
     56   explicit RationalFstImpl(const RationalFstOptions &opts)
     57       : ReplaceFstImpl<A>(ReplaceFstOptions(opts, kNoLabel)),
     58         nonterminals_(0) {
     59     SetType("rational");
     60   }
     61 
     62   // Implementation of UnionFst(fst1,fst2)
     63   void InitUnion(const Fst<A> &fst1, const Fst<A> &fst2) {
     64     uint64 props1 = fst1.Properties(kFstProperties, false);
     65     uint64 props2 = fst2.Properties(kFstProperties, false);
     66     SetInputSymbols(fst1.InputSymbols());
     67     SetOutputSymbols(fst1.OutputSymbols());
     68     rfst_.AddState();
     69     rfst_.AddState();
     70     rfst_.SetStart(0);
     71     rfst_.SetFinal(1, Weight::One());
     72     rfst_.SetInputSymbols(fst1.InputSymbols());
     73     rfst_.SetOutputSymbols(fst1.OutputSymbols());
     74     nonterminals_ = 2;
     75     rfst_.AddArc(0, A(0, -1, Weight::One(), 1));
     76     rfst_.AddArc(0, A(0, -2, Weight::One(), 1));
     77     AddFst(0, &rfst_);
     78     AddFst(-1, &fst1);
     79     AddFst(-2, &fst2);
     80     SetRoot(0);
     81     SetProperties(UnionProperties(props1, props2, true), kCopyProperties);
     82   }
     83 
     84   // Implementation of ConcatFst(fst1,fst2)
     85   void InitConcat(const Fst<A> &fst1, const Fst<A> &fst2) {
     86     uint64 props1 = fst1.Properties(kFstProperties, false);
     87     uint64 props2 = fst2.Properties(kFstProperties, false);
     88     SetInputSymbols(fst1.InputSymbols());
     89     SetOutputSymbols(fst1.OutputSymbols());
     90     rfst_.AddState();
     91     rfst_.AddState();
     92     rfst_.AddState();
     93     rfst_.SetStart(0);
     94     rfst_.SetFinal(2, Weight::One());
     95     rfst_.SetInputSymbols(fst1.InputSymbols());
     96     rfst_.SetOutputSymbols(fst1.OutputSymbols());
     97     nonterminals_ = 2;
     98     rfst_.AddArc(0, A(0, -1, Weight::One(), 1));
     99     rfst_.AddArc(1, A(0, -2, Weight::One(), 2));
    100     AddFst(0, &rfst_);
    101     AddFst(-1, &fst1);
    102     AddFst(-2, &fst2);
    103     SetRoot(0);
    104     SetProperties(ConcatProperties(props1, props2, true), kCopyProperties);
    105   }
    106 
    107   // Implementation of ClosureFst(fst, closure_type)
    108   void InitClosure(const Fst<A> &fst, ClosureType closure_type) {
    109     uint64 props = fst.Properties(kFstProperties, false);
    110     SetInputSymbols(fst.InputSymbols());
    111     SetOutputSymbols(fst.OutputSymbols());
    112     if (closure_type == CLOSURE_STAR) {
    113       rfst_.AddState();
    114       rfst_.SetStart(0);
    115       rfst_.SetFinal(0, Weight::One());
    116       rfst_.AddArc(0, A(0, -1, Weight::One(), 0));
    117     } else {
    118       rfst_.AddState();
    119       rfst_.AddState();
    120       rfst_.SetStart(0);
    121       rfst_.SetFinal(1, Weight::One());
    122       rfst_.AddArc(0, A(0, -1, Weight::One(), 1));
    123       rfst_.AddArc(1, A(0, 0, Weight::One(), 0));
    124     }
    125     rfst_.SetInputSymbols(fst.InputSymbols());
    126     rfst_.SetOutputSymbols(fst.OutputSymbols());
    127     AddFst(0, &rfst_);
    128     AddFst(-1, &fst);
    129     SetRoot(0);
    130     nonterminals_ = 1;
    131     SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR, true),
    132                   kCopyProperties);
    133   }
    134 
    135   // Implementation of Union(Fst &, RationalFst *)
    136   void AddUnion(const Fst<A> &fst) {
    137     uint64 props1 = Properties();
    138     uint64 props2 = fst.Properties(kFstProperties, false);
    139     VectorFst<A> afst;
    140     afst.AddState();
    141     afst.AddState();
    142     afst.SetStart(0);
    143     afst.SetFinal(1, Weight::One());
    144     afst.AddArc(0, A(0, -nonterminals_, Weight::One(), 1));
    145     Union(&rfst_, afst);
    146     SetFst(0, &rfst_);
    147     ++nonterminals_;
    148     SetProperties(UnionProperties(props1, props2, true), kCopyProperties);
    149   }
    150 
    151   // Implementation of Concat(Fst &, RationalFst *)
    152   void AddConcat(const Fst<A> &fst) {
    153     uint64 props1 = Properties();
    154     uint64 props2 = fst.Properties(kFstProperties, false);
    155     VectorFst<A> afst;
    156     afst.AddState();
    157     afst.AddState();
    158     afst.SetStart(0);
    159     afst.SetFinal(1, Weight::One());
    160     afst.AddArc(0, A(0, -nonterminals_, Weight::One(), 1));
    161     Concat(&rfst_, afst);
    162     SetFst(0, &rfst_);
    163     ++nonterminals_;
    164     SetProperties(ConcatProperties(props1, props2, true), kCopyProperties);
    165   }
    166 
    167   // Implementation of Closure(RationalFst *, closure_type)
    168   void AddClosure(ClosureType closure_type) {
    169     uint64 props = Properties();
    170     Closure(&rfst_, closure_type);
    171     SetFst(0, &rfst_);
    172     SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR, true),
    173                   kCopyProperties);
    174   }
    175 
    176  private:
    177   VectorFst<A> rfst_;   // rational topology machine; uses neg. nonterminals
    178   Label nonterminals_;  // # of nonterminals used
    179 
    180   DISALLOW_EVIL_CONSTRUCTORS(RationalFstImpl);
    181 };
    182 
    183 // Parent class for the delayed rational operations - delayed union,
    184 // concatenation, and closure.  This class attaches interface to
    185 // implementation and handles reference counting.
    186 template <class A>
    187 class RationalFst : public Fst<A> {
    188  public:
    189   friend class CacheStateIterator< RationalFst<A> >;
    190   friend class ArcIterator< RationalFst<A> >;
    191   friend class CacheArcIterator< RationalFst<A> >;
    192   friend void Union<>(RationalFst<A> *fst1, const Fst<A> &fst2);
    193   friend void Concat<>(RationalFst<A> *fst1, const Fst<A> &fst2);
    194   friend void Closure<>(RationalFst<A> *fst, ClosureType closure_type);
    195 
    196   typedef A Arc;
    197   typedef typename A::Weight Weight;
    198   typedef typename A::StateId StateId;
    199   typedef CacheState<A> State;
    200 
    201   virtual StateId Start() const { return impl_->Start(); }
    202   virtual Weight Final(StateId s) const { return impl_->Final(s); }
    203   virtual size_t NumArcs(StateId s) const { return impl_->NumArcs(s); }
    204   virtual size_t NumInputEpsilons(StateId s) const {
    205     return impl_->NumInputEpsilons(s);
    206   }
    207   virtual size_t NumOutputEpsilons(StateId s) const {
    208     return impl_->NumOutputEpsilons(s);
    209   }
    210   virtual uint64 Properties(uint64 mask, bool test) const {
    211     if (test) {
    212       uint64 known, test = TestProperties(*this, mask, &known);
    213       impl_->SetProperties(test, known);
    214       return test & mask;
    215     } else {
    216       return impl_->Properties(mask);
    217     }
    218   }
    219   virtual const string& Type() const { return impl_->Type(); }
    220   virtual const SymbolTable* InputSymbols() const {
    221     return impl_->InputSymbols();
    222   }
    223   virtual const SymbolTable* OutputSymbols() const {
    224     return impl_->OutputSymbols();
    225   }
    226 
    227   virtual inline void InitStateIterator(StateIteratorData<A> *data) const;
    228 
    229   virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const {
    230     impl_->InitArcIterator(s, data);
    231   }
    232 
    233  protected:
    234   RationalFst() : impl_(new RationalFstImpl<A>(RationalFstOptions())) {}
    235   explicit RationalFst(const RationalFstOptions &opts)
    236       : impl_(new RationalFstImpl<A>(opts)) {}
    237 
    238 
    239   RationalFst(const RationalFst<A> &fst) : impl_(fst.impl_) {
    240     impl_->IncrRefCount();
    241   }
    242 
    243   virtual ~RationalFst() { if (!impl_->DecrRefCount()) delete impl_; }
    244 
    245   RationalFstImpl<A> *Impl() { return impl_; }
    246 
    247  private:
    248   RationalFstImpl<A> *impl_;
    249 
    250   void operator=(const RationalFst<A> &fst);  // disallow
    251 };
    252 
    253 // Specialization for RationalFst.
    254 template <class A>
    255 class StateIterator< RationalFst<A> >
    256     : public CacheStateIterator< RationalFst<A> > {
    257  public:
    258   explicit StateIterator(const RationalFst<A> &fst)
    259       : CacheStateIterator< RationalFst<A> >(fst) {}
    260 };
    261 
    262 // Specialization for RationalFst.
    263 template <class A>
    264 class ArcIterator< RationalFst<A> >
    265     : public CacheArcIterator< RationalFst<A> > {
    266  public:
    267   typedef typename A::StateId StateId;
    268 
    269   ArcIterator(const RationalFst<A> &fst, StateId s)
    270       : CacheArcIterator< RationalFst<A> >(fst, s) {
    271     if (!fst.impl_->HasArcs(s))
    272       fst.impl_->Expand(s);
    273   }
    274 
    275  private:
    276   DISALLOW_EVIL_CONSTRUCTORS(ArcIterator);
    277 };
    278 
    279 template <class A> inline
    280 void RationalFst<A>::InitStateIterator(StateIteratorData<A> *data) const {
    281   data->base = new StateIterator< RationalFst<A> >(*this);
    282 }
    283 
    284 }  // namespace fst
    285 
    286 #endif  // FST_LIB_RATIONAL_H__
    287