Hi,

If I have an information source x bits long with an entropy of n bits,
Is it possible to mathematically calculate the maximum potential
compression ratio that Huffman Coding could yield on the information
source with respect to its entropy?

Clearly, if you have a proper model, typical strings are the most likely strings generated by the source, and thus you have *usually* the compression ratio Huffman grants you, but in the unlikely event of an atypical string you might have no compression at all, and rather an expansion.

Clearly, if you have a proper model, typical strings are the most likely strings generated by the source, and thus you have *usually* the compression ratio Huffman grants you, but in the unlikely event of an atypical string you might have no compression at all, and rather an expansion.

Of course, expansion only occurs from to the overhead of transmitting
to model. In compressing the symbols alone, Huffman encoding
guarantees an output less than or equal to the input size.

Thomas Richter <thor at (no spam) math.tu-berlin.de> wrote:
sebastian schrieb:
(snip)
Of course, expansion only occurs from to the overhead of transmitting
to model. In compressing the symbols alone, Huffman encoding
guarantees an output less than or equal to the input size.

That wasn't my point, though. My point was rather: "NO, IT DOESN'T".

Example: use the following Huffman code:

A -> 1
B -> 01
C -> 000
D -> 001

Does this Huffman code ensure "compression"?
Not at all. If I feed it by *any* message I like to, *most* of the
messages will be expanded, so it clearly doesn't ensure it.

As far as I know, there are two ways to use Huffman coding.
One is to use a static table based on expected statisical
distribution for the data. Group 3 FAX does that. Morse code
does that.

The other way is to generate one based on the specific data set
to be compressed. In that case, and not including the bits needed
to code the table, it would seem that output should not be greater,
though could be equal. If all symbols have equal probability
then the result will be equal.

I thought unix used to have a program to do huffman code file
compression but I don't see it now.

Back to the OP: There, we had the question what we can say about Huffman
compression if we know something about the entropy of the source.
Entropy, again, is a term computed from probabilities. Not from relative
frequencies. Mixing the two is a common error, but that's not the same
thing. Probabilities can be assumed and are part of the model. Relative
frequencies are measured on an input string. If we only know the
entropy, we still do not know anything about the string. Only how it
would typically look like, but not how it does look like.

Back to the OP: There, we had the question what we can say about
Huffman compression if we know something about the entropy of the
source. Entropy, again, is a term computed from probabilities. Not
from relative frequencies. Mixing the two is a common error, but
that's not the same thing. Probabilities can be assumed and are part
of the model. Relative frequencies are measured on an input string. If
we only know the entropy, we still do not know anything about the
string. Only how it would typically look like, but not how it does
look like.

Hey I have a question which sits in the back of my head, since you
start to be "so picky" :^)

Do you actually know a single example, where you do know the
real-entropy^tm of a source? You make the impression that
real-entropy^tm is a deterministic / calculateable term, and not an
extrapolation of an observation.

I would agree with that theoretically the sources real-entropy^tm is
distinct to observed entropy, but both (in general) are respective a
given model, and because of that the real-entropy^tm is of limited use
(you know your observed entropy is never absolute correct not even in
respect to a specific model, and it's only x% efficient) given the fact
that it is very difficult to get exactly.

Well actually I do can imagine a source with observation==real, that is
when you say something for example can only and only create "Hamlet",
not a byte more, no variation, nothing different.

Buuut then real-entropy^tm is identical to the entropy of the coded
stream (let's say LZ, 123k, the compressed file can't give you anything
else than "Hamlet").

This of course (for me) can't be true (it means claiming
universal==specific, contradiction), and is of doubtful use, because you
don't want to create a specific model for each finite message. I'm
referring to programs here, you don't want to program a specific model
for a specific single message.

That's the point of my example, either you have infinite source and you
try to model fragments of it by approximating the source's
real-entropy^tm though piecewise observation (human-brain => "Hamlet",
but also others, infinite others), or you model context-free atomic
universally independent finite sources which makes no sense whatsoever.

In the end I suspect, expect that real-entropy^tm can't be quantified
in absolutes, and the best approximation would come from KC (then we get
model independent entropy, if you don't count KC as a model as well).

And simply waiting for the computer with infinite computational
abilities, we just accept our little poor custom-model dependent entropy
as liable approximation, which in most cases because of convenience is
plain order-0 entropy (of a little piece of an infinite string: that are
all the other "files" you want to compress and haven't yet).

So, I hope I'm not completely out of my mind. And to ask the question
again, maybe lost in my discourse:

Do you actually know a single example, where you do know the
real-entropy^tm of a source?

Oh, I don't allow to count artificial constructed sources according an
entropy. My emphasis is more about an equivalent to "know real-Pi^tm",
which was observed, then approximated, then modelled, then absolutely
determined, and now the verify a circle in reality though the model Pi,
instead of verifying Pi as before. Taking the number "5" and saying
"this constant is '5', exactly and always", is not the sort of answer I
thought of.

glen herrmannsfeldt schrieb:
.....
Lets get away from the math and look at actual real compression
problems.  If I have a file I want to compress, already stored
in disk, I can count the number of each character in that file.
I then don't care about 'typical' but just this one file.

Sure enough, you do what all other people also do: You built up a
probability model from the observed characters.

Many compression algorithms allow for stream compression,
where output can be generated before the end of the input
string is known.  That is certainly nice, but is not always
required.  I was going to look at the man page for pack and compact,
but they don't seem to exist on the systems I use.

Such stream compressors are the back-end of many compression standards.
LZ and its variants are stream compressors. The MQ coder in JPEG 2000
and JBIG is a stream compressor.

Nevertheless, they all have a model that *guesses* probabilities.

Back to the OP: There, we had the question what we can say about
Huffman compression if we know something about the entropy of the
source. Entropy, again, is a term computed from probabilities. Not
from relative frequencies. Mixing the two is a common error, but
that's not the same thing. Probabilities can be assumed and are part
of the model. Relative frequencies are measured on an input string. If
we only know the entropy, we still do not know anything about the
string. Only how it would typically look like, but not how it does
look like.

Lets get away from the math and look at actual real compression
problems. If I have a file I want to compress, already stored
in disk, I can count the number of each character in that file.
I then don't care about 'typical' but just this one file.

Many compression algorithms allow for stream compression,
where output can be generated before the end of the input
string is known. That is certainly nice, but is not always
required. I was going to look at the man page for pack and compact,
but they don't seem to exist on the systems I use.

That's just backwards from what I'd say. Entropy and probabilities are
nothing you "know by observation", i.e. it is not a measurable quantity.
Probabilities and entropies are *assumed*. They are part of a model. You
cannot compute them. You can assume them.

If the requirement is 'compress file X, as stored on disk' then yes
I do know the probabilities.

For stream compression, say writing data to a tape while it is
being generated, then I don't know the frequencies in advance.

I might have one buffer full, but not the whole data stream.
In that case, the algorithm has to rely on the observations of
previous data, that is, it is causal.

Some people need one type of algorithm, others can use either.

If you have the whole file of concern there are no
"guesses" you can calculate the probabilities of each
symbol exactly.