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 // Copyright 2005-2010 Google, Inc. 16 // Author: riley (at) google.com (Michael Riley) 17 // 18 // \file 19 // Class to compute the difference between two FSAs 20 21 #ifndef FST_LIB_DIFFERENCE_H__ 22 #define FST_LIB_DIFFERENCE_H__ 23 24 #include <vector> 25 using std::vector; 26 #include <algorithm> 27 28 #include <fst/cache.h> 29 #include <fst/compose.h> 30 #include <fst/complement.h> 31 32 33 namespace fst { 34 35 template <class A, 36 class M = Matcher<Fst<A> >, 37 class F = SequenceComposeFilter<M>, 38 class T = GenericComposeStateTable<A, typename F::FilterState> > 39 struct DifferenceFstOptions : public ComposeFstOptions<A, M, F, T> { 40 explicit DifferenceFstOptions(const CacheOptions &opts, 41 M *mat1 = 0, M *mat2 = 0, 42 F *filt = 0, T *sttable= 0) 43 : ComposeFstOptions<A, M, F, T>(mat1, mat2, filt, sttable) { } 44 45 DifferenceFstOptions() {} 46 }; 47 48 // Computes the difference between two FSAs. This version is a delayed 49 // Fst. Only strings that are in the first automaton but not in second 50 // are retained in the result. 51 // 52 // The first argument must be an acceptor; the second argument must be 53 // an unweighted, epsilon-free, deterministic acceptor. One of the 54 // arguments must be label-sorted. 55 // 56 // Complexity: same as ComposeFst. 57 // 58 // Caveats: same as ComposeFst. 59 template <class A> 60 class DifferenceFst : public ComposeFst<A> { 61 public: 62 using ImplToFst< ComposeFstImplBase<A> >::SetImpl; 63 using ImplToFst< ComposeFstImplBase<A> >::GetImpl; 64 65 using ComposeFst<A>::CreateBase1; 66 67 typedef A Arc; 68 typedef typename A::Weight Weight; 69 typedef typename A::StateId StateId; 70 71 // A - B = A ^ B'. 72 DifferenceFst(const Fst<A> &fst1, const Fst<A> &fst2, 73 const CacheOptions &opts = CacheOptions()) { 74 typedef RhoMatcher< Matcher<Fst<A> > > R; 75 76 ComplementFst<A> cfst(fst2); 77 ComposeFstOptions<A, R> copts(CacheOptions(), 78 new R(fst1, MATCH_NONE), 79 new R(cfst, MATCH_INPUT, 80 ComplementFst<A>::kRhoLabel)); 81 SetImpl(CreateBase1(fst1, cfst, copts)); 82 83 if (!fst1.Properties(kAcceptor, true)) { 84 FSTERROR() << "DifferenceFst: 1st argument not an acceptor"; 85 GetImpl()->SetProperties(kError, kError); 86 } 87 } 88 89 template <class M, class F, class T> 90 DifferenceFst(const Fst<A> &fst1, const Fst<A> &fst2, 91 const DifferenceFstOptions<A, M, F, T> &opts) { 92 typedef RhoMatcher<M> R; 93 94 ComplementFst<A> cfst(fst2); 95 ComposeFstOptions<A, R> copts(opts); 96 copts.matcher1 = new R(fst1, MATCH_NONE, kNoLabel, MATCHER_REWRITE_ALWAYS, 97 opts.matcher1); 98 copts.matcher2 = new R(cfst, MATCH_INPUT, ComplementFst<A>::kRhoLabel, 99 MATCHER_REWRITE_ALWAYS, opts.matcher2); 100 101 SetImpl(CreateBase1(fst1, cfst, copts)); 102 103 if (!fst1.Properties(kAcceptor, true)) { 104 FSTERROR() << "DifferenceFst: 1st argument not an acceptor"; 105 GetImpl()->SetProperties(kError, kError); 106 } 107 } 108 109 // See Fst<>::Copy() for doc. 110 DifferenceFst(const DifferenceFst<A> &fst, bool safe = false) 111 : ComposeFst<A>(fst, safe) {} 112 113 // Get a copy of this DifferenceFst. See Fst<>::Copy() for further doc. 114 virtual DifferenceFst<A> *Copy(bool safe = false) const { 115 return new DifferenceFst<A>(*this, safe); 116 } 117 }; 118 119 120 // Specialization for DifferenceFst. 121 template <class A> 122 class StateIterator< DifferenceFst<A> > 123 : public StateIterator< ComposeFst<A> > { 124 public: 125 explicit StateIterator(const DifferenceFst<A> &fst) 126 : StateIterator< ComposeFst<A> >(fst) {} 127 }; 128 129 130 // Specialization for DifferenceFst. 131 template <class A> 132 class ArcIterator< DifferenceFst<A> > 133 : public ArcIterator< ComposeFst<A> > { 134 public: 135 typedef typename A::StateId StateId; 136 137 ArcIterator(const DifferenceFst<A> &fst, StateId s) 138 : ArcIterator< ComposeFst<A> >(fst, s) {} 139 }; 140 141 // Useful alias when using StdArc. 142 typedef DifferenceFst<StdArc> StdDifferenceFst; 143 144 145 typedef ComposeOptions DifferenceOptions; 146 147 148 // Computes the difference between two FSAs. This version is writes 149 // the difference to an output MutableFst. Only strings that are in 150 // the first automaton but not in second are retained in the result. 151 // 152 // The first argument must be an acceptor; the second argument must be 153 // an unweighted, epsilon-free, deterministic acceptor. One of the 154 // arguments must be label-sorted. 155 // 156 // Complexity: same as Compose. 157 // 158 // Caveats: same as Compose. 159 template<class Arc> 160 void Difference(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2, 161 MutableFst<Arc> *ofst, 162 const DifferenceOptions &opts = DifferenceOptions()) { 163 typedef Matcher< Fst<Arc> > M; 164 165 if (opts.filter_type == AUTO_FILTER) { 166 CacheOptions nopts; 167 nopts.gc_limit = 0; // Cache only the last state for fastest copy. 168 *ofst = DifferenceFst<Arc>(ifst1, ifst2, nopts); 169 } else if (opts.filter_type == SEQUENCE_FILTER) { 170 DifferenceFstOptions<Arc> dopts; 171 dopts.gc_limit = 0; // Cache only the last state for fastest copy. 172 *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts); 173 } else if (opts.filter_type == ALT_SEQUENCE_FILTER) { 174 DifferenceFstOptions<Arc, M, AltSequenceComposeFilter<M> > dopts; 175 dopts.gc_limit = 0; // Cache only the last state for fastest copy. 176 *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts); 177 } else if (opts.filter_type == MATCH_FILTER) { 178 DifferenceFstOptions<Arc, M, MatchComposeFilter<M> > dopts; 179 dopts.gc_limit = 0; // Cache only the last state for fastest copy. 180 *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts); 181 } 182 183 if (opts.connect) 184 Connect(ofst); 185 } 186 187 } // namespace fst 188 189 #endif // FST_LIB_DIFFERENCE_H__ 190
