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@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> 25using std::vector; 26#include <algorithm> 27 28#include <fst/cache.h> 29#include <fst/compose.h> 30#include <fst/complement.h> 31 32 33namespace fst { 34 35template <class A, 36 class M = Matcher<Fst<A> >, 37 class F = SequenceComposeFilter<M>, 38 class T = GenericComposeStateTable<A, typename F::FilterState> > 39struct 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. 59template <class A> 60class 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. 121template <class A> 122class 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. 131template <class A> 132class 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. 142typedef DifferenceFst<StdArc> StdDifferenceFst; 143 144 145typedef 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. 159template<class Arc> 160void 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