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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityIs 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?
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.
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.
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:
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.