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 25namespace fst { 26 27template <uint64 T = 0> 28struct 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. 43template <class A> 44class 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'. 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> 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 79 DifferenceFst(const DifferenceFst<A> &fst) 80 : ComposeFst<A>(fst) {} 81 82 virtual DifferenceFst<A> *Copy() const { 83 return new DifferenceFst<A>(*this); 84 } 85}; 86 87 88// Specialization for DifferenceFst. 89template <class A> 90class StateIterator< DifferenceFst<A> > 91 : public StateIterator< ComposeFst<A> > { 92 public: 93 explicit StateIterator(const DifferenceFst<A> &fst) 94 : StateIterator< ComposeFst<A> >(fst) {} 95}; 96 97 98// Specialization for DifferenceFst. 99template <class A> 100class ArcIterator< DifferenceFst<A> > 101 : public ArcIterator< ComposeFst<A> > { 102 public: 103 typedef typename A::StateId StateId; 104 105 ArcIterator(const DifferenceFst<A> &fst, StateId s) 106 : ArcIterator< ComposeFst<A> >(fst, s) {} 107}; 108 109// Useful alias when using StdArc. 110typedef DifferenceFst<StdArc> StdDifferenceFst; 111 112 113typedef 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. 127template<class Arc> 128void 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