/home/mhx/git/github/libmoost/include/moost/algorithm/similarity.hpp

Go to the documentation of this file.

/* vim:set ts=3 sw=3 sts=3 et: */
#ifndef MOOST_ALGORITHM_SIMILARITY_HPP__
#define MOOST_ALGORITHM_SIMILARITY_HPP__

#include <cmath>

namespace moost { namespace algorithm {

template <typename FloatType>
struct SimpleAccumulatorPolicy
{
   void operator() (FloatType& accu, const FloatType& val) const
   {
      accu += val;
   }
};

template < typename FloatType,
           class ForwardIteratorX,
           class WeightAccessPolicyX,
           class ForwardIteratorY,
           class WeightAccessPolicyY,
           class AccumulatorPolicy >
FloatType cosine_similarity(ForwardIteratorX x_beg, ForwardIteratorX x_end, WeightAccessPolicyX x_weight,
                            ForwardIteratorY y_beg, ForwardIteratorY y_end, WeightAccessPolicyY y_weight,
                            AccumulatorPolicy& accu)
{
   FloatType sum, norm_x, norm_y;

   sum = norm_x = norm_y = 0.0;

   while (x_beg != x_end && y_beg != y_end)
   {
      if (*x_beg < *y_beg)
      {
         FloatType x = x_weight(*x_beg);
         norm_x += x*x;
         ++x_beg;
      }
      else if (*y_beg < *x_beg)
      {
         FloatType y = y_weight(*y_beg);
         norm_y += y*y;
         ++y_beg;
      }
      else
      {
         FloatType x = x_weight(*x_beg);
         FloatType y = y_weight(*y_beg);
         accu(sum, x*y);
         norm_x += x*x;
         norm_y += y*y;
         ++x_beg;
         ++y_beg;
      }
   }

   if (sum == 0.0)
   {
      return 0.0;
   }

   for (; x_beg != x_end; ++x_beg)
   {
      FloatType x = x_weight(*x_beg);
      norm_x += x*x;
   }

   for (; y_beg != y_end; ++y_beg)
   {
      FloatType y = y_weight(*y_beg);
      norm_y += y*y;
   }

   return sum/std::sqrt(norm_x*norm_y);
}

/* Default implementation using SimpleAccumulatorPolicy */
template < typename FloatType,
           class ForwardIteratorX,
           class WeightAccessPolicyX,
           class ForwardIteratorY,
           class WeightAccessPolicyY >
FloatType cosine_similarity(ForwardIteratorX x_beg, ForwardIteratorX x_end, WeightAccessPolicyX x_weight,
                            ForwardIteratorY y_beg, ForwardIteratorY y_end, WeightAccessPolicyY y_weight)
{
   SimpleAccumulatorPolicy<FloatType> accu;
   return cosine_similarity<FloatType>(x_beg, x_end, x_weight, y_beg, y_end, y_weight, accu);
}

}}

#endif