1 // concat.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 // Functions and classes to compute the concat of two FSTs. 18 19 #ifndef FST_LIB_CONCAT_H__ 20 #define FST_LIB_CONCAT_H__ 21 22 #include <algorithm> 23 24 #include "fst/lib/mutable-fst.h" 25 #include "fst/lib/rational.h" 26 27 namespace fst { 28 29 // Computes the concatenation (product) of two FSTs; this version 30 // modifies its MutableFst argument. If FST1 transduces string x to y 31 // with weight a and FST2 transduces string w to v with weight b, then 32 // their concatenation transduces string xw to yv with Times(a, b). 33 // 34 // Complexity: 35 // - Time: O(V1 + V2 + E2) 36 // - Space: O(V1 + V2 + E2) 37 // where Vi = # of states and Ei = # of arcs of the ith FST. 38 template<class Arc> 39 void Concat(MutableFst<Arc> *fst1, const Fst<Arc> &fst2) { 40 typedef typename Arc::StateId StateId; 41 typedef typename Arc::Label Label; 42 typedef typename Arc::Weight Weight; 43 44 StateId start1 = fst1->Start(); 45 if (start1 == kNoStateId) 46 return; 47 48 uint64 props1 = fst1->Properties(kFstProperties, false); 49 uint64 props2 = fst2.Properties(kFstProperties, false); 50 51 StateId numstates1= fst1->NumStates(); 52 53 for (StateIterator< Fst<Arc> > siter2(fst2); 54 !siter2.Done(); 55 siter2.Next()) { 56 StateId s1 = fst1->AddState(); 57 StateId s2 = siter2.Value(); 58 fst1->SetFinal(s1, fst2.Final(s2)); 59 for (ArcIterator< Fst<Arc> > aiter(fst2, s2); 60 !aiter.Done(); 61 aiter.Next()) { 62 Arc arc = aiter.Value(); 63 arc.nextstate += numstates1; 64 fst1->AddArc(s1, arc); 65 } 66 } 67 68 StateId start2 = fst2.Start(); 69 for (StateId s1 = 0; s1 < numstates1; ++s1) { 70 Weight final = fst1->Final(s1); 71 if (final != Weight::Zero()) { 72 fst1->SetFinal(s1, Weight::Zero()); 73 if (start2 != kNoStateId) 74 fst1->AddArc(s1, Arc(0, 0, final, start2 + numstates1)); 75 } 76 } 77 if (start2 != kNoStateId) 78 fst1->SetProperties(ConcatProperties(props1, props2), kFstProperties); 79 } 80 81 82 // Computes the concatentation of two FSTs. This version modifies its 83 // RationalFst input. 84 template<class Arc> 85 void Concat(RationalFst<Arc> *fst1, const Fst<Arc> &fst2) { 86 fst1->Impl()->AddConcat(fst2); 87 } 88 89 90 typedef RationalFstOptions ConcatFstOptions; 91 92 93 // Computes the concatenation (product) of two FSTs; this version is a 94 // delayed Fst. If FST1 transduces string x to y with weight a and FST2 95 // transduces string w to v with weight b, then their concatenation 96 // transduces string xw to yv with Times(a, b). 97 // 98 // Complexity: 99 // - Time: O(v1 + e1 + v2 + e2), 100 // - Space: O(v1 + v2) 101 // where vi = # of states visited and ei = # of arcs visited of the 102 // ith FST. Constant time and space to visit an input state or arc is 103 // assumed and exclusive of caching. 104 template <class A> 105 class ConcatFst : public RationalFst<A> { 106 public: 107 using RationalFst<A>::Impl; 108 109 typedef A Arc; 110 typedef typename A::Weight Weight; 111 typedef typename A::StateId StateId; 112 113 ConcatFst(const Fst<A> &fst1, const Fst<A> &fst2) { 114 Impl()->InitConcat(fst1, fst2); 115 } 116 117 ConcatFst(const Fst<A> &fst1, const Fst<A> &fst2, 118 const ConcatFstOptions &opts) : RationalFst<A>(opts) { 119 Impl()->InitConcat(fst1, fst2); 120 } 121 122 ConcatFst(const ConcatFst<A> &fst) : RationalFst<A>(fst) {} 123 124 virtual ConcatFst<A> *Copy() const { return new ConcatFst<A>(*this); } 125 }; 126 127 128 // Specialization for ConcatFst. 129 template <class A> 130 class StateIterator< ConcatFst<A> > : public StateIterator< RationalFst<A> > { 131 public: 132 explicit StateIterator(const ConcatFst<A> &fst) 133 : StateIterator< RationalFst<A> >(fst) {} 134 }; 135 136 137 // Specialization for ConcatFst. 138 template <class A> 139 class ArcIterator< ConcatFst<A> > : public ArcIterator< RationalFst<A> > { 140 public: 141 typedef typename A::StateId StateId; 142 143 ArcIterator(const ConcatFst<A> &fst, StateId s) 144 : ArcIterator< RationalFst<A> >(fst, s) {} 145 }; 146 147 148 // Useful alias when using StdArc. 149 typedef ConcatFst<StdArc> StdConcatFst; 150 151 } // namespace fst 152 153 #endif // FST_LIB_CONCAT_H__ 154