Let us assume that I have a sequence of positive integers, no clue about the length of the sequence and the range of the values in the sequence. Very less chance of repeating any numbers in the sequence. The numbers in the sequence might be completely random numbers. If we wish to represent this sequence of numbers using a variable length binary representation. Which is the best encoding scheme currently available?
The Elias gamma coding scheme is fine to use. Let me know something else that may work better than Elias gamma coding scheme.
If we define the efficiency of a storage scheme as the number of bits a number requires in isolation divided by the number of bits the storage scheme requires, then the Elias gamma storage scheme has an efficiency approaching 50% on large numbers.
A more efficient scheme is to represent numbers in base $b$ arithmetic where $b=2^n-1$. Thus, each digit in base $b$ requires $n$ bits. However, this leaves one value unused, the one where all the bits in a 'digit' are equal to 1. We use that value to indicate the end of the number.
The efficiency of the base $b$ scheme approaches $log(b)/log(1+b)$ for very large numbers. Hence, making $b$ large means we can approach 100% efficiency. But, making $b$ large imposes a penalty on the storage of small numbers.
@Prof. Alun Wyn-jones , Thanks much for detailed description. I am really looking for a variable length representation which works like EliasGamma but may have better efficiency. I am just trying encode a run-length sequence to the binary form.
- Badges
- Science topic
- Similar topics
- Computer Science
- Research Topics