include/lshkit/metric.h

Go to the documentation of this file.

/* 
    Copyright (C) 2008 Wei Dong <wdong@princeton.edu>. All Rights Reserved.
  
    This file is part of LSHKIT.
  
    LSHKIT is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    LSHKIT is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with LSHKIT.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef __FERRET_METRIC__
#define __FERRET_METRIC__

// This file implements some common distance functions.

#include <functional>

namespace lshkit { namespace metric {

template <typename T /* real type */>
class l1 : public std::binary_function<T, T, float>
{
    unsigned dim_;
public:
    l1 (unsigned dim) : dim_(dim) {}
    float operator () (const T *first1, const T *first2) const
    {
        float r = 0.0;
        for (unsigned i = 0; i < dim_; ++i)
        {
            r += std::fabs(first1[i] - first2[i]);
        }
        return r;
    }
};

template <typename T /* real type */>
class l2 : public std::binary_function<const T*, const T*, float>
{
    unsigned dim_;
public:
    l2 (unsigned dim) : dim_(dim) {}
    float operator () (const T *first1, const T *first2) const
    {
        float r = 0.0;
        for (unsigned i = 0; i < dim_; ++i)
        {
            r += sqr(first1[i] - first2[i]);
        }
        return std::sqrt(r);
    }
};


template <typename T /* real type */>
class l2sqr : public std::binary_function<const T*, const T*, float>
{
    unsigned dim_;
public:
    l2sqr (unsigned dim) : dim_(dim) {}
    float operator () (const T *first1, const T *first2) const
    {
        float r = 0.0;
        for (unsigned i = 0; i < dim_; ++i)
        {
            r += sqr(first1[i] - first2[i]);
        }
        return r;
    }
};

template <typename T /* real type */>
class max : public std::binary_function<const T*, const T*, float>
{
    unsigned dim_;
public:
    max (unsigned dim) : dim_(dim) {}
    float operator () (const T *first1, const T *first2) const
    {
        double r = std::numeric_limits<T>::min();
        for (unsigned i = 0; i < dim_; ++i)
        {
            r += max(r, std::fabs(first1[i] - first2[i]));
        }
        return (float)std::sqrt(r);
    }
};


struct basic_hamming
{
    static unsigned char_bit_cnt[];

    template <typename B>
    unsigned __hamming (B a, B b)
    {
        B c = a ^ b;
        unsigned char *p = reinterpret_cast<unsigned char *>(&c);
        unsigned r = 0;
        for (unsigned i = 0; i < sizeof(B); i++)
        {
            r += char_bit_cnt[*p++];
        }
        return r;
    }

    unsigned __hamming (unsigned char c1, unsigned char c2) const
    {
        return char_bit_cnt[c1 ^ c2];
    }

};


template <typename T>
struct hamming : public std::binary_function<const T*, const T*, float>, public basic_hamming
{
    unsigned dim_;
public:

    hamming(unsigned dim): dim_(dim) {}
    float operator () (const T *first1, const T *first2) const
    {
        unsigned r = 0;
        for (unsigned i = 0; i < dim_; ++i)
        {
            r += __hamming(first1[i], first2[i]);
        }
        return r;
    }
};


}}

#endif

---