2
$\begingroup$

Let $f:\mathbb{N}\rightarrow\{0,1\}^*$ be an injective computable function whose image is a prefix-free set, or more formally $\forall i,j \in \mathbb{N}: \forall x \in \{0,1\}^*: f(i) \cdot x = f(j) \rightarrow i = j$ where $\cdot$ is concatenation. I'll call $f$ a computable prefix code. A simple example is $f(n) = 1^n \cdot 0$.

If $f$ and $g$ are computable prefix codes, define $f \le g$ to mean $\exists c, n_0 \in \mathbb{N}: \forall n \in \mathbb{N}: n \ge n_0 \rightarrow \vert f(n) \vert \lt \vert g(n) \vert + c$. That is, $f$ compresses as well as $g$ if for sufficiently large $n$, values of $f$ are no more than a constant longer than values of $g$. And I'll say $f$ compresses better than $g$ if $f \le g \land \neg(g \le f)$.

The question is, given a computable prefix code $g$, is there always a better compressor $f$?

I know how to define an infinite sequence of codes, each better than the last: start with some number encoded in unary (with a null terminator), then use that as the length of another number encoded in binary, then use that as the length of another number encoded in binary, etc. some fixed number of times taking the final number as a result. I can make a compressor better than all of those by first calculating how many logarithms it takes to reduce the number to $1$ and outputting that number in unary, selecting the best of the previous set of codes. And I think I can work out how to extend this to an improving sequence of codes indexed by the computable ordinals.

This seems like a decent start but one problem is that $\le$ is not a total ordering and I can construct examples of codes that are not worse than any member of the above sequence, just give very short strings to some sparse set like the powers of $2$ and long strings to every other number.

I'm afraid I'm overlooking something obvious. Is there some method where given a program for some computable prefix code we can construct a better one, or just prove that one exists?

$\endgroup$
1
+200
$\begingroup$

Given any computable prefix free code, it is possible to construct a computable prefix free code that is strictly better. The basic idea is to alter the original code by increasing the length of some of the original codewords by 1 so that we can make room to occasionally have significantly shorter codewords.

Say we are given a computable prefix free code $f$. Define $g$ as follows.

  1. Set $g(0) = f(0)^\frown0$ (where $^\frown$ means concatenation).
  2. Let $n_0$ be the smallest number such that $|f(n_0)| > |f(0)| + 1$.
  3. For each $0 < n < n_0$ set $g(n) = f(n)$.
  4. Set $g(n_0) = f(0)^\frown1$.
  5. Set $g(n_0 + 1) = f(n_0 + 1)^\frown0$.
  6. Let $n_1$ be the smallest number such that $n_1 > n_0 + 1$ and $|f(n_1)| > |f(n_0 + 1)| + 2$.
  7. For each $n_0 + 1 < n < n_1$ set $g(n) = f(n)$.
  8. Set $g(n_1) = f(n_0 + 1)^\frown 1$.
  9. And so on.

In general, let $n_k$ be the smallest number greater than $n_{k - 1} + 1$ such that $|f(n_k)| > |f(n_{k - 1} + 1)| + k + 1$ and set $f(n_k) = f(n_{k - 1} + 1)^\frown 1$.

This $g$ is a prefix free code and its codewords are never more than one bit longer than those of $f$. But for every $n_k$, $|g(n_k)| \leq |f(n_k)| - k$. So $g$ is strictly better than $f$.

By the way, prefix free codes are characterized by Kraft's inequality. Namely, there is a binary prefix free code where the codewords have lengths $l_0, l_1, \ldots$ if and only if $\sum_{n = 1}^\infty 2^{-l_n} \leq 1$. Also, the proof of this is effective. If you are given an increasing sequence satsifying the above condition then there is a computable prefix free code where the lengths of the codewords matches the given sequence. It is possible to use this property to give another proof very similar to the one above (essentially we are replacing $2^{-l_{n_k + 1}}$ by $2^{-l_{n_k + 1}}/2$ so that we can replace $2^{-l_{n_k}}$ by $2^{-l_{n_{k - 1}}}/2$) and in general to understand what prefix free codes can and cannot look like.

$\endgroup$
  • $\begingroup$ Now I am thinking something stronger is possible: for any $b, f$ there is a $g$ such that $\exists n_0: \forall n: n \ge n_0 \rightarrow \vert f(n) \vert \lt \vert g(n) \vert - b$. Since $\forall b: \exists k: \sum_{n \ge k} 2^{-\vert f(n) \vert} \le 2^{-b}$, and the function returning $k$ given $b$ is computable, there is an encoding that saves $b$ bits for all sufficiently large numbers, not just infinitely many. Does that make sense? $\endgroup$ – Dan Brumleve May 28 '17 at 6:22
  • $\begingroup$ Yes, that is correct. $\endgroup$ – Patrick Lutz May 30 '17 at 5:28

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.