include/lshkit/sketch.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 __LSHKIT_SKETCH__
#define __LSHKIT_SKETCH__

#include <lshkit/matrix.h>


namespace lshkit {

template <typename LSH, typename CHUNK = unsigned char>
class Sketch
{
    BOOST_CONCEPT_ASSERT((DeltaLshConcept<LSH>));

    unsigned dim_;
    std::vector<LSH> lsh_;

public:
    typedef typename LSH::Parameter Parameter;
    typedef typename LSH::Domain Domain; 
    static const unsigned CHUNK_BIT = sizeof(CHUNK) * 8; // #bits in CHUNK

    Sketch() {
    }

    template <typename Engine>
    void reset (unsigned chunks, Parameter param, Engine &engine) {
        dim_ = chunks;
        lsh_.resize(dim_ * CHUNK_BIT);
        for (unsigned i = 0; i < lsh_.size(); ++i) lsh_[i].reset(param, engine);
    }

    template <typename Engine>
    Sketch(unsigned chunks, Parameter param, Engine &engine) : 
        dim_(chunks), lsh_(dim_ * CHUNK_BIT)
    {
        for (unsigned i = 0; i < lsh_.size(); ++i) lsh_[i].reset(param, engine);
    }

    void apply (Domain in, CHUNK *out) const
    {
        unsigned l = 0;
        for (unsigned i = 0; i < dim_; ++i) {
            out[i] = 0;
            for (unsigned j = 0; j < CHUNK_BIT; ++j) {
                unsigned k = lsh_[l++](in);
                out[i] = out[i] | (k << j);
            }
        }
    }
    

    void apply (Domain in, CHUNK *out, float *asym) const
    {
        unsigned l = 0;
        for (unsigned i = 0; i < dim_; ++i) {
            out[i] = 0;
            for (unsigned j = 0; j < CHUNK_BIT; ++j) {
                unsigned k = lsh_[l](in, &asym[l]);
                out[i] = out[i] | (k << j);
                l++;
            }
        }
    }

    template<class Archive>
    void serialize(Archive & ar, const unsigned int version)
    {
        ar & dim_;
        ar & lsh_;
    }

    void load (std::istream &is) {
        serialize(is, 0);
    }

    void save (std::ostream &os) {
        serialize(os, 0);
    }

    unsigned getBits () const {
        return dim_ * CHUNK_BIT;
    }

    unsigned getChunks () const {
        return dim_;
    }
};


template <typename CHUNK = unsigned char>
class WeightedHammingHelper
{
public:
    static const unsigned CHUNK_BIT = sizeof(CHUNK) * 8;

    WeightedHammingHelper(unsigned chunks)
        : nchunk_(chunks), lookup_(1 << CHUNK_BIT, chunks)
    {
    }


    void update (const CHUNK *in, const float *asym)
    {
        unsigned l = 0;
        for (unsigned i = 0; i < nchunk_; ++i) {
            CHUNK q = in[i];
            CHUNK p = 0;
            for (;;) {
                CHUNK c = q ^ p;
                float v = 0;
                for (unsigned j = 0; j < CHUNK_BIT; ++j) {
                    if (c & (1 << j)) {
                        v += asym[l + j];
                    }
                }
                lookup_[i][p] = v;
                ++p;
                if (p == 0) break;
            }
            l += CHUNK_BIT;
        }
    }

    float distTo (const CHUNK *in)
    {
        float dist = 0;
        for (unsigned i = 0; i < nchunk_; ++i) {
            dist += lookup_[i][in[i]];
        }
        return dist;
    }

private:
    unsigned nchunk_;
    Matrix<float> lookup_;
};


}

#endif

---