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@google.com (Kasturi Rangan Raghavan) 17// Inspiration: allauzen@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 32namespace fst { 33 34// Below SparseTupleWeight*Mapper are used in conjunction with 35// SparseTupleWeightMap to compute the respective semiring operations 36template<class W, class K> 37struct SparseTupleWeightPlusMapper { 38 W Map(const K& k, const W& v1, const W& v2) const { 39 return Plus(v1, v2); 40 } 41}; 42 43template<class W, class K> 44struct SparseTupleWeightTimesMapper { 45 W Map(const K& k, const W& v1, const W& v2) const { 46 return Times(v1, v2); 47 } 48}; 49 50template<class W, class K> 51struct 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 61template<class W, class K> 62struct 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 79template <class W, class K = int> 80class 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 149template <class W, class K> 150inline 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 159template <class W, class K> 160inline 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 169template <class W, class K> 170inline 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 180template <class W, class K> 181inline 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 191template <class W, class K> 192inline 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 201template <class W, class K> 202inline 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 208template <class W, class K> 209inline 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 215template <class W, class K> 216inline 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