GoKawiilA while back I wrote about language modeling without neural networks, where I generated Shakespeare with an unbounded n-gram model: no weights, no training, just counting. Fortuitously, I came across the paper Language Modeling is Compression, which mentioned the compression–prediction equivalence:
every prediction model is inherently a compressor, and all compression algorithms are prediction models.
This led to the natural question: can gzip do language modeling? No neural network, no learned parameters, nothing. Just the compressor that ships with your operating system. You prime it with a corpus, give it a normal text prompt, and it continues that prompt by searching for the byte sequences that compress best. Here’s some real, unedited output after priming it on tiny Shakespeare:
gzipt --corpus data/tinyshakespeare.txt --prompt $'MENENIUS:
' --length 200
MENENIUS: 'Though all at once canq MARCIUS: Pray now, nocamest thou to a morsel . LARTIUS: Hence, and I' the end admire, where G again; and after it ag .
It turns out, kind of? It’s not exactly coherent text, but it clearly knows something about the text. Much more than I expected gzip to know. So how can a compressor generate this?
Compression is prediction#
Think about what a compressor does. It spends few bytes on data it “expects” and many bytes on data it doesn’t. If I hand you a file that’s the letter A repeated a million times, you can describe it in one sentence. A million random bytes, on the other hand, have no structure to exploit and barely compress at all.
This is not a coincidence; it’s the core of information theory. The number of bits needed to encode a symbol is $-\log_2 p$, where $p$ is the probability the model assigns to it. High probability means few bits. So any compressor has a probability model hiding inside it, whether or not anyone wrote one down.
... continue reading