Home -> Playground -> Jacobson's Rank

Adjust the bit array size, n.

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

n bits

n / log²(n) cells, each encoded using log(n) 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.

* 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.