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