FST  openfst-1.7.3
OpenFst Library
sparse-tuple-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 // Sparse version of tuple-weight, based on tuple-weight.h.
5 // Internally stores sparse key, value pairs in linked list. The default value
6 // element is the assumed value of unset keys. Internal singleton
7 // implementation that stores first key, value pair as a initialized member
8 // variable to avoid unnecessary allocation on heap. Use
9 // SparseTupleWeightIterator to iterate through the key,value pairs. Note:
10 // this does NOT iterate through the default value.
11 //
12 // Sparse tuple weight set operation definitions.
13 
14 #ifndef FST_SPARSE_TUPLE_WEIGHT_H_
15 #define FST_SPARSE_TUPLE_WEIGHT_H_
16 
17 #include <algorithm>
18 #include <list>
19 #include <stack>
20 #include <string>
21 #include <unordered_map>
22 #include <utility>
23 
24 
25 #include <fst/weight.h>
26 
27 
28 namespace fst {
29 
30 template <class W, class K>
32 
33 // Arbitrary dimension tuple weight, stored as a sorted linked-list.
34 // W is any weight class, and K is the key value type. kNoKey (-1) is reserved
35 // for internal use.
36 template <class W, class K = int>
38  public:
40 
42  using Pair = std::pair<K, W>;
43  using Weight = W;
44  using Index = K;
45 
46  constexpr static K kNoKey = -1;
47 
49 
50  ~SparseTupleWeight() noexcept = default;
51 
52  template <class Iterator>
54  Init();
55  // Assumes input iterator is sorted.
56  for (auto it = begin; it != end; ++it) PushBack(*it);
57  }
58 
59  // Initialize component `key` to `weight`, with `default_weight` for all
60  // other components.
61  SparseTupleWeight(const K &key, const W &weight, const W &default_weight)
62  : default_(default_weight),
63  first_(weight == default_weight ? kNoKey : key, weight) {}
64 
65  explicit SparseTupleWeight(const W &weight) { Init(weight); }
66 
68  Init(weight.DefaultValue());
69  SetDefaultValue(weight.DefaultValue());
70  for (Iterator it(weight); !it.Done(); it.Next()) {
71  PushBack(it.Value());
72  }
73  }
74 
76  // Don't move the default, so weight.default_ is still valid.
77  : default_(weight.default_), // NOLINT
78  first_(std::move(weight.first_)),
79  rest_(std::move(weight.rest_)) {
80  // move leaves the source in a valid but unspecified state.
81  // Make sure the source weight is empty.
82  weight.first_ = Pair(kNoKey, W::NoWeight());
83  weight.rest_.clear();
84  }
85 
86  static const SparseTupleWeight &Zero() {
87  static const SparseTupleWeight zero(W::Zero());
88  return zero;
89  }
90 
91  static const SparseTupleWeight &One() {
92  static const SparseTupleWeight one(W::One());
93  return one;
94  }
95 
96  static const SparseTupleWeight &NoWeight() {
97  static const SparseTupleWeight no_weight(W::NoWeight());
98  return no_weight;
99  }
100 
101  std::istream &Read(std::istream &strm) {
102  ReadType(strm, &default_);
103  ReadType(strm, &first_);
104  return ReadType(strm, &rest_);
105  }
106 
107  std::ostream &Write(std::ostream &strm) const {
108  WriteType(strm, default_);
109  WriteType(strm, first_);
110  return WriteType(strm, rest_);
111  }
112 
114  if (this == &weight) return *this; // Checks for identity.
115  Init(weight.DefaultValue());
116  for (Iterator it(weight); !it.Done(); it.Next()) {
117  PushBack(it.Value());
118  }
119  return *this;
120  }
121 
123  if (this == &weight) return *this; // Checks for identity.
124  // Don't move the default, so weight.default_ is still valid.
125  default_ = weight.default_;
126  first_ = std::move(weight.first_);
127  rest_ = std::move(weight.rest_);
128  // move leaves the source in a valid but unspecified state.
129  // Make sure the source weight is empty.
130  weight.first_ = Pair(kNoKey, W::NoWeight());
131  weight.rest_.clear();
132  return *this;
133  }
134 
135  bool Member() const {
136  if (!DefaultValue().Member()) return false;
137  for (Iterator it(*this); !it.Done(); it.Next()) {
138  if (!it.Value().second.Member()) return false;
139  }
140  return true;
141  }
142 
143  // Assumes H() function exists for the hash of the key value.
144  size_t Hash() const {
145  size_t h = 0;
146  static const std::hash<K> H;
147  for (Iterator it(*this); !it.Done(); it.Next()) {
148  h = 5 * h + H(it.Value().first);
149  h = 13 * h + it.Value().second.Hash();
150  }
151  return h;
152  }
153 
154  SparseTupleWeight Quantize(float delta = kDelta) const {
155  SparseTupleWeight weight;
156  for (Iterator it(*this); !it.Done(); it.Next()) {
157  weight.PushBack(it.Value().first, it.Value().second.Quantize(delta));
158  }
159  return weight;
160  }
161 
163  ReverseWeight weight(DefaultValue().Reverse());
164  for (Iterator it(*this); !it.Done(); it.Next()) {
165  weight.PushBack(it.Value().first, it.Value().second.Reverse());
166  }
167  return weight;
168  }
169 
170  void Init(const W &default_value = W::Zero()) {
171  first_ = Pair(kNoKey, W::NoWeight());
172  // Initialized to the reserved key value.
173  default_ = default_value;
174  rest_.clear();
175  }
176 
177  size_t Size() const {
178  if (first_.first == kNoKey) {
179  return 0;
180  } else {
181  return rest_.size() + 1;
182  }
183  }
184 
185  inline void PushBack(const K &key, const W &weight,
186  bool default_value_check = true) {
187  PushBack(std::make_pair(key, weight), default_value_check);
188  }
189 
190  inline void PushBack(const Pair &pair, bool default_value_check = true) {
191  if (default_value_check && pair.second == default_) return;
192  if (first_.first == kNoKey) {
193  first_ = pair;
194  } else {
195  rest_.push_back(pair);
196  }
197  }
198 
199  // Returns the `key`-th component, or the default value if not set.
200  const W &Value(const K &key) const {
201  // TODO(rybach): Consider binary search.
202  Iterator iter(*this);
203  for (; !iter.Done() && iter.Value().first < key; iter.Next()) continue;
204  return !iter.Done() && iter.Value().first == key ? iter.Value().second
205  : DefaultValue();
206  }
207 
208  void SetValue(const K &key, const W &w) {
209  if (w == DefaultValue()) {
210  ClearValue(key);
211  } else {
212  SetValueToNonDefault(key, w);
213  }
214  }
215 
216  void SetDefaultValue(const W &value) { default_ = value; }
217 
218  const W &DefaultValue() const { return default_; }
219 
220  private:
221  void SetValueToNonDefault(const K &key, const W &w) {
222  // Don't use SparseTupleWeightIterator, since that's const.
223  if (first_.first == kNoKey) {
224  first_ = Pair(key, w);
225  } else if (key < first_.first) {
226  rest_.push_front(first_);
227  first_ = Pair(key, w);
228  } else if (key == first_.first) {
229  first_.second = w;
230  } else {
231  const auto i =
232  std::find_if(rest_.begin(), rest_.end(),
233  [key](const Pair &p) { return p.first >= key; });
234  if (i != rest_.end() && i->first == key) {
235  i->second = w;
236  } else {
237  rest_.insert(i, Pair(key, w));
238  }
239  }
240  }
241 
242  // Removes the weight value for `key`, having the effect of setting
243  // it to `DefaultValue()`.
244  void ClearValue(const K &key) {
245  if (key == first_.first) {
246  if (!rest_.empty()) {
247  first_ = rest_.front();
248  rest_.pop_front();
249  } else {
250  first_.first = kNoKey;
251  }
252  } else if (key > first_.first) {
253  const auto i =
254  std::find_if(rest_.begin(), rest_.end(),
255  [key](const Pair &p) { return p.first >= key; });
256  if (i != rest_.end() && i->first == key) {
257  rest_.erase(i);
258  }
259  }
260  }
261 
262  // Assumed default value of uninitialized keys, by default W::Zero().
263  W default_;
264 
265  // Key values pairs are first stored in first_, then fill rest_ this way we
266  // can avoid dynamic allocation in the common case where the weight is a
267  // single key/value pair.
268  Pair first_;
269  std::list<Pair> rest_;
270 
271  friend class SparseTupleWeightIterator<W, K>;
272 };
273 
274 // Declare storage for kNoKey since it is passed by reference.
275 template <class W, class K>
277 
278 template <class W, class K>
280  public:
282  using const_iterator = typename std::list<Pair>::const_iterator;
283  using iterator = typename std::list<Pair>::iterator;
284 
286  : first_(weight.first_),
287  rest_(weight.rest_),
288  init_(true),
289  iter_(rest_.begin()) {}
290 
291  bool Done() const {
292  if (init_) {
293  return first_.first == SparseTupleWeight<W, K>::kNoKey;
294  } else {
295  return iter_ == rest_.end();
296  }
297  }
298 
299  const Pair &Value() const { return init_ ? first_ : *iter_; }
300 
301  void Next() {
302  if (init_) {
303  init_ = false;
304  } else {
305  ++iter_;
306  }
307  }
308 
309  void Reset() {
310  init_ = true;
311  iter_ = rest_.begin();
312  }
313 
314  private:
315  const Pair &first_;
316  const std::list<Pair> &rest_;
317  bool init_; // In the initialized state?
318  const_iterator iter_;
319 };
320 
321 // M must be callable as a function W(K, W, W).
322 // K will be kNoKey when mapping the default value.
323 template <class W, class K, class M>
325  const SparseTupleWeight<W, K> &w1,
326  const SparseTupleWeight<W, K> &w2,
327  const M &operator_mapper) {
330  const auto &v1_def = w1.DefaultValue();
331  const auto &v2_def = w2.DefaultValue();
332  result->SetDefaultValue(
333  operator_mapper(SparseTupleWeight<W, K>::kNoKey, v1_def, v2_def));
334  while (!w1_it.Done() || !w2_it.Done()) {
335  const auto &k1 = (w1_it.Done()) ? w2_it.Value().first : w1_it.Value().first;
336  const auto &k2 = (w2_it.Done()) ? w1_it.Value().first : w2_it.Value().first;
337  const auto &v1 = (w1_it.Done()) ? v1_def : w1_it.Value().second;
338  const auto &v2 = (w2_it.Done()) ? v2_def : w2_it.Value().second;
339  if (k1 == k2) {
340  result->PushBack(k1, operator_mapper(k1, v1, v2));
341  if (!w1_it.Done()) w1_it.Next();
342  if (!w2_it.Done()) w2_it.Next();
343  } else if (k1 < k2) {
344  result->PushBack(k1, operator_mapper(k1, v1, v2_def));
345  w1_it.Next();
346  } else {
347  result->PushBack(k2, operator_mapper(k2, v1_def, v2));
348  w2_it.Next();
349  }
350  }
351 }
352 
353 template <class W, class K>
354 inline bool operator==(const SparseTupleWeight<W, K> &w1,
355  const SparseTupleWeight<W, K> &w2) {
356  const auto &v1_def = w1.DefaultValue();
357  const auto &v2_def = w2.DefaultValue();
358  if (v1_def != v2_def) return false;
361  while (!w1_it.Done() || !w2_it.Done()) {
362  const auto &k1 = (w1_it.Done()) ? w2_it.Value().first : w1_it.Value().first;
363  const auto &k2 = (w2_it.Done()) ? w1_it.Value().first : w2_it.Value().first;
364  const auto &v1 = (w1_it.Done()) ? v1_def : w1_it.Value().second;
365  const auto &v2 = (w2_it.Done()) ? v2_def : w2_it.Value().second;
366  if (k1 == k2) {
367  if (v1 != v2) return false;
368  if (!w1_it.Done()) w1_it.Next();
369  if (!w2_it.Done()) w2_it.Next();
370  } else if (k1 < k2) {
371  if (v1 != v2_def) return false;
372  w1_it.Next();
373  } else {
374  if (v1_def != v2) return false;
375  w2_it.Next();
376  }
377  }
378  return true;
379 }
380 
381 template <class W, class K>
382 inline bool operator!=(const SparseTupleWeight<W, K> &w1,
383  const SparseTupleWeight<W, K> &w2) {
384  return !(w1 == w2);
385 }
386 
387 template <class W, class K>
388 inline std::ostream &operator<<(std::ostream &strm,
389  const SparseTupleWeight<W, K> &weight) {
390  CompositeWeightWriter writer(strm);
391  writer.WriteBegin();
392  writer.WriteElement(weight.DefaultValue());
393  for (SparseTupleWeightIterator<W, K> it(weight); !it.Done(); it.Next()) {
394  writer.WriteElement(it.Value().first);
395  writer.WriteElement(it.Value().second);
396  }
397  writer.WriteEnd();
398  return strm;
399 }
400 
401 template <class W, class K>
402 inline std::istream &operator>>(std::istream &strm,
403  SparseTupleWeight<W, K> &weight) {
404  CompositeWeightReader reader(strm);
405  reader.ReadBegin();
406  W def;
407  bool more = reader.ReadElement(&def);
408  weight.Init(def);
409  while (more) {
410  K key;
411  reader.ReadElement(&key);
412  W v;
413  more = reader.ReadElement(&v);
414  weight.PushBack(key, v);
415  }
416  reader.ReadEnd();
417  return strm;
418 }
419 
420 } // namespace fst
421 
422 #endif // FST_SPARSE_TUPLE_WEIGHT_H_
void PushBack(const Pair &pair, bool default_value_check=true)
void PushBack(const K &key, const W &weight, bool default_value_check=true)
~SparseTupleWeight() noexcept=default
SparseTupleWeight & operator=(SparseTupleWeight &&weight) noexcept
void Init(const W &default_value=W::Zero())
std::ostream & Write(std::ostream &strm) const
std::pair< K, typename Arc::Weight > Pair
void SparseTupleWeightMap(SparseTupleWeight< W, K > *result, const SparseTupleWeight< W, K > &w1, const SparseTupleWeight< W, K > &w2, const M &operator_mapper)
static const SparseTupleWeight & Zero()
static const SparseTupleWeight & One()
SparseTupleWeightIterator(const SparseTupleWeight< W, K > &weight)
static const SparseTupleWeight & NoWeight()
void SetValue(const K &key, const W &w)
std::ostream & WriteType(std::ostream &strm, const T t)
Definition: util.h:155
std::istream & operator>>(std::istream &strm, FloatWeightTpl< T > &w)
Definition: float-weight.h:160
SparseTupleWeight(Iterator begin, Iterator end)
SparseTupleWeight(const K &key, const W &weight, const W &default_weight)
bool operator==(const PdtStateTuple< S, K > &x, const PdtStateTuple< S, K > &y)
Definition: pdt.h:133
void SetDefaultValue(const W &value)
std::ostream & operator<<(std::ostream &strm, const FloatWeightTpl< T > &w)
Definition: float-weight.h:146
static constexpr K kNoKey
SparseTupleWeight(const W &weight)
constexpr bool operator!=(const FloatWeightTpl< T > &w1, const FloatWeightTpl< T > &w2)
Definition: float-weight.h:119
typename SparseTupleWeight< W, K >::Pair Pair
const W & DefaultValue() const
SparseTupleWeight & operator=(const SparseTupleWeight &weight)
SparseTupleWeight(const SparseTupleWeight &weight)
typename std::list< Pair >::const_iterator const_iterator
std::istream & Read(std::istream &strm)
bool ReadElement(T *comp, bool last=false)
Definition: weight.h:351
const W & Value(const K &key) const
SparseTupleWeight Quantize(float delta=kDelta) const
typename std::list< Pair >::iterator iterator
std::istream & ReadType(std::istream &strm, T *t)
Definition: util.h:47
void WriteElement(const T &comp)
Definition: weight.h:301
SparseTupleWeight(SparseTupleWeight &&weight) noexcept
ReverseWeight Reverse() const
constexpr float kDelta
Definition: weight.h:109