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