| // 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__ |