[Solved]: Variable Length Encoding of Integers

Problem Detail: 

I was just researching Fibonacci encoding of integers. Numbers are encoded in binary and where no two consecutive bits are equal to 1 - other than to terminate the number.

Now other schemes are possible, for example having three or more 1's terminating the number. These representations are more efficient (shorter) for larger numbers but less so for small numbers.

My question is, is it possible to have an optimal scheme where the number of terminating 1's increase as the size of the number increases? And have no ambiguity.

Some examples to clarify:

a. 0 = '1', 1 = '01', 2 = '001', 3 = '0001', 4 = '00001', 5 = '000001', 6 = '0000001'

b. 0 = '11', 1 = '011', 2 = '0011', 3 = '1011', 4 = '00011', 5 = '10011', 6 = '01011'

c. 0 = '111', 1 = '0111', 2 = '00111', 3 = '10111', 4 = '000111', 5 = '100111', 6 = '010111'

These use 1, 2, and 3 terminating 1's respectively.

Asked By : Guillermo Phillips

Answered By : Yuval Filmus

There is no optimal scheme for encoding integers. To understand what this statement even means, we need a few definitions.

---

A codeword $w$ is a word over the alphabet $\{0,1\}$.

A sequence of codewords $w_0,w_1,w_2,\ldots$ is a code.

A code $w_0,w_1,w_2,\ldots$ is prefix-free if no $w_i$ is a prefix of any $w_j$ for $i \neq j$.

A code $w_0,w_1,w_2,\ldots$ is monotone if $|w_0| \leq |w_1| \leq |w_2| \leq \cdots$.

An integer encoding scheme is a monotone prefix-free code.

An integer encoding scheme $x_0,x_1,x_2,\ldots$ is better than an integer encoding scheme $y_0,y_1,y_2,\ldots$ if $|x_i| - |y_i| \to -\infty$.

---

The codes that you give are examples of integer encoding schemes which get progressively better.

Theorem. For any integer encoding scheme $y$ there is a better integer encoding scheme $x$.

In fact, the situation is even worse: there is no optimal sequence of codes:

Theorem. For any sequence $y_1,y_2,\ldots$ of integer encoding schemes there is an integer encoding scheme $x$ better than all of them.

For proofs see, for example, this paper.

Elias came up with a sequence of codes, including the gamma and delta codes, which are progressively better, culminating in the limiting omega code; but even this code isn't optimal.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28719