Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

RankSelect uses double the space needed #548

Open
jorgehermo9 opened this issue Aug 12, 2023 · 0 comments
Open

RankSelect uses double the space needed #548

jorgehermo9 opened this issue Aug 12, 2023 · 0 comments

Comments

@jorgehermo9
Copy link

jorgehermo9 commented Aug 12, 2023

Currently, the RankSelect data structure stores rank samples for every s bits, but it stores the superblocks_1 samples and the superblocks_0 samples. It is not necessary to store the superblocks_0 samples, because given any position i, its associated rank_1 sample is in the position i/s on the superblocks_1 sample vector, and the superblock_0 sample at that point can be easily calculated as i - superblocks_1[i/s] without needing to store it...
Storing also the superblocks_0 when it could be easily calculated, duplicates the space used by this data structure.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant