rscsample05.cpp
Go to the documentation of this file.
/*
Copyright(c) 2002-2020 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
*/
/** \example rscsample05.cpp
Example of how to use collaborative compression (XOR compression)
for a group of bit-transposed sparse vectors in a data-frame
\sa bm::sparse_vector
\sa bm::rsc_sparse_vector
\sa bm::sparse_vector_serializer
\sa bm::sparse_vector_deserializer
\sa rscsample02.cpp
\sa svsample02.cpp
*/
/*! \file rscsample05.cpp
\brief Example: collaborative compression (XOR compression)
*/
#include <iostream>
#include <vector>
#include <cassert>
#include "bm.h"
#include "bmsparsevec.h"
#include "bmsparsevec_compr.h"
#include "bmsparsevec_serial.h"
using namespace std;
// type definitions
//
typedef bm::bvector<> bvector_type;
typedef bm::sparse_vector<unsigned short, bvector_type> sparse_vector_u16;
typedef bm::sparse_vector<unsigned, bvector_type> sparse_vector_u32;
typedef bm::rsc_sparse_vector<unsigned, sparse_vector_u32 > rsc_sparse_vector_u32;
typedef bm::sparse_vector_serializer<rsc_sparse_vector_u32> csv_serializer_type;
typedef bm::sparse_vector_serializer<sparse_vector_u16> sv16_serializer_type;
typedef bm::sparse_vector_deserializer<rsc_sparse_vector_u32> csv_deserializer_type;
typedef bm::sparse_vector_deserializer<sparse_vector_u16> sv16_deserializer_type;
/// sample data-frame structure with multiple bm vectors
///
struct sample_data_frame
{
rsc_sparse_vector_u32 csv1;
rsc_sparse_vector_u32 csv2;
rsc_sparse_vector_u32 csv3;
sparse_vector_u16 sv0; // non-compressed sparse vector
sample_data_frame()
: sv0(bm::use_null)
{}
};
/// Estimate raw data size
///
inline
size_t raw_data_size(const sample_data_frame& df)
{
size_t sz = 0;
if (df.csv1.size())
sz += df.csv1.size() * sizeof(df.csv1.get(0));
if (df.csv2.size())
sz += df.csv2.size() * sizeof(df.csv2.get(0));
if (df.csv3.size())
sz += df.csv3.size() * sizeof(df.csv3.get(0));
if (df.sv0.size())
sz += df.sv0.size() * sizeof(df.sv0.get(0));
return sz;
}
/// generate some data just to illustrate the case
///
static
void fill_test_data(sample_data_frame& df)
{
for (unsigned i = 0; i < 65536; i+=7)
{
df.csv1.set(i, 4);
df.csv2.set(i, 8);
df.csv3.set(i, 17);
df.sv0.set(i, i % 256);
}
// rebuild Rank-Select index once data are loaded
df.csv1.sync();
df.csv2.sync();
df.csv3.sync();
}
/// paranoiya check to make sure data frame matches pre-generated values
static
void test_data(sample_data_frame& df)
{
for (unsigned i = 0; i < 65536; i+=7)
{
auto v1 = df.csv1.get(i);
assert(v1 == 4); (void)v1;
auto v2 = df.csv2.get(i);
assert(v2 == 8); (void)v2;
auto v3 = df.csv3.get(i);
assert(v3 == 17); (void)v3;
auto v0 = df.sv0.get(i);
assert(v0 == i % 256); (void)v0;
}
}
/**
Copy buffer content into the buffer
@internal
*/
template<typename SVLay>
unsigned char* copy_buffer(unsigned char* buf_ptr, const SVLay& sv_lay)
{
auto s = sv_lay.size();
::memcpy(buf_ptr, sv_lay.buf(), s);
return buf_ptr + s;
}
/// serialize with disabled XOR compression
///
static
void serialize_df0(const sample_data_frame& df,
std::vector<unsigned char>& buf,
csv_serializer_type& csv_ser,
sv16_serializer_type& sv16_ser)
{
csv_ser.set_xor_ref(false); // disable XOR compression
// buffers for serialization
bm::sparse_vector_serial_layout<rsc_sparse_vector_u32> sv_lay1, sv_lay2, sv_lay3;
bm::sparse_vector_serial_layout<sparse_vector_u16> sv_lay0;
// serialize all data-frame vectors in their natural order (1, 2, 3 ... N)
//
csv_ser.serialize(df.csv1, sv_lay1);
csv_ser.serialize(df.csv2, sv_lay2);
csv_ser.serialize(df.csv3, sv_lay3);
sv16_ser.serialize(df.sv0, sv_lay0);
size_t sz = (sizeof(size_t) * 3) +
sv_lay1.size() + sv_lay2.size() + sv_lay3.size() + sv_lay0.size();
buf.resize(sz);
unsigned char* buf_ptr = buf.data(); // low level access to vector memory
// serialize data-frame header with sizes of containers
{
auto s = sv_lay1.size();
::memcpy(buf_ptr, &s, sizeof(s));
buf_ptr += sizeof(s);
}
{
auto s = sv_lay2.size();
::memcpy(buf_ptr, &s, sizeof(s));
buf_ptr += sizeof(s);
}
{
auto s = sv_lay3.size();
::memcpy(buf_ptr, &s, sizeof(s));
buf_ptr += sizeof(s);
}
{
auto s = sv_lay0.size();
::memcpy(buf_ptr, &s, sizeof(s));
buf_ptr += sizeof(s);
}
// save all serialization buffers to one BLOB
buf_ptr = copy_buffer(buf_ptr, sv_lay1);
buf_ptr = copy_buffer(buf_ptr, sv_lay2);
buf_ptr = copy_buffer(buf_ptr, sv_lay3);
buf_ptr = copy_buffer(buf_ptr, sv_lay0);
}
/// Simple (individual) de-serialization of vectors in the data-frame
///
static
void deserialize_df0(sample_data_frame& df,
const std::vector<unsigned char>& buf,
csv_deserializer_type& csv_dser,
sv16_deserializer_type& sv16_dser)
{
assert(buf.size() > sizeof(size_t)*3);
size_t sz1, sz2, sz3, sz0;
const unsigned char* data_ptr = buf.data();
// read the header to be able to calculate deserialization
// offsets within BLOB
//
::memcpy(&sz1, data_ptr, sizeof(size_t));
data_ptr += sizeof(size_t);
::memcpy(&sz2, data_ptr, sizeof(size_t));
data_ptr += sizeof(size_t);
::memcpy(&sz3, data_ptr, sizeof(size_t));
data_ptr += sizeof(size_t);
::memcpy(&sz0, data_ptr, sizeof(size_t));
data_ptr += sizeof(size_t);
csv_dser.deserialize(df.csv1, data_ptr);
data_ptr += sz1;
csv_dser.deserialize(df.csv2, data_ptr);
data_ptr += sz2;
csv_dser.deserialize(df.csv3, data_ptr);
data_ptr += sz3;
sv16_dser.deserialize(df.sv0, data_ptr);
data_ptr += sz0;
}
/// Data frame serialization using collaborative method (XOR compression)
///
static
void serialize_df2(const sample_data_frame& df,
std::vector<unsigned char>& buf,
csv_serializer_type& csv_ser,
sv16_serializer_type& sv16_ser)
{
try
{
// reference vector(s) to keep all bit-planes for collaborative compresson
csv_serializer_type::bv_ref_vector_type bv_ref;
// Build the list of reference vectors participating in our data-frame
// Important: add references in reverse (sic!) order (N ... 3, 2, 1)
// Important: add all data frame vectors
bv_ref.add_sparse_vector(df.sv0); // (!) last vectors is added first
bv_ref.add_sparse_vector(df.csv3);
bv_ref.add_sparse_vector(df.csv2);
bv_ref.add_sparse_vector(df.csv1);
csv_ser.set_xor_ref(&bv_ref); // connect reference vector to serializer
sv16_ser.set_xor_ref(&bv_ref); // connect reference vector to sv16 serializer
// compute XOR similarity model - it is common for all serializers
// and must be added after set_xor_ref()
//
bm::xor_sim_params x_params;
csv_serializer_type::xor_sim_model_type sim_model;
csv_ser.compute_sim_model(sim_model, bv_ref, x_params);
// add similarity model to each serializer
//
csv_ser.set_sim_model(&sim_model);
sv16_ser.set_sim_model(&sim_model);
// buffers for serialization
bm::sparse_vector_serial_layout<rsc_sparse_vector_u32> sv_lay1, sv_lay2, sv_lay3;
bm::sparse_vector_serial_layout<sparse_vector_u16> sv_lay0;
// serialize all data-frame vectors in their natural order (1, 2, 3 ... N)
//
csv_ser.serialize(df.csv1, sv_lay1);
csv_ser.serialize(df.csv2, sv_lay2);
csv_ser.serialize(df.csv3, sv_lay3);
sv16_ser.serialize(df.sv0, sv_lay0);
size_t sz = (sizeof(size_t) * 4) +
sv_lay1.size() + sv_lay2.size() + sv_lay3.size() + sv_lay0.size();
buf.resize(sz);
unsigned char* buf_ptr = buf.data(); // low level access to vector memory
// serialize data-frame header with sizes of containers
{
auto s = sv_lay1.size();
::memcpy(buf_ptr, &s, sizeof(s));
buf_ptr += sizeof(s);
}
{
auto s = sv_lay2.size();
::memcpy(buf_ptr, &s, sizeof(s));
buf_ptr += sizeof(s);
}
{
auto s = sv_lay3.size();
::memcpy(buf_ptr, &s, sizeof(s));
buf_ptr += sizeof(s);
}
{
auto s = sv_lay0.size();
::memcpy(buf_ptr, &s, sizeof(s));
buf_ptr += sizeof(s);
}
// save all serialization buffers to one BLOB
//
buf_ptr = copy_buffer(buf_ptr, sv_lay1);
buf_ptr = copy_buffer(buf_ptr, sv_lay2);
buf_ptr = copy_buffer(buf_ptr, sv_lay3);
buf_ptr = copy_buffer(buf_ptr, sv_lay0);
// if serializer is re-used we need to disconnect it from the
// current frame reference vectors
csv_ser.set_xor_ref(nullptr);
sv16_ser.set_xor_ref(nullptr);
}
catch (...)
{
// catch block is used to guarantee that serialiers
// are not associated with a dead reference vector
//
csv_ser.set_xor_ref(nullptr);
sv16_ser.set_xor_ref(nullptr);
throw;
}
}
/// Collaborative de-serialization of vectors in the data-frame
///
static
void deserialize_df2(sample_data_frame& df,
const std::vector<unsigned char>& buf,
csv_deserializer_type& csv_dser,
sv16_deserializer_type& sv16_dser)
{
assert(buf.size() > sizeof(size_t)*3);
try
{
size_t sz1, sz2, sz3, sz0;
const unsigned char* data_ptr = buf.data();
// read the header to be able to calculate deserialization
// offsets within BLOB
//
::memcpy(&sz1, data_ptr, sizeof(size_t));
data_ptr += sizeof(size_t);
::memcpy(&sz2, data_ptr, sizeof(size_t));
data_ptr += sizeof(size_t);
::memcpy(&sz3, data_ptr, sizeof(size_t));
data_ptr += sizeof(size_t);
::memcpy(&sz0, data_ptr, sizeof(size_t));
data_ptr += sizeof(size_t);
// reference vector for XOR deserialization
//
bm::sparse_vector_deserializer<rsc_sparse_vector_u32>::bv_ref_vector_type bv_ref;
// ----------------------------------------------------------
// first pass: build reference vectors, pre-construct vectors
//
csv_dser.deserialize_structure(df.csv1, data_ptr);
data_ptr += sz1;
csv_dser.deserialize_structure(df.csv2, data_ptr);
data_ptr += sz2;
csv_dser.deserialize_structure(df.csv3, data_ptr);
data_ptr += sz3;
sv16_dser.deserialize_structure(df.sv0, data_ptr);
data_ptr += sz0;
// construct the reference vector
// Important: add references in reverse (sic!) order (N ... 3, 2, 1)
// Important: add all data frame vectors
//
bv_ref.add_vectors(df.sv0.get_bmatrix()); // (!) last comes first
bv_ref.add_vectors(df.csv3.get_bmatrix());
bv_ref.add_vectors(df.csv2.get_bmatrix());
bv_ref.add_vectors(df.csv1.get_bmatrix());
// all de-serializers in the data-frame connect to the same set of refs
csv_dser.set_xor_ref(&bv_ref);
sv16_dser.set_xor_ref(&bv_ref);
// -------------------------------------------------------------
// second pass: data deserialization
//
// get deserialization start-pointer again
data_ptr = buf.data() + (4 * sizeof(size_t));
// it is important that second pass uses 'false' as a third arument
// to keep pre-created vectors structure, which is otherwise destroyed
//
csv_dser.deserialize(df.csv1, data_ptr, false);
data_ptr += sz1;
csv_dser.deserialize(df.csv2, data_ptr, false);
data_ptr += sz2;
csv_dser.deserialize(df.csv3, data_ptr, false);
data_ptr += sz3;
sv16_dser.deserialize(df.sv0, data_ptr, false);
data_ptr += sz0;
// disconnect deserialized from the reference vector
// before leaving the scope
//
csv_dser.set_xor_ref(nullptr);
sv16_dser.set_xor_ref(nullptr);
}
catch (...)
{
// catch block is used to guarantee that de-serialiers
// are not associated with a dead reference vector
//
csv_dser.set_xor_ref(nullptr);
sv16_dser.set_xor_ref(nullptr);
throw;
}
}
int main(void)
{
try
{
std::vector<unsigned char> buf0, buf2;
{
sample_data_frame df1; // sample data-frame
fill_test_data(df1); // add some test data
test_data(df1);
size_t raw_size = raw_data_size(df1);
cout << "raw size: " << raw_size << endl;
// declare serializers for sparse vectors of different types
csv_serializer_type csv_ser;
sv16_serializer_type sv16_ser;
serialize_df0(df1, buf0, csv_ser, sv16_ser);
cout << "Plain serializarion: " << buf0.size() << endl;
serialize_df2(df1, buf2, csv_ser, sv16_ser);
cout << "XOR data frame serialization: " << buf2.size() << endl;
}
// de-serialiers for sparse vectors of different types
// please note that de-serializers are reusable
//
csv_deserializer_type csv_dser;
sv16_deserializer_type sv16_dser;
// run simple deserialization here, test results
{
sample_data_frame df0; // empty data frame to read into
deserialize_df0(df0, buf0, csv_dser, sv16_dser);
test_data(df0); // check to make sure we are OK
}
// collaborative deserialization (XOR decode)
{
sample_data_frame df2;
deserialize_df2(df2, buf2, csv_dser, sv16_dser);
test_data(df2);
}
}
catch(std::exception& ex)
{
std::cerr << ex.what() << std::endl;
return 1;
}
return 0;
}
bm.h
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
bmsparsevec.h
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
bmsparsevec_compr.h
Compressed sparse container rsc_sparse_vector<> for integer types.
bmsparsevec_serial.h
Serialization for sparse_vector<>.
bm::base_sparse_vector::get_bmatrix
const bmatrix_type & get_bmatrix() const BMNOEXCEPT
Definition bmbmatrix.h:553
bm::bv_ref_vector::add_vectors
void add_vectors(const BMATR &bmatr)
Append basic bit-matrix to the list of reference vectors.
Definition bmxor.h:726
bm::bv_ref_vector::add_sparse_vector
void add_sparse_vector(const SV &sv)
Add bit-transposed sparse vector as a bit-matrix.
Definition bmxor.h:739
bm::bvector
Bitvector Bit-vector container with runtime compression of bits.
Definition bm.h:115
bm::rsc_sparse_vector
Rank-Select compressed sparse vector.
Definition bmsparsevec_compr.h:59
bm::rsc_sparse_vector::get_bmatrix
const bmatrix_type & get_bmatrix() const BMNOEXCEPT
Definition bmsparsevec_compr.h:878
bm::rsc_sparse_vector::set
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
Definition bmsparsevec_compr.h:1323
bm::rsc_sparse_vector::sync
void sync(bool force)
Re-calculate rank-select index for faster access to vector.
Definition bmsparsevec_compr.h:1442
bm::rsc_sparse_vector::get
value_type get(size_type idx) const BMNOEXCEPT
get specified element without bounds checking
Definition bmsparsevec_compr.h:1579
bm::rsc_sparse_vector::size
size_type size() const BMNOEXCEPT
return size of the vector
Definition bmsparsevec_compr.h:1071
bm::sparse_vector_deserializer
sparse vector de-serializer
Definition bmsparsevec_serial.h:327
bm::sparse_vector_deserializer::deserialize
void deserialize(SV &sv, const unsigned char *buf, bool clear_sv=true)
Definition bmsparsevec_serial.h:1222
bm::sparse_vector_deserializer::bv_ref_vector_type
bm::serializer< bvector_type >::bv_ref_vector_type bv_ref_vector_type
Definition bmsparsevec_serial.h:335
bm::sparse_vector_deserializer::deserialize_structure
void deserialize_structure(SV &sv, const unsigned char *buf)
Definition bmsparsevec_serial.h:1235
bm::sparse_vector_deserializer::set_xor_ref
void set_xor_ref(bv_ref_vector_type *bv_ref_ptr)
Set external XOR reference vectors (data frame referenece vectors).
Definition bmsparsevec_serial.h:1185
bm::sparse_vector_serializer
Definition bmsparsevec_serial.h:176
bm::sparse_vector_serializer< rsc_sparse_vector_u32 >::bv_ref_vector_type
bm::serializer< bvector_type >::bv_ref_vector_type bv_ref_vector_type
Definition bmsparsevec_serial.h:186
bm::sparse_vector_serializer::set_xor_ref
void set_xor_ref(bool is_enabled) BMNOEXCEPT
Turn ON and OFF XOR compression of sparse vectors Enables XOR reference compression for the sparse ve...
Definition bmsparsevec_serial.h:804
bm::sparse_vector_serializer::compute_sim_model
void compute_sim_model(xor_sim_model_type &sim_model, const bv_ref_vector_type &ref_vect, const bm::xor_sim_params &params)
Calculate XOR similarity model for ref_vector refernece vector must be associated before.
Definition bmsparsevec_serial.h:813
bm::sparse_vector_serializer::set_sim_model
void set_sim_model(const xor_sim_model_type *sim_model) BMNOEXCEPT
Attach serizalizer to a pre-computed similarity model.
Definition bmsparsevec_serial.h:824
bm::sparse_vector_serializer::serialize
void serialize(const SV &sv, sparse_vector_serial_layout< SV > &sv_layout)
Serialize sparse vector into a memory buffer(s) structure.
Definition bmsparsevec_serial.h:941
bm::sparse_vector_serializer< rsc_sparse_vector_u32 >::xor_sim_model_type
bm::serializer< bvector_type >::xor_sim_model_type xor_sim_model_type
Definition bmsparsevec_serial.h:188
bm::sparse_vector
succinct sparse vector with runtime compression using bit-slicing / transposition method
Definition bmsparsevec.h:87
bm::sparse_vector::get
value_type get(size_type idx) const BMNOEXCEPT
get specified element without bounds checking
Definition bmsparsevec.h:1758
bm::sparse_vector::size
size_type size() const BMNOEXCEPT
return size of the vector
Definition bmsparsevec.h:729
bm::sparse_vector::set
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
Definition bmsparsevec.h:1849
bm
Definition bm.h:78
copy_buffer
unsigned char * copy_buffer(unsigned char *buf_ptr, const SVLay &sv_lay)
Copy buffer content into the buffer.
Definition rscsample05.cpp:134
sv16_serializer_type
bm::sparse_vector_serializer< sparse_vector_u16 > sv16_serializer_type
Definition rscsample05.cpp:56
fill_test_data
static void fill_test_data(sample_data_frame &df)
generate some data just to illustrate the case
Definition rscsample05.cpp:95
csv_serializer_type
bm::sparse_vector_serializer< rsc_sparse_vector_u32 > csv_serializer_type
Definition rscsample05.cpp:55
deserialize_df0
static void deserialize_df0(sample_data_frame &df, const std::vector< unsigned char > &buf, csv_deserializer_type &csv_dser, sv16_deserializer_type &sv16_dser)
Simple (individual) de-serialization of vectors in the data-frame.
Definition rscsample05.cpp:202
csv_deserializer_type
bm::sparse_vector_deserializer< rsc_sparse_vector_u32 > csv_deserializer_type
Definition rscsample05.cpp:57
main
int main(void)
Definition rscsample05.cpp:444
sparse_vector_u16
bm::sparse_vector< unsigned short, bvector_type > sparse_vector_u16
Definition rscsample05.cpp:51
rsc_sparse_vector_u32
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 > rsc_sparse_vector_u32
Definition rscsample05.cpp:53
test_data
static void test_data(sample_data_frame &df)
paranoiya check to make sure data frame matches pre-generated values
Definition rscsample05.cpp:113
sv16_deserializer_type
bm::sparse_vector_deserializer< sparse_vector_u16 > sv16_deserializer_type
Definition rscsample05.cpp:58
serialize_df0
static void serialize_df0(const sample_data_frame &df, std::vector< unsigned char > &buf, csv_serializer_type &csv_ser, sv16_serializer_type &sv16_ser)
serialize with disabled XOR compression
Definition rscsample05.cpp:144
deserialize_df2
static void deserialize_df2(sample_data_frame &df, const std::vector< unsigned char > &buf, csv_deserializer_type &csv_dser, sv16_deserializer_type &sv16_dser)
Collaborative de-serialization of vectors in the data-frame.
Definition rscsample05.cpp:345
serialize_df2
static void serialize_df2(const sample_data_frame &df, std::vector< unsigned char > &buf, csv_serializer_type &csv_ser, sv16_serializer_type &sv16_ser)
Data frame serialization using collaborative method (XOR compression).
Definition rscsample05.cpp:244
raw_data_size
size_t raw_data_size(const sample_data_frame &df)
Estimate raw data size.
Definition rscsample05.cpp:78
bm::sparse_vector_serial_layout
layout class for serialization buffer structure
Definition bmsparsevec_serial.h:58
bm::sparse_vector_serial_layout::size
size_t size() const BMNOEXCEPT
return current serialized size
Definition bmsparsevec_serial.h:85
bm::xor_sim_params
Parameters for XOR similarity search.
Definition bmxor.h:59
sample_data_frame
sample data-frame structure with multiple bm vectors
Definition rscsample05.cpp:63
sample_data_frame::sample_data_frame
sample_data_frame()
Definition rscsample05.cpp:70
sample_data_frame::csv3
rsc_sparse_vector_u32 csv3
Definition rscsample05.cpp:66
sample_data_frame::csv2
rsc_sparse_vector_u32 csv2
Definition rscsample05.cpp:65
sample_data_frame::sv0
sparse_vector_u16 sv0
Definition rscsample05.cpp:68
sample_data_frame::csv1
rsc_sparse_vector_u32 csv1
Definition rscsample05.cpp:64
sparse_vector_u32
bm::sparse_vector< unsigned, bm::bvector<> > sparse_vector_u32
Definition xsample02.cpp:68
rsc_sparse_vector_u32
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 > rsc_sparse_vector_u32
Definition xsample03.cpp:205
bvector_type
bm::bvector bvector_type
Definition xsample07a.cpp:94