Concise Data Structures Part 2: Concise Data Structures for Bitvectors - Retrieva TECH BLOG Concise data structure - Wikipedia
Concise Bit Vector (Complete Dictionary) - Mister Miscellaneous
- Rank and select are constant time
- This feature itself is OK with [cumulative sum
- The feature is that it can be kept compact assuming the value range is 0/1
- If the original range is small enough, the table pull will result in O(1)
- Table of size 256 for 8 bits
- If you keep track of the number of 1’s (RANK) up to that point every 8 bits, it will be O(1) up to that point as well.
- Compress this table itself one more step.
- For example, record RANK every 512 bits.
- Local, Express, Limited Express Idea
- Compress this table itself one more step.
- If the original range is small enough, the table pull will result in O(1)
This page is auto-translated from /nishio/簡潔ビットベクトル using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.