Int_vector compressed with Elias-Fano

[amallia]

I was wondering if there is an easy way to compress a non-decreasing sequence of integers using Elias-Fano coding. I know that sd_vector is using it to compress a bitvector. Thank you.

[mpetri]

The sd_vector has a constructor taking 2 iterators: sd_vector(const t_itr begin,const t_itr end). So you can construct an sd vector using the begin() and end() iterators of the int_vector. Then you can use select_1 to access the original elements in the int_vector in the sd_vector representation

[amallia]

@mpetri thanks for the explanation. Regarding the construction it is now clear.

Could you provide an example of select_1 to access the original elements? Moreover, it would be useful to have a next_geq* operation, is it possible to do it with the current implementation?

*next_geq stays for next greater or equal and tries to find the given value in the list of integers or - if not present - the smallest of the greatest, returning the position of the chosen element.

Thank you

[danielsaad]

Hi @amallia . After talking with @simongog I created this example:

 sdsl::int_vector<64>v = {1,3,5,6,8};
 sdsl::sd_vector<> vs(v.begin(),v.end());
 sdsl::sd_vector<>::select_1_type sel1;
 sdsl::util::init_support(sel1,&vs);
 cout << sel1(3)-sel1(2)  << endl;

First we do a partial sum of the elements in the int_vector. Second we construct a sd_vector from the partial sum array. Finally, the ith element can be retrieved by doing select(i+1)-select(i), if i>0 and select(1), if i=0

In the example, the number 2 shall be printed.

[amallia]

Thank you for the example!