Add rank and select?

Two common building blocks for specialized data structures are rank and select.

For example, if our collection is a list of booleans (or bits), select(n) would return the index of the nth item which is set to true; rank(n) would return the number of true elements up to the nth index -- rank is sometimes also called population count or popcnt. Corresponding operations for false elements are sometimes called select0 and rank0.

These operations may not seem like much, but when they are implemented efficiently, they form the foundation for a number of more powerful data structures, such as wavelet trees. Broadly, data structures built on rank and select are often referred to as "succinct data structures," as they often use very little additional memory beyond what would be required to store the elements sequentially.

Is the Swift Algorithms package the right place to add these fundamental oeprations? I would be interested in contributing to the implementation, or having a conversation about this topic :slight_smile:

4 Likes

I hope to see this! If Swift Algorithms has implementation of rank and select, it is really great.

1 Like

Does it make more sense for these to be generic algorithms that exist on all sequences or collections or for these to be specific operations on a specialized type?

We have a GSoC student working on a BitArray/BitSet data structure, these algorithms seem like good candidates for that data structure.

This is definitely the right place for us to be having the conversation!

2 Likes

Hello, Kyle! Nice to talk with you again. I hope you’re well.

The latter, I think. There are further operations built on top of efficient rank and select for bits that would be better candidates for generic algorithms.

Yay! Agreed there. Depending on the integer width and the CPU architecture there are a number of highly efficient tricks to compute these; in some cases with a single instruction.

Glad I am in the right the place. :slight_smile:

1 Like