feature-vector.H

Go to the documentation of this file.

// Copyright 2012, Google Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//   * Redistributions of source code must retain the above copyright
//     notice, this list of conditions and the following disclaimer.
//   * Redistributions in binary form must reproduce the above
//     copyright notice, this list of conditions and the following disclaimer
//     in the documentation and/or other materials provided with the
//     distribution.
//   * Neither the name of Google Inc. nor the names of its
//     contributors may be used to endorse or promote products derived from
//     this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
// -----------------------------------------------------------------------------
//
//

#ifndef RERANKER_FEATURE_VECTOR_H_
#define RERANKER_FEATURE_VECTOR_H_

#include <iostream>
#include <map>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include "string-canonicalizer.H"

namespace reranker {

using std::cerr;
using std::endl;
using std::map;
using std::ostream;
using std::string;
using std::unordered_map;
using std::unordered_set;

template <typename T>
struct DelKey {
  static const T Get() { return T(); }
};

template <>
struct DelKey<int> {
  static const int Get() { return -1; }
};

template <>
struct DelKey<double> {
  static const double Get() { return -1.0; }
};

template <>
struct DelKey<string> {
  static const string Get() { return ""; }
};

template<typename T>
struct UidGetter {
  static const T &Get(const T &uid) { return uid; }
};

template<>
struct UidGetter<string> {
  static const string &Get(const string &uid) {
    return StringCanonicalizer::Get(uid);
  }
};

template <typename K, typename V,
          //typename Map = google::sparse_hash_map<K, V> >
          //typename Map = map<K, V> >
          typename Map = unordered_map<K, V> >
class FeatureVector {
 public:
  FeatureVector() {
    //features_.set_deleted_key(DelKey<K>::Get());
  }

  FeatureVector(const Map &features) : features_(features) {
    //features_.set_deleted_key(DelKey<K>::Get());
  }

  template <typename MapType>
  FeatureVector(const MapType &features) {
    //features_.set_deleted_key(DelKey<K>::Get());
    for (typename MapType::const_iterator it = features.begin();
         it != features.end(); ++it) {
      features_.insert(*it);
    }
  }

  virtual ~FeatureVector() {}

  // Forward type declarations that mirror what STL maps do.
  typedef K key_type;
  typedef V mapped_type;

  typedef Map FeatureMap;
  typedef typename FeatureMap::const_iterator const_iterator;

  // accessors

  const_iterator begin() const {
    return features_.begin();
  }

  const_iterator end() const {
    return features_.end();
  }

  unordered_set<K> &GetNonZeroFeatures(unordered_set<K> &set) const {
    for (const_iterator it = features_.begin(); it != features_.end(); ++it) {
      set.insert(it->first);
    }
    return set;
  }

  unordered_set<K> &RemoveNonZeroFeatures(unordered_set<K> &set) const {
    for (const_iterator it = features_.begin(); it != features_.end(); ++it) {
      set.erase(it->first);
    }
    return set;
  }

  unordered_set<K> &RemoveEqualFeatures(const FeatureVector<K,V> &other,
                                        unordered_set<K> &set) const {
    for (const_iterator it = features_.begin(); it != features_.end(); ++it) {
      const K &uid = it->first;
      if (set.find(uid) != set.end() &&
          GetWeight(uid) == other.GetWeight(uid)) {
        set.erase(uid);
      }
    }
    return set;
  }

  V GetWeight(const K &uid) const {
    const_iterator feature_it = features_.find(uid);
    return feature_it == features_.end() ? V() : feature_it->second;
  }

  V GetValue(const K &uid) const {
    return GetWeight(uid);
  }

  size_t size() const { return features_.size(); }

  bool empty() const { return features_.empty(); }

  V Dot(const FeatureVector<K,V> &other) const {
    bool this_is_smaller = size() < other.size();
    const FeatureVector &small = this_is_smaller ? *this : other;
    const FeatureVector &large = this_is_smaller ? other : *this;
    V dot_product = V();
    for (const_iterator it = small.features_.begin();
         it != small.features_.end();
         ++it) {
      dot_product += it->second * large.GetWeight(it->first);
    }
    return dot_product;
  }

  // mutators

  V IncrementWeight(const K &uid, V by) {
    const K &canonical_uid = UidGetter<K>::Get(uid);
    V default_val = V();  // zero
    // Short circuit: if we're trying to increase a feature's weight by
    // zero, bail out early.
    bool no_increase = by == default_val;
    iterator feature_it = features_.find(canonical_uid);
    if (feature_it == features_.end()) {
      if (no_increase) {
        return default_val;
      }
      features_[canonical_uid] = by;
      return by;
    } else {
      if (no_increase) {
        return feature_it->second;
      }
      V new_weight = feature_it->second + by;
      if (new_weight == default_val) {
        features_.erase(canonical_uid);
      } else {
        feature_it->second = new_weight;
      }
      return new_weight;
    }
  }

  V IncrementValue(const K &uid, V by) {
    return IncrementWeight(uid, by);
  }

  V SetWeight(const K &uid, V new_weight) {
    V old_weight = GetWeight(uid);
    if (new_weight == V()) {
      features_.erase(uid);
    } else {
      features_[uid] = new_weight;
    }
    return old_weight;
  }

  V SetValue(const K &uid, V new_value) {
    return SetWeight(uid, new_value);
  }

  FeatureVector<K,V> &Scale(V scalar) {
    for (iterator it = features_.begin(); it != features_.end(); ++it) {
      it->second = it->second * scalar;
    }
    return *this;
  }

  FeatureVector<K,V> &AddScaledVector(const FeatureVector<K,V> &other,
                                      V scalar) {
    for (const_iterator it = other.begin(); it != other.end(); ++it) {
      IncrementWeight(it->first, scalar * it->second);
    }
    return *this;
  }

  template <typename Collection>
  FeatureVector<K,V> &AddScaledSubvector(const Collection &feature_uids,
                                         const FeatureVector<K,V> &
                                         feature_vector,
                                         V scalar) {
    for (typename Collection::const_iterator it = feature_uids.begin();
         it != feature_uids.end();
         ++it) {
      IncrementWeight(*it, feature_vector.GetWeight(*it) * scalar);
    }
    return *this;
  }

  template <typename Collection>
  FeatureVector<K,V> &IncrementWeights(const Collection &feature_uids,
                                       V increment) {
    for (typename Collection::const_iterator it = feature_uids.begin();
         it != feature_uids.end();
         ++it) {
      IncrementWeight(*it, increment);
    }
    return *this;
  }

  void clear() {
    features_.clear();
  }

  // I/O methods

  // TODO(dbikel): Add methods to serialize and de-serialize to/from protobuf's.

  friend ostream &operator<<(ostream &os, const FeatureVector<K,V> &fv) {
    os << "[";
    const_iterator it = fv.features_.begin();
    if (it != fv.features_.end()) {
      os << it->first << "=" << it->second;
      ++it;
    }
    for ( ; it != fv.features_.end(); ++it) {
      os << " " << it->first << "=" << it->second;
    }
    os << "]";
    return os;
  }

 private:
  // a helpful internal typedef for mutating methods
  typedef typename FeatureMap::iterator iterator;

  // data members
  FeatureMap features_;
};

}  // namespace reranker

#endif