intersect.h revision 8fc5a7f51e62cb4ae44a27bdf4176d04adc80ede
15d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// intersect.h 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Licensed under the Apache License, Version 2.0 (the "License"); 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// you may not use this file except in compliance with the License. 56e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// You may obtain a copy of the License at 66e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// http://www.apache.org/licenses/LICENSE-2.0 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Unless required by applicable law or agreed to in writing, software 105f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// distributed under the License is distributed on an "AS IS" BASIS, 116e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// See the License for the specific language governing permissions and 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// limitations under the License. 146e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// 156e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// 166e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// \file 176e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// Class to compute the intersection of two FSAs 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef FST_LIB_INTERSECT_H__ 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define FST_LIB_INTERSECT_H__ 216e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 226e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#include "fst/lib/compose.h" 236e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 246e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)namespace fst { 256e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 266e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)template <uint64 T = 0> 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct IntersectFstOptions : public ComposeFstOptions<T> { }; 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Computes the intersection (Hadamard product) of two FSAs. This 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// version is a delayed Fst. Only strings that are in both automata 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// are retained in the result. 33868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The two arguments must be acceptors. One of the arguments must be 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// label-sorted. 36c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// 37c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Complexity: same as ComposeFst. 38c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// 39868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Caveats: same as ComposeFst. 40868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)template <class A> 41868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)class IntersectFst : public ComposeFst<A> { 42c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) public: 43c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) using ComposeFst<A>::Impl; 44868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 456e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) typedef A Arc; 46868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typedef typename A::Weight Weight; 474e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) typedef typename A::StateId StateId; 486e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 494e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) IntersectFst(const Fst<A> &fst1, const Fst<A> &fst2) 50c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) : ComposeFst<A>(fst1, fst2) { 51c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (!fst1.Properties(kAcceptor, true) || !fst2.Properties(kAcceptor, true)) 52868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) LOG(FATAL) << "IntersectFst: arguments not both acceptors"; 53c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) uint64 props1 = fst1.Properties(kFstProperties, false); 54c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) uint64 props2 = fst2.Properties(kFstProperties, false); 55c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Impl()->SetProperties(IntersectProperties(props1, props2), 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kCopyProperties); 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 58f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 59f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) template <uint64 T> 60f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) IntersectFst(const Fst<A> &fst1, const Fst<A> &fst2, 61a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) const IntersectFstOptions<T> &opts) 62a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) : ComposeFst<A>(fst1, fst2, ComposeFstOptions<T>(opts)) { 63f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if (!fst1.Properties(kAcceptor, true) || !fst2.Properties(kAcceptor, true)) 64f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) LOG(FATAL) << "IntersectFst: arguments not both acceptors"; 65a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) uint64 props1 = fst1.Properties(kFstProperties, false); 66a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) uint64 props2 = fst2.Properties(kFstProperties, false); 67f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) Impl()->SetProperties(IntersectProperties(props1, props2), 68f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) kCopyProperties); 69f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 70a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 71a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) IntersectFst(const IntersectFst<A> &fst) : ComposeFst<A>(fst) {} 72f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 73f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) virtual IntersectFst<A> *Copy() const { 74f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return new IntersectFst<A>(*this); 75f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 76f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)}; 776e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 786e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 796e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// Specialization for IntersectFst. 806e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)template <class A> 816e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)class StateIterator< IntersectFst<A> > 82c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) : public StateIterator< ComposeFst<A> > { 836e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) public: 846e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) explicit StateIterator(const IntersectFst<A> &fst) 85c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) : StateIterator< ComposeFst<A> >(fst) {} 86c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)}; 87c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 88c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 89c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Specialization for IntersectFst. 90c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)template <class A> 91c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)class ArcIterator< IntersectFst<A> > 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : public ArcIterator< ComposeFst<A> > { 936e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) public: 946e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) typedef typename A::StateId StateId; 956e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 96c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ArcIterator(const IntersectFst<A> &fst, StateId s) 976e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) : ArcIterator< ComposeFst<A> >(fst, s) {} 986e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)}; 99c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 100c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Useful alias when using StdArc. 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef IntersectFst<StdArc> StdIntersectFst; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef ComposeOptions IntersectOptions; 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1066e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Computes the intersection (Hadamard product) of two FSAs. This 108f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// version writes the intersection to an output MurableFst. Only 1096d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)// strings that are in both automata are retained in the result. 1106d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)// 1116d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)// The two arguments must be acceptors. One of the arguments must be 1126d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)// label-sorted. 1136d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles)// 1146e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)// Complexity: same as Compose. 115868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 116c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Caveats: same as Compose. 1176e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)template<class Arc> 118c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)void Intersect(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2, 11990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) MutableFst<Arc> *ofst, 12090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) const IntersectOptions &opts = IntersectOptions()) { 12190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) IntersectFstOptions<> nopts; 1226e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) nopts.gc_limit = 0; // Cache only the last state for fastest copy. 12390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) *ofst = IntersectFst<Arc>(ifst1, ifst2, nopts); 124d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) if (opts.connect) 1255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) Connect(ofst); 1265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} // namespace fst 1295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1306e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#endif // FST_LIB_INTERSECT_H__ 131d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)