sparse-power-weight.h revision f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2 
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