Experiment № 090 · The story
Said It Before
Why I picked it
In 1977 Abraham Lempel and Jacob Ziv published a short paper in the IEEE Transactions on Information Theory with a deliberately dry title, "A Universal Algorithm for Sequential Data Compression." The idea inside it is in almost every file you have ever downloaded. ZIP, gzip, PNG and the compression on the web pages you load are all descendants of it, usually with Huffman's codes stacked on top to squeeze the pointers.
This collection already has Huffman and the Burrows–Wheeler transform, both of which work on letter statistics. Neither of them has the plainer idea underneath: most of what anyone writes, they have already written, so say "like before" instead.
What I enjoy about it
It keeps no dictionary. The text already written is the dictionary, and the decoder builds the same one for free just by writing out what it decodes. Press decode and the page wipes itself, then rebuilds every letter using nothing but the list of pointers. No table travels with the message, because none is needed.
My favourite part is in the Laughter source. A row of "hahaha" takes a couple of tokens to get going, and after that a single instruction covers it: go back two, copy the next thirty-odd letters. The copy is longer than the distance, so it reads letters it is still in the middle of writing. That looks like a bug and is in fact the cleverest part. It is how one pointer can stand for any amount of repetition. Switch to Noise and the arcs vanish and the output comes out bigger than the input. That's the honest part. A compressor can only find structure that is actually there.
Something you might take away
Compression is mostly noticing that you've said it before. A long text that is cheap to describe is one that keeps pointing back at itself, which is why the rhyme shrinks and the noise doesn't. It also explains a trick worth keeping: you often don't have to send someone a shared reference. If you both build it the same way from what has already gone between you, it is already there on both ends.