Consider a storing a permutation of 2^8 = 256 elements. The easiest way to store it is a byte array of length 256, consuming 8*256 = 2048 bits total.

The densest possible encoding is mixed radix based on the factorial, requiring log(256!)/log(2) = 1683.996 bits. (The .996 is a nice coincidence.)

A hybrid approach does bit-packing. The first 128 elements use 8 bits per element, then the next 64 use 7 bits, and so forth. sum(i=0,7,2^i*(i+1)) = 1793 bits.

## No comments :

Post a Comment