Home -> Playground -> Jacobson's Rank

Jacobson's Rank

Adjust the bit array size, n.

See that R1 and R2 grow sub-linearly with respect to n.

B

10 bits

n bits

R1

4 bits

n / log²(n) cells, each encoded using log(n) bits

R2

6 bits

n / log(n) cells, each encoded using log(log(n)) bits

██████████ + ████ + ███████ = 19 bits

A cumulative rank value is stored for every log²(n) bit "chunk" from B.

GOTCHA'S

* R1 Stores "cumulative rank" values from B. Since those values can approach n, each cell is encoded using log(n) bits.

* R2 Stores "relative cumulative rank" values from B. Since they are reletive, each value can be encoded using log(log(n)) bits.