FST  openfst-1.7.2
OpenFst Library
float-weight.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 //
4 // Float weight set and associated semiring operation definitions.
5 
6 #ifndef FST_FLOAT_WEIGHT_H_
7 #define FST_FLOAT_WEIGHT_H_
8 
9 #include <algorithm>
10 #include <climits>
11 #include <cmath>
12 #include <cstdlib>
13 #include <cstring>
14 #include <limits>
15 #include <sstream>
16 #include <string>
17 #include <type_traits>
18 
19 #include <fst/util.h>
20 #include <fst/weight.h>
21 
22 
23 namespace fst {
24 
25 // Numeric limits class.
26 template <class T>
27 class FloatLimits {
28  public:
29  static constexpr T PosInfinity() {
30  return std::numeric_limits<T>::infinity();
31  }
32 
33  static constexpr T NegInfinity() { return -PosInfinity(); }
34 
35  static constexpr T NumberBad() { return std::numeric_limits<T>::quiet_NaN(); }
36 };
37 
38 // Weight class to be templated on floating-points types.
39 template <class T = float>
41  public:
42  using ValueType = T;
43 
44  FloatWeightTpl() noexcept {}
45 
46  constexpr FloatWeightTpl(T f) : value_(f) {} // NOLINT
47 
48  // TODO(mjansche): Leave implicit once Android NDK r18 is the default.
49  FloatWeightTpl(const FloatWeightTpl<T> &) = default;
50  FloatWeightTpl(FloatWeightTpl<T> &&) noexcept = default;
51 
52  FloatWeightTpl<T> &operator=(const FloatWeightTpl<T> &) = default;
53  FloatWeightTpl<T> &operator=(FloatWeightTpl<T> &&) noexcept = default;
54 
55  std::istream &Read(std::istream &strm) { return ReadType(strm, &value_); }
56 
57  std::ostream &Write(std::ostream &strm) const {
58  return WriteType(strm, value_);
59  }
60 
61  size_t Hash() const {
62  size_t hash = 0;
63  // Avoid using union, which would be undefined behavior.
64  // Use memcpy, similar to bit_cast, but sizes may be different.
65  // This should be optimized into a single move instruction by
66  // any reasonable compiler.
67  std::memcpy(&hash, &value_, std::min(sizeof(hash), sizeof(value_)));
68  return hash;
69  }
70 
71  constexpr const T &Value() const { return value_; }
72 
73  protected:
74  void SetValue(const T &f) { value_ = f; }
75 
76  static constexpr const char *GetPrecisionString() {
77  return sizeof(T) == 4 ? ""
78  : sizeof(T) == 1 ? "8"
79  : sizeof(T) == 2 ? "16"
80  : sizeof(T) == 8 ? "64"
81  : "unknown";
82  }
83 
84  private:
85  T value_;
86 };
87 
88 // Single-precision float weight.
90 
91 template <class T>
92 constexpr bool operator==(const FloatWeightTpl<T> &w1,
93  const FloatWeightTpl<T> &w2) {
94 #if (defined(__i386__) || defined(__x86_64__)) && !defined(__SSE2_MATH__)
95 // With i387 instructions, excess precision on a weight in an 80-bit
96 // register may cause it to compare unequal to that same weight when
97 // stored to memory. This breaks =='s reflexivity, in turn breaking
98 // NaturalLess.
99 #error "Please compile with -msse -mfpmath=sse, or equivalent."
100 #endif
101  return w1.Value() == w2.Value();
102 }
103 
104 // These seemingly unnecessary overloads are actually needed to make
105 // comparisons like FloatWeightTpl<float> == float compile. If only the
106 // templated version exists, the FloatWeightTpl<float>(float) conversion
107 // won't be found.
108 constexpr bool operator==(const FloatWeightTpl<float> &w1,
109  const FloatWeightTpl<float> &w2) {
110  return operator==<float>(w1, w2);
111 }
112 
113 constexpr bool operator==(const FloatWeightTpl<double> &w1,
114  const FloatWeightTpl<double> &w2) {
115  return operator==<double>(w1, w2);
116 }
117 
118 template <class T>
119 constexpr bool operator!=(const FloatWeightTpl<T> &w1,
120  const FloatWeightTpl<T> &w2) {
121  return !(w1 == w2);
122 }
123 
124 constexpr bool operator!=(const FloatWeightTpl<float> &w1,
125  const FloatWeightTpl<float> &w2) {
126  return operator!=<float>(w1, w2);
127 }
128 
129 constexpr bool operator!=(const FloatWeightTpl<double> &w1,
130  const FloatWeightTpl<double> &w2) {
131  return operator!=<double>(w1, w2);
132 }
133 
134 template <class T>
135 constexpr bool FloatApproxEqual(T w1, T w2, float delta = kDelta) {
136  return w1 <= w2 + delta && w2 <= w1 + delta;
137 }
138 
139 template <class T>
140 constexpr bool ApproxEqual(const FloatWeightTpl<T> &w1,
141  const FloatWeightTpl<T> &w2, float delta = kDelta) {
142  return FloatApproxEqual(w1.Value(), w2.Value(), delta);
143 }
144 
145 template <class T>
146 inline std::ostream &operator<<(std::ostream &strm,
147  const FloatWeightTpl<T> &w) {
148  if (w.Value() == FloatLimits<T>::PosInfinity()) {
149  return strm << "Infinity";
150  } else if (w.Value() == FloatLimits<T>::NegInfinity()) {
151  return strm << "-Infinity";
152  } else if (w.Value() != w.Value()) { // Fails for IEEE NaN.
153  return strm << "BadNumber";
154  } else {
155  return strm << w.Value();
156  }
157 }
158 
159 template <class T>
160 inline std::istream &operator>>(std::istream &strm, FloatWeightTpl<T> &w) {
161  string s;
162  strm >> s;
163  if (s == "Infinity") {
165  } else if (s == "-Infinity") {
167  } else {
168  char *p;
169  T f = strtod(s.c_str(), &p);
170  if (p < s.c_str() + s.size()) {
171  strm.clear(std::ios::badbit);
172  } else {
173  w = FloatWeightTpl<T>(f);
174  }
175  }
176  return strm;
177 }
178 
179 // Tropical semiring: (min, +, inf, 0).
180 template <class T>
182  public:
183  using typename FloatWeightTpl<T>::ValueType;
187 
188  TropicalWeightTpl() noexcept : FloatWeightTpl<T>() {}
189 
190  constexpr TropicalWeightTpl(T f) : FloatWeightTpl<T>(f) {}
191 
192  static constexpr TropicalWeightTpl<T> Zero() { return Limits::PosInfinity(); }
193 
194  static constexpr TropicalWeightTpl<T> One() { return 0; }
195 
196  static constexpr TropicalWeightTpl<T> NoWeight() {
197  return Limits::NumberBad();
198  }
199 
200  static const string &Type() {
201  static const string *const type =
202  new string(string("tropical") +
204  return *type;
205  }
206 
207  constexpr bool Member() const {
208  // All floating point values except for NaNs and negative infinity are valid
209  // tropical weights.
210  //
211  // Testing membership of a given value can be done by simply checking that
212  // it is strictly greater than negative infinity, which fails for negative
213  // infinity itself but also for NaNs. This can usually be accomplished in a
214  // single instruction (such as *UCOMI* on x86) without branching logic.
215  //
216  // An additional wrinkle involves constexpr correctness of floating point
217  // comparisons against NaN. GCC is uneven when it comes to which expressions
218  // it considers compile-time constants. In particular, current versions of
219  // GCC do not always consider (nan < inf) to be a constant expression, but
220  // do consider (inf < nan) to be a constant expression. (See
221  // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88173 and
222  // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88683 for details.) In order
223  // to allow Member() to be a constexpr function accepted by GCC, we write
224  // the comparison here as (-inf < v).
225  return Limits::NegInfinity() < Value();
226  }
227 
228  TropicalWeightTpl<T> Quantize(float delta = kDelta) const {
229  if (!Member() || Value() == Limits::PosInfinity()) {
230  return *this;
231  } else {
232  return TropicalWeightTpl<T>(std::floor(Value() / delta + 0.5F) * delta);
233  }
234  }
235 
236  constexpr TropicalWeightTpl<T> Reverse() const { return *this; }
237 
238  static constexpr uint64 Properties() {
240  }
241 };
242 
243 // Single precision tropical weight.
245 
246 template <class T>
248  const TropicalWeightTpl<T> &w2) {
249  return (!w1.Member() || !w2.Member()) ? TropicalWeightTpl<T>::NoWeight()
250  : w1.Value() < w2.Value() ? w1 : w2;
251 }
252 
253 // See comment at operator==(FloatWeightTpl<float>, FloatWeightTpl<float>)
254 // for why these overloads are present.
256  const TropicalWeightTpl<float> &w2) {
257  return Plus<float>(w1, w2);
258 }
259 
261  const TropicalWeightTpl<double> &w2) {
262  return Plus<double>(w1, w2);
263 }
264 
265 template <class T>
267  const TropicalWeightTpl<T> &w2) {
268  // The following is safe in the context of the Tropical (and Log) semiring
269  // for all IEEE floating point values, including infinities and NaNs,
270  // because:
271  //
272  // * If one or both of the floating point Values is NaN and hence not a
273  // Member, the result of addition below is NaN, so the result is not a
274  // Member. This supersedes all other cases, so we only consider non-NaN
275  // values next.
276  //
277  // * If both Values are finite, there is no issue.
278  //
279  // * If one of the Values is infinite, or if both are infinities with the
280  // same sign, the result of floating point addition is the same infinity,
281  // so there is no issue.
282  //
283  // * If both of the Values are infinities with opposite signs, the result of
284  // adding IEEE floating point -inf + inf is NaN and hence not a Member. But
285  // since -inf was not a Member to begin with, returning a non-Member result
286  // is fine as well.
287  return TropicalWeightTpl<T>(w1.Value() + w2.Value());
288 }
289 
291  const TropicalWeightTpl<float> &w2) {
292  return Times<float>(w1, w2);
293 }
294 
296  const TropicalWeightTpl<double> &w2) {
297  return Times<double>(w1, w2);
298 }
299 
300 template <class T>
302  const TropicalWeightTpl<T> &w2,
303  DivideType typ = DIVIDE_ANY) {
304  // The following is safe in the context of the Tropical (and Log) semiring
305  // for all IEEE floating point values, including infinities and NaNs,
306  // because:
307  //
308  // * If one or both of the floating point Values is NaN and hence not a
309  // Member, the result of subtraction below is NaN, so the result is not a
310  // Member. This supersedes all other cases, so we only consider non-NaN
311  // values next.
312  //
313  // * If both Values are finite, there is no issue.
314  //
315  // * If w2.Value() is -inf (and hence w2 is not a Member), the result of ?:
316  // below is NoWeight, which is not a Member.
317  //
318  // Whereas in IEEE floating point semantics 0/inf == 0, this does not carry
319  // over to this semiring (since TropicalWeight(-inf) would be the analogue
320  // of floating point inf) and instead Divide(Zero(), TropicalWeight(-inf))
321  // is NoWeight().
322  //
323  // * If w2.Value() is inf (and hence w2 is Zero), the resulting floating
324  // point value is either NaN (if w1 is Zero or if w1.Value() is NaN) and
325  // hence not a Member, or it is -inf and hence not a Member; either way,
326  // division by Zero results in a non-Member result.
327  using Weight = TropicalWeightTpl<T>;
328  return w2.Member() ? Weight(w1.Value() - w2.Value()) : Weight::NoWeight();
329 }
330 
332  const TropicalWeightTpl<float> &w2,
333  DivideType typ = DIVIDE_ANY) {
334  return Divide<float>(w1, w2, typ);
335 }
336 
338  const TropicalWeightTpl<double> &w2,
339  DivideType typ = DIVIDE_ANY) {
340  return Divide<double>(w1, w2, typ);
341 }
342 
343 // Power(w, n) calculates the n-th power of w with respect to semiring Times.
344 //
345 // In the case of the Tropical (and Log) semiring, the exponent n is not
346 // restricted to be an integer. It can be a floating point value, for example.
347 //
348 // In weight.h, a narrower and hence more broadly applicable version of
349 // Power(w, n) is defined for arbitrary weight types and non-negative integer
350 // exponents n (of type size_t) and implemented in terms of repeated
351 // multiplication using Times.
352 //
353 // Without further provisions this means that, when an expression such as
354 //
355 // Power(TropicalWeightTpl<float>::One(), static_cast<size_t>(2))
356 //
357 // is specified, the overload of Power() is ambiguous. The template function
358 // below could be instantiated as
359 //
360 // Power<float, size_t>(const TropicalWeightTpl<float> &, size_t)
361 //
362 // and the template function defined in weight.h (further specialized below)
363 // could be instantiated as
364 //
365 // Power<TropicalWeightTpl<float>>(const TropicalWeightTpl<float> &, size_t)
366 //
367 // That would lead to two definitions with identical signatures, which results
368 // in a compilation error. To avoid that, we hide the definition of Power<T, V>
369 // when V is size_t, so only Power<W> is visible. Power<W> is further
370 // specialized to Power<TropicalWeightTpl<...>>, and the overloaded definition
371 // of Power<T, V> is made conditionally available only to that template
372 // specialization.
373 
374 template <class T, class V,
375  bool Enable = !std::is_same<V, size_t>::value,
376  typename std::enable_if<Enable>::type * = nullptr>
378  using Weight = TropicalWeightTpl<T>;
379  return (!w.Member() || n != n) ? Weight::NoWeight()
380  : (n == 0 || w == Weight::One()) ? Weight::One()
381  : Weight(w.Value() * n);
382 }
383 
384 // Specializes the library-wide template to use the above implementation; rules
385 // of function template instantiation require this be a full instantiation.
386 
387 template <>
388 constexpr TropicalWeightTpl<float> Power<TropicalWeightTpl<float>>(
389  const TropicalWeightTpl<float> &weight, size_t n) {
390  return Power<float, size_t, true>(weight, n);
391 }
392 
393 template <>
394 constexpr TropicalWeightTpl<double> Power<TropicalWeightTpl<double>>(
395  const TropicalWeightTpl<double> &weight, size_t n) {
396  return Power<double, size_t, true>(weight, n);
397 }
398 
399 
400 // Log semiring: (log(e^-x + e^-y), +, inf, 0).
401 template <class T>
402 class LogWeightTpl : public FloatWeightTpl<T> {
403  public:
404  using typename FloatWeightTpl<T>::ValueType;
408 
409  LogWeightTpl() noexcept : FloatWeightTpl<T>() {}
410 
411  constexpr LogWeightTpl(T f) : FloatWeightTpl<T>(f) {}
412 
413  static constexpr LogWeightTpl Zero() { return Limits::PosInfinity(); }
414 
415  static constexpr LogWeightTpl One() { return 0; }
416 
417  static constexpr LogWeightTpl NoWeight() { return Limits::NumberBad(); }
418 
419  static const string &Type() {
420  static const string *const type =
421  new string(string("log") + FloatWeightTpl<T>::GetPrecisionString());
422  return *type;
423  }
424 
425  constexpr bool Member() const {
426  // The comments for TropicalWeightTpl<>::Member() apply here unchanged.
427  return Limits::NegInfinity() < Value();
428  }
429 
430  LogWeightTpl<T> Quantize(float delta = kDelta) const {
431  if (!Member() || Value() == Limits::PosInfinity()) {
432  return *this;
433  } else {
434  return LogWeightTpl<T>(std::floor(Value() / delta + 0.5F) * delta);
435  }
436  }
437 
438  constexpr LogWeightTpl<T> Reverse() const { return *this; }
439 
440  static constexpr uint64 Properties() {
442  }
443 };
444 
445 // Single-precision log weight.
447 
448 // Double-precision log weight.
450 
451 namespace internal {
452 
453 // -log(e^-x + e^-y) = x - LogPosExp(y - x), assuming x >= 0.0.
454 inline double LogPosExp(double x) {
455  DCHECK(!(x < 0)); // NB: NaN values are allowed.
456  return log1p(exp(-x));
457 }
458 
459 // -log(e^-x - e^-y) = x - LogNegExp(y - x), assuming x > 0.0.
460 inline double LogNegExp(double x) {
461  DCHECK_GT(x, 0);
462  return log1p(-exp(-x));
463 }
464 
465 // a +_log b = -log(e^-a + e^-b) = KahanLogSum(a, b, ...).
466 // Kahan compensated summation provides an error bound that is
467 // independent of the number of addends. Assumes b >= a;
468 // c is the compensation.
469 inline double KahanLogSum(double a, double b, double *c) {
470  DCHECK_GE(b, a);
471  double y = -LogPosExp(b - a) - *c;
472  double t = a + y;
473  *c = (t - a) - y;
474  return t;
475 }
476 
477 // a -_log b = -log(e^-a - e^-b) = KahanLogDiff(a, b, ...).
478 // Kahan compensated summation provides an error bound that is
479 // independent of the number of addends. Assumes b > a;
480 // c is the compensation.
481 inline double KahanLogDiff(double a, double b, double *c) {
482  DCHECK_GT(b, a);
483  double y = -LogNegExp(b - a) - *c;
484  double t = a + y;
485  *c = (t - a) - y;
486  return t;
487 }
488 
489 } // namespace internal
490 
491 template <class T>
493  const LogWeightTpl<T> &w2) {
494  using Limits = FloatLimits<T>;
495  const T f1 = w1.Value();
496  const T f2 = w2.Value();
497  if (f1 == Limits::PosInfinity()) {
498  return w2;
499  } else if (f2 == Limits::PosInfinity()) {
500  return w1;
501  } else if (f1 > f2) {
502  return LogWeightTpl<T>(f2 - internal::LogPosExp(f1 - f2));
503  } else {
504  return LogWeightTpl<T>(f1 - internal::LogPosExp(f2 - f1));
505  }
506 }
507 
509  const LogWeightTpl<float> &w2) {
510  return Plus<float>(w1, w2);
511 }
512 
514  const LogWeightTpl<double> &w2) {
515  return Plus<double>(w1, w2);
516 }
517 
518 template <class T>
520  const LogWeightTpl<T> &w2) {
521  // The comments for Times(Tropical...) above apply here unchanged.
522  return LogWeightTpl<T>(w1.Value() + w2.Value());
523 }
524 
526  const LogWeightTpl<float> &w2) {
527  return Times<float>(w1, w2);
528 }
529 
531  const LogWeightTpl<double> &w2) {
532  return Times<double>(w1, w2);
533 }
534 
535 template <class T>
537  const LogWeightTpl<T> &w2,
538  DivideType typ = DIVIDE_ANY) {
539  // The comments for Divide(Tropical...) above apply here unchanged.
540  using Weight = LogWeightTpl<T>;
541  return w2.Member() ? Weight(w1.Value() - w2.Value()) : Weight::NoWeight();
542 }
543 
545  const LogWeightTpl<float> &w2,
546  DivideType typ = DIVIDE_ANY) {
547  return Divide<float>(w1, w2, typ);
548 }
549 
551  const LogWeightTpl<double> &w2,
552  DivideType typ = DIVIDE_ANY) {
553  return Divide<double>(w1, w2, typ);
554 }
555 
556 // The comments for Power<>(Tropical...) above apply here unchanged.
557 
558 template <class T, class V,
559  bool Enable = !std::is_same<V, size_t>::value,
560  typename std::enable_if<Enable>::type * = nullptr>
561 constexpr LogWeightTpl<T> Power(const LogWeightTpl<T> &w, V n) {
562  using Weight = LogWeightTpl<T>;
563  return (!w.Member() || n != n) ? Weight::NoWeight()
564  : (n == 0 || w == Weight::One()) ? Weight::One()
565  : Weight(w.Value() * n);
566 }
567 
568 // Specializes the library-wide template to use the above implementation; rules
569 // of function template instantiation require this be a full instantiation.
570 
571 template <>
572 constexpr LogWeightTpl<float> Power<LogWeightTpl<float>>(
573  const LogWeightTpl<float> &weight, size_t n) {
574  return Power<float, size_t, true>(weight, n);
575 }
576 
577 template <>
578 constexpr LogWeightTpl<double> Power<LogWeightTpl<double>>(
579  const LogWeightTpl<double> &weight, size_t n) {
580  return Power<double, size_t, true>(weight, n);
581 }
582 
583 // Specialization using the Kahan compensated summation.
584 template <class T>
585 class Adder<LogWeightTpl<T>> {
586  public:
588 
589  explicit Adder(Weight w = Weight::Zero())
590  : sum_(w.Value()),
591  c_(0.0) { }
592 
593  Weight Add(const Weight &w) {
594  using Limits = FloatLimits<T>;
595  const T f = w.Value();
596  if (f == Limits::PosInfinity()) {
597  return Sum();
598  } else if (sum_ == Limits::PosInfinity()) {
599  sum_ = f;
600  c_ = 0.0;
601  } else if (f > sum_) {
602  sum_ = internal::KahanLogSum(sum_, f, &c_);
603  } else {
604  sum_ = internal::KahanLogSum(f, sum_, &c_);
605  }
606  return Sum();
607  }
608 
609  Weight Sum() { return Weight(sum_); }
610 
611  void Reset(Weight w = Weight::Zero()) {
612  sum_ = w.Value();
613  c_ = 0.0;
614  }
615 
616  private:
617  double sum_;
618  double c_; // Kahan compensation.
619 };
620 
621 // MinMax semiring: (min, max, inf, -inf).
622 template <class T>
623 class MinMaxWeightTpl : public FloatWeightTpl<T> {
624  public:
625  using typename FloatWeightTpl<T>::ValueType;
629 
630  MinMaxWeightTpl() noexcept : FloatWeightTpl<T>() {}
631 
632  constexpr MinMaxWeightTpl(T f) : FloatWeightTpl<T>(f) {} // NOLINT
633 
634  static constexpr MinMaxWeightTpl Zero() { return Limits::PosInfinity(); }
635 
636  static constexpr MinMaxWeightTpl One() { return Limits::NegInfinity(); }
637 
638  static constexpr MinMaxWeightTpl NoWeight() { return Limits::NumberBad(); }
639 
640  static const string &Type() {
641  static const string *const type =
642  new string(string("minmax") + FloatWeightTpl<T>::GetPrecisionString());
643  return *type;
644  }
645 
646  // Fails for IEEE NaN.
647  constexpr bool Member() const { return Value() == Value(); }
648 
649  MinMaxWeightTpl<T> Quantize(float delta = kDelta) const {
650  // If one of infinities, or a NaN.
651  if (!Member() ||
652  Value() == Limits::NegInfinity() || Value() == Limits::PosInfinity()) {
653  return *this;
654  } else {
655  return MinMaxWeightTpl<T>(std::floor(Value() / delta + 0.5F) * delta);
656  }
657  }
658 
659  constexpr MinMaxWeightTpl<T> Reverse() const { return *this; }
660 
661  static constexpr uint64 Properties() {
663  }
664 };
665 
666 // Single-precision min-max weight.
668 
669 // Min.
670 template <class T>
672  const MinMaxWeightTpl<T> &w2) {
673  return (!w1.Member() || !w2.Member()) ? MinMaxWeightTpl<T>::NoWeight()
674  : w1.Value() < w2.Value() ? w1 : w2;
675 }
676 
678  const MinMaxWeightTpl<float> &w2) {
679  return Plus<float>(w1, w2);
680 }
681 
683  const MinMaxWeightTpl<double> &w2) {
684  return Plus<double>(w1, w2);
685 }
686 
687 // Max.
688 template <class T>
690  const MinMaxWeightTpl<T> &w2) {
691  return (!w1.Member() || !w2.Member()) ? MinMaxWeightTpl<T>::NoWeight()
692  : w1.Value() >= w2.Value() ? w1 : w2;
693 }
694 
696  const MinMaxWeightTpl<float> &w2) {
697  return Times<float>(w1, w2);
698 }
699 
701  const MinMaxWeightTpl<double> &w2) {
702  return Times<double>(w1, w2);
703 }
704 
705 // Defined only for special cases.
706 template <class T>
708  const MinMaxWeightTpl<T> &w2,
709  DivideType typ = DIVIDE_ANY) {
710  return w1.Value() >= w2.Value() ? w1 : MinMaxWeightTpl<T>::NoWeight();
711 }
712 
714  const MinMaxWeightTpl<float> &w2,
715  DivideType typ = DIVIDE_ANY) {
716  return Divide<float>(w1, w2, typ);
717 }
718 
720  const MinMaxWeightTpl<double> &w2,
721  DivideType typ = DIVIDE_ANY) {
722  return Divide<double>(w1, w2, typ);
723 }
724 
725 // Converts to tropical.
726 template <>
728  constexpr TropicalWeight operator()(const LogWeight &w) const {
729  return w.Value();
730  }
731 };
732 
733 template <>
735  constexpr TropicalWeight operator()(const Log64Weight &w) const {
736  return w.Value();
737  }
738 };
739 
740 // Converts to log.
741 template <>
743  constexpr LogWeight operator()(const TropicalWeight &w) const {
744  return w.Value();
745  }
746 };
747 
748 template <>
750  constexpr LogWeight operator()(const Log64Weight &w) const {
751  return w.Value();
752  }
753 };
754 
755 // Converts to log64.
756 template <>
758  constexpr Log64Weight operator()(const TropicalWeight &w) const {
759  return w.Value();
760  }
761 };
762 
763 template <>
765  constexpr Log64Weight operator()(const LogWeight &w) const {
766  return w.Value();
767  }
768 };
769 
770 // This function object returns random integers chosen from [0,
771 // num_random_weights). The boolean 'allow_zero' determines whether Zero() and
772 // zero divisors should be returned in the random weight generation. This is
773 // intended primary for testing.
774 template <class Weight>
776  public:
778  bool allow_zero = true,
779  const size_t num_random_weights = kNumRandomWeights)
780  : allow_zero_(allow_zero), num_random_weights_(num_random_weights) {}
781 
782  Weight operator()() const {
783  const int n = rand() % (num_random_weights_ + allow_zero_); // NOLINT
784  if (allow_zero_ && n == num_random_weights_) return Weight::Zero();
785  return Weight(n);
786  }
787 
788  private:
789  // Permits Zero() and zero divisors.
790  const bool allow_zero_;
791  // Number of alternative random weights.
792  const size_t num_random_weights_;
793 };
794 
795 template <class T>
797  : public FloatWeightGenerate<TropicalWeightTpl<T>> {
798  public:
801 
802  explicit WeightGenerate(bool allow_zero = true,
803  size_t num_random_weights = kNumRandomWeights)
804  : Generate(allow_zero, num_random_weights) {}
805 
806  Weight operator()() const { return Weight(Generate::operator()()); }
807 };
808 
809 template <class T>
811  : public FloatWeightGenerate<LogWeightTpl<T>> {
812  public:
815 
816  explicit WeightGenerate(bool allow_zero = true,
817  size_t num_random_weights = kNumRandomWeights)
818  : Generate(allow_zero, num_random_weights) {}
819 
820  Weight operator()() const { return Weight(Generate::operator()()); }
821 };
822 
823 // This function object returns random integers chosen from [0,
824 // num_random_weights). The boolean 'allow_zero' determines whether Zero() and
825 // zero divisors should be returned in the random weight generation. This is
826 // intended primary for testing.
827 template <class T>
829  public:
831 
832  explicit WeightGenerate(bool allow_zero = true,
833  size_t num_random_weights = kNumRandomWeights)
834  : allow_zero_(allow_zero), num_random_weights_(num_random_weights) {}
835 
836  Weight operator()() const {
837  const int n = (rand() % // NOLINT
838  (2 * num_random_weights_ + allow_zero_)) -
839  num_random_weights_;
840  if (allow_zero_ && n == num_random_weights_) {
841  return Weight::Zero();
842  } else if (n == -num_random_weights_) {
843  return Weight::One();
844  } else {
845  return Weight(n);
846  }
847  }
848 
849  private:
850  // Permits Zero() and zero divisors.
851  const bool allow_zero_;
852  // Number of alternative random weights.
853  const size_t num_random_weights_;
854 };
855 
856 } // namespace fst
857 
858 #endif // FST_FLOAT_WEIGHT_H_
WeightGenerate(bool allow_zero=true, size_t num_random_weights=kNumRandomWeights)
Definition: float-weight.h:802
ExpectationWeight< X1, X2 > Divide(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2, DivideType typ=DIVIDE_ANY)
void Reset(Weight w=Weight::Zero())
Definition: float-weight.h:611
static constexpr TropicalWeightTpl< T > Zero()
Definition: float-weight.h:192
constexpr TropicalWeight operator()(const LogWeight &w) const
Definition: float-weight.h:728
uint64_t uint64
Definition: types.h:32
constexpr Log64Weight operator()(const LogWeight &w) const
Definition: float-weight.h:765
static constexpr uint64 Properties()
Definition: float-weight.h:661
WeightGenerate(bool allow_zero=true, size_t num_random_weights=kNumRandomWeights)
Definition: float-weight.h:832
constexpr uint64 kRightSemiring
Definition: weight.h:115
ExpectationWeight< X1, X2 > Times(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
static constexpr LogWeightTpl Zero()
Definition: float-weight.h:413
static constexpr MinMaxWeightTpl NoWeight()
Definition: float-weight.h:638
static constexpr MinMaxWeightTpl One()
Definition: float-weight.h:636
constexpr uint64 kCommutative
Definition: weight.h:120
#define DCHECK_GT(x, y)
Definition: log.h:73
std::ostream & Write(std::ostream &strm) const
Definition: float-weight.h:57
WeightGenerate(bool allow_zero=true, size_t num_random_weights=kNumRandomWeights)
Definition: float-weight.h:816
constexpr uint64 kLeftSemiring
Definition: weight.h:112
Weight operator()() const
Definition: float-weight.h:782
constexpr Log64Weight operator()(const TropicalWeight &w) const
Definition: float-weight.h:758
void SetValue(const T &f)
Definition: float-weight.h:74
static const string & Type()
Definition: float-weight.h:640
static constexpr uint64 Properties()
Definition: float-weight.h:238
static constexpr T PosInfinity()
Definition: float-weight.h:29
TropicalWeightTpl< T > Quantize(float delta=kDelta) const
Definition: float-weight.h:228
std::ostream & WriteType(std::ostream &strm, const T t)
Definition: util.h:155
static constexpr LogWeightTpl One()
Definition: float-weight.h:415
static constexpr TropicalWeightTpl< T > One()
Definition: float-weight.h:194
constexpr bool FloatApproxEqual(T w1, T w2, float delta=kDelta)
Definition: float-weight.h:135
constexpr FloatWeightTpl(T f)
Definition: float-weight.h:46
static constexpr T NumberBad()
Definition: float-weight.h:35
FloatWeightGenerate(bool allow_zero=true, const size_t num_random_weights=kNumRandomWeights)
Definition: float-weight.h:777
std::istream & operator>>(std::istream &strm, FloatWeightTpl< T > &w)
Definition: float-weight.h:160
constexpr TropicalWeightTpl< T > Reverse() const
Definition: float-weight.h:236
static constexpr const char * GetPrecisionString()
Definition: float-weight.h:76
bool operator==(const PdtStateTuple< S, K > &x, const PdtStateTuple< S, K > &y)
Definition: pdt.h:133
constexpr LogWeight operator()(const TropicalWeight &w) const
Definition: float-weight.h:743
MinMaxWeightTpl< T > Quantize(float delta=kDelta) const
Definition: float-weight.h:649
static constexpr LogWeightTpl NoWeight()
Definition: float-weight.h:417
constexpr uint64 kIdempotent
Definition: weight.h:123
ExpectationWeight< X1, X2 > Plus(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
Adder(Weight w=Weight::Zero())
Definition: float-weight.h:589
std::ostream & operator<<(std::ostream &strm, const FloatWeightTpl< T > &w)
Definition: float-weight.h:146
constexpr MinMaxWeightTpl(T f)
Definition: float-weight.h:632
LogWeightTpl< T > Quantize(float delta=kDelta) const
Definition: float-weight.h:430
constexpr bool operator!=(const FloatWeightTpl< T > &w1, const FloatWeightTpl< T > &w2)
Definition: float-weight.h:119
static constexpr TropicalWeightTpl< T > NoWeight()
Definition: float-weight.h:196
constexpr LogWeightTpl< T > Reverse() const
Definition: float-weight.h:438
double LogPosExp(double x)
Definition: float-weight.h:454
double KahanLogSum(double a, double b, double *c)
Definition: float-weight.h:469
TropicalWeightTpl() noexcept
Definition: float-weight.h:188
std::istream & Read(std::istream &strm)
Definition: float-weight.h:55
Weight Add(const Weight &w)
Definition: float-weight.h:593
LogWeightTpl() noexcept
Definition: float-weight.h:409
constexpr bool Member() const
Definition: float-weight.h:207
FloatWeightTpl() noexcept
Definition: float-weight.h:44
double LogNegExp(double x)
Definition: float-weight.h:460
MinMaxWeightTpl() noexcept
Definition: float-weight.h:630
constexpr bool Member() const
Definition: float-weight.h:647
constexpr uint64 kPath
Definition: weight.h:126
constexpr bool ApproxEqual(const FloatWeightTpl< T > &w1, const FloatWeightTpl< T > &w2, float delta=kDelta)
Definition: float-weight.h:140
constexpr bool Member() const
Definition: float-weight.h:425
size_t Hash() const
Definition: float-weight.h:61
constexpr size_t kNumRandomWeights
Definition: weight.h:130
static const string & Type()
Definition: float-weight.h:200
static constexpr uint64 Properties()
Definition: float-weight.h:440
static constexpr MinMaxWeightTpl Zero()
Definition: float-weight.h:634
constexpr TropicalWeight operator()(const Log64Weight &w) const
Definition: float-weight.h:735
std::istream & ReadType(std::istream &strm, T *t)
Definition: util.h:47
constexpr MinMaxWeightTpl< T > Reverse() const
Definition: float-weight.h:659
#define DCHECK(x)
Definition: log.h:70
constexpr TropicalWeightTpl< T > Power(const TropicalWeightTpl< T > &w, V n)
Definition: float-weight.h:377
#define DCHECK_GE(x, y)
Definition: log.h:75
constexpr LogWeight operator()(const Log64Weight &w) const
Definition: float-weight.h:750
static const string & Type()
Definition: float-weight.h:419
DivideType
Definition: weight.h:142
constexpr float kDelta
Definition: weight.h:109
constexpr const T & Value() const
Definition: float-weight.h:71
constexpr LogWeightTpl(T f)
Definition: float-weight.h:411
constexpr TropicalWeightTpl(T f)
Definition: float-weight.h:190
double KahanLogDiff(double a, double b, double *c)
Definition: float-weight.h:481
static constexpr T NegInfinity()
Definition: float-weight.h:33