Why does Huffman coding eliminate entropy that Lempel-Ziv doesn't?

Question

The popular DEFLATE algorithm uses Huffman coding on top of Lempel-Ziv.

In general, if we have a random source of data (= 1 bit entropy/bit), no encoding, including Huffman, is likely to compress it on average. If Lempel-Ziv were "perfect" (which it approaches for most classes of sources, as the length goes to infinity), post encoding with Huffman wouldn't help. Of course, Lempel-Ziv isn't perfect, at least with finite length, and so some redundancy remains.

It is this remaining redundancy which the Huffman coding partially eliminates and thereby improves compression.

My question is: Why is this remaining redundancy successfully eliminated by Huffman coding and not LZ? What properties of Huffman versus LZ make this happen? Would simply running LZ again (that is, encoding the LZ compressed data with LZ a second time) accomplish something similar? If not, why not? Likewise, would first compressing with Huffman and then afterwards with LZ work, and if not, why?

UPDATE: It is clear that even after LZ, some redundancy will remain. Several people have made that point. What isn't clear is: Why is that remaining redundancy better addressed by Huffman than LZ? What's unique about it in contrast with the original source redundancy, where LZ works better than Huffman?

Answer 1

This was originally a comment, but it got too long.

If you look at DEFLATE, what is being compressed by Huffman is the output of LZ77; LZ77 works by (when this takes fewer bits than the raw data) sending an pointer earlier into the string being compressed, and a match length that tells how many symbols to take after the pointer. The theory shows that, even without additional compression, this technique eventually converges to the source entropy. However, in data compression, any time you have a distribution that isn't completely random, you might as well compress it. There's no reason to believe that the output of LZ77—the pointers and the match lengths—are completely random. They have to converge to complete randomness in the asymptotic limit, since LZ77 is asymptotically optimal, but in practice you only use a finite dictionary, so they presumably stay far enough away from being completely random that you win by doing further compression on them. Naturally, you use one Huffman code for the pointers and another for the match lengths, since these two processes have different statistics.

Why use Huffman rather than LZ for the second round of compression? The big advantage LZ has over Huffman is in treating dependencies between symbols. In English, if one letter is a 'q', the next is extremely likely to be a 'u', and so on. If the symbols are independent events, then Huffman is simpler and works just as well or better for short strings. For the output of LZ77, my intuition is that the symbols should be fairly independent, so Huffman should work better.

Answer 2

Data compression is really about two things: modelling and encoding. Algorithms of the LZ family model the text as a concatenation of exact repetitions, which is asymptotically optimal for many random sources and reasonably good for many real texts. For some inputs, this model can be quite bad, however. For example, you cannot use LZ to compress a suffix array directly, even though the suffix array is as compressible as the original text.

LZ77 encodes the input as a sequence of tuples $(p, \ell, c)$, one per repetition, where $p$ is a pointer to an earlier occurrence, $\ell$ is the length of the repetition, and $c$ is the next character. Usually this sequence does not contain many (reasonably long) exact repetitions, so we cannot use another LZ-based algorithm to compress it. Instead, we have to look for other models.

Of the three components of a tuple, the pointer can be thought as a large random integer, so encoding it as a $\log n$-bit integer (for an input of length $n$) is a reasonably good choice. On the other hand, repetition lengths are usually small, so we should encode them with codes that favor small numbers over large numbers. Huffman is one suitable coding scheme, and there are others as well. The characters after repetitions are probably not evenly distributed, so we can use a zero-order compressor such as Huffman to squeeze out the most obvious redundance.

So in short, Huffman beats LZ in compressing the tuples, as its model (fixed distribution vs. exact repetitions) is a better match for the data.

Answer 3

I belive the answer lies in the lookup dictionary size.

Data has a sense of locality (that is to say, if a piece of data has been used, it is likely that it will be used again soon), and the LZ algorithm takes advantage of this in the lookup dictionary construction. It generates a trie with a finite amount of possible nodes, to keep lookups fast. When it hits the size limit, it makes another trie, "forgetting" about the previous one. So it has to build again the lookup table for the simpler characters, but if some words are not used anymore, they are not kept in memory anymore, so an smaller encoding can be used.

Therefore, a LZ output can be reduced further with Huffman encoding, for this redundancy in the creation of the lookup tries can be detected by statistical analysis.

Answer 4

Perhaps I am off track here, but Huffman encoding looks at the entire input to build its encoding table (tree), whereas Lempel-Ziv encodes as it goes along. This is both an advantage and a disadvantage for Huffman. The disandvantage is obvioious, namely that we have to see the entire input before we can begin. The advantage is that Huffman will take into account statistics that occurs anywhere in the input, whereas Lempel-Ziv has to build up to it progressively. Or to put it in a different way, Lempel-Ziv has a "direction" which Huffman does not.

But all this is just my naive way of imagining how things are. We would need a real proof here to see how exactly Huffman outperforms Lempel-Ziv.

Answer 5

The short answer is, LZ is a "universal" algorithm in that it doesn't need to know the exact distribution of the source (just needs the assumption that the source is stationary and ergodic). But Huffman isn't; it needs to know the exact distribution from which the source is sampled (for making the Huffman tree). This additional information makes Huffman attain tight compression guarantees. However for practical file compression algorithms Huffman may be less favorable since it will first need to gather empirical statistics of the file and then do the actual compression in a second half, while LZ can be implemented online. Running LZ on a compressed sequence does not necessarily eliminate the remaining redundancy since the processed source no longer satisfies the theoretical requirements of the algorithm on the second round (ergodicity and stationarity).

More details can be found in standard information theory texts, e.g., Elements of Information Theory by Cover and Thomas.