openfst-1.2.6/src/include/fst/difference.h

Go to the documentation of this file.

///  difference.h

///  Licensed under the Apache License, Version 2.0 (the "License");
///  you may not use this file except in compliance with the License.
///  You may obtain a copy of the License at
/// 
///      http://www.apache.org/licenses/LICENSE-2.0
/// 
///  Unless required by applicable law or agreed to in writing, software
///  distributed under the License is distributed on an "AS IS" BASIS,
///  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
///  See the License for the specific language governing permissions and
///  limitations under the License.
/// 
///  Copyright 2005-2010 Google, Inc.
///  Author: riley@google.com (Michael Riley)
/// 
///  \file
///  Class to compute the difference between two FSAs

#ifndef FST_LIB_DIFFERENCE_H__
#define FST_LIB_DIFFERENCE_H__

#include <vector>
using std::vector;
#include <algorithm>
#include <fst/cache.h>
#include <fst/compose.h>
#include <fst/complement.h>

namespace fst {

template <class A,
          class M = Matcher<Fst<A> >,
          class F = SequenceComposeFilter<M>,
          class T = GenericComposeStateTable<A, typename F::FilterState> >
struct DifferenceFstOptions : public ComposeFstOptions<A, M, F, T> {
  explicit DifferenceFstOptions(const CacheOptions &opts,
                                M *mat1 = 0, M *mat2 = 0,
                                F *filt = 0, T *sttable= 0)
      : ComposeFstOptions<A, M, F, T>(mat1, mat2, filt, sttable) { }

  DifferenceFstOptions() {}
};

///  Computes the difference between two FSAs. This version is a delayed
///  Fst. Only strings that are in the first automaton but not in second
///  are retained in the result.
/// 
///  The first argument must be an acceptor; the second argument must be
///  an unweighted, epsilon-free, deterministic acceptor. One of the
///  arguments must be label-sorted.
/// 
///  Complexity: same as ComposeFst.
/// 
///  Caveats: same as ComposeFst.
template <class A>
class DifferenceFst : public ComposeFst<A> {
 public:
  using ImplToFst< ComposeFstImplBase<A> >::SetImpl;

  using ComposeFst<A>::CreateBase1;

  typedef A Arc;
  typedef typename A::Weight Weight;
  typedef typename A::StateId StateId;

  ///  A - B = A ^ B'.
  DifferenceFst(const Fst<A> &fst1, const Fst<A> &fst2,
                const CacheOptions &opts = CacheOptions()) {
    if (!fst1.Properties(kAcceptor, true))
      LOG(FATAL) << "DifferenceFst: 1st argument not an acceptor";

    typedef RhoMatcher< Matcher<Fst<A> > > R;

    ComplementFst<A> cfst(fst2);
    ComposeFstOptions<A, R> copts(CacheOptions(),
                                  new R(fst1, MATCH_NONE),
                                  new R(cfst, MATCH_INPUT,
                                        ComplementFst<A>::kRhoLabel));
    SetImpl(CreateBase1(fst1, cfst, copts));
 }

  template <class M, class F, class T>
  DifferenceFst(const Fst<A> &fst1, const Fst<A> &fst2,
                const DifferenceFstOptions<A, M, F, T> &opts) {
    if (!fst1.Properties(kAcceptor, true))
      LOG(FATAL) << "DifferenceFst: 1st argument not an acceptor";

    typedef RhoMatcher<M> R;

    ComplementFst<A> cfst(fst2);
    ComposeFstOptions<A, R> copts(opts);
    copts.matcher1 = new R(fst1, MATCH_NONE, kNoLabel, MATCHER_REWRITE_ALWAYS,
                           opts.matcher1);
    copts.matcher2 = new R(cfst, MATCH_INPUT, ComplementFst<A>::kRhoLabel,
                           MATCHER_REWRITE_ALWAYS, opts.matcher2);

    SetImpl(CreateBase1(fst1, cfst, copts));
  }

  ///  See Fst<>::Copy() for doc.
  DifferenceFst(const DifferenceFst<A> &fst, bool safe = false)
      : ComposeFst<A>(fst, safe) {}

  ///  Get a copy of this DifferenceFst. See Fst<>::Copy() for further doc.
  virtual DifferenceFst<A> *Copy(bool safe = false) const {
    return new DifferenceFst<A>(*this, safe);
  }
};


///  Specialization for DifferenceFst.
template <class A>
class StateIterator< DifferenceFst<A> >
    : public StateIterator< ComposeFst<A> > {
 public:
  explicit StateIterator(const DifferenceFst<A> &fst)
      : StateIterator< ComposeFst<A> >(fst) {}
};


///  Specialization for DifferenceFst.
template <class A>
class ArcIterator< DifferenceFst<A> >
    : public ArcIterator< ComposeFst<A> > {
 public:
  typedef typename A::StateId StateId;

  ArcIterator(const DifferenceFst<A> &fst, StateId s)
      : ArcIterator< ComposeFst<A> >(fst, s) {}
};

///  Useful alias when using StdArc.
typedef DifferenceFst<StdArc> StdDifferenceFst;


typedef ComposeOptions DifferenceOptions;


///  Computes the difference between two FSAs. This version is writes
///  the difference to an output MutableFst. Only strings that are in
///  the first automaton but not in second are retained in the result.
/// 
///  The first argument must be an acceptor; the second argument must be
///  an unweighted, epsilon-free, deterministic acceptor.  One of the
///  arguments must be label-sorted.
/// 
///  Complexity: same as Compose.
/// 
///  Caveats: same as Compose.
template<class Arc>
void Difference(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
             MutableFst<Arc> *ofst,
             const DifferenceOptions &opts = DifferenceOptions()) {
  typedef Matcher< Fst<Arc> > M;

  if (opts.filter_type == AUTO_FILTER) {
    CacheOptions nopts;
    nopts.gc_limit = 0; ///<  Cache only the last state for fastest copy.
    *ofst = DifferenceFst<Arc>(ifst1, ifst2, nopts);
  } else if (opts.filter_type == SEQUENCE_FILTER) {
    DifferenceFstOptions<Arc> dopts;
    dopts.gc_limit = 0; ///<  Cache only the last state for fastest copy.
    *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
  } else if (opts.filter_type == ALT_SEQUENCE_FILTER) {
    DifferenceFstOptions<Arc, M, AltSequenceComposeFilter<M> > dopts;
    dopts.gc_limit = 0; ///<  Cache only the last state for fastest copy.
    *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
  } else if (opts.filter_type == MATCH_FILTER) {
    DifferenceFstOptions<Arc, M, MatchComposeFilter<M> > dopts;
    dopts.gc_limit = 0; ///<  Cache only the last state for fastest copy.
    *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
  }

  if (opts.connect)
    Connect(ofst);
}

}  ///  namespace fst

#endif  ///  FST_LIB_DIFFERENCE_H__