include/fst/sparse-power-weight.h

// 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__