FST  openfst-1.7.3 OpenFst Library
sparse-power-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 // Cartesian power weight semiring operation definitions, using
5 // SparseTupleWeight as underlying representation.
6
7 #ifndef FST_SPARSE_POWER_WEIGHT_H_
8 #define FST_SPARSE_POWER_WEIGHT_H_
9
10 #include <climits>
11 #include <string>
12
14 #include <fst/weight.h>
15
16
17 namespace fst {
18
19 // Sparse cartesian power semiring: W ^ n
20 //
21 // Forms:
22 //
23 // - a left semimodule when W is a left semiring,
24 // - a right semimodule when W is a right semiring,
25 // - a bisemimodule when W is a semiring,
26 // the free semimodule of rank n over W
27 //
28 // The Times operation is overloaded to provide the left and right scalar
29 // products.
30 //
31 // K is the key value type. kNoKey (-1) is reserved for internal use
32 template <class W, class K = int>
33 class SparsePowerWeight : public SparseTupleWeight<W, K> {
34  public:
37
39
40  explicit SparsePowerWeight(const Base &weight)
41  : Base(weight) {}
42
43  template <class Iterator>
45  : Base(begin, end) {}
46
47  // Initialize component `key` to `weight`, with `default_weight` for all
48  // other components.
49  SparsePowerWeight(const K &key, const W &weight,
50  const W &default_weight = W::Zero())
51  : Base(key, weight, default_weight) {}
52
53  static const SparsePowerWeight &Zero() {
54  static const SparsePowerWeight zero(Base::Zero());
55  return zero;
56  }
57
58  static const SparsePowerWeight &One() {
59  static const SparsePowerWeight one(Base::One());
60  return one;
61  }
62
63  static const SparsePowerWeight &NoWeight() {
64  static const SparsePowerWeight no_weight(
65  Base::NoWeight());
66  return no_weight;
67  }
68
69  // Overide this: Overwrite the Type method to reflect the key type if using
70  // a non-default key type.
71  static const std::string &Type() {
72  static const std::string *const type = [] {
73  std::string type = W::Type() + "_^n";
74  if (sizeof(K) != sizeof(uint32)) {
75  type += "_" + std::to_string(CHAR_BIT * sizeof(K));
76  }
77  return new std::string(type);
78  }();
79  return *type;
80  }
81
82  static constexpr uint64 Properties() {
83  return W::Properties() &
85  }
86
87  SparsePowerWeight Quantize(float delta = kDelta) const {
88  return SparsePowerWeight(Base::Quantize(delta));
89  }
90
92  return ReverseWeight(Base::Reverse());
93  }
94 };
95
96 template <class W, class K, class M>
98  const SparsePowerWeight<W, K> &w1,
99  const SparsePowerWeight<W, K> &w2,
100  const M &operator_mapper) {
102  SparseTupleWeightMap(&result, w1, w2, operator_mapper);
103  return result;
104 }
105
106 // Semimodule plus operation.
107 template <class W, class K>
109  const SparsePowerWeight<W, K> &w2) {
110  return SparsePowerWeightMap(w1, w2, [](const K &k, const W &v1, const W &v2) {
111  return Plus(v1, v2);
112  });
113 }
114
115 // Semimodule times operation.
116 template <class W, class K>
118  const SparsePowerWeight<W, K> &w2) {
119  return SparsePowerWeightMap(w1, w2, [](const K &k, const W &v1, const W &v2) {
120  return Times(v1, v2);
121  });
122 }
123
124 // Semimodule divide operation.
125 template <class W, class K>
127  const SparsePowerWeight<W, K> &w2,
128  DivideType type = DIVIDE_ANY) {
129  return SparsePowerWeightMap(w1, w2,
130  [type](const K &k, const W &v1, const W &v2) {
131  return Divide(v1, v2, type);
132  });
133 }
134
135 // Semimodule dot product operation.
136 template <class W, class K>
137 inline const W &DotProduct(const SparsePowerWeight<W, K> &w1,
138  const SparsePowerWeight<W, K> &w2) {
139  const SparsePowerWeight<W, K> product = Times(w1, w2);
140  W result(W::Zero());
141  for (SparseTupleWeightIterator<W, K> it(product); !it.Done(); it.Next()) {
142  result = Plus(result, it.Value().second);
143  }
144  return result;
145 }
146
147 template <class W, class K>
148 inline bool ApproxEqual(const SparsePowerWeight<W, K> &w1,
149  const SparsePowerWeight<W, K> &w2,
150  float delta = kDelta) {
151  auto result = SparsePowerWeightMap(
152  w1, w2, [delta](const K &k, const W &v1, const W &v2) {
153  return ApproxEqual(v1, v2, delta) ? W::One() : W::Zero();
154  });
155  return result == SparsePowerWeight<W, K>::One();
156 }
157
158 template <class W, class K>
159 inline SparsePowerWeight<W, K> Times(const W &k,
160  const SparsePowerWeight<W, K> &w2) {
161  const SparseTupleWeight<W, K> t2(k);
162  const SparsePowerWeight<W, K> w1(t2);
163  return Times(w1, w2);
164 }
165
166 template <class W, class K>
168  const W &k) {
169  const SparseTupleWeight<W, K> t2(k);
170  const SparsePowerWeight<W, K> w2(t2);
171  return Times(w1, w2);
172 }
173
174 template <class W, class K>
176  const W &k,
177  DivideType divide_type = DIVIDE_ANY) {
178  const SparseTupleWeight<W, K> t2(k);
179  const SparsePowerWeight<W, K> w2(t2);
180  return Divide(w1, w2, divide_type);
181 }
182
183 // This function object generates weights over the Cartesian power of rank
184 // n over the underlying weight. This is intended primarily for testing.
185 template <class W, class K>
187  public:
190
191  explicit WeightGenerate(bool allow_zero = true,
192  size_t sparse_power_rank = 3)
193  : generate_(allow_zero), sparse_power_rank_(sparse_power_rank) {}
194
195  Weight operator()() const {
196  Weight weight;
197  for (size_t i = 1; i <= sparse_power_rank_; ++i) {
198  weight.PushBack(i, generate_(), true);
199  }
200  return weight;
201  }
202
203  private:
204  const Generate generate_;
205  const size_t sparse_power_rank_;
206 };
207
208 } // namespace fst
209
210 #endif // FST_SPARSE_POWER_WEIGHT_H_
void PushBack(const K &key, const W &weight, bool default_value_check=true)
SparsePowerWeight(const K &key, const W &weight, const W &default_weight=W::Zero())
static const SparsePowerWeight & NoWeight()
ExpectationWeight< X1, X2 > Divide(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2, DivideType typ=DIVIDE_ANY)
uint64_t uint64
Definition: types.h:32
static const SparsePowerWeight & One()
static constexpr uint64 Properties()
constexpr uint64 kRightSemiring
Definition: weight.h:115
void SparseTupleWeightMap(SparseTupleWeight< W, K > *result, const SparseTupleWeight< W, K > &w1, const SparseTupleWeight< W, K > &w2, const M &operator_mapper)
static const SparseTupleWeight & Zero()
ExpectationWeight< X1, X2 > Times(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
static const SparseTupleWeight & One()
constexpr uint64 kCommutative
Definition: weight.h:120
constexpr uint64 kLeftSemiring
Definition: weight.h:112
SparsePowerWeight< W, K > SparsePowerWeightMap(const SparsePowerWeight< W, K > &w1, const SparsePowerWeight< W, K > &w2, const M &operator_mapper)
static const SparseTupleWeight & NoWeight()
SparsePowerWeight(Iterator begin, Iterator end)
SparsePowerWeight Quantize(float delta=kDelta) const
W DotProduct(const PowerWeight< W, n > &w1, const PowerWeight< W, n > &w2)
Definition: power-weight.h:138
static const SparsePowerWeight & Zero()
SparsePowerWeight< typename W::ReverseWeight, K > ReverseWeight
constexpr uint64 kIdempotent
Definition: weight.h:123
ExpectationWeight< X1, X2 > Plus(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
static const std::string & Type()
uint32_t uint32
Definition: types.h:31
constexpr bool ApproxEqual(const FloatWeightTpl< T > &w1, const FloatWeightTpl< T > &w2, float delta=kDelta)
Definition: float-weight.h:140
SparseTupleWeight Quantize(float delta=kDelta) const
SparsePowerWeight(const Base &weight)
WeightGenerate(bool allow_zero=true, size_t sparse_power_rank=3)
DivideType
Definition: weight.h:142
ReverseWeight Reverse() const
constexpr float kDelta
Definition: weight.h:109
ReverseWeight Reverse() const