From: tromp@cwi.nl (John Tromp)
Newsgroups: rec.puzzles
Subject: Re: Serial representation of arbitrary data
Date: 15 Dec 92 10:16:34 GMT

warwick@cs.uq.oz.au (Warwick Allison) writes:


>This is a strange problem.  Maybe it has an obvious solution.
>The problem is this:
>	Represent a sequence of arbitrary length binary values.
>Do it in as short a number of bits as possible.

This problem has been well-studied in the context of algorithmic information
theory, which is generally concerned with minimal encodings of objects.
I assume you are not interested in the general case where a universal
Turing machine is doing the decoding, because then shortest encodings turn
out to be uncomputable. So let's restrict ourselves to computable encodings.

Basically, there is an optimal solution, but it's far from obvious.
However, it's easy to give a sequence of increasingly good approximations
to this optimal encoding. Note that the essence of your problem is to find
an encoding for integers which is `prefix-free', i.e. no codeword is a proper
prefix of another one. In this way you can concatenate the encodings without
losing track of the boundaries.

The simplest encoding of a non-negative integer n is n ones followed by a 0,
known as the unary encoding.

e_0(n) ::= 1^{n}0

Better is to precede n (the string n is simply the n-th string in the
lexicographic ordering of all strings "" < "0" < "1" < "00" < "01" < ...),
with a unary encoding of its length, which is the encoding you proposed.

e_1(n) ::= e_0(length(n))n

We can keep improving on this with the general scheme

e_{i+1}(n) ::= e_i(length(n))n

One might think that this is the end of the story, but it can be continued
with a new twist: suppose we just keep prefixing lengths until it gets to "0",
then all we need to decode is to know the number of iterations, which we'll
denote length*(n):

E_0(n) ::= e_0(length*(n))e_{length*(n)}(n)

This will improve on any of the e_i encodings for large enough n.

From here it's obvious that we can continue with more improvements,
but for practical purposes n doesn't go to infinity and so ...

The `optimal' variation is based, not on iterated length, but on iterated
logarithms. If we define (with logarithms to base 2)

L(n) ::= log(n) + log(log(n)) + log(log(log(n))) + ... + (0,1],

then it turns out that the summation over all n of 2^{-L(n)} is finite
(less than 8 in fact, if I'm correct).
By something known as Kraft's inequality this imples the existence of
a prefix-code of the integers of length L(n)+3. This is in some sense
(which is beyond the scope of this article) optimal and the prefix-code
can be effectively constructed if one is willing to compute those iterated
logs with sufficient precision. For more information, one is well advised
to look up references to Algorithmic Information Theory aka
Kolmogorov Complexity, by experts in the field such as Paul Vitanyi, Ming Li
(still busy working on their book) and Gregory Chaitin.

>  _-_|\      warwick@cs.uq.oz.au            /Disclaimer:
> /     * <-- Computer Science Department,  /  
> \_.-._/     University of Queensland,    /   C references are NULL && void*
>      v      Brisbane, Australia.        /  


-John Tromp (tromp@cwi.nl)         f() is total -- R.L. Goodstein
define s(n){;auto e,r;for(0;n;n/=b)r+=n%b*(b+1)^s(e++);return(r)}
define f(n){;for(b=2;n;b++)n=s(n)-1;return(b)} for(n=0;1;n++)f(n)
Newsgroups: rec.puzzles