Home | History | Annotate | Download | only in lib 
      1 // intersect.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 // Class to compute the intersection of two FSAs
     18 
     19 #ifndef FST_LIB_INTERSECT_H__
     20 #define FST_LIB_INTERSECT_H__
     21 
     22 #include "fst/lib/compose.h"
     23 
     24 namespace fst {
     25 
     26 template <uint64 T = 0>
     27 struct IntersectFstOptions : public ComposeFstOptions<T> { };
     28 
     29 
     30 // Computes the intersection (Hadamard product) of two FSAs. This
     31 // version is a delayed Fst.  Only strings that are in both automata
     32 // are retained in the result.
     33 //
     34 // The two arguments must be acceptors. One of the arguments must be
     35 // label-sorted.
     36 //
     37 // Complexity: same as ComposeFst.
     38 //
     39 // Caveats:  same as ComposeFst.
     40 template <class A>
     41 class IntersectFst : public ComposeFst<A> {
     42  public:
     43   using ComposeFst<A>::Impl;
     44 
     45   typedef A Arc;
     46   typedef typename A::Weight Weight;
     47   typedef typename A::StateId StateId;
     48 
     49   IntersectFst(const Fst<A> &fst1, const Fst<A> &fst2)
     50       : ComposeFst<A>(fst1, fst2) {
     51     if (!fst1.Properties(kAcceptor, true) || !fst2.Properties(kAcceptor, true))
     52       LOG(FATAL) << "IntersectFst: arguments not both acceptors";
     53     uint64 props1 = fst1.Properties(kFstProperties, false);
     54     uint64 props2 = fst2.Properties(kFstProperties, false);
     55     Impl()->SetProperties(IntersectProperties(props1, props2),
     56                           kCopyProperties);
     57   }
     58 
     59   template <uint64 T>
     60   IntersectFst(const Fst<A> &fst1, const Fst<A> &fst2,
     61                const IntersectFstOptions<T> &opts)
     62       : ComposeFst<A>(fst1, fst2, ComposeFstOptions<T>(opts)) {
     63     if (!fst1.Properties(kAcceptor, true) || !fst2.Properties(kAcceptor, true))
     64       LOG(FATAL) << "IntersectFst: arguments not both acceptors";
     65     uint64 props1 = fst1.Properties(kFstProperties, false);
     66     uint64 props2 = fst2.Properties(kFstProperties, false);
     67     Impl()->SetProperties(IntersectProperties(props1, props2),
     68                           kCopyProperties);
     69   }
     70 
     71   IntersectFst(const IntersectFst<A> &fst) : ComposeFst<A>(fst) {}
     72 
     73   virtual IntersectFst<A> *Copy() const {
     74     return new IntersectFst<A>(*this);
     75   }
     76 };
     77 
     78 
     79 // Specialization for IntersectFst.
     80 template <class A>
     81 class StateIterator< IntersectFst<A> >
     82     : public StateIterator< ComposeFst<A> > {
     83  public:
     84   explicit StateIterator(const IntersectFst<A> &fst)
     85       : StateIterator< ComposeFst<A> >(fst) {}
     86 };
     87 
     88 
     89 // Specialization for IntersectFst.
     90 template <class A>
     91 class ArcIterator< IntersectFst<A> >
     92     : public ArcIterator< ComposeFst<A> > {
     93  public:
     94   typedef typename A::StateId StateId;
     95 
     96   ArcIterator(const IntersectFst<A> &fst, StateId s)
     97       : ArcIterator< ComposeFst<A> >(fst, s) {}
     98 };
     99 
    100 // Useful alias when using StdArc.
    101 typedef IntersectFst<StdArc> StdIntersectFst;
    102 
    103 
    104 typedef ComposeOptions IntersectOptions;
    105 
    106 
    107 // Computes the intersection (Hadamard product) of two FSAs. This
    108 // version writes the intersection to an output MurableFst. Only
    109 // strings that are in both automata are retained in the result.
    110 //
    111 // The two arguments must be acceptors. One of the arguments must be
    112 // label-sorted.
    113 //
    114 // Complexity: same as Compose.
    115 //
    116 // Caveats:  same as Compose.
    117 template<class Arc>
    118 void Intersect(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
    119              MutableFst<Arc> *ofst,
    120              const IntersectOptions &opts = IntersectOptions()) {
    121   IntersectFstOptions<> nopts;
    122   nopts.gc_limit = 0;  // Cache only the last state for fastest copy.
    123   *ofst = IntersectFst<Arc>(ifst1, ifst2, nopts);
    124   if (opts.connect)
    125     Connect(ofst);
    126 }
    127 
    128 }  // namespace fst
    129 
    130 #endif  // FST_LIB_INTERSECT_H__
    131