1 // sparse-power-weight.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 // Copyright 2005-2010 Google, Inc. 16 // Author: krr (at) google.com (Kasturi Rangan Raghavan) 17 // Inspiration: allauzen (at) google.com (Cyril Allauzen) 18 // 19 // \file 20 // Cartesian power weight semiring operation definitions. 21 // Uses SparseTupleWeight as underlying representation. 22 23 #ifndef FST_LIB_SPARSE_POWER_WEIGHT_H__ 24 #define FST_LIB_SPARSE_POWER_WEIGHT_H__ 25 26 #include<string> 27 28 #include <fst/sparse-tuple-weight.h> 29 #include <fst/weight.h> 30 31 32 namespace fst { 33 34 // Below SparseTupleWeight*Mapper are used in conjunction with 35 // SparseTupleWeightMap to compute the respective semiring operations 36 template<class W, class K> 37 struct SparseTupleWeightPlusMapper { 38 W Map(const K& k, const W& v1, const W& v2) const { 39 return Plus(v1, v2); 40 } 41 }; 42 43 template<class W, class K> 44 struct SparseTupleWeightTimesMapper { 45 W Map(const K& k, const W& v1, const W& v2) const { 46 return Times(v1, v2); 47 } 48 }; 49 50 template<class W, class K> 51 struct SparseTupleWeightDivideMapper { 52 SparseTupleWeightDivideMapper(DivideType divide_type) { 53 divide_type_ = divide_type; 54 } 55 W Map(const K& k, const W& v1, const W& v2) const { 56 return Divide(v1, v2, divide_type_); 57 } 58 DivideType divide_type_; 59 }; 60 61 template<class W, class K> 62 struct SparseTupleWeightApproxMapper { 63 SparseTupleWeightApproxMapper(float delta) { delta_ = delta; } 64 W Map(const K& k, const W& v1, const W& v2) const { 65 return ApproxEqual(v1, v2, delta_) ? W::One() : W::Zero(); 66 } 67 float delta_; 68 }; 69 70 // Sparse cartesian power semiring: W ^ n 71 // Forms: 72 // - a left semimodule when W is a left semiring, 73 // - a right semimodule when W is a right semiring, 74 // - a bisemimodule when W is a semiring, 75 // the free semimodule of rank n over W 76 // The Times operation is overloaded to provide the 77 // left and right scalar products. 78 // K is the key value type. kNoKey(-1) is reserved for internal use 79 template <class W, class K = int> 80 class SparsePowerWeight : public SparseTupleWeight<W, K> { 81 public: 82 using SparseTupleWeight<W, K>::Zero; 83 using SparseTupleWeight<W, K>::One; 84 using SparseTupleWeight<W, K>::NoWeight; 85 using SparseTupleWeight<W, K>::Quantize; 86 using SparseTupleWeight<W, K>::Reverse; 87 88 typedef SparsePowerWeight<typename W::ReverseWeight, K> ReverseWeight; 89 90 SparsePowerWeight() {} 91 92 SparsePowerWeight(const SparseTupleWeight<W, K> &w) : 93 SparseTupleWeight<W, K>(w) { } 94 95 template <class Iterator> 96 SparsePowerWeight(Iterator begin, Iterator end) : 97 SparseTupleWeight<W, K>(begin, end) { } 98 99 SparsePowerWeight(const K &key, const W &w) : 100 SparseTupleWeight<W, K>(key, w) { } 101 102 static const SparsePowerWeight<W, K> &Zero() { 103 static const SparsePowerWeight<W, K> zero(SparseTupleWeight<W, K>::Zero()); 104 return zero; 105 } 106 107 static const SparsePowerWeight<W, K> &One() { 108 static const SparsePowerWeight<W, K> one(SparseTupleWeight<W, K>::One()); 109 return one; 110 } 111 112 static const SparsePowerWeight<W, K> &NoWeight() { 113 static const SparsePowerWeight<W, K> no_weight( 114 SparseTupleWeight<W, K>::NoWeight()); 115 return no_weight; 116 } 117 118 // Overide this: Overwrite the Type method to reflect the key type 119 // if using non-default key type. 120 static const string &Type() { 121 static string type; 122 if(type.empty()) { 123 type = W::Type() + "_^n"; 124 if(sizeof(K) != sizeof(uint32)) { 125 string size; 126 Int64ToStr(8 * sizeof(K), &size); 127 type += "_" + size; 128 } 129 } 130 return type; 131 } 132 133 static uint64 Properties() { 134 uint64 props = W::Properties(); 135 return props & (kLeftSemiring | kRightSemiring | 136 kCommutative | kIdempotent); 137 } 138 139 SparsePowerWeight<W, K> Quantize(float delta = kDelta) const { 140 return SparseTupleWeight<W, K>::Quantize(delta); 141 } 142 143 ReverseWeight Reverse() const { 144 return SparseTupleWeight<W, K>::Reverse(); 145 } 146 }; 147 148 // Semimodule plus operation 149 template <class W, class K> 150 inline SparsePowerWeight<W, K> Plus(const SparsePowerWeight<W, K> &w1, 151 const SparsePowerWeight<W, K> &w2) { 152 SparsePowerWeight<W, K> ret; 153 SparseTupleWeightPlusMapper<W, K> operator_mapper; 154 SparseTupleWeightMap(&ret, w1, w2, operator_mapper); 155 return ret; 156 } 157 158 // Semimodule times operation 159 template <class W, class K> 160 inline SparsePowerWeight<W, K> Times(const SparsePowerWeight<W, K> &w1, 161 const SparsePowerWeight<W, K> &w2) { 162 SparsePowerWeight<W, K> ret; 163 SparseTupleWeightTimesMapper<W, K> operator_mapper; 164 SparseTupleWeightMap(&ret, w1, w2, operator_mapper); 165 return ret; 166 } 167 168 // Semimodule divide operation 169 template <class W, class K> 170 inline SparsePowerWeight<W, K> Divide(const SparsePowerWeight<W, K> &w1, 171 const SparsePowerWeight<W, K> &w2, 172 DivideType type = DIVIDE_ANY) { 173 SparsePowerWeight<W, K> ret; 174 SparseTupleWeightDivideMapper<W, K> operator_mapper(type); 175 SparseTupleWeightMap(&ret, w1, w2, operator_mapper); 176 return ret; 177 } 178 179 // Semimodule dot product 180 template <class W, class K> 181 inline const W& DotProduct(const SparsePowerWeight<W, K> &w1, 182 const SparsePowerWeight<W, K> &w2) { 183 const SparsePowerWeight<W, K>& product = Times(w1, w2); 184 W ret(W::Zero()); 185 for (SparseTupleWeightIterator<W, K> it(product); !it.Done(); it.Next()) { 186 ret = Plus(ret, it.Value().second); 187 } 188 return ret; 189 } 190 191 template <class W, class K> 192 inline bool ApproxEqual(const SparsePowerWeight<W, K> &w1, 193 const SparsePowerWeight<W, K> &w2, 194 float delta = kDelta) { 195 SparseTupleWeight<W, K> ret; 196 SparseTupleWeightApproxMapper<W, K> operator_mapper(kDelta); 197 SparseTupleWeightMap(&ret, w1, w2, operator_mapper); 198 return ret == SparsePowerWeight<W, K>::One(); 199 } 200 201 template <class W, class K> 202 inline SparsePowerWeight<W, K> Times(const W &k, 203 const SparsePowerWeight<W, K> &w2) { 204 SparsePowerWeight<W, K> w1(k); 205 return Times(w1, w2); 206 } 207 208 template <class W, class K> 209 inline SparsePowerWeight<W, K> Times(const SparsePowerWeight<W, K> &w1, 210 const W &k) { 211 SparsePowerWeight<W, K> w2(k); 212 return Times(w1, w2); 213 } 214 215 template <class W, class K> 216 inline SparsePowerWeight<W, K> Divide(const SparsePowerWeight<W, K> &w1, 217 const W &k, 218 DivideType divide_type = DIVIDE_ANY) { 219 SparsePowerWeight<W, K> w2(k); 220 return Divide(w1, w2, divide_type); 221 } 222 223 } // namespace fst 224 225 #endif // FST_LIB_SPARSE_POWER_WEIGHT_H__ 226
