diff options
Diffstat (limited to 'kaldi_io/src/tools/openfst/include/fst/difference.h')
| -rw-r--r-- | kaldi_io/src/tools/openfst/include/fst/difference.h | 189 |
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: 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 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__ |