Original string: 9 A’s, 4 B’s, 2 C’s, 1 D, 3 A’s, 9 D’s — 28 characters.
Counted by symbol: 12 A’s, 10 D’s, 4 B’s, 2 C’s.
Entropy coders are almost always the final step in any compression algorithm and are what produce the final compressed artifact: a raw bitstream, which is just a bare sequence of bits with none of the structure a file format would wrap around it.
I want to focus on the last two steps, because this is important. Our data model hands the entropy coder a set of probabilities to encode your data as efficiently as possible. Probabilities go in, compressed bitstream comes out:
Entropy Coder
100101110
Now, let’s be honest: this is all still a bit hand-wavy. What does an entropy coder even DO with all these probabilities? How does that help it do the squishing?
Bookmark this sectionSquishing data with probabilities Every entropy coder is a unique snowflake, and the way they use probabilities to compress your data differs wildly. To keep things simple, we’re going to focus on just one for now: arithmetic coding. I’m choosing it because it best illustrates how better probabilities make for better compression.
Bookmark this sectionArithmetic coding What if I told you that you could represent an entire dataset with a single number? Does this sound crazy? I thought so too, but that’s exactly what arithmetic coding promises.
Let’s say we want to compress the string “ABABAAC”A B A B A A C. We can find the probabilities of each symbol (character) by dividing the total count by the total length of the string, which is 7:
Original string: 1 A, 1 B, 1 A, 1 B, 2 A’s, 1 C — 7 characters.
Counted by symbol: 4 A’s, 2 B’s, 1 C.
We can represent these probabilities on a range from 0-1.
The range from 0 to 1, divided into one section per symbol, each as wide as that symbol’s probability and ordered widest first: A covers 0 to 0.571, B covers 0.571 to 0.857, C covers 0.857 to 1.
With this setup, we’re ready to do the actual compressing.
For each symbol in our string, starting with “A”, we shrink our range to fit within that symbol’s section. Importantly, we’re still dividing that new range with the same probabilities, but they now have new, smaller ranges.
Click the arrows to encode each symbol and see how the range shrinks over time:
Interactive, step-by-step illustration of arithmetic coding for the string A B A B A A C, where every symbol shares one probability distribution. It starts at the full range from 0 to 1 with nothing encoded. Each step highlights the slice the next symbol encodes into, then reveals the range that slice becomes. The last step zooms in on the final range.
ABABAACNext character
Range: [0.00000, 1.00000)
Once we run out of symbols, we end up with a teeny weeny baby range: [0.38730, 0.38855).
The final number that will represent our entire data can be any number in this range, and ideally, it should be the number that requires the fewest bits possible. You can calculate this with a bit of math, but because I’m nice I’ll just give you the answer: 0.3876953125. So let’s compare: Our original string, “ABABAAC”A B A B A A C, in its raw 8-bit ASCII code requires 56 bits in total, whereas our final number requires only 10.
So, we have our magical number, but how do we use this to decode our original message? Buckle up, this is going to seem like a magic trick.
Bookmark this sectionDecompressing arithmetic codes In addition to our magic number, our decompressor also receives the same probabilities we used to compress so it can rebuild that starting range of [0, 1). To decode our original message, it finds which section our magic number falls into and records that symbol. Then it shrinks the range to fit within that section, and repeats the whole process.
Interactive, step-by-step illustration of arithmetic decoding of the number 0.3876953125. Symbol probabilities split the range from 0 to 1 into slices: A 57 percent, B 29 percent, C 14 percent. Each step zooms in on the current range, shows where the number falls inside it — that slice is the decoded symbol — and then reveals the range that slice becomes. The last step decodes the last symbol, recovering the whole string.
Next character
Range: [0.00000, 1.00000)
Pretty neat, huh?
We’ve now seen how an entropy coder can compress our data using a set of probabilities. As cool as arithmetic coding is (it’s not just me, right?), much of the heavy-lifting comes from the model. Remember: compression loves redundancy. Given this, what do you think would happen if our symbols had more repetition?
Bookmark this sectionHow probabilities affect compression Here’s a new string where the letter A dominates, with a probability of 0.833.
Original string: 10 A’s, 1 B, 1 C — 12 characters.
Counted by symbol: 10 A’s, 1 B, 1 C.
It turns out, this skewed probability distribution makes a big difference. Let’s see how it stacks up against our old string when we apply arithmetic coding:
Final number0.38769531250.1474609375
Our first string managed to compress to an average of 1.38 bits/symbol, whereas our longer string compressed to 0.82 bits/symbol. When your data is more skewed (i.e. the higher the probabilities of some of your symbols), the better the compression ratio.
This avg bits/symbol is a very important number. It’s called entropy, and it is the bedrock of compression.
Bookmark this sectionEntropy Consider the following sentence:
“Yesterday I saw an animal when I was walking downtown. It was a _____.”
How many guesses do you think it would take you to fill in the blank? If it was a common animal like bird, you might get it on the first try. But what if the answer was bear? That would probably take quite a few guesses.
Let’s say these are the possible answers, along with their probabilities written as fractions:
Knowing the probabilities, we can actually calculate how many guesses it would take to guess correctly, on average, per animal.
Now, notice that each animal is half as likely as the one before, with the exception of fox and bear (these are probabilities, so our numbers need to add up to 1). If we were to guess each animal in order, from most probable to least, we’d have a 50/50 chance of being right each time. As such, we can determine the number of guesses it would take to guess a given animal (on average) using a yes/no decision tree. We start with the most likely animal at the top, and work our way down:
A yes/no decision tree over the animals. Is it a bird? If yes, bird, 1 guess. If no, is it a squirrel? If yes, squirrel, 2 guesses. If no, is it a cat? If yes, cat, 3 guesses. If no, is it a fox? If yes, fox, 4 guesses. If no, bear, 4 guesses.
yesnoyesnoyesnoyesnobird?squirrel?cat?fox?BIRD1 guessSQUIRREL2 guessesCAT3 guessesFOX4 guessesBEAR4 guesses
Let’s get back to compression. Symbols with higher probabilities help us compress better, and we see the same pattern in our decision tree: the more probable animals require fewer guesses. If we treat the animals as symbols and swap the yes’s and no’s for 1’s and 0’s, the number of guesses becomes exactly the number of bits needed to represent each one. If we record the 1’s and 0’s we take to reach each animal you’ll see that the more common animals get shorter “codewords” (unique sequences of bits), and rarer animals get longer ones.
A yes/no tree over the animals. Each yes branch is labeled 1 and each no branch is labeled 0, so an animal’s code word is the branch labels that reach it. Is it a bird? If yes, bird, code word 1. If no, is it a squirrel? If yes, squirrel, code word 01. If no, is it a cat? If yes, cat, code word 001. If no, is it a fox? If yes, fox, code word 0001. If no, bear, code word 0000.
10101010bird?squirrel?cat?fox?BIRD1SQUIRREL01CAT001FOX0001BEAR0000
Assigning codewords to symbols like this is actually another type of entropy coder called Huffman coding, which is used in popular tools like gzip and Brotli. Instead of encoding our data into a single number, like with arithmetic coding, the Huffman method creates codewords to represent each symbol.
But there’s a problem: what happens when our probabilities aren’t neatly divided in half? If cat had a probability of 0.3973, then the likelihood of the answer being a cat or not a cat isn’t 50/50 anymore. Every path down the tree is a whole number of “guesses”, so we’re forced to round, and rounding means paying for bits we don’t need. How can we tell the absolute fewest number of bits required to represent a given symbol?
Turns out we can calculate this with a little bit of math:
If we plug in our animal probabilities, you’ll see we get the same number of bits as guesses from our decision tree:
If we get the average −log2(probability)negative log base 2 of probability of all our symbols, that tells us our entropy.
The most important thing to understand about entropy is that it’s the floor. This is the smallest number of bits per symbol we can achieve for a given set of data. It ain’t getting any more squished.
But wait, if there’s really a limit to how much you can compress data, why isn’t there just one mega God-compressor that we use on everything? Well, that’s because entropy is specific to a set of probabilities. If we can make our probability distribution more skewed, we can compress things more.
Bookmark this sectionContext matters
Up until now, we’ve been working with a very simple type of model that only cares about a symbol’s frequency. count / total_symbols = its probability.
But context can greatly affect a symbol’s probability. For example, in the entire English language, the letter U has a probability of ~0.028. However, when preceded by a Q, this shoots up to ~0.999.
On top of that, higher probabilities compress into fewer bits. We saw this before in the arithmetic coding section, but now we can prove it with math:
Using a single context to determine the probability of a symbol is called an order-1 model. It answers the question, “Given (some context), what is the probability of (symbol)?” With order-1, you factor in the previous symbol as your context, but you could expand this to order-2, order-3, order-4, and so on, which look at the previous N symbols.
But how do we feed this into an entropy coder? Previously our model was just a table of probabilities per symbol, but with context, we suddenly have a whole set of tables, one for each preceding symbol. So what do we do?
Let’s see what happens when we apply arithmetic coding to the string “TO BE OR NOT TO BE” using an order-1 model. Notice that with each symbol we encode, our new ranges contain a different set of probabilities.
Interactive, step-by-step illustration of arithmetic coding for the string T O space B E space O R space N O T space T O space B E, where each symbol’s probability is conditioned on the previous symbol. It starts at the full range from 0 to 1 with nothing encoded. Each step highlights the slice the next symbol encodes into, then reveals the range that slice becomes. The last step zooms in on the final range.
TO BE OR NOT TO BENext character
Range: [0.00000, 1.00000)
Ok, but how much does using order-N models actually impact compression?
Final number0.0499914009290.058705
Wow! Using an order-1 model cut our compressed output by more than half! Clearly, adding context gives us stronger probabilities. In other words, it helps us predict what symbol comes next.
Do you know what else is really good at prediction?
Bookmark this sectionLanguage modeling and compression To say that there’s an overlap between LLMs and compression would be a huge understatement. In fact, in 2023, Google DeepMind released a paper arguing that language modeling and compression are two views of the same thing.
This might seem like an odd claim. After all, when you think of using LLMs, you probably think of typing a prompt into an AI chatbot and it responding with an answer. How is that compression?
You might have heard LLMs described as “fancy autocomplete”, and this is essentially true. When you submit a prompt to an LLM, that becomes the context the model uses to return a set of probabilities for the next possible words. It then chooses one of those options and appends it to the context. Rinse and repeat. That’s how LLMs generate text.