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 24 namespace fst { 25 26 template <uint64 T = 0> 27 struct 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. 40 template <class A> 41 class 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 IntersectFst(const Fst<A> & fst1,const Fst<A> & fst2)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> IntersectFst(const Fst<A> & fst1,const Fst<A> & fst2,const IntersectFstOptions<T> & opts)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 IntersectFst(const IntersectFst<A> & fst)71 IntersectFst(const IntersectFst<A> &fst) : ComposeFst<A>(fst) {} 72 Copy()73 virtual IntersectFst<A> *Copy() const { 74 return new IntersectFst<A>(*this); 75 } 76 }; 77 78 79 // Specialization for IntersectFst. 80 template <class A> 81 class StateIterator< IntersectFst<A> > 82 : public StateIterator< ComposeFst<A> > { 83 public: StateIterator(const IntersectFst<A> & fst)84 explicit StateIterator(const IntersectFst<A> &fst) 85 : StateIterator< ComposeFst<A> >(fst) {} 86 }; 87 88 89 // Specialization for IntersectFst. 90 template <class A> 91 class ArcIterator< IntersectFst<A> > 92 : public ArcIterator< ComposeFst<A> > { 93 public: 94 typedef typename A::StateId StateId; 95 ArcIterator(const IntersectFst<A> & fst,StateId s)96 ArcIterator(const IntersectFst<A> &fst, StateId s) 97 : ArcIterator< ComposeFst<A> >(fst, s) {} 98 }; 99 100 // Useful alias when using StdArc. 101 typedef IntersectFst<StdArc> StdIntersectFst; 102 103 104 typedef 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. 117 template<class Arc> 118 void 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