From: torbenm@diku.dk (Torben AEgidius Mogensen)
Newsgroups: rec.puzzles
Subject: Re: Serial representation of arbitrary data
Date: 16 Dec 92 15:52:02 GMT
Organization: Department of Computer Science, U of Copenhagen

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.

There is no fixed "best" solution to this, as it depends on the
probabilities for the possible sequences. Note that there can not be a
uniform distribution (as then the probability of each sequence would
be 0). One obvious solution is to represent a number with N+1 bits
(note that no number has 0 bits) by some representation of N followed
by the N+1 bits of value. But this leads back to how the number N is
to be represented (as this can have arbitrary size), so a recursive
schema is needed.

Another solution is to use a kind of infinite Hamming code if the
probabilities of all numbers are known in advance, p0 being the
probability of 0, p1 being the probability of 1 etc, p0+p1+p2+... =1.
One usually starts by the least probable value, but unless there is a
limit on the size of the numbers (which the premise is that there
isn't) there is no least probable number.  So my suggestion is to cut
at an arbitrary level (say, 7) and then let p7' be p8+p9+.... We can
then build a Hamming tree in the usual way for the 9 possibilities
0-7 and >7. Each of these are given a bit-sequence (of varying
length). If the sequence represent one of the possibilities 0-7, then
the next number starts just after the bit sequence. Otherwise a
representation of the actual number using the probabilities p8/p7',
p9/p7',... is found. When building the Hamming tree for the numbers
8,9,... a new cutoff is needed etc.

Assuming (arbitrarily) that the probability for the number n is
k/((n+1)^2), where k = 6/(pi^2) we get the following probabilities for 0-7
and >7:

p0 = k
p1 = k/4
p2 = k/9
...
p7 = k/64
p7' = k*0.117512

The Hamming tree for these values are

		    ^
		   / \
		  /\  \
		 /  ^  \
		/  / \  \
	       /  /   \  \
	      /  ^     \  \
	     /  / \     \  \
	    /  /   \     \  \
	   /  ^     \     \  \
	  /  / \     \     \  \
	 /  /  /\    /\    /\  \
	1  5  7  6  4  3  2 >7  0

So the numbers are represented by the following sequences

 0  1
 1  01
 2  0110
 3  01011
 4  01010
 5  01000
 6  010011
 7  010010
>7  0111 + code for the number

So the sequence 354 would be represented by 010110100001010. Note that
there are no separation codes. The codes for the numbers just follow
after each other. When building the codes for the larger numbers,
larger groups are needed, otherwise the representation size becomes
exponential. A doubling or quadrupling of the size is probably good.
Actually, the larger the groups are, the better the density of the
representation, approaching the (unattainable) optimum in the limit.
A finite size for each group must be chosen, but the size can well
approach infinity in the limit. A size of 8 for the first group is
probably too little with the chosen probability distribution. The
distribution is not very good either, as the chance of the number
being 0 is about 60%. Something like k/((n+10)^2) is probably a better
compromise if no actual distribution is known.

To conclude: the question is meaningless unless some distribution of
the numbers is known. Even if a distribution is known, there (for most
distributions) is no single best coding, but rather infinite families
of codings that in the limit can approach an optimal coding.

	Torben Mogensen (torbenm@diku.dk)
Newsgroups: rec.puzzles