A Gentle Introduction to Data Compression

Well written! I was just looking for the Shannon Minimum Coding Rate definition the other day, so it was nice to have a quick refresher on the basics.

This also highlights a fundamental issue: the coding scheme is tailored to the expected data input. That's why there's no one-size-fits-all compression algorithm, and you can achieve far greater efficiency if you have a good model of the shape of the input data. (The same applies to lossy)

The MCR is also a nice way to demonstrate how random data can't be compressed. Let's say you have 256 symbols, each with probability 1/256 (independent etc). The Shannon Entropy = -sum(P(x) * log2(P(x) for x in 0..255) = -2^8 * 2^-8 * -8 = 8 bits. No compression possible.

lz77 is a little hard to explain, but I don't have any degree in CS nor math and I managed to understand it a little, not that I could really be able to reproduce it.

isn't lz77 the most efficient text compression algorithm ?

I found Compressor Head quite enjoyable: https://www.youtube.com/watch?v=Eb7rzMxHyOk&list=PLOU2XLYxms...

I think that for beginners it's far better to talk about the LZ-style algorithms first, since they are much easier to understand without requiring any discussion of probabilities and the associated maths; the idea of replacing repeated strings with a reference to them is very intuitive, and so is the implementation of an LZ compressor/decompressor. In fact, an in-memory LZ decompressor core can be written in less than two dozen bytes of x86 instructions, and can easily outperform the fastest Huffman decompressor.

When I was interested enough in compression to read about it, the majority of the information I could find seemed highly theoretical and made me think that Huffman was a good first step so I managed to write a simple static/dynamic Huffman compressor/decompressor, but that didn't work so well. It was "fast enough", but the compression ratio was disappointing. When I discovered LZ the difference was amazing: an extremely simple algorithm, requiring about an order of magnitude less code in implementation, that compressed much better than Huffman for data which would intuitively be compressible.

In retrospect, it's quite clear that Huffman and other "variable length code" techniques only work because of nonuniformity in symbol probabilities, so it is ineffective on data containing repeating patterns but uniform probability. E.g. take a string 256 bytes long containing all the byte values 0, 1, 2, ... 253, 254, 255; and repeat that string multiple times in a file. LZ can easily compress that pattern but Huffman can't. (Does LZ rely on probability nonuniformity? It doesn't look like it.) The fact that many common methods like FLATE use Huffman only to compress the output of LZ on their input probably reflects this, but I don't think I've seen such an intuitive explanation for it before.

Huffman encoding reminds me of UTF-8. What is the connection there? Is UTF-8 based on Huffman encoding?