Add-on for simongog/sdsl-lite that defines a new compressed bitvector called s9_vector
Implements a new type of compressed bit vector with support of rank1 and select1 operations. s9_vector is based on a previous implementation that was made with libcds in mind and adds new features such as block size as a template parameter, 64 bits support and several bug fixes.
Converts the input bit_vector into a compressed bitvector using gap encoding and then compresses the resulting integer vector using Simple 9 encoding for each block previously defined.
First install simongog/sdsl-lite as usual. Then include the new bitvector header that is in include/sdsl/s9_vector.hpp as it's shown in the next example:
#include <iostream> #include <sdsl/int_vector.hpp> #include <sdsl/rrr_vector.hpp> #include <sdsl/sd_vector.hpp> #include "s9_vector.hpp" using namespace std; using namespace sdsl; int main(){ bit_vector b = bit_vector(80*(1<<20),0); for (size_t i=0; i<b.size(); i+=100) b[i] = 1; cout << "Size in Bytes:\n" << endl; cout << "Original\t" << size_in_bytes(b) << endl; rrr_vector<63> rrrb(b); cout << "RRR\t\t" << size_in_bytes(rrrb) << endl; sd_vector<> sdb(b); cout << "SD\t\t" << size_in_bytes(sdb) << endl; s9_vector<> s9b(b); cout << "S9\t\t" << size_in_bytes(s9b) << endl; s9_vector<128, int_vector<32>> s9b32(b); cout << "S9(32)\t\t" << size_in_bytes(s9b32) << endl; return 0; }