add implementation for kaldi io (by ymz)

1 files changed, 189 insertions, 0 deletions

diff --git a/kaldi_io/src/tools/openfst/include/fst/difference.h b/kaldi_io/src/tools/openfst/include/fst/difference.h
new file mode 100644
index 0000000..8a3306f
--- /dev/null
+++ b/kaldi_io/src/tools/openfst/include/fst/difference.h
@@ -0,0 +1,189 @@
+// 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: [email protected] (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 ImplToFst< ComposeFstImplBase<A> >::GetImpl;
+
+  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()) {
+    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));
+
+    if (!fst1.Properties(kAcceptor, true)) {
+      FSTERROR() << "DifferenceFst: 1st argument not an acceptor";
+      GetImpl()->SetProperties(kError, kError);
+    }
+ }
+
+  template <class M, class F, class T>
+  DifferenceFst(const Fst<A> &fst1, const Fst<A> &fst2,
+                const DifferenceFstOptions<A, M, F, T> &opts) {
+    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));
+
+    if (!fst1.Properties(kAcceptor, true)) {
+      FSTERROR() << "DifferenceFst: 1st argument not an acceptor";
+      GetImpl()->SetProperties(kError, kError);
+    }
+  }
+
+  // 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__