6
$\begingroup$

The naturals $\mathbb{N}$ can be encoded with a binary unary code such as

$$ \begin{align} 1&=0_b\\ 2&=10_b\\ 3&=110_b\\ &... \end{align} $$ The length this the encoding grows linearly with the natural number it represents. For example the length of $110_b$ is 3 and it also represents the number 3.

I am looking for an upper bound on the optimality of the prefix free encoding. For example, can we design a prefix coding of $\mathbb{N}$ such that the length of the encoding grows according to ~$\sqrt{n}$, instead of $n$. Is there an upper bound on the optimality that we can prove?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You say that encoding is unary and then ask if you can make it sublinear? Simply, no, there is no way to do it without using arbitrary amount of 0's for each number. Yet $\sqrt n$ encoding is useless as usage of two symbols allows you logarithmic encoding. $\endgroup$ – rus9384 Aug 25 '17 at 15:13
  • 2
    $\begingroup$ @rus9384 No, I am asking for the most compact prefix code for $\mathbb{N}$ $\endgroup$ – Alexandre H. Tremblay Aug 25 '17 at 15:23
12
$\begingroup$

I wrote a paper on this. The short answer is that there is no optimal encoding, nor even an optimal sequence of better and better encodings.

Kraft's inequality states that there is a prefix code with word lengths $k_0,k_1,\ldots$ if and only if $$ \sum_{n=0}^\infty 2^{-k_i} \leq 1. $$ This gives a positive answer to your question. Concretely, Elias gamma coding has code word length $O(\log n)$. The idea is simple: first you encode the bit-length of the integer using your method (using roughly $\log_2 n + 1$ bits), then you encode the number itself (using another roughly $\log_2 n$ bits), for a total of roughly $2\log_2n + 1$ bits.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Can we then say that a prefix code can always be made more optimal? As result, the strongest provable upper bound is when the natural are encoded using all binary strings (not just prefix code)? $\endgroup$ – Alexandre H. Tremblay Aug 28 '17 at 14:20
  • $\begingroup$ Yes, a prefix code can always be improved. A related result is that there is no strongest provable upper bound. $\endgroup$ – Yuval Filmus Aug 28 '17 at 14:21
  • $\begingroup$ Surely, it cannot be made better than if you use all available binary strings to encoded them (ignoring the prefix code requirement), so that must be an upper bound, correct? $\endgroup$ – Alexandre H. Tremblay Aug 28 '17 at 14:30
  • $\begingroup$ Why stop at binary strings? You can get another upper bound from ternary strings. $\endgroup$ – Yuval Filmus Aug 28 '17 at 14:32
  • $\begingroup$ The problem is that this upper bound can be improved. Your bound shows that the length of the $n$th codeword must be at least roughly $\log n$, but you can improve it to $\log n + \log \log n$, for example. In contrast, there are codes in which the $n$th codeword has length roughly $2\log n$ and roughly $\log n + 2\log\log n$. $\endgroup$ – Yuval Filmus Aug 28 '17 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.