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