Version 6.3.0

Release Notes

1. The main story of this release is to improve rsc_sparse_vector>< (Rank-Select compressed container) to add const_iterator class to simplify access to container content. Container now provides both C-stype (decode* methods) and iterator. This release also includes significant optimizations to improve Rank-Select access.

2. rscsample03.cpp illustrates usage of: bm::rsc_sparse_vector<>::const_iterator
3. Performance optimization: rsc_sparse_vector<>::decode* methods (up to 2x improvement)
4. Performance optimization: bvector<>::enumerator (constant iterator for bvector<> to decode bit-vector as indexes of set bits)
5. New method to compute corrected rank bvector<>::rank_corrected() New method computes rank() minus value(0 or 1) of the index value. rank_corrected() is faster than an equivalent expression of "rank()-test()" BitMagic uses rank_corrected() in succinct algorithms for container address resolution. sample17.cpp Example reworked to illustrate rank_corrected()

Download v6.3.0 (Sourceforge) GitHub

Technical notes on Rank-Select sparse vector

Rank-Select Succinct data representation is also known as “NULL values compression”. This is not a truly compression method, it is a succinct method. The terminological difference between compression and succinct is our ability to access the data in compressed form (with some penalty) without decoding the whole data block or compression page.

BitMagic implementation of Rank-Select compressed vector combines two methods: NULL compression implemented with Rank-Select method AND bit-transposition. Bit transposition implements a succinct variant of variable bit codec.

Combination of both methods in one container allows to achieve better in-memory compation without loosing ability to search and access data, trading CPU penalty for memory and disk storage efficiency.