The main story of this release is to improve
rsc_sparse_vector><(Rank-Select compressed container) to add
const_iteratorclass 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.
illustrates usage of:
rsc_sparse_vector<>::decode*methods (up to 2x improvement)
bvector<>::enumerator(constant iterator for bvector<> to decode bit-vector as indexes of set bits)
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()
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.