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