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
32 namespace fst {
33
34 // Below SparseTupleWeight*Mapper are used in conjunction with
35 // SparseTupleWeightMap to compute the respective semiring operations
36 template<class W, class K>
37 struct SparseTupleWeightPlusMapper {
MapSparseTupleWeightPlusMapper38 W Map(const K& k, const W& v1, const W& v2) const {
39 return Plus(v1, v2);
40 }
41 };
42
43 template<class W, class K>
44 struct SparseTupleWeightTimesMapper {
MapSparseTupleWeightTimesMapper45 W Map(const K& k, const W& v1, const W& v2) const {
46 return Times(v1, v2);
47 }
48 };
49
50 template<class W, class K>
51 struct SparseTupleWeightDivideMapper {
SparseTupleWeightDivideMapperSparseTupleWeightDivideMapper52 SparseTupleWeightDivideMapper(DivideType divide_type) {
53 divide_type_ = divide_type;
54 }
MapSparseTupleWeightDivideMapper55 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
61 template<class W, class K>
62 struct SparseTupleWeightApproxMapper {
SparseTupleWeightApproxMapperSparseTupleWeightApproxMapper63 SparseTupleWeightApproxMapper(float delta) { delta_ = delta; }
MapSparseTupleWeightApproxMapper64 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
79 template <class W, class K = int>
80 class 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
SparsePowerWeight()90 SparsePowerWeight() {}
91
SparsePowerWeight(const SparseTupleWeight<W,K> & w)92 SparsePowerWeight(const SparseTupleWeight<W, K> &w) :
93 SparseTupleWeight<W, K>(w) { }
94
95 template <class Iterator>
SparsePowerWeight(Iterator begin,Iterator end)96 SparsePowerWeight(Iterator begin, Iterator end) :
97 SparseTupleWeight<W, K>(begin, end) { }
98
SparsePowerWeight(const K & key,const W & w)99 SparsePowerWeight(const K &key, const W &w) :
100 SparseTupleWeight<W, K>(key, w) { }
101
Zero()102 static const SparsePowerWeight<W, K> &Zero() {
103 static const SparsePowerWeight<W, K> zero(SparseTupleWeight<W, K>::Zero());
104 return zero;
105 }
106
One()107 static const SparsePowerWeight<W, K> &One() {
108 static const SparsePowerWeight<W, K> one(SparseTupleWeight<W, K>::One());
109 return one;
110 }
111
NoWeight()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.
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
Properties()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
Reverse()143 ReverseWeight Reverse() const {
144 return SparseTupleWeight<W, K>::Reverse();
145 }
146 };
147
148 // Semimodule plus operation
149 template <class W, class K>
Plus(const SparsePowerWeight<W,K> & w1,const SparsePowerWeight<W,K> & w2)150 inline 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
159 template <class W, class K>
Times(const SparsePowerWeight<W,K> & w1,const SparsePowerWeight<W,K> & w2)160 inline 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
169 template <class W, class K>
170 inline 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
180 template <class W, class K>
DotProduct(const SparsePowerWeight<W,K> & w1,const SparsePowerWeight<W,K> & w2)181 inline 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
191 template <class W, class K>
192 inline 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
201 template <class W, class K>
Times(const W & k,const SparsePowerWeight<W,K> & w2)202 inline 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
208 template <class W, class K>
Times(const SparsePowerWeight<W,K> & w1,const W & k)209 inline 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
215 template <class W, class K>
216 inline 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