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 // 16 // \file 17 // Class to compute the difference between two FSAs 18 19 #ifndef FST_LIB_DIFFERENCE_H__ 20 #define FST_LIB_DIFFERENCE_H__ 21 22 #include "fst/lib/compose.h" 23 #include "fst/lib/complement.h" 24 25 namespace fst { 26 27 template <uint64 T = 0> 28 struct DifferenceFstOptions 29 : public ComposeFstOptions<T | COMPOSE_FST2_RHO> { }; 30 31 32 // Computes the difference between two FSAs. This version is a delayed 33 // Fst. Only strings that are in the first automaton but not in second 34 // are retained in the result. 35 // 36 // The first argument must be an acceptor; the second argument must be 37 // an unweighted, epsilon-free, deterministic acceptor. One of the 38 // arguments must be label-sorted. 39 // 40 // Complexity: same as ComposeFst. 41 // 42 // Caveats: same as ComposeFst. 43 template <class A> 44 class DifferenceFst : public ComposeFst<A> { 45 public: 46 using ComposeFst<A>::Impl; 47 48 typedef A Arc; 49 typedef typename A::Weight Weight; 50 typedef typename A::StateId StateId; 51 52 // A - B = A ^ B'. DifferenceFst(const Fst<A> & fst1,const Fst<A> & fst2)53 DifferenceFst(const Fst<A> &fst1, const Fst<A> &fst2) 54 : ComposeFst<A>(fst1, 55 ComplementFst<A>(fst2), 56 ComposeFstOptions<COMPOSE_FST2_RHO>()) { 57 if (!fst1.Properties(kAcceptor, true)) 58 LOG(FATAL) << "DifferenceFst: 1st argument not an acceptor"; 59 uint64 props1 = fst1.Properties(kFstProperties, false); 60 uint64 props2 = fst2.Properties(kFstProperties, false); 61 Impl()->SetProperties(DifferenceProperties(props1, props2), 62 kCopyProperties); 63 } 64 65 template <uint64 T> DifferenceFst(const Fst<A> & fst1,const Fst<A> & fst2,const DifferenceFstOptions<T> & opts)66 DifferenceFst(const Fst<A> &fst1, const Fst<A> &fst2, 67 const DifferenceFstOptions<T> &opts) 68 : ComposeFst<A>(fst1, 69 ComplementFst<A>(fst2), 70 ComposeFstOptions<T | COMPOSE_FST2_RHO>(opts)) { 71 if (!fst1.Properties(kAcceptor, true)) 72 LOG(FATAL) << "DifferenceFst: 1st argument not an acceptor"; 73 uint64 props1 = fst1.Properties(kFstProperties, false); 74 uint64 props2 = fst2.Properties(kFstProperties, false); 75 Impl()->SetProperties(DifferenceProperties(props1, props2), 76 kCopyProperties); 77 } 78 DifferenceFst(const DifferenceFst<A> & fst)79 DifferenceFst(const DifferenceFst<A> &fst) 80 : ComposeFst<A>(fst) {} 81 Copy()82 virtual DifferenceFst<A> *Copy() const { 83 return new DifferenceFst<A>(*this); 84 } 85 }; 86 87 88 // Specialization for DifferenceFst. 89 template <class A> 90 class StateIterator< DifferenceFst<A> > 91 : public StateIterator< ComposeFst<A> > { 92 public: StateIterator(const DifferenceFst<A> & fst)93 explicit StateIterator(const DifferenceFst<A> &fst) 94 : StateIterator< ComposeFst<A> >(fst) {} 95 }; 96 97 98 // Specialization for DifferenceFst. 99 template <class A> 100 class ArcIterator< DifferenceFst<A> > 101 : public ArcIterator< ComposeFst<A> > { 102 public: 103 typedef typename A::StateId StateId; 104 ArcIterator(const DifferenceFst<A> & fst,StateId s)105 ArcIterator(const DifferenceFst<A> &fst, StateId s) 106 : ArcIterator< ComposeFst<A> >(fst, s) {} 107 }; 108 109 // Useful alias when using StdArc. 110 typedef DifferenceFst<StdArc> StdDifferenceFst; 111 112 113 typedef ComposeOptions DifferenceOptions; 114 115 116 // Computes the difference between two FSAs. This version is writes 117 // the difference to an output MutableFst. Only strings that are in 118 // the first automaton but not in second are retained in the result. 119 // 120 // The first argument must be an acceptor; the second argument must be 121 // an unweighted, epsilon-free, deterministic acceptor. One of the 122 // arguments must be label-sorted. 123 // 124 // Complexity: same as Compose. 125 // 126 // Caveats: same as Compose. 127 template<class Arc> 128 void Difference(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2, 129 MutableFst<Arc> *ofst, 130 const DifferenceOptions &opts = DifferenceOptions()) { 131 DifferenceFstOptions<> nopts; 132 nopts.gc_limit = 0; // Cache only the last state for fastest copy. 133 *ofst = DifferenceFst<Arc>(ifst1, ifst2, nopts); 134 if (opts.connect) 135 Connect(ofst); 136 } 137 138 } // namespace fst 139 140 #endif // FST_LIB_DIFFERENCE_H__ 141