| // sparse-power-weight.h |
| |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| // |
| // Copyright 2005-2010 Google, Inc. |
| // Author: krr@google.com (Kasturi Rangan Raghavan) |
| // Inspiration: allauzen@google.com (Cyril Allauzen) |
| // |
| // \file |
| // Cartesian power weight semiring operation definitions. |
| // Uses SparseTupleWeight as underlying representation. |
| |
| #ifndef FST_LIB_SPARSE_POWER_WEIGHT_H__ |
| #define FST_LIB_SPARSE_POWER_WEIGHT_H__ |
| |
| #include<string> |
| |
| #include <fst/sparse-tuple-weight.h> |
| #include <fst/weight.h> |
| |
| |
| namespace fst { |
| |
| // Below SparseTupleWeight*Mapper are used in conjunction with |
| // SparseTupleWeightMap to compute the respective semiring operations |
| template<class W, class K> |
| struct SparseTupleWeightPlusMapper { |
| W Map(const K& k, const W& v1, const W& v2) const { |
| return Plus(v1, v2); |
| } |
| }; |
| |
| template<class W, class K> |
| struct SparseTupleWeightTimesMapper { |
| W Map(const K& k, const W& v1, const W& v2) const { |
| return Times(v1, v2); |
| } |
| }; |
| |
| template<class W, class K> |
| struct SparseTupleWeightDivideMapper { |
| SparseTupleWeightDivideMapper(DivideType divide_type) { |
| divide_type_ = divide_type; |
| } |
| W Map(const K& k, const W& v1, const W& v2) const { |
| return Divide(v1, v2, divide_type_); |
| } |
| DivideType divide_type_; |
| }; |
| |
| template<class W, class K> |
| struct SparseTupleWeightApproxMapper { |
| SparseTupleWeightApproxMapper(float delta) { delta_ = delta; } |
| W Map(const K& k, const W& v1, const W& v2) const { |
| return ApproxEqual(v1, v2, delta_) ? W::One() : W::Zero(); |
| } |
| float delta_; |
| }; |
| |
| // Sparse cartesian power semiring: W ^ n |
| // Forms: |
| // - a left semimodule when W is a left semiring, |
| // - a right semimodule when W is a right semiring, |
| // - a bisemimodule when W is a semiring, |
| // the free semimodule of rank n over W |
| // The Times operation is overloaded to provide the |
| // left and right scalar products. |
| // K is the key value type. kNoKey(-1) is reserved for internal use |
| template <class W, class K = int> |
| class SparsePowerWeight : public SparseTupleWeight<W, K> { |
| public: |
| using SparseTupleWeight<W, K>::Zero; |
| using SparseTupleWeight<W, K>::One; |
| using SparseTupleWeight<W, K>::NoWeight; |
| using SparseTupleWeight<W, K>::Quantize; |
| using SparseTupleWeight<W, K>::Reverse; |
| |
| typedef SparsePowerWeight<typename W::ReverseWeight, K> ReverseWeight; |
| |
| SparsePowerWeight() {} |
| |
| SparsePowerWeight(const SparseTupleWeight<W, K> &w) : |
| SparseTupleWeight<W, K>(w) { } |
| |
| template <class Iterator> |
| SparsePowerWeight(Iterator begin, Iterator end) : |
| SparseTupleWeight<W, K>(begin, end) { } |
| |
| SparsePowerWeight(const K &key, const W &w) : |
| SparseTupleWeight<W, K>(key, w) { } |
| |
| static const SparsePowerWeight<W, K> &Zero() { |
| static const SparsePowerWeight<W, K> zero(SparseTupleWeight<W, K>::Zero()); |
| return zero; |
| } |
| |
| static const SparsePowerWeight<W, K> &One() { |
| static const SparsePowerWeight<W, K> one(SparseTupleWeight<W, K>::One()); |
| return one; |
| } |
| |
| static const SparsePowerWeight<W, K> &NoWeight() { |
| static const SparsePowerWeight<W, K> no_weight( |
| SparseTupleWeight<W, K>::NoWeight()); |
| return no_weight; |
| } |
| |
| // Overide this: Overwrite the Type method to reflect the key type |
| // if using non-default key type. |
| static const string &Type() { |
| static string type; |
| if(type.empty()) { |
| type = W::Type() + "_^n"; |
| if(sizeof(K) != sizeof(uint32)) { |
| string size; |
| Int64ToStr(8 * sizeof(K), &size); |
| type += "_" + size; |
| } |
| } |
| return type; |
| } |
| |
| static uint64 Properties() { |
| uint64 props = W::Properties(); |
| return props & (kLeftSemiring | kRightSemiring | |
| kCommutative | kIdempotent); |
| } |
| |
| SparsePowerWeight<W, K> Quantize(float delta = kDelta) const { |
| return SparseTupleWeight<W, K>::Quantize(delta); |
| } |
| |
| ReverseWeight Reverse() const { |
| return SparseTupleWeight<W, K>::Reverse(); |
| } |
| }; |
| |
| // Semimodule plus operation |
| template <class W, class K> |
| inline SparsePowerWeight<W, K> Plus(const SparsePowerWeight<W, K> &w1, |
| const SparsePowerWeight<W, K> &w2) { |
| SparsePowerWeight<W, K> ret; |
| SparseTupleWeightPlusMapper<W, K> operator_mapper; |
| SparseTupleWeightMap(&ret, w1, w2, operator_mapper); |
| return ret; |
| } |
| |
| // Semimodule times operation |
| template <class W, class K> |
| inline SparsePowerWeight<W, K> Times(const SparsePowerWeight<W, K> &w1, |
| const SparsePowerWeight<W, K> &w2) { |
| SparsePowerWeight<W, K> ret; |
| SparseTupleWeightTimesMapper<W, K> operator_mapper; |
| SparseTupleWeightMap(&ret, w1, w2, operator_mapper); |
| return ret; |
| } |
| |
| // Semimodule divide operation |
| template <class W, class K> |
| inline SparsePowerWeight<W, K> Divide(const SparsePowerWeight<W, K> &w1, |
| const SparsePowerWeight<W, K> &w2, |
| DivideType type = DIVIDE_ANY) { |
| SparsePowerWeight<W, K> ret; |
| SparseTupleWeightDivideMapper<W, K> operator_mapper(type); |
| SparseTupleWeightMap(&ret, w1, w2, operator_mapper); |
| return ret; |
| } |
| |
| // Semimodule dot product |
| template <class W, class K> |
| inline const W& DotProduct(const SparsePowerWeight<W, K> &w1, |
| const SparsePowerWeight<W, K> &w2) { |
| const SparsePowerWeight<W, K>& product = Times(w1, w2); |
| W ret(W::Zero()); |
| for (SparseTupleWeightIterator<W, K> it(product); !it.Done(); it.Next()) { |
| ret = Plus(ret, it.Value().second); |
| } |
| return ret; |
| } |
| |
| template <class W, class K> |
| inline bool ApproxEqual(const SparsePowerWeight<W, K> &w1, |
| const SparsePowerWeight<W, K> &w2, |
| float delta = kDelta) { |
| SparseTupleWeight<W, K> ret; |
| SparseTupleWeightApproxMapper<W, K> operator_mapper(kDelta); |
| SparseTupleWeightMap(&ret, w1, w2, operator_mapper); |
| return ret == SparsePowerWeight<W, K>::One(); |
| } |
| |
| template <class W, class K> |
| inline SparsePowerWeight<W, K> Times(const W &k, |
| const SparsePowerWeight<W, K> &w2) { |
| SparsePowerWeight<W, K> w1(k); |
| return Times(w1, w2); |
| } |
| |
| template <class W, class K> |
| inline SparsePowerWeight<W, K> Times(const SparsePowerWeight<W, K> &w1, |
| const W &k) { |
| SparsePowerWeight<W, K> w2(k); |
| return Times(w1, w2); |
| } |
| |
| template <class W, class K> |
| inline SparsePowerWeight<W, K> Divide(const SparsePowerWeight<W, K> &w1, |
| const W &k, |
| DivideType divide_type = DIVIDE_ANY) { |
| SparsePowerWeight<W, K> w2(k); |
| return Divide(w1, w2, divide_type); |
| } |
| |
| } // namespace fst |
| |
| #endif // FST_LIB_SPARSE_POWER_WEIGHT_H__ |