I was reading about compression recently when I stumbled upon something crazy: that compressors and LLMs are, at their core, trying to solvethe exact same problem.
In this post, I’m going to walk us through the basics of compression to understand its deep relationship with language modeling. It’s probably going to blow your mind.
There are many ways of shrinking data. Takeminification, for example: it works by stripping code down to the bare minimum that machines need to parse. Human-readable variables are reduced to single letters; whitespace and comments are removed.
The resulting file is considerably smaller, and yet you’d almost never hear minification mentioned in the field of data compression. Why is that?
Minification is fairly straightforward: it just tosses out any syntax that’s not required by machines. But “true” compression relies onredundancyto condense data.
Consider the string“AAAAAAAAABBBBCCDAAADDDDDDDDD”of nine A’s, four B’s, two C’s, one D, three A’s, then nine D’s: there’s alotof redundancy here. We could encode this as a shorter string by noting the total run of each character in order:
Original string:9 A’s, 4 B’s, 2 C’s, 1 D, 3 A’s, 9 D’s—28characters,224bits.
Replacing each run with its character and how many times it repeats givesA9B4C2D1A3D9—12characters,96bits,57percent smaller.
Using standard 8-bit ASCII encoding, our original string requires224 bits, whereas our compressed string (“A9B4C2D1A3D9”) needs only96. Not bad!
The above technique is just one compression method (it’s calledrun-length encoding), but we can do much better. Actual compressors like gzip, Brotli, etc, rely on several methods to shrink data. Let’s take a look.
There are roughly three “organs” of modern compression tools:transforms,models, andentropy coders. I’m talking about these terms as if they were clear and distinct things, but the lines can get a little blurry, and they arerarelyused in isolation.
Transformsare the preprocessing steps that make our data easier to compress. The method we saw earlier
(run-length encoding) is an example of a transform, but it’s worth noting that transforms don’talwaysshrink the
data. Sometimes they can be used to createmoreredundancy, and the more redundancy, the more we can compress later
on. We aren’t going to focus on transforms in this article, but they’re still an important part of any compression tool.