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

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?

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.

• I'm with you on your 1st paragraph: LZ still leaves some redundancy to further compress. But your 2nd paragraph still seems to be jumping, if not hand waving. There are two assertions: 1. The redundancy remaining after LZ is zero-order (that is, p(X_n) is approx. independent of x_n-1; I'm using the term zero-order as in zero-order model, eg data-compression.com/theory.shtml ) and 2. On zero-order redundancy, Huffman works better than LZ; On higher-order redundancy, LZ works better. Perhaps these assertions are both true, but you haven't justified either – SRobertJames Aug 8 '11 at 4:35
• @Robert: Higher-order correlations have no effect whatsoever on Huffman coding. LZ works asymptotically optimally for higher-order redundancy, but the extra overhead required means that it doesn't do as well on finite-length zero-order sources. This must have been studied experimentally in the literature somewhere; maybe somebody else can give a pointer to a reference. For point 1, my intuition is that any higher-order redundancy remaining after LZ is too complicated to be used in any simple coding scheme, but I have no good way to justify this. – Peter Shor Aug 8 '11 at 5:03

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.

• Thank you, Jouni. It sounds like the main redundancy left is that rep lengths are usually smaller rather than larger (not evenly distributed over [0,2^n]). Huffman does well on this zero order asymmetry, whereas LZ really needs larger features to work well. Is that correct? And why not use Huffman to start with - why bother with LZ at all? – SRobertJames Aug 8 '11 at 14:31
• If we compress the text directly with Huffman, we cannot get better compression than zero-order entropy. However, most real texts have significant sources of redundancy that cannot be modelled adequately with zero-order entropy. In many cases, using LZ before Huffman allows us to compress this redundancy. – Jouni Sirén Aug 9 '11 at 10:12

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.

• I accept the first paragraph: you explain why LZ leaves redundancy. But the second paragraph seems to be quite a leap: Why does Huffman catch this redundancy? Why not LZ again? And, if Huffman is more comprehensive, why not just it to start with? – SRobertJames Aug 8 '11 at 2:28

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.

• People have defined adaptive Huffman coding, which only looks at the input once. For the purposes of this discussion, adaptive and non-adaptive Huffman coding will behave pretty similarly. – Peter Shor Aug 9 '11 at 12:42

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.

• I think that the stationary ergodic source is just an assumption that makes LZ easier to analyze. After all, the compression is based on combinatorial properties of the input, which just happen to coincide nicely with the statistical properties in many cases. Consider, for example, a collection of English language texts in plain text format, followed by the same texts in HTML format. LZ compresses this collection quite nicely, even though it does not look like something generated by a stationary ergodic source. – Jouni Sirén Aug 14 '11 at 15:52
• @Jouni: I would disagree with this comment; I think that in some sense, plain text English language looks a lot like a stationary ergodic source, and this resemblance is exactly what LZ is taking advantage of. – Peter Shor Aug 15 '11 at 2:13
• @Peter: But in this case, the source first generates some texts in plain text format, and then exactly the same texts in HTML format. This change from plain text to HTML at some arbitrary point seems to break the ergodic stationary property. On the other hand, compression results are much better than when compressing the plain texts and the HTML texts separately, as there is a lot of mutual information between a text in plain text format and the same text in HTML format. – Jouni Sirén Aug 15 '11 at 12:14