8
$\begingroup$

Is Huffman coding always optimal since it uses Shanon's ideas? What about text, image, video, ... compression?

Is this subject still active in the field? What classical or modern references should I read?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ You might look at en.wikipedia.org/wiki/Kolmogorov_complexity $\endgroup$
    – Dávid Natingga
    Aug 25, 2012 at 4:13
  • $\begingroup$ DavidToth's link is the answer. In short "no". You cannot prove any data is compressed minimally (which of course makes it impossible to prove an optimal algorithm) $\endgroup$
    – edA-qa mort-ora-y
    Aug 25, 2012 at 6:58
  • 2
    $\begingroup$ @edA-qamort-ora-y: "You cannot prove any data is compressed minimally" — this is not true. Cf. the halting problem, which in general is undecidable, but of course there are some programs for which we can prove that it halts or does not halt. Cf. also the busy beaver function; some values of the function are known. $\endgroup$
    – Jukka Suomela
    Aug 25, 2012 at 13:19
  • $\begingroup$ @JukkaSuomela, yes, my phrasing was not thorough in that regards. You can obviously have specific sets of data which could be shown to be optimally compressed. My guess however is that the size of such data is extremely small. $\endgroup$
    – edA-qa mort-ora-y
    Aug 25, 2012 at 13:50
  • $\begingroup$ A cool metric you might be interested in is the normalized compression distance (NCD). Vitanyi & Li among others have papers on it. In short, it works quite well for all kinds of data and majorizes all other metrics in a sense. Check the Vitanyi & Li book on Kolmogorov complexity for a good starter if you want. $\endgroup$
    – Juho
    Aug 26, 2012 at 23:28

4 Answers 4

Reset to default
9
$\begingroup$

Huffman coding is optimal for a symbol-to-symbol coding where the probabilities of every symbol are independent and known before-hand. However, when these conditions are not satisfied (as in image, video), other coding techniques such as LZW, JPEG, etc. are used. For more details, you can go through the book "Introduction to Data Compression" by Khalid Sayood.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Other than purely random data I don't think any data type meets these conditions. $\endgroup$
    – edA-qa mort-ora-y
    Aug 25, 2012 at 6:51
  • 4
    $\begingroup$ But the other techniques are not symbol-to-symbol. That's how they achieve better compression. And that's also why Huffman coding is rarely used by itself. $\endgroup$
    – svick
    Aug 26, 2012 at 16:05
7
$\begingroup$

There is a version of the Lempel-Ziv algorithm which is optimal in some scenarios. Namely, if the input comes from an ergodic Markov chain, then the asymptotic rate of the Lempel-Ziv algorithm equals the entropy. For more on that, take a look at Chapter 13 of Cover and Thomas.

Improve this answer
$\endgroup$
7
$\begingroup$

Huffman compression, with certain assumptions that usually don't apply to real files, can be proven to be optimal.

Several compression algorithms compress some kinds of files smaller than the Huffman algorithm, therefore Huffman isn't optimal. These algorithms exploit one or another of the caveats in the Huffman optimality proof.

Whenever we have (a) we code each symbol independently in an integer number of bits, and (b) each symbol is "unrelated" to the other symbols we transmit (no mutual information, statistically independent, etc.), and (c) the receiver knows the probability distribution of every possible symbol, then Huffman compression is optimal (produces the smallest compressed files).

(a) symbol-by-symbol: By relaxing the binary Huffman restriction that each input symbol must be encoded as an integer number of bits, several compression algorithms, such as range coding, are never worse than, and usually better than, standard Huffman.

(b) unrelated symbols: most real data files have some mutual information between symbols. One can do better than plain Huffman by "decorrelating" the symbols, and then using the Huffman algorithm on these decorrelated symbols.

(c) known probability distribution: Usually the receiver does not know the exact probability distribution. So typical Huffman compression algorithms send a frequency table first, then send the compressed data. Several "adaptive" compression algorithms, such as Polar tree coding, can get better compression than Huffman because they converge on the probability distribution, or adapt to a changing probability distribution, without ever explicitly sending a frequency table.

Books and papers discussing such better-than-Huffman compression:

Improve this answer
$\endgroup$
2
$\begingroup$

The optimal compression rate is related to the entropy of the data.

From the Wikipedia article http://en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem:

N i.i.d. random variables each with entropy H(X) can be compressed into more than N H(X) bits with negligible risk of information loss, as N tends to infinity; but conversely, if they are compressed into fewer than N H(X) bits it is virtually certain that information will be lost.

Improve this answer
$\endgroup$
1
  • $\begingroup$ why is this downvoted? $\endgroup$
    – Sasho Nikolov
    Aug 29, 2012 at 3:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.