14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// difference.h 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License"); 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License. 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// http://www.apache.org/licenses/LICENSE-2.0 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS, 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License. 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Class to compute the difference between two FSAs 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_DIFFERENCE_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_DIFFERENCE_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/compose.h" 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/complement.h" 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <uint64 T = 0> 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct DifferenceFstOptions 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public ComposeFstOptions<T | COMPOSE_FST2_RHO> { }; 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes the difference between two FSAs. This version is a delayed 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Fst. Only strings that are in the first automaton but not in second 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// are retained in the result. 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The first argument must be an acceptor; the second argument must be 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// an unweighted, epsilon-free, deterministic acceptor. One of the 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// arguments must be label-sorted. 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: same as ComposeFst. 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Caveats: same as ComposeFst. 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass DifferenceFst : public ComposeFst<A> { 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using ComposeFst<A>::Impl; 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // A - B = A ^ B'. 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DifferenceFst(const Fst<A> &fst1, const Fst<A> &fst2) 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ComposeFst<A>(fst1, 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComplementFst<A>(fst2), 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeFstOptions<COMPOSE_FST2_RHO>()) { 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!fst1.Properties(kAcceptor, true)) 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "DifferenceFst: 1st argument not an acceptor"; 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props1 = fst1.Properties(kFstProperties, false); 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props2 = fst2.Properties(kFstProperties, false); 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Impl()->SetProperties(DifferenceProperties(props1, props2), 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kCopyProperties); 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project template <uint64 T> 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DifferenceFst(const Fst<A> &fst1, const Fst<A> &fst2, 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const DifferenceFstOptions<T> &opts) 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ComposeFst<A>(fst1, 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComplementFst<A>(fst2), 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ComposeFstOptions<T | COMPOSE_FST2_RHO>(opts)) { 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!fst1.Properties(kAcceptor, true)) 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "DifferenceFst: 1st argument not an acceptor"; 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props1 = fst1.Properties(kFstProperties, false); 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props2 = fst2.Properties(kFstProperties, false); 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Impl()->SetProperties(DifferenceProperties(props1, props2), 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kCopyProperties); 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DifferenceFst(const DifferenceFst<A> &fst) 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ComposeFst<A>(fst) {} 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual DifferenceFst<A> *Copy() const { 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return new DifferenceFst<A>(*this); 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for DifferenceFst. 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StateIterator< DifferenceFst<A> > 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public StateIterator< ComposeFst<A> > { 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit StateIterator(const DifferenceFst<A> &fst) 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : StateIterator< ComposeFst<A> >(fst) {} 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for DifferenceFst. 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcIterator< DifferenceFst<A> > 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public ArcIterator< ComposeFst<A> > { 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator(const DifferenceFst<A> &fst, StateId s) 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ArcIterator< ComposeFst<A> >(fst, s) {} 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Useful alias when using StdArc. 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef DifferenceFst<StdArc> StdDifferenceFst; 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef ComposeOptions DifferenceOptions; 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes the difference between two FSAs. This version is writes 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the difference to an output MutableFst. Only strings that are in 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the first automaton but not in second are retained in the result. 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The first argument must be an acceptor; the second argument must be 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// an unweighted, epsilon-free, deterministic acceptor. One of the 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// arguments must be label-sorted. 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: same as Compose. 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Caveats: same as Compose. 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc> 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Difference(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2, 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project MutableFst<Arc> *ofst, 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const DifferenceOptions &opts = DifferenceOptions()) { 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DifferenceFstOptions<> nopts; 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project nopts.gc_limit = 0; // Cache only the last state for fastest copy. 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *ofst = DifferenceFst<Arc>(ifst1, ifst2, nopts); 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (opts.connect) 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Connect(ofst); 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_DIFFERENCE_H__ 141