### 11 releases

0.2.1 | Oct 3, 2023 |
---|---|

0.2.0 | Oct 2, 2023 |

0.1.8 | Sep 28, 2023 |

0.1.7 | Aug 14, 2023 |

#**1130** in Data structures

**GPL-3.0-only**

**10MB**

1.5K
SLoC

# ransel - a library for succinct rank/select data structures

Succinct data structures offer a space-efficient way to store bitmaps (or sets of integers, depending on your point of view). They use a simple but powerful API based on 2 basic functions:

*rank*which given a an element*x*from the domain of the set, returns the number of elements of the set which are less than*x*.*select*which given an index*i*from the range of the set, returns the*ith*smallest element of the set.

There are a number of derived operations, but they may all be expressed in terms of *rank* and *select*. In some cases, however, we do use special implementations which may have better runtime performance than the naive implementations.

###
`lib.rs`

:

The

library provides a rank/select API to sets of integers originally
due to Guy Jacobson:`ransel`

Jacobson, G., 1989, October. Space-efficient static trees and graphs. In 30th annual symposium on foundations of computer science (pp. 549-554). IEEE Computer Society.

The beauty of the rank/select API is that it allows many useful operations to be performed over sets of integers (or bitmaps, depending on your point of view), without needing to think about the underlying representation of the set. Indeed, there are many different representations that can be used depending on the expected density and size of the set.

Various forms of this API have been presented (notably Simon Gog's sdsl-lite), with slightly varying definitions. The definition we use is uniformly 0-based.

Given a set

of non-negative integers over a finite domain, we define:`S`

is the size of the domain, and is at least 1 greater than the largest
element in `S .size()`

`S`

.

is the number of elements in `S .count()`

`S`

.

is the number of elements in `S .rank(x)`

`S`

that are strictly less than `x`

.
`rank_1`

is an alias, and `rank_0`

is the complementary definition: the number
of non-negative integers less than `x`

that are *not*in

`S`

(n.b. `rank_0`

and
`rank_1`

may be defined in terms of each other, with `S.rank_0(x) = x - S.rank_1(x)).

is the i-th smallest element in `S .select(i)`

`S`

, with `0`

being the index of the
first element.The API is broken down in to components:

The

trait exposes the `ImpliedSet`

and `size`

operations.`count`

The

trait exposes `Rank`

and its associated operations.`rank`

The

trait exposes `Select`

and its associated operations.`select`