1// random-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: riley@google.com (Michael Riley) 17// 18// \file 19// Function objects to generate random weights in various semirings 20// for testing purposes. 21 22#ifndef FST_LIB_RANDOM_WEIGHT_H__ 23#define FST_LIB_RANDOM_WEIGHT_H__ 24 25#include <cstdlib> 26#include <ctime> 27#include <vector> 28using std::vector; 29 30 31#include <fst/float-weight.h> 32#include <fst/product-weight.h> 33#include <fst/string-weight.h> 34#include <fst/lexicographic-weight.h> 35#include <fst/power-weight.h> 36#include <fst/signed-log-weight.h> 37#include <fst/sparse-power-weight.h> 38 39 40namespace fst { 41 42// The boolean 'allow_zero' below determines whether Zero() and zero 43// divisors should be returned in the random weight generation. 44 45// This function object returns TropicalWeightTpl<T>'s that are random integers 46// chosen from [0, kNumRandomWeights). 47template <class T> 48class TropicalWeightGenerator_ { 49 public: 50 typedef TropicalWeightTpl<T> Weight; 51 52 TropicalWeightGenerator_(int seed = time(0), bool allow_zero = true) 53 : allow_zero_(allow_zero) { 54 srand(seed); 55 } 56 57 Weight operator() () const { 58 int n = rand() % (kNumRandomWeights + allow_zero_); 59 if (allow_zero_ && n == kNumRandomWeights) 60 return Weight::Zero(); 61 62 return Weight(static_cast<T>(n)); 63 } 64 65 private: 66 // The number of alternative random weights. 67 static const int kNumRandomWeights = 5; 68 69 bool allow_zero_; // permit Zero() and zero divisors 70}; 71 72template <class T> const int TropicalWeightGenerator_<T>::kNumRandomWeights; 73 74typedef TropicalWeightGenerator_<float> TropicalWeightGenerator; 75 76 77// This function object returns LogWeightTpl<T>'s that are random integers 78// chosen from [0, kNumRandomWeights). 79template <class T> 80class LogWeightGenerator_ { 81 public: 82 typedef LogWeightTpl<T> Weight; 83 84 LogWeightGenerator_(int seed = time(0), bool allow_zero = true) 85 : allow_zero_(allow_zero) { 86 srand(seed); 87 } 88 89 Weight operator() () const { 90 int n = rand() % (kNumRandomWeights + allow_zero_); 91 if (allow_zero_ && n == kNumRandomWeights) 92 return Weight::Zero(); 93 94 return Weight(static_cast<T>(n)); 95 } 96 97 private: 98 // Number of alternative random weights. 99 static const int kNumRandomWeights = 5; 100 101 bool allow_zero_; // permit Zero() and zero divisors 102}; 103 104template <class T> const int LogWeightGenerator_<T>::kNumRandomWeights; 105 106typedef LogWeightGenerator_<float> LogWeightGenerator; 107 108 109// This function object returns MinMaxWeightTpl<T>'s that are random integers 110// chosen from (-kNumRandomWeights, kNumRandomWeights) in addition to 111// One(), and Zero() if zero is allowed. 112template <class T> 113class MinMaxWeightGenerator_ { 114 public: 115 typedef MinMaxWeightTpl<T> Weight; 116 117 MinMaxWeightGenerator_(int seed = time(0), bool allow_zero = true) 118 : allow_zero_(allow_zero) { 119 srand(seed); 120 } 121 122 Weight operator() () const { 123 int n = (rand() % (2*kNumRandomWeights + allow_zero_)) - kNumRandomWeights; 124 if (allow_zero_ && n == kNumRandomWeights) 125 return Weight::Zero(); 126 else if (n == -kNumRandomWeights) 127 return Weight::One(); 128 129 return Weight(static_cast<T>(n)); 130 } 131 132 private: 133 // Parameters controlling the number of alternative random weights. 134 static const int kNumRandomWeights = 5; 135 136 bool allow_zero_; // permit Zero() and zero divisors 137}; 138 139template <class T> const int MinMaxWeightGenerator_<T>::kNumRandomWeights; 140 141typedef MinMaxWeightGenerator_<float> MinMaxWeightGenerator; 142 143 144// This function object returns StringWeights that are random integer 145// strings chosen from {1,...,kAlphabetSize}^{0,kMaxStringLength} U { Zero } 146template <typename L, StringType S = STRING_LEFT> 147class StringWeightGenerator { 148 public: 149 typedef StringWeight<L, S> Weight; 150 151 StringWeightGenerator(int seed = time(0), bool allow_zero = true) 152 : allow_zero_(allow_zero) { 153 srand(seed); 154 } 155 156 Weight operator() () const { 157 int n = rand() % (kMaxStringLength + allow_zero_); 158 if (allow_zero_ && n == kMaxStringLength) 159 return Weight::Zero(); 160 161 vector<L> v; 162 for (int i = 0; i < n; ++i) 163 v.push_back(rand() % kAlphabetSize + 1); 164 return Weight(v.begin(), v.end()); 165 } 166 167 private: 168 // Alphabet size for random weights. 169 static const int kAlphabetSize = 5; 170 // Number of alternative random weights. 171 static const int kMaxStringLength = 5; 172 173 bool allow_zero_; // permit Zero() and zero 174}; 175 176template <typename L, StringType S> 177const int StringWeightGenerator<L, S>::kAlphabetSize; 178template <typename L, StringType S> 179const int StringWeightGenerator<L, S>::kMaxStringLength; 180 181 182// This function object returns a weight generator over the product of the 183// weights (by default) for the generators G1 and G2. 184template <class G1, class G2, 185 class W = ProductWeight<typename G1::Weight, typename G2::Weight> > 186class ProductWeightGenerator { 187 public: 188 typedef typename G1::Weight W1; 189 typedef typename G2::Weight W2; 190 typedef W Weight; 191 192 ProductWeightGenerator(int seed = time(0), bool allow_zero = true) 193 : generator1_(seed, allow_zero), generator2_(seed, allow_zero) {} 194 195 Weight operator() () const { 196 W1 w1 = generator1_(); 197 W2 w2 = generator2_(); 198 return Weight(w1, w2); 199 } 200 201 private: 202 G1 generator1_; 203 G2 generator2_; 204}; 205 206 207// This function object returns a weight generator for a lexicographic weight 208// composed out of weights for the generators G1 and G2. For lexicographic 209// weights, we cannot generate zeroes for the two subweights separately: 210// weights are members iff both members are zero or both members are non-zero. 211template <class G1, class G2> 212class LexicographicWeightGenerator { 213 public: 214 typedef typename G1::Weight W1; 215 typedef typename G2::Weight W2; 216 typedef LexicographicWeight<W1, W2> Weight; 217 218 LexicographicWeightGenerator(int seed = time(0), bool allow_zero = true) 219 : generator1_(seed, false), generator2_(seed, false), 220 allow_zero_(allow_zero) {} 221 222 Weight operator() () const { 223 if (allow_zero_) { 224 int n = rand() % (kNumRandomWeights + allow_zero_); 225 if (n == kNumRandomWeights) 226 return Weight(W1::Zero(), W2::Zero()); 227 } 228 W1 w1 = generator1_(); 229 W2 w2 = generator2_(); 230 return Weight(w1, w2); 231 } 232 233 private: 234 G1 generator1_; 235 G2 generator2_; 236 static const int kNumRandomWeights = 5; 237 bool allow_zero_; 238}; 239 240template <class G1, class G2> 241const int LexicographicWeightGenerator<G1, G2>::kNumRandomWeights; 242 243 244// Product generator of a string weight generator and an 245// arbitrary weight generator. 246template <class L, class G, StringType S = STRING_LEFT> 247class GallicWeightGenerator 248 : public ProductWeightGenerator<StringWeightGenerator<L, S>, G> { 249 250 public: 251 typedef ProductWeightGenerator<StringWeightGenerator<L, S>, G> PG; 252 typedef typename G::Weight W; 253 typedef GallicWeight<L, W, S> Weight; 254 255 GallicWeightGenerator(int seed = time(0), bool allow_zero = true) 256 : PG(seed, allow_zero) {} 257 258 GallicWeightGenerator(const PG &pg) : PG(pg) {} 259}; 260 261// This function object returms a weight generator over the catersian power 262// of rank n of the weights for the generator G. 263template <class G, unsigned int n> 264class PowerWeightGenerator { 265 public: 266 typedef typename G::Weight W; 267 typedef PowerWeight<W, n> Weight; 268 269 PowerWeightGenerator(int seed = time(0), bool allow_zero = true) 270 : generator_(seed, allow_zero) {} 271 272 Weight operator()() const { 273 Weight w; 274 for (size_t i = 0; i < n; ++i) { 275 W r = generator_(); 276 w.SetValue(i, r); 277 } 278 return w; 279 } 280 281 private: 282 G generator_; 283}; 284 285// This function object returns SignedLogWeightTpl<T>'s that are 286// random integers chosen from [0, kNumRandomWeights). 287// The sign is randomly chosen as well. 288template <class T> 289class SignedLogWeightGenerator_ { 290 public: 291 typedef SignedLogWeightTpl<T> Weight; 292 293 SignedLogWeightGenerator_(int seed = time(0), bool allow_zero = true) 294 : allow_zero_(allow_zero) { 295 srand(seed); 296 } 297 298 Weight operator() () const { 299 int m = rand() % 2; 300 int n = rand() % (kNumRandomWeights + allow_zero_); 301 302 return SignedLogWeightTpl<T>( 303 (m == 0) ? 304 TropicalWeight(-1.0) : 305 TropicalWeight(1.0), 306 (allow_zero_ && n == kNumRandomWeights) ? 307 LogWeightTpl<T>::Zero() : 308 LogWeightTpl<T>(static_cast<T>(n))); 309 } 310 311 private: 312 // Number of alternative random weights. 313 static const int kNumRandomWeights = 5; 314 bool allow_zero_; // permit Zero() and zero divisors 315}; 316 317template <class T> const int SignedLogWeightGenerator_<T>::kNumRandomWeights; 318 319typedef SignedLogWeightGenerator_<float> SignedLogWeightGenerator; 320 321// This function object returms a weight generator over the catersian power 322// of rank n of the weights for the generator G. 323template <class G, class K, unsigned int n> 324class SparsePowerWeightGenerator { 325 public: 326 typedef typename G::Weight W; 327 typedef SparsePowerWeight<W, K> Weight; 328 329 SparsePowerWeightGenerator(int seed = time(0), bool allow_zero = true) 330 : generator_(seed, allow_zero) {} 331 332 Weight operator()() const { 333 Weight w; 334 for (size_t i = 1; i <= n; ++i) { 335 W r = generator_(); 336 K p = i; 337 w.Push(p, r, true); 338 } 339 return w; 340 } 341 342 private: 343 G generator_; 344}; 345 346} // namespace fst 347 348#endif // FST_LIB_RANDOM_WEIGHT_H__ 349