How does RRR work?
Building the RRR structure
When you build an RRR structure you have to define the bitstring and a sample rate.
BitSequenceRRR::BitSequenceRRR(const BitString & bs, uint sample_rate);
bs is the source data
sample_rate is todo
BLOCK_SIZE := 15, by definition.
C_field_bits := 4, it means how many bits required to express BLOCK_SIZE
Note: I use these values from here without the variable names.
C_len := number of 4 bit blocks in source data
C := uint array with size enough to hold C_len * 4 bits
It makes a table_offset object named “E” with BLOCK_SIZE parameter:
This call creates:
- 2 simple arrays: short_bitmaps[2^(15+1)], offset_class[15+2];
- 2 two dimensional arrays (with dimension (15+1)x(15+1)): binomial, log2binomial
- 1 array (_List) with size 2^(15+1+1)
See how these tables look like: binomial table, log2binomial table, short_bitmaps, offset_class
You get the log2binomial table by ceiling the log2 values of the binomial table.
You get short_bitmaps array by iterating all possible numbers with the given number of 1s in it’s binary form.
offset_class array contains the offsets (in short_bitmaps) of the classes of ones.
Note: short_bitmaps and offset_class tables was generated with BLOCK_SIZE set to 4 for readability.
I have no idea what is the purpose of _List after the creation of these tables (it’s saved as rev_offset). The algorithm for filling sort_bitmaps and offset_class arrays are REALLY complicated, contains deep recursion, names written in Spanish.. so I skip describing it’s inner working.
It iterates through the source data and counts the number of ones in 15 bit groups (see BLOCK_SIZE). In the iteration it always sets the next 4 bits (see C_field_bits) of array “C” with this number.
While iterating the total number of ones is summed and … todo
Getting the 15 bit parts and setting the 4 bit parts in uint arrays is done by using the uint arrays as packed arrays.
These are the functions for handling arrays as packed arrays (libcdsBasics.h):
inline uint get_var_field(const uint *A, const size_t ini, const size_t fin); inline void set_field(uint *A, const size_t len, const size_t index, const uint x)
Problems and inefficiencies in RRR
- Zeroing is done one by one. A standard library call should be used instead!
- generaClase function uses deep recursion which is inefficient
- There are lots of +1s,+2s in array dimensions which are unnecessary
so you assembly this?
At that time I’ve lost interest (and time) for working out how RRR works in libcds. Visit Alex Bowe’s page if you are interested in RRR: https://alexbowe.com/rrr/