Basic
We want to store a list of positive integers using not too much memory.
An int is usually strored in 32 bits, but small values have a lot of zeros on the left
Decimal => Binary
5 => 0000 0000 0000 0000 0000 0000 0000 0101
1895 => 0000 0000 0000 0000 0000 0111 0110 0111
Since we don't know in advance the biggest value of our list, we can't set a maximum value and use instead of 32bits, X bits where X is the number of bits used for that maximum value. eg, if our values would be between 0 and 255, we knew we could encode our values on 8 bits instead of 32.
Elias gamma will allow us to encode our values on a variable number of bits. It is more complicated that Elias Gamma but is more optimal to encode big values in memory.
We can also generalize and encode positive and negatives integer.
3 steps encoding
We want to encode X > 0
1/ Express X as 2^N +M , N has to be the ighest possible and M are the remaining bits
2/ Encode N+1 with Elias Gamma : GN
3 / Append M to the right of GN
Examples
X=8
1) X = 1000 = 2^3 + 000X=3
2) GN = gamma(4) = 00100
3) Deltacode = 00100 000
1) X = 11= 2^1 + 1X=14
2) GN = gamma(2) = 010
3) Deltacode = 010 1
1) X = 1110 = 2^3 + 110
2) GN = gamma(4) = 00100
3) Deltacode = 00100 110