Home | History | Annotate | Download | only in lib 
      1 // concat.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 concat of two FSTs.
     18 
     19 #ifndef FST_LIB_CONCAT_H__
     20 #define FST_LIB_CONCAT_H__
     21 
     22 #include <algorithm>
     23 
     24 #include "fst/lib/mutable-fst.h"
     25 #include "fst/lib/rational.h"
     26 
     27 namespace fst {
     28 
     29 // Computes the concatenation (product) of two FSTs; this version
     30 // modifies its MutableFst argument.  If FST1 transduces string x to y
     31 // with weight a and FST2 transduces string w to v with weight b, then
     32 // their concatenation transduces string xw to yv with Times(a, b).
     33 //
     34 // Complexity:
     35 // - Time: O(V1 + V2 + E2)
     36 // - Space: O(V1 + V2 + E2)
     37 // where Vi = # of states and Ei = # of arcs of the ith FST.
     38 template<class Arc>
     39 void Concat(MutableFst<Arc> *fst1, const Fst<Arc> &fst2) {
     40   typedef typename Arc::StateId StateId;
     41   typedef typename Arc::Label Label;
     42   typedef typename Arc::Weight Weight;
     43 
     44   StateId start1 = fst1->Start();
     45   if (start1 == kNoStateId)
     46     return;
     47 
     48   uint64 props1 = fst1->Properties(kFstProperties, false);
     49   uint64 props2 = fst2.Properties(kFstProperties, false);
     50 
     51   StateId numstates1= fst1->NumStates();
     52 
     53   for (StateIterator< Fst<Arc> > siter2(fst2);
     54        !siter2.Done();
     55        siter2.Next()) {
     56     StateId s1 = fst1->AddState();
     57     StateId s2 = siter2.Value();
     58     fst1->SetFinal(s1, fst2.Final(s2));
     59     for (ArcIterator< Fst<Arc> > aiter(fst2, s2);
     60          !aiter.Done();
     61          aiter.Next()) {
     62       Arc arc = aiter.Value();
     63       arc.nextstate += numstates1;
     64       fst1->AddArc(s1, arc);
     65     }
     66   }
     67 
     68   StateId start2 = fst2.Start();
     69   for (StateId s1 = 0; s1 < numstates1; ++s1) {
     70     Weight final = fst1->Final(s1);
     71     if (final != Weight::Zero()) {
     72       fst1->SetFinal(s1, Weight::Zero());
     73       if (start2 != kNoStateId)
     74         fst1->AddArc(s1, Arc(0, 0, final, start2 + numstates1));
     75     }
     76   }
     77   if (start2 != kNoStateId)
     78     fst1->SetProperties(ConcatProperties(props1, props2), kFstProperties);
     79 }
     80 
     81 
     82 // Computes the concatentation of two FSTs. This version modifies its
     83 // RationalFst input.
     84 template<class Arc>
     85 void Concat(RationalFst<Arc> *fst1, const Fst<Arc> &fst2) {
     86   fst1->Impl()->AddConcat(fst2);
     87 }
     88 
     89 
     90 typedef RationalFstOptions ConcatFstOptions;
     91 
     92 
     93 // Computes the concatenation (product) of two FSTs; this version is a
     94 // delayed Fst. If FST1 transduces string x to y with weight a and FST2
     95 // transduces string w to v with weight b, then their concatenation
     96 // transduces string xw to yv with Times(a, b).
     97 //
     98 // Complexity:
     99 // - Time: O(v1 + e1 + v2 + e2),
    100 // - Space: O(v1 + v2)
    101 // where vi = # of states visited and ei = # of arcs visited of the
    102 // ith FST. Constant time and space to visit an input state or arc is
    103 // assumed and exclusive of caching.
    104 template <class A>
    105 class ConcatFst : public RationalFst<A> {
    106  public:
    107   using RationalFst<A>::Impl;
    108 
    109   typedef A Arc;
    110   typedef typename A::Weight Weight;
    111   typedef typename A::StateId StateId;
    112 
    113   ConcatFst(const Fst<A> &fst1, const Fst<A> &fst2) {
    114     Impl()->InitConcat(fst1, fst2);
    115   }
    116 
    117   ConcatFst(const Fst<A> &fst1, const Fst<A> &fst2,
    118             const ConcatFstOptions &opts) : RationalFst<A>(opts) {
    119     Impl()->InitConcat(fst1, fst2);
    120   }
    121 
    122   ConcatFst(const ConcatFst<A> &fst) : RationalFst<A>(fst) {}
    123 
    124   virtual ConcatFst<A> *Copy() const { return new ConcatFst<A>(*this); }
    125 };
    126 
    127 
    128 // Specialization for ConcatFst.
    129 template <class A>
    130 class StateIterator< ConcatFst<A> > : public StateIterator< RationalFst<A> > {
    131  public:
    132   explicit StateIterator(const ConcatFst<A> &fst)
    133       : StateIterator< RationalFst<A> >(fst) {}
    134 };
    135 
    136 
    137 // Specialization for ConcatFst.
    138 template <class A>
    139 class ArcIterator< ConcatFst<A> > : public ArcIterator< RationalFst<A> > {
    140  public:
    141   typedef typename A::StateId StateId;
    142 
    143   ArcIterator(const ConcatFst<A> &fst, StateId s)
    144       : ArcIterator< RationalFst<A> >(fst, s) {}
    145 };
    146 
    147 
    148 // Useful alias when using StdArc.
    149 typedef ConcatFst<StdArc> StdConcatFst;
    150 
    151 }  // namespace fst
    152 
    153 #endif  // FST_LIB_CONCAT_H__
    154