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?
$\begingroup$
$\endgroup$
7
-
2$\begingroup$ You might look at en.wikipedia.org/wiki/Kolmogorov_complexity $\endgroup$– Dávid NatinggaAug 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-yAug 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 SuomelaAug 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-yAug 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$– JuhoAug 26, 2012 at 23:28
|
Show 2 more comments
4 Answers
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ Other than purely random data I don't think any data type meets these conditions. $\endgroup$ 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$– svickAug 26, 2012 at 16:05
$\begingroup$
$\endgroup$
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.
answered Aug 28, 2012 at 21:37
$\begingroup$
$\endgroup$
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:
- Comp.compression FAQ
- Matt Mahoney. Data Compression Explained
- Ian H. Witten, Alistair Moffat, and Timothy C. Bell. Managing Gigabytes.
- Wikibooks: Data Compression is a rough draft
- the footnotes of Wikipedia: data compression
$\begingroup$
$\endgroup$
1
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.
