14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// intersect.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 intersection of two FSAs 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_INTERSECT_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_INTERSECT_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/compose.h" 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <uint64 T = 0> 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct IntersectFstOptions : public ComposeFstOptions<T> { }; 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes the intersection (Hadamard product) of two FSAs. This 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// version is a delayed Fst. Only strings that are in both automata 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// are retained in the result. 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The two arguments must be acceptors. One of the arguments must be 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// label-sorted. 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: same as ComposeFst. 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Caveats: same as ComposeFst. 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass IntersectFst : public ComposeFst<A> { 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using ComposeFst<A>::Impl; 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project IntersectFst(const Fst<A> &fst1, const Fst<A> &fst2) 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ComposeFst<A>(fst1, fst2) { 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!fst1.Properties(kAcceptor, true) || !fst2.Properties(kAcceptor, true)) 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "IntersectFst: arguments not both acceptors"; 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props1 = fst1.Properties(kFstProperties, false); 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props2 = fst2.Properties(kFstProperties, false); 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Impl()->SetProperties(IntersectProperties(props1, props2), 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kCopyProperties); 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project template <uint64 T> 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project IntersectFst(const Fst<A> &fst1, const Fst<A> &fst2, 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const IntersectFstOptions<T> &opts) 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ComposeFst<A>(fst1, fst2, ComposeFstOptions<T>(opts)) { 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!fst1.Properties(kAcceptor, true) || !fst2.Properties(kAcceptor, true)) 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "IntersectFst: arguments not both acceptors"; 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props1 = fst1.Properties(kFstProperties, false); 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props2 = fst2.Properties(kFstProperties, false); 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Impl()->SetProperties(IntersectProperties(props1, props2), 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kCopyProperties); 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project IntersectFst(const IntersectFst<A> &fst) : ComposeFst<A>(fst) {} 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual IntersectFst<A> *Copy() const { 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return new IntersectFst<A>(*this); 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for IntersectFst. 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StateIterator< IntersectFst<A> > 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public StateIterator< ComposeFst<A> > { 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit StateIterator(const IntersectFst<A> &fst) 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : StateIterator< ComposeFst<A> >(fst) {} 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for IntersectFst. 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcIterator< IntersectFst<A> > 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public ArcIterator< ComposeFst<A> > { 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator(const IntersectFst<A> &fst, StateId s) 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ArcIterator< ComposeFst<A> >(fst, s) {} 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Useful alias when using StdArc. 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef IntersectFst<StdArc> StdIntersectFst; 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef ComposeOptions IntersectOptions; 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes the intersection (Hadamard product) of two FSAs. This 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// version writes the intersection to an output MurableFst. Only 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// strings that are in both automata are retained in the result. 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The two arguments must be acceptors. One of the arguments must be 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// label-sorted. 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: same as Compose. 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Caveats: same as Compose. 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc> 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Intersect(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2, 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project MutableFst<Arc> *ofst, 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const IntersectOptions &opts = IntersectOptions()) { 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project IntersectFstOptions<> nopts; 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project nopts.gc_limit = 0; // Cache only the last state for fastest copy. 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *ofst = IntersectFst<Arc>(ifst1, ifst2, nopts); 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (opts.connect) 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Connect(ofst); 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_INTERSECT_H__ 131