Subject: Re: theoretical compression factor

From: [email-masked] (Douglas W. Jones,201H MLH,3193350740,3193382879)
Date: 3 Apr 91 19:46:35 GMT

>From article <[email-masked]>,
by [email-masked] (David M. Read):

>>Is p lg p a hard-and-fast bound or not? I still think it's an average.
> 
> You can get arbitrarily close to that sum, but you may not go under
> it, unless you *increase* entropy somewhere else.

Right, but, speaking as a Computer Scientist with a degree in Physics ...

Information theoretic entropy is mathematically identical to quantum
mechanical entropy.  I think that this is one of the biggest surprises
in 20th century science, given that Shannon didn't set out to apply
statistical thermodynamics to information flow problems.  Once he
recognized that the mathematics was the same, he was quite happy to
borrow names like entropy for the information theoretic quantities
that he needed to name.

Back to the subject, the entropy of a message, is a hard and fast bound
on the compression only in a statistical sense.  If your compression
algorithm compresses some message to fewer bits than the entropy
indicates, then your algorithm must compress some other message to more
than p log p bits.  This is the tradeoff that parallels the second law
of thermodynamics.

In information theory, the entropy of a message can only be measured
relative to a statistical model of the source.  For example, we can use
observed letter frequencies to build a model for English, but having
done so, we have no guarantee that the language used from that point on
will correspond to the frequencies we measured.

Also, better source models, for example, letter pair frequencies or word
frequencies, lead to lower entropy values.

					Doug Jones
					[email-masked]

---

From: [email-masked] (Victor Miller)
Date: 4 Apr 91 15:23:53 GMT

There are two kinds (at least) of information: statistical, of which
entropy is the answer (only in an expected sense), and computational,
as in Kolmogorov-Chaitin-Martin-Lof, etc.  My favorite example to get
people thinking is from a paper of Ziv and Lempel:  Construct a
sequence of bits as follows: first write down in order all 1 digit
binary numbers (with leading zeroes if they are there), then all two
digit, etc.  The surprising fact that they prove is that this sequence
is incompressible by ANY finite-state compressor (of which Huffman, or
arithmetic coders are good examples), but it is rather easy to see
that an efficient way of transmitting this sequence is to send a
program to generate it, along with the length of the sequence.
--
			Victor S. Miller
			Vnet and Bitnet:  VICTOR at WATSON
			Internet: [email-masked]
			IBM, TJ Watson Research Center