Data Compression

Compression is not just about shrinking files — it is the bridge between raw data and the models that understand it. When you train a language model to predict the next word, you are teaching it to compress the text: a well-written sentence is shorter because it is more predictable. Understanding compression gives you the intuition behind why models are trained the way they are, why they are measured in bits and tokens, and why larger models need more data. It also unlocks nearby concepts in your library: Shannon Entropy, Huffman Coding, Cross-Entropy Loss, and KL Divergence — all of which are just different answers to the same question: what makes data compressible? Master this and you will see the maths that runs under ChatGPT, speech recognition, and even how your phone stores photos.

Think of a sentence in a novel. 'The quick brown fox jumps over the lazy dog.' If you had to send this to a friend over a very slow text connection, you would not send the whole thing letter by letter. You would find a way to shorten it. Maybe you both agree that 'the' is written as 'th', 'quick' as 'qk', and so on. That is compression — finding a shorter way to represent the same information. Now think of a photo of a blue sky. Most of the pixels are the same colour — a very deep blue. If you named that colour 'B' and then said 'B repeated 1000 times', you have made the photo much smaller without losing anything. That is lossless compression: you can reconstruct the exact original. But sometimes you can throw away detail that nobody will notice — like the tiny variations in the blue that your eye cannot see. That is lossy compression: the file is even smaller, but you can never get the original back exactly. Compression is everywhere: ZIP files, JPEG photos, MP3 music, and even the way your phone makes a call. It is all about finding what is redundant in the data and removing it.

Imagine you are packing a suitcase for a trip. You have a pile of clothes. If you fold each shirt and place it next to its identical twin, you can squash them together — that is redundancy. Lossless compression is like folding: you can unfold it later and get the same shirt. Lossy compression is like cutting off the sleeves because you never wear them anyway — the suitcase is lighter, but you will never get the full shirt back. Now think about how you pack more efficiently when you learn that some clothes are more likely to be worn than others. You give the favourite shirt a bigger space, the rarely worn one a tiny corner. That is like Huffman coding: common symbols get short codes, rare ones get long. The entropy of the data is like the total number of shirts you must pack, regardless of how you fold. No matter how clever you are, you cannot pack more than the minimum number of shirts — that is the entropy bound. The suitcase is the file, the clothes are the data, and the folding is the algorithm. The analogy stops when you consider that a suitcase has a fixed size, but compression is about reducing the data to fit, not about a fixed container — you can always make the file smaller if you are willing to lose more detail (the rate-distortion curve).

Data compression is the process of encoding information using fewer bits than the original representation, either by exploiting statistical redundancy (lossless) or by discarding perceptually unimportant detail (lossy), and the minimum number of bits needed to encode a source is given by its entropy.

This is your first step into information theory, the branch of maths that quantifies information itself. Before this, you have not studied probability or statistics, so we will build from scratch. But you already know how to count, add, and multiply — that is all we need. Compression is the direct gateway to Shannon Entropy (the theoretical limit), Huffman Coding (a practical way to approach that limit), Cross-Entropy Loss (how models measure their error in bits), and KL Divergence (what it costs to use the wrong probability model). Every one of these concepts in your library is a variation on the same theme: how well can you predict the next symbol?