bmalgo_similarity.h
Go to the documentation of this file.
#ifndef BMALGO_SIMILARITY__H__INCLUDED__
#define BMALGO_SIMILARITY__H__INCLUDED__
/*
Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
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.
For more information please visit: http://bitmagic.io
*/
#include <algorithm>
#include <functional>
#include <vector>
#ifndef BM__H__INCLUDED__
// BitMagic utility headers do not include main "bm.h" declaration
// #include "bm.h" or "bm64.h" explicitly
# error missing include (bm.h or bm64.h)
#endif
#include "bmfunc.h"
#include "bmdef.h"
#include "bmalgo_impl.h"
namespace bm
{
/*! Similarity descriptor between two objects (bit vectors, blocks, etc)
\internal
*/
template <typename SO, unsigned DMD_SZ, typename IDX_VALUE, typename SValue, typename SFunc>
class similarity_descriptor
{
public:
typedef SO similarity_object_type;
typedef SValue similarity_value_type;
typedef SFunc similarity_functor;
public:
similarity_descriptor()
: so1_(0), so2_(0), so1_idx_(0), so2_idx_(0)
{
similarity_ = 0;
}
similarity_descriptor(const SO* so1, const SO* so2,
const distance_metric_descriptor* dmd_ptr)
:so1_(so1),
so2_(so2),
so1_idx_(0), so2_idx_(0)
{
for (size_t i = 0; i < DMD_SZ; ++i)
dmd_[i] = dmd_ptr[i];
similarity_ = 0;
}
similarity_descriptor(const SO* so1, IDX_VALUE i1,
const SO* so2, IDX_VALUE i2,
const distance_metric_descriptor* dmd_ptr)
:so1_(so1), so2_(so2), so1_idx_(i1), so2_idx_(i2)
{
for (size_t i = 0; i < DMD_SZ; ++i)
dmd_[i] = dmd_ptr[i];
similarity_ = 0;
}
similarity_descriptor(const similarity_descriptor& sd)
: similarity_(sd.similarity_),
so1_(sd.so1_),
so2_(sd.so2_),
so1_idx_(sd.so1_idx_),
so2_idx_(sd.so2_idx_)
{
for (size_t i = 0; i < DMD_SZ; ++i)
dmd_[i] = sd.dmd_[i];
}
similarity_descriptor& operator=(const similarity_descriptor& sd)
{
similarity_ = sd.similarity_;
so1_ = sd.so1_; so2_ = sd.so2_;
so1_idx_ = sd.so1_idx_; so2_idx_ = sd.so2_idx_;
for (size_t i = 0; i < DMD_SZ; ++i)
dmd_[i] = sd.dmd_[i];
return *this;
}
bool operator > (const similarity_descriptor& sd) const
{
return similarity_ > sd.similarity_;
}
SValue similarity() const { return similarity_; }
void set_similarity(SValue s) { similarity_ = s;}
const SO* get_first() const { return so1_; }
const SO* get_second() const { return so2_; }
IDX_VALUE get_first_idx() const { return so1_idx_; }
IDX_VALUE get_second_idx() const { return so2_idx_; }
distance_metric_descriptor* distance_begin() { return &dmd_[0]; }
distance_metric_descriptor* distance_end() { return &dmd_[DMD_SZ]; }
void set_metric(size_t i, distance_metric metric)
{
BM_ASSERT(i < DMD_SZ);
dmd_[i].metric = metric;
}
protected:
SValue similarity_; //< final similarity product
const SO* so1_; //< object 1 for similarity comparison
const SO* so2_; //< object 2 for similarity comparison
IDX_VALUE so1_idx_; //< index of object 1
IDX_VALUE so2_idx_; //< index of object 2
distance_metric_descriptor dmd_[DMD_SZ]; //< array of distance operations defined on objects
};
/*!
Batch of objects for similarity measurement
\internal
*/
template<class SDESCR>
struct similarity_batch
{
typedef SDESCR similaruty_descriptor_type;
typedef typename SDESCR::similarity_object_type similarity_object_type;
typedef typename SDESCR::similarity_value_type similarity_value_type;
typedef typename SDESCR::similarity_functor similarity_functor;
typedef std::vector<SDESCR> vector_type;
/// run the similarity calculation using distance metrics engine
void calculate()
{
for( size_t i = 0; i < descr_vect_.size(); ++i)
{
similaruty_descriptor_type& sdescr = descr_vect_[i];
const similarity_object_type* so1 = sdescr.get_first();
const similarity_object_type* so2 = sdescr.get_second();
distance_metric_descriptor* dit = sdescr.distance_begin();
distance_metric_descriptor* dit_end = sdescr.distance_end();
bm::distance_operation(*so1, *so2, dit, dit_end);
// reduce: use functor to compute final similarity metric
similarity_functor func;
similarity_value_type d = func(dit, dit_end);
sdescr.set_similarity(d);
} // for i
}
void sort()
{
std::sort(descr_vect_.begin(), descr_vect_.end(), std::greater<SDESCR>());
}
void reserve(size_t cap)
{
descr_vect_.reserve(cap);
}
void push_back(const similaruty_descriptor_type& sdt)
{
descr_vect_.push_back(sdt);
}
public:
std::vector<SDESCR> descr_vect_;
};
/**
Utility function to build jaccard similarity batch for sparse_vector<>
\internal
*/
template<class SIMBATCH, class SV>
void build_jaccard_similarity_batch(SIMBATCH& sbatch, const SV& sv)
{
size_t planes = sv.get_bmatrix().rows();//slices();
sbatch.reserve((planes * planes) / 2);
bm::distance_metric_descriptor dmd[2];
dmd[0].metric = bm::COUNT_AND;
dmd[1].metric = bm::COUNT_OR;
// build a batch for triangular distance matrix
//
for (unsigned i = 0; i < planes; ++i)
{
if (const typename SV::bvector_type* bv1 = sv.get_slice(i))
{
for (unsigned j = i+1; j < planes; ++j)
{
const typename SV::bvector_type* bv2 = sv.get_slice(j);
if (bv2 && bv1 != bv2)
sbatch.push_back(typename SIMBATCH::similaruty_descriptor_type(bv1, i, bv2, j, &dmd[0]));
} // for j
}
} // for i
}
} // namespace bm
#endif
bmalgo_impl.h
Algorithms for bvector<>.
bmdef.h
Definitions(internal).
BM_ASSERT
#define BM_ASSERT
Definition bmdef.h:139
bmfunc.h
Bit manipulation primitives (internal).
bm::similarity_descriptor::dmd_
distance_metric_descriptor dmd_[DMD_SZ]
Definition bmalgo_similarity.h:128
bm::similarity_descriptor::get_second_idx
IDX_VALUE get_second_idx() const
Definition bmalgo_similarity.h:110
bm::similarity_descriptor::so2_
const SO * so2_
Definition bmalgo_similarity.h:125
bm::similarity_descriptor::similarity_descriptor
similarity_descriptor(const SO *so1, IDX_VALUE i1, const SO *so2, IDX_VALUE i2, const distance_metric_descriptor *dmd_ptr)
Definition bmalgo_similarity.h:68
bm::similarity_descriptor::so2_idx_
IDX_VALUE so2_idx_
Definition bmalgo_similarity.h:127
bm::similarity_descriptor::similarity_descriptor
similarity_descriptor()
Definition bmalgo_similarity.h:51
bm::similarity_descriptor::similarity_descriptor
similarity_descriptor(const similarity_descriptor &sd)
Definition bmalgo_similarity.h:78
bm::similarity_descriptor::similarity
SValue similarity() const
Definition bmalgo_similarity.h:103
bm::similarity_descriptor::get_first
const SO * get_first() const
Definition bmalgo_similarity.h:106
bm::similarity_descriptor::similarity_descriptor
similarity_descriptor(const SO *so1, const SO *so2, const distance_metric_descriptor *dmd_ptr)
Definition bmalgo_similarity.h:57
bm::similarity_descriptor::similarity_functor
SFunc similarity_functor
Definition bmalgo_similarity.h:49
bm::similarity_descriptor::set_metric
void set_metric(size_t i, distance_metric metric)
Definition bmalgo_similarity.h:115
bm::similarity_descriptor::operator=
similarity_descriptor & operator=(const similarity_descriptor &sd)
Definition bmalgo_similarity.h:88
bm::similarity_descriptor::so1_
const SO * so1_
Definition bmalgo_similarity.h:124
bm::similarity_descriptor::similarity_value_type
SValue similarity_value_type
Definition bmalgo_similarity.h:48
bm::similarity_descriptor::similarity_
SValue similarity_
Definition bmalgo_similarity.h:123
bm::similarity_descriptor::distance_end
distance_metric_descriptor * distance_end()
Definition bmalgo_similarity.h:113
bm::similarity_descriptor::so1_idx_
IDX_VALUE so1_idx_
Definition bmalgo_similarity.h:126
bm::similarity_descriptor::set_similarity
void set_similarity(SValue s)
Definition bmalgo_similarity.h:104
bm::similarity_descriptor::similarity_object_type
SO similarity_object_type
Definition bmalgo_similarity.h:47
bm::similarity_descriptor::distance_begin
distance_metric_descriptor * distance_begin()
Definition bmalgo_similarity.h:112
bm::similarity_descriptor::get_second
const SO * get_second() const
Definition bmalgo_similarity.h:107
bm::similarity_descriptor::get_first_idx
IDX_VALUE get_first_idx() const
Definition bmalgo_similarity.h:109
bm::similarity_descriptor::operator>
bool operator>(const similarity_descriptor &sd) const
Definition bmalgo_similarity.h:98
bm::distance_operation
void distance_operation(const BV &bv1, const BV &bv2, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) BMNOEXCEPT
Distance computing template function.
Definition bmalgo_impl.h:766
bm::distance_metric
distance_metric
Distance metrics codes defined for vectors A and B.
Definition bmalgo_impl.h:58
bm::COUNT_AND
@ COUNT_AND
(A & B).count()
Definition bmalgo_impl.h:59
bm::COUNT_OR
@ COUNT_OR
(A | B).count()
Definition bmalgo_impl.h:61
bm
Definition bm.h:78
bm::build_jaccard_similarity_batch
void build_jaccard_similarity_batch(SIMBATCH &sbatch, const SV &sv)
Utility function to build jaccard similarity batch for sparse_vector<>.
Definition bmalgo_similarity.h:190
bm::distance_metric_descriptor
Distance metric descriptor, holds metric code and result.
Definition bmalgo_impl.h:87
bm::distance_metric_descriptor::metric
distance_metric metric
Definition bmalgo_impl.h:94
bm::similarity_batch
Definition bmalgo_similarity.h:137
bm::similarity_batch::descr_vect_
std::vector< SDESCR > descr_vect_
Definition bmalgo_similarity.h:181
bm::similarity_batch::reserve
void reserve(size_t cap)
Definition bmalgo_similarity.h:170
bm::similarity_batch::similarity_object_type
SDESCR::similarity_object_type similarity_object_type
Definition bmalgo_similarity.h:139
bm::similarity_batch::vector_type
std::vector< SDESCR > vector_type
Definition bmalgo_similarity.h:142
bm::similarity_batch::push_back
void push_back(const similaruty_descriptor_type &sdt)
Definition bmalgo_similarity.h:175
bm::similarity_batch::similaruty_descriptor_type
SDESCR similaruty_descriptor_type
Definition bmalgo_similarity.h:138
bm::similarity_batch::calculate
void calculate()
run the similarity calculation using distance metrics engine
Definition bmalgo_similarity.h:145
bm::similarity_batch::sort
void sort()
Definition bmalgo_similarity.h:165
bm::similarity_batch::similarity_value_type
SDESCR::similarity_value_type similarity_value_type
Definition bmalgo_similarity.h:140
bm::similarity_batch::similarity_functor
SDESCR::similarity_functor similarity_functor
Definition bmalgo_similarity.h:141