The Side Gig That Pays $8,000 Per Percent
Adam: Hi, I’m Adam Gordon Bell, and this is CoRecursive. And today I have here with me, which seems to be a trend, Don.
Don: Hello. I’m Don McKay, and I’m back.
Adam: So I sent you a text yesterday. What did I send you?
Don: You found us a side gig that pays $8,000, 8,000 Canadian dollars per 1%. And then I blocked you. No.
Adam: Blocked me. Yeah. So The thing that I wanted to talk about, I actually printed it out. It’s a real contest. It’s been around for about 20 years and there’s, there’s a prize.
Compress One Gigabyte, Win Half a Million
Don:
Losslessly compress the one gigabyte file enwik9 to less than 110 megabytes. More precisely, create a Linux or Windows compressor comp exe of the size S1 that compresses enwik9 to archive exe of size S2 such that S equals S1 plus S2 less than L…
Don: Equals yeah. 110 megabytes. It’s got, like, a whole bunch of them. It’s like 110,793,128.
Adam: So it’s, it’s zipping a file basically, you’re being paid to zip a file smaller than somebody else has zipped it.
Don: Oh, and then eventually you’ll run into problems because you’ll have to invent some other compression algorithm that will do it?
Adam: But the, so the file is a gigabyte of Wikipedia data, and then, whoever can make it into the smallest file and then reconstitute it, gets money.
Don: Yeah, I think I figured this out though. It’s middle out.
Adam: There’s more.
Don: Oh.
You are eligible for a prize of five hundred thousand euros: five hundred thousand euros times one minus S divided by L. Being able to compress well is closely related to intelligence as explained below. While intelligence is a slippery concept, file sizes are hard numbers.
Why a Zip File Contest Claims to Chase AGI
Don:
The intention of this prize is to encourage development of intelligent compressors programs as a path to AGI.
Adam: It’s a weird thing to say. The development of intelligent compressors, as a path to artificial general intelligence." it feels like saying, you know, like this, this, crossword contest will clear the way for world peace. Step one, really small zip file.
Don: Oh, it’s just a three-step process.
Adam: I mean, we may be simplifying it, but yeah. So when I was a kid, zipping was very important. I think my first computer had maybe, it was either 40 megabytes or 80 megabytes. You would run out of space very quickly. Had…
Don: Well, if you Wanted to take anything with you, you used to have to compress things down to put them on disk, and then you could, you know, split the file across multiple disks.
Adam: Which was a pain. Yeah, and I used WinRAR for that, I remember. And you…
Don: Used LHA. Yeah, I used to freeze and thaw things.
Adam: Anyways, here’s the thing I want to try to beat the contest, right? I don’t think we can get the whole 500,000 euros, but maybe we can get a 1% improvement, and then we can make some money.
Don: Cool. Yeah, I’ve, I’ve never actually looked into how compression works, so this will be enlightening.
First Attempt: Just Run Gzip on It
Adam: So I got my computer here, my MacBook Pro, Can you see this, or it’s way too small?
Don: It looks like, you’ve done an LS in Linux on some files that are in a directory.
Adam: So there’s enwik8 and enwik9, so if I gzip it…
Don: Have you not rehearsed this?
Adam: I never rehearse. I like to just let it fly.
Don: And let it fly. Okay.
Adam: Okay, so here we go. So enwik9, Originally, this is our… What was it?
Don: Originally it is one gigabyte, and they want you to compress it down to 110 megs.
Adam: Where did we get to? So we got it down to three hundred and twenty-two, megabytes from the original, one gigabyte. So that’s pretty good, we got, it’s like a third of the size almost exactly, right? We’ve taken it. So that’s our first step. We just– We send this in, collect our money.
Don: Well, I mean, you didn’t meet the requirement. It has to go down to a hundred and ten.
Adam: Oh, yeah, yeah, you’re right. So we’re at 322. We need to get it down.
Don: Yeah, you need to get it down to, what is it, 110.
Adam: We got a ways to go.
Don: Yeah, I mean, it doesn’t look like you’re getting close to the target.
Rolling Our Own Compressor From Scratch
Adam: Yeah. In fact, I did, try to double compress and it doesn’t, it didn’t gain me anything. And here I’m using gzip with, negative nine, which I believe is the…
Don: The maximum?
Adam: The maximum.
Don: Yeah. So you’ve reached the limits of the gzip algorithm.
Adam: Yeah. So we need to do something else. Okay. So I think the key thing to do is to just try to build our own compression algorithm, because I don’t think we’re gonna win with just gzip. Seems like somebody might have thought of that and collected it already. The easiest way that I can think of to make a file smaller, right? Like you, you just have a bunch of characters and some of the characters repeat. So the easiest thing I, I know of is just like when you have a repetition, you take it out, ‘Cause the whole idea with compression is, yeah, you need to find a way to just…
Don: Find patterns and then you replace those patterns with a symbol that’s smaller.
Adam: Yeah, and it’s each compression algorithm, ‘cause there’s a bunch of different ones, right? They each look and look for and are good at finding certain types of patterns. And if you actually don’t have those type of patterns, then it’s not useful. So each compression algorithm is sort of like a bet, on the type of output.
Don: Like a text file is, will compress more than some, a complex binary or something like that…
Adam: Yeah. And like the raw video frames of a video file can be compressed very well by like MPEG. But if you just took all those raw frames and tried to run them through a zip, they might not work as well because the MPEG encoder actually understands the type of patterns that are in a video…
Don: Yeah.
Adam: Yeah, I’m showing you basically my, my little algorithm. What are you seeing?
Don: You have a function that you’ve written that runs through a byte array and performs some kind of, transformation on it.
Adam: So I have a box for my, my little Python algorithm, and then sort of I can feed it input, and then I can kind of get an answer for how that compresses. And then I have this big button that lets me run it against the data set from the Hutter Prize. Okay, so here’s my first algorithm, right? So it’s just run length encoding. And then I’m gonna run it on this string, which I assume must be in Wikipedia somewhere, which just says, “No!” with an exclamation mark.
def encode(data: bytes) -> bytes:
out = bytearray()
i = 0
while i < len(data):
byte = data[i]
run = 1
while i + run < len(data) and data[i + run] == byte and run < 255:
run += 1
out.append(run) # write the run length ...
out.append(byte) # ... then the byte itself
i += run
return bytes(out)
def decode(data: bytes) -> bytes:
out = bytearray()
for i in range(0, len(data), 2):
count, byte = data[i], data[i + 1]
out.extend([byte] * count)
return bytes(out)
Run-length encoding, in full. Instead of writing a byte over and over, write it once with a count.
Don: So you’re, you’re going to replace all of the Os with another symbol that’s less space.
Adam: Yeah, this is my attempt to beat the prize, right?
Don: But isn’t that sort of what, gzip probably already incorporates?
Adam: W-we’ll find out. Okay, so if I run it on my no, yeah, it changes it to this format, right? So it’ll say, like, one N and then 24 O’s and then one exclamation mark. So…
Don: Less space than all of the 24 Os. Yeah.
Adam: Yeah. And so the, the compression ratio on that is, it’s 4.3 times smaller.
Don: Yeah, which that’s good.
Adam: That’s good. But if I run it on– Okay, here’s Don laughing.
Don: So just ha ha ha ha. So now there’s not quite repeat– like, there’s the same characters, but they’re not repeated sequentially.
Adam: Yeah. Okay, so I run on that and, yeah, the output format now, ‘cause for every letter I need to put the, the frequency of it, and now my, my compression ratio is… Well, I’ve actually made the document longer. Okay, so it’s not looking good, but let’s run the thing, on the Wikipedia small corpus. Okay, So you– it actually made the Wikipedia corpus larger. So we– our, our compression ratio is 0.53, so we’re doubling the size, which is worse than our zip.
Don: Yeah. The zip’s 2.74 times. And the record is 9.03.
Adam: Yeah, we got a ways to go.
Don: You gotta, yeah, ‘cause you’ve, you’ve made it bigger by…
Adam: Wrong direction. I think we’re Go…
Don: Yeah. It goes the wrong direction. So it’d be like turning a one gig file into a 1.5 gig.
"Noooooooooooooooooooooooo!" 26 bytes -> 6 bytes 4.33x
"hahahahahaha" 12 bytes -> 24 bytes 0.50x (grew)
enwik8 100,000,000 bytes -> 188,987,386 bytes 0.53x (grew)
The three runs, as measured. RLE bets that the same byte repeats, back to back — and English never keeps that promise.
Pointing Back Instead of Repeating Yourself
Adam: Yeah, now we know how to make files bigger. Okay, so I have another idea. The thing, the other thing that we could do is instead of just looking at, you know, letters repeating, we could assume that text repeats.
Don: Yeah, and it does because we use words and we use the same words over and over again.
Adam: Yeah. And so my new idea is whenever we find, a repetition of something, then instead of putting in that repeated text, we just put a pointer back to where it was. So…
def encode(s: str):
"""Tokens are either ('lit', ch) or ('ptr', distance, length)."""
out, i, n = [], 0, len(s)
while i < n:
best_len, best_dist = 0, 0
for j in range(i): # search everything seen so far
length = 0
while i + length < n and s[j + length] == s[i + length]:
length += 1 # matches may overlap the cursor
if length > best_len:
best_len, best_dist = length, i - j
if best_len >= 3: # only worth a pointer if we copy 3+
out.append(("ptr", best_dist, best_len)); i += best_len
else:
out.append(("lit", s[i])); i += 1
return out
The second algorithm. When the text ahead repeats something already seen, emit a pointer instead — “go back D characters and copy L of them”.
Don: Makes sense to me.
Adam: Yeah. So in this example, which I would like you to sing no…
Don: Like the, the Row, Row, Row Your Boat gently down the stream, and then merrily, merrily, merrily, life is but a dream. Know I don’t think I have to read the whole thing, do I?
Don: People Row, Row Your Boat. Which has a lot of repeated words in a pattern.
Adam: So yeah, I have my little algorithm. It’s just gonna– Basically, it’s like pointers from C, right? But in text. Whenever we have some text that repeats, we’ll just say like, “Use that.” So if we run this on row, row, row your boat, we end up with something like this.
Adam: So it ends up with row, and then it says repeat four to eight. So it’s, it’s taken the two rows out and replaced them with a pointer back. And then it’s got your boat gently down the stream merrily, and then the repeated merrilies become pointers back. And then it has life is but a…
Don: Stream.
Adam: Oh, it’s– Oh, it’s even catching part of letters.
Don: Yeah. It doesn’t know that it’s a word…
Adam: Okay, very cool. The– It works even better than I thought.
Don: Better than you anticipated.
Adam: And… Then it just ends with this, this final pointer because the whole thing repeats, gives us…
Don: Then… I see. Like, so that whole verse is now a pointer that the second verse just points to instead of…
Adam: Okay, actually we already ran it, so what do we get?
Don: 2.84 times. See? There you go.
r o w ␣ ◀4,8 y o u r ␣ b o a t ↵
g e n t l y ␣ d o w n ␣ t h e ␣ s t r e a m ↵
m e r r i ◀24,3 ◀8,23 ↵
l i f e ␣ i s ␣ b u t ␣ a ␣ d ◀52,5 ◀97,96
58 literals + 5 pointers = 68 bytes from 193 chars -> 2.84x
The song, sung twice. Each ◀D,L means “go back D and copy L” — and that last token, ◀97,96, is the entire second verse in a single pointer.
Adam: We’re getting somewhere. Suffice it to say that that is less good than gzip, but we’re making progress.
Don: Yeah, you’re going in the right direction.
Adam: That is a more likely pattern than, are just like repeated specific letters.
Don: You’ve widened your pattern recognition.
Adam: Yeah…
What Morse Code Knew About Compression
Don: Yeah.
Adam: But we can do even better, which dates back in some ways to Morse code? A clever thing that, that he did they don’t all have the same length, of dashes and dots. The most common, letters, if you’re doing a telegraph…
Don: Are shorter.
Adam: Are shorter, which allows you to compress things down…
Don: Yeah.
Don: Side note, SOS doesn’t stand for anything. It was just the simplest pattern to remember.
Adam: Oh, because it’s dashes and dots?
Don: Yeah. People think that the, the letters SOS actually stand for something. It doesn’t stand for anything, it’s just that the three longs and the three shorts are the easiest thing to remember, so it’s the easiest pattern to transmit.
Adam: That’s awesome. Yeah, I thought it was like save our, save our ship.
Don: Yeah, it doesn’t stand for anything…
Huffman’s Term Paper Nobody Could Solve
Adam: Okay, so the, the next thing we’re gonna hit is, like, an important idea.
Adam: It’s not mine, but an important idea in compression. So in the fall of 1951, there’s this grad student, and his name is David Huffman, and he’s 25, and he’s going to Ohio University, and he’s two years out of the Navy. And, has a class, and in the class they say, “You know, you can take the final exam,” “Or you can write a term paper instead.” and you want to come up with the frequency.
Adam: You wanna come up with a mapping so that the most frequent things, use the, the least amount of terms, but it’s not just come up with a scheme like that, like Morse code did. It’s, you know, come up the provably correct way to take a bunch of text and figure out what’s most common and give it a binary mapping, so that, that was the homework project, the professor’s name was Robert Fano, and he doesn’t tell them that as part of this assignment that this problem he puts to them is one that he can’t solve himself. And he was the professor. But it gets worse because he had been working with a colleague on this problem, and his colleague was Claude Shannon, who we’ll talk about later. Claude Shannon, invented digitally. Information theory.
Adam: He invented the bit, the idea that you could transmit information, he, he invented the whole field. Super interesting guy. He could not solve it either. He was a genius, and these two could not solve this problem, and he’s like…
Don: You know what? Give it to the student.
Adam: If you don’t wanna do the final, just prove this thing."
Don: Just take this thing that we’ve struggled with through our career.
Adam: Yeah.
Don: You know, figure it out.
Adam: I think you have a quote.
Don:
Huffman worked on the problem for months, developing a number of approaches, but none that he could prove to be the most efficient. Finally, he despaired of– He despaired? He despaired of ever reaching a solution and decided to start studying for the final. Just as he was throwing his notes into the garbage, the solution came to him. “It was the most singular moment of my life,” Huffman says. “There was an absolute lightning of sudden realization.”
Adam: I always have this thing, especially if I’m working on a problem and I can’t solve it, and then when I put it away…
Don: Your subconscious crunches on it.
Adam: Yeah, Do you know, do you ever have when you’re a kid, it was this thing and it, it has… Needles. They’re not sharp, but you like…
Don: The… Yeah, yeah. Yeah, Kaven got one of those. They’re like, they’re plastic now, not metal, and they’re like multicolored. But yeah, it’s the, all of the, matrix of, little pins, and you can push something into it and you can see the impression.
Adam: Somebody told me before, you know, your brain kind of works like that, where, like, different areas, different thoughts, they get activated. So you’re thinking about something, and it’s sort of, like, pushing up on all these areas. If you’re trying to brainstorm an idea, like, there might be something in the back of your head, and so that causes an area to light up a little bit, you can imagine, oh, here’s an idea around the topic, and so that needle goes up. But there’s also all these other things going on, like the other things you’ve thought of and whatever, right? So the, the idea is there and it’s pushed up, but so is a lot of other things.
Don: And you can’t– Yeah, there’s too much noise.
Adam: You can’t see it. But then if you walk away, you know, the other things you were thinking about, they all sort of settle down, and then you can see, like, oh, there’s that idea. The, the other needles have fallen away, and I can see this one is just jetting up a little bit.
Don: Yeah, that makes a lot of sense.
Adam: Right? So his paper that he submitted became one of the most cited papers in computer science.
Don: I’d like to see, it’s like, “Oh…
Adam: Yeah.
Don: I mean, I knew you could.”
Adam: Tell you that this is an unsolved problem and that Claude Shannon, the smartest guy that I have ever met, could not solve this?
Don: Saying the…
Don: I mean, you did okay.
Adam: Yeah, we’ll give you a pass on the class, so this idea, though, Huffman, it becomes called Huffman encoding. And I mean, it, it’s used everywhere, his paper that he submitted became one of the most cited papers in computer science. So this is used inside of gzip, yeah, he never, it or anything, so it was just like a concept he, you know, ended up becoming.
Betty Beat the Best Bet: Huffman by Hand
Adam: Computer science professor and, and leading a department.
Adam: Probably helped that he had solved this great thing for his career, right? So here’s my version of that…
Don: Betty beat the best bet.
Adam: It’s like a tongue twister, but…
Don: Twister, yeah but it…
Adam: If I run it, it’s going to go through and find what characters are the most frequently. And probably not surprising, there’s a lot of B’s and E’s in here, and so it ends up– Oh, and T. Apparently T is the most common. I would’ve thought it was the B. You can see it ends up with this table.
def build_tree(freq):
"""Repeatedly glue the two lightest nodes under a new parent."""
heap = [(w, i, ("leaf", s)) for i, (s, w) in enumerate(freq.items())]
heapq.heapify(heap)
tie = len(heap)
while len(heap) > 1:
w1, _, a = heapq.heappop(heap) # the two rarest so far ...
w2, _, b = heapq.heappop(heap)
heapq.heappush(heap, (w1 + w2, tie, ("node", a, b))) # ... under a new parent
tie += 1
return heap[0][2]
def assign_codes(node, prefix=""):
"""Walk the finished tree: left = 0, right = 1. The rarest symbols sit
deepest, so the commonest end up with the shortest codes."""
if node[0] == "leaf":
return {node[1]: prefix or "0"}
return {**assign_codes(node[1], prefix + "0"),
**assign_codes(node[2], prefix + "1")}
Huffman’s idea, the one Fano and Shannon couldn’t crack: build the tree from the leaves up.
Don: Right, and it assigns it a binary code. One zero and zero one. Has a four-letter code, yeah.
sym freq prob code bits ideal -log2(p)
'T' 6 0.2609 10 2 1.9386
'E' 5 0.2174 01 2 2.2016
'B' 4 0.1739 110 3 2.5236
' ' 4 0.1739 111 3 2.5236
'Y' 1 0.0435 0000 4 4.5236
'A' 1 0.0435 0001 4 4.5236
'H' 1 0.0435 0010 4 4.5236
'S' 1 0.0435 0011 4 4.5236
Huffman: 2.6957 bits/symbol entropy floor: 2.6488 waste: 1.02x
On enwik8: 5.1089 bits/byte -> 63,861,724 bytes 1.57x
BETTY BEAT THE BEST BET, run through it. Provably the best code that spends a whole number of bits per symbol — and that last clause is the cage.
Adam: And the other thing that’s happening here that’s very valuable is we’re not encoding any of the other stuff. We don’t have to worry about ampersand or whatever, right? We only need to encode the things that are actually in the text. It’s all, this is all capitals. We don’t have to encode lowercase. We’re only focused in on the most frequent characters.
Don: Yeah, including space.
Adam: Including the space, yes, which we have. But yeah, how much smaller is this version?
Don: So it says it’s, raw bytes. It was eight bits/for SIM, and then it’s 2.7, so 66% versus raw.
Adam: So we’re 66% smaller. Let’s try to run our corpus. So when we run this against the Wikipedia standard, we’ve actually gotten a smaller file, which is good. Before we were inc…
Don: Yeah, 1.56% of times.
Adam: Sweet. So we’re making progress. We have a long ways to go before we beat the prize.
Don: Get that sweet, sweet 5,000 euros.
Adam: Get that sweet euros. But…
Don: I like how it’s in euros, but when you texted me about it, you did the conversion on my behalf to put it into dollars. You’re like, “Oh, euros, he’s not gonna know about that, so I’m gonna do the conversion here.” It’s about 8,000 Canadian dollars.
Adam: I didn’t know what a euro was worth. Did you?
Don: A euro? No, not offhand. Like I do know that it’s about, one and a half.
Adam: So the first algorithm we did was run length encoding, which was like that, that…
Don: Yeah.
Adam: Well. Then we did the pointer one, which worked well. So the pointer one.
Don: Actually did compress something. Yeah.
Adam: Yeah. And so that was invented by two information theorists, Jacob Ziv and Abraham Lempel…
Don: Do you know what year?
Adam: 1977. So that was a long time ago, right? And then the one we just did, the Huffman encoding, was obviously by this David Huffman. But you put those two things together, guess what you get.
Don: A more efficient algorithm?
Adam: That is, that very…
Don: Driven…
Adam: Gzip, or zip.
Don: Okay. So like everything that’s the common standard.
Adam: That’s the common standard is the zip file, and the zip file just uses those two algorithms.
Don: Kidding.
Phil Katz, PKZIP, and a Lawsuit Over Typos
Adam: So those two algorithms were combined into this compression algorithm, a program that I believe was called ARC, and it was big in, like, the BBS days. There was a free version of this ARC, archive builder, I mean, it was just the most common format. And then there was this guy named Phil Katz. So yeah, in, in the late ’80s before, you know, the internet, there was all these BBSs, and so compression was important because you just had dial-up. There was this ARC format, and it was, you know, it was usable by this company called C. Phil Katz lived in Milwaukee, and he was kind of a really good hacker, and he liked to write things in assembly. And so he wrote his own version of their archiver, and he called it PKARC for the Phil Katz Archive.
Don: Okay. Is that where PKZIP comes from?
Adam: That’s where PKZIP is… Yeah.
Don: PKZIP… Together. Oh, okay.
Adam: Yeah. And so it exactly what ARC does. It, it does the equivalent algorithm, except because he handwrites assembly, it’s, like, super fast. And people start using this PKARC. Everybody switches to it on all these bulletin boards. So this C company gets mad, right? He’s just, like, replaced their thing with a better thing, right? So they sue him because, you know, he’s copied what they’ve code and released it."
Adam: And it becomes this big court case, and I don’t know all the details of it, but apparently they find that there is some comments in their source code where there’s typos, and then they get his source code, and he has the same typos.
Don: Oh, to try and prove that he just copied it?
Adam: That he copied it and then made some improvements. So he loses the lawsuit. And in– out of frustration, I assume he’s like, “Well, F this nonsense.” He rewrites, right? It’s just these two algorithms that we just went through. He rewrites it in a text file from scratch and shares it with the world. So now there’s an implementation of how to do this that is unencumbered and, you know, has no cost, and he kind of did it a little bit out of spite. But yeah, this became PKZIP, and because the P and K was for Philip Katz, and everybody just adopted it ‘cause it was free, and it also was fast ‘cause he was good at what he did. And yeah, did you have PKZIP?
Don: Yeah. Yeah. No, of course.
Adam: I never knew what it stood for.
Don: No, I didn’t know what it stood for either. No.
Adam: Yeah, so because it was, unencumbered, it, it… That’s what made it popular, right? Anybody could use.
Don: Was open, yeah.
Adam: It was open. And so, you know, you get it used in WinZip. You get it, you know, when the, when the GNU Project is trying to open source things, they’re like, “Oh, we can use this.” Right? So that’s where you get gzip. The algorithm, the, the combination of the two of them is called DEFLATE apparently. Yeah, and then his life kind of went sideways. I guess he had a drinking problem. And yeah, he was found dead in his… He was found dead April 2000 in a hotel room in Milwaukee. He was 37 years old. Yeah, he did not make it very far.
Don: Sad.
Adam: No, it’s super sad. He was clearly talented at what he did, but I mean, addiction can be a challenge.
Don: Hmm.
Adam: But he left his mark on the world, right? Everybody’s still using the software.
Arithmetic Coding and Less Than One Bit
Adam: So with what we have so far, we can compress a file and do pretty good. We won’t win our contest, but if I have a file where a character is used a lot, I don’t have a way what’s the way to say it? Imagine this, right? So I have, a 25-sided dice. Does such a thing exist?
Don: Most often it’s a 20-sider.
Adam: 20 sides.
Don: Then it goes up to, I think, I think you can get a 25. It’s odd, but I think the next step up is, like, a 30.
Adam: Yeah. Okay, so we have a D20 we have letters on it, but all the letters are A except for one, which is a B.
Don: Okay.
Adam: So I, I roll it, I get like A, A, A…
Don: 95% chance of getting an A.
Adam: Yeah. And so if I make text like that, what we’ve created here, necessarily help or there’s a different way, which is called, arithmetic coding, encode so arithmetic coding has this idea. The math is a little bit more complex, but it tries to look at why don’t I just, what’s surprising? And so the way they do that for this is very simple, here’s the, here’s the compressed format. What are you seeing?
Don: It looks like it’s just noting where the Bs occur, at which position.
Adam: Right? So you never have to say AAAA. You just say, “Here’s a B, here’s a…
Don: Every- and everything else is A…
Adam: And everything else is A, which allows you to get below one bit per character.
a die with 20 faces — 19 say A, one says B · rolled 1,000 times
AAAAAAABAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABABAABAAAAAABAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAA
BAABAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
… 1,000 rolls in all
the whole page, rewritten:
B at 8 · B at 13 · B at 55 · B at 57 · B at 60 · B at 67 · B at 119 · B at 135 ·
B at 161 · B at 164 · B at 193 · B at 241 · B at 246 · … (50 B's total)
naive — one bit per roll 1,000 bits 1.000 / roll
the B-list 498 bits 0.498 / roll
entropy floor 286 bits 0.2864 / roll
cost of one A 0.0740 bits
The d20, rolled. You never write the A’s down — you write where the B’s were, which is the whole trick: 0.498 bits a roll, and Huffman cannot go below 1.
def cost(p):
"""Bits to record a symbol you were p-sure of."""
return math.log2(1 / p)
p (how sure) -log2(p) bits
0.5 1.0000
0.75 0.4150
0.9 0.1520
0.95 0.0740
0.99 0.0145
0.999 0.0014
What arithmetic coding pays instead. Routine correctness is nearly free — you only pay real bits at the surprises.
Don: Yeah, I mean, that’s the stats for this, this test data. But I mean, the test data is basically, like, a ton of A’s and a couple B’s.
Adam: So this example is very…
Don: It’s– yeah, it’s very specific to the scenario.
Adam: But it does come up in the real world where something is so common, that you wanna actually encode it at less than a bit of information. I can show you. Here’s my results table overall, here’s our run length encoding. This is on the big file. So our, our run length encoding made the file twice the size.
Adam: That wasn’t very good. Zip makes it, more than a third of the size, right? So 2.74. This is our arithmetic coding.
Don: Which is 3.96. It’s almost down to a quarter.
Adam: It’s funny, so I had this guy, Jan, Colette? I had this great episode right? And he was in France, and he ended up building his own compression system that was better, Zip. And it, it’s called, ZST…
Don: Okay.
Adam: Zstandard, and it uses this arithmetic coding concept. And he was trying to explain it to me, how you can store a character in less than a bit, which is what, what we just showed, right? We were able to, to compress all those as. It’s easy for me to understand it in the A example. It’s harder for me to understand how.
Don: Context of an actual document.
Adam: In the context of an actual document, how it works. But the way it ends up working out mathematically is that you only use as many bits for a character to do with how surprising it is. And so I showed an extreme example where the A is not surprising at all, so all we’re encoding is the B, it’s able to use fractional bits to encode things.
Running Out of Ideas at Four Times Smaller
Adam: And so this idea had been around for a while. There were some patent problems that allowed people– that made it problematic for people to use it. But he brought it to common usage by making an open source project, allowing lots of people to do it, and he went from just being a hobbyist person building his own compression algorithms to working at Facebook, and this algorithm is now, used everywhere. That gets us to here…
Don: Yeah.
Adam: We are almost at four times.
Don: That would be like, if you’re down to almost a quarter, right? So around 250 megs.
Adam: Go, I guess.
Don: Yeah.
Adam: I don’t know. That’s, that’s where I run out of ideas. What do you got?
Don: Well, that’s where you run out of ideas. Let’s find somebody who’s figured it out and bring them on the podcast.
Adam: Yeah, exactly. All right, Don, what do you got? I did the first part. You do the second part where we win.
Don: Question mark, question mark, question mark, profit.
Adam: Exactly. Exactly.
Don: I don’t know. I guess a combination of approaches. I mean, it’s either that or coming up with a new idea on how to compress something. It seems like compression at its core is just recognizing patterns and replacing them with something smaller…
Adam: Or another way to phrase that, that people have, used, which at first I found confusing, the Huffman encoding, right, is it’s taking this idea, it’s, it’s predicting that there is a uneven distribution of characters. And the run-length encoding, it hit that immediately because its expectations are for repetition. It, it worked very well on, on one thing…
Don: Yes.
Adam: The rest it failed on. A compression algorithm in some ways needs to be able to predict what the file format is gonna look like.
Don: Yeah. So if you’re encoding something that’s an English language document, then there’s certain predictions you can make around the structure of that document because it’s using English as a language.
Adam: You are onto something.
Don: Sometimes I’m smart. Coffee’s kicking in.
Adam: Yeah man, the challenge is always that you’re too smart I…
Don: I have to be just dumb enough.
Adam: Yeah, ‘cause I bring you here to try to explain something and you’re like, “Oh yeah, what if they did that?” You’re like the, you’re like Huffman with the papers like, “I got, I think I got something here.” And you’re like, you’re like, “Jesus Christ, we’ve been working on this…
Don: And you just did it in a weekend?
Adam: Yeah.
Shannon’s Guessing Game With The Big Sleep
Adam: Okay, I have the next thing now. So it’s 1950 and there’s Claude Shannon, right? And Claude Shannon has this problem that he came up with. So he had defined the bit, and he had come up with this idea about transmitting information. He worked at…
Adam: Bell Labs. What does it say? He proved that every stream of information has a floor, an irreducible bottom, the minimum important information in it, which he called entropy, right?
Adam: So the theory says that there’s a way to make things smaller, he was never able to figure out if there was a bottom so he was kind of dancing around this idea of compression, right? If you’re transmitting information, some of it is important, some of it is not, right? Like if we’re talking on the phone and you miss a word, I probably still know what you’re saying, but if I miss every other word, sometimes I’ll put it together, but, but sometimes I won’t. And so his idea was it’s entropy, it’s this transmission of information. He’s an information theorist, and that there’s essential information you’re transferring, and if we remove too much, it’s gone. It is– It’s a easy idea to think about, but I mean, the math around it is very complex. So to figure out his estimate for this amount of information, he came up with a game, so we have here, some text.
Don: The Big Sleep.
Adam: The Big Sleep by Raymond Chandler, Raymond Chandler, are you familiar with him at all? He…
Don: No.
Adam: He wrote these noir detective novels.
Don: Oh, okay.
Adam: I think he, he’s one of the… There’s several authors of them, but he was one of the most famous, right? Where it’s like a smoky room, and the names on the door, and damsel in distress. So here’s the game he comes up with. His wife, is sitting where you are. He’s sitting here. He reads her part of the sentence, so it says, “It was about eleven.” Now, the game is you need to guess what the next letter is. And going back to where we were before, just like our text documents, we’re gonna– we’ll limit it to lowercase letters and a space. We’re just gonna reduce the domain to make it a little easier. Can you guess what the next letter is?
Don: Oh, for o’clock.
Adam: All right, let’s try it. That’s right. So you got O on the first guess, and he records these numbers…
Don: Oh, okay.
Adam: So on that letter, you got it on the first. So what’s your next guess?
Don: I think it was o’clock wouldn’t it be like an apostrophe?
Adam: So we don’t have apostrophes ‘cause… I just reduced it down to make it simple.
Don: Oh, okay.
Don: C?
Adam: Got it.
Don: L-O-C-K C?
Adam: Got it. And so you were able to guess all the letters on the first try there, but okay, what’s next?
Don: A for at night.
Adam: Nope.
Don: I for in the evening.
Adam: Oh. I think you got it, right? The wild thing is how much little information is actually needed to transmit the English here, you were able to predict it the predictable letters cost one guess is what he says. A surprise letter can cost five or six. Now you didn’t even get that high. You only got as high as two. But, he says on a demonstration passage, 100 plus letters of Raymond Chandler’s book, the guess was correct, a one about seven out of 10 times…
What If There Were a Second Don?
Adam: I find this part hard to explain. What he’s trying to say is, there’s actually, if you try to encode this information as, like, ASCII or binary or whatever, it will take a lot of numbers. But actually a lot of that is unnecessary. The, the actual surprising things are, are very small. You guessed almost all of these from the get, and it took you only two guesses to, to get to some of them. So here’s his crazy idea in 1950. This is the guy, by the way, who couldn’t solve the Huffman thing, so what he said is, imagine there’s a second Don, I put the same problem to Don number two, if I assume that Don will always get the same order, I don’t actually need to know what the text is here. I only need to know how many times I need to ask Don to get and so I’ve just compressed using Don…
Don: Were able to do this because you knew what, the correct answer was.
Adam: So you’re saying I wouldn’t be able to decompress it? Okay, but here’s the, here’s the tricky part. He’s saying no, that’s not the case, right?
Don: Yeah… I guess I got lost in… That’s where I’m struggling. So yeah, I get that I guessed correctly most times.
Adam: Mm-hmm.
Don: Because I was given the beginning prompt of it was about 11:00. I could kind of extrapolate what the rest of the sentence was. And when I guess, you’re able to check against an uncompressed version of the document to tell me I was right or not. Otherwise, how do we know?
Adam: Yeah. So you compress the word o’clock. Given, given it was 11, you compress the word o’clock to six ones, and so his idea is to, to transmit the word o’clock that it finishes, that it follows from 11. I could just write down those six ones in the beginning. It was 11…
Don: And then you’d have to have somebody like me on the other end.
Adam: You have to have a Don on the other end.
Don: That would be able to do what I just did.
Adam: And we play the same game, but I don’t actually know the answer this time. I know that when you say your first number, if, if you got the number two before, I have to say like, “No, try again.” And that second number is the number that goes in. So the person on the other side doesn’t actually need to know the answer. They just need to how Don would get.
Don: To guess with guess, yeah.
Is a Lookup Table Really a Prediction?
Adam: This is messed up.
Don: Is that- that might… Yeah, that’s messed up. But, yeah, I get it now.
Adam: But he’s– I mean, he did this in 1950, so computers were pretty simplified, but he called it like a digital twin. You know, if we had a Don on the other side, an exact Don duplicate, I could decode the sentences without knowing what it was because I would know your guesses would be the same as his. In his thinking, what he’s saying is he’s, he identified a range based on a human, bits and he published this bracket. 0.6 to 1.3, per character. But it’s, it’s clever. He managed to figure out how he could use, well, a physical person’s brain.
Adam: As a, as a compression mechanism.
Don: Yeah. And it would be that specific person because each code would be individual to a person’s thought process. Yeah, because…
Adam: If it was a slightly different person, they might pick a different letter.
Don: They pick a different letter.
Adam: And it would all be blown.
Don: Yeah.
Adam: Out of the water. But the interesting thing is, from his, perspective then, all of these compression algorithms, become prediction algorithms, right? ‘Cause what you’re trying to do is predict what comes next, and you’re just really good at predicting English language ‘cause you understand it very well. So that means that our other algorithms, way the Huffman encoding tries to predict things is by looking at all the characters and seeing which are most common. And that’s its power to predict things, is it knows, this is the most frequent thing…
Don: Well, I don’t think that it’s guessing. It knows what the answer is. It knows that T occurs this many times.
Adam: This is the, the confusing part, when you encoded that word, you came up with like one, one, one, one, which meant it was your first guess. But if you think of the Huffman table as a prediction, then that means by default, the very first thing it predicts is T for any answer.
Adam: But if T is wrong, then it predicts the second one… E. And then these ones, it takes a while for it to predict it, so it goes further down. So it ends up with a similar encoding as you, but it takes it a lot longer. I think…
Don: E yeah, I… Yeah, no, I, I understand. It would take the, the table it came up with, but I thought that it was making this table so that it could replace the character with a different code.
Adam: It is.
Don: So it’s not making a prediction, it’s doing a substitution.
Adam: I guess.
Don: But you could use its same information as a prediction because it’s already kinda done the work to find out what the most common thing is. And instead of using that as its prediction, it’s using that as a, “Oh, well, I’ll replace this with a small code. And the ones that are least, I’ll replace those with a, a larger code.” It’s not using it to, like, predict the actual letter.
Adam: Yeah, but there’s a way to view them that they are the same, right? Another way is it’s saying like, “Oh, you’re just…” it’s treating you as a lookup table, when it’s saying, when Don says one, it’s like, “Well, what, how do I look up one in the Don table?” I’m like, “Well, you just ask him. Like, given the sentence, what’s the first letter you’d come up with?”
Why File Size Is a Test of Intelligence
Adam: But it gets at this key thing, right? Which was the, the guy on that Hutter Prize, and what did, what did he say? Do you have that first.
Don: Being.
Adam: Something about intelligence and compression being the same thing.
Don:
Able to compress well is closely related to intelligence as explained below. While intelligence is a slippery concept, file sizes are hard numbers.
Adam: Yeah. So he’s saying that past these certain easy tricks, the way that you compress a file actually has to do with intelligently understanding it, which is what you did as part of that game…
Don: Yeah, because I understood English, so I could make a educated guess.
Adam: So the whole point of the prize is that if we pay people to compress files smaller and smaller, they’re gonna have to come up with machines, algorithms that actually understand English language text.
Don: Yeah, ‘cause I mean, if I didn’t understand English, I would just be picking a letter at random. Well, not exactly, I guess, because some letters are more common than others in English.
Adam: Yeah. Or you’d get a little better, you’d do the Huffman thing and you’d be like, “Well, the most common letter is A, so I pick A.”
Shannon’s Flame-Throwing Trumpet
Adam: That’s, that’s the relationship, right? Earlier we had the, the tongue twister about Betty. Well, so Betty was Claude Shannon’s wife, and he tested this theory on her. So Betty was the person who did the guessing…
Don: Yeah.
Adam: And then he, he made the paper out of it. And then Claude Shannon’s just a super interesting guy.
Adam: I should do an episode on him, but he built a flame-throwing trumpet. When he played the trumpet, it shot flames out of it. He built a machine that had a button on the top, and when you pressed the button, a hand came out and then closed.
Don: There’s a, there’s a… Yeah, there’s a, a toy you can get now.
Adam: So I think it’s based on something he made. I mean, his was very simple. It was just like a switch, I think. And when you flip the switch, a hand would come out…
Don: Wait, flip it back. Yeah.
Adam: But yeah, from this came the concept of entropy or surprise. The thing that he got down in information theory was like the meaning of a message is how surprising it is. So the letters where you had to, where you got it the first try were not very surprising. And so there was actually very little information there. So they could be compressed very small. If you had to guess a lot, then that meant that that character was surprising. And so this notion of surprising puts a cap on the size that you can compress things. So our A, A, A, A’s and then occasionally a B, the A’s were never surprising. So we only had to encode the B’s.
Don: Like he, in 1951, he figured all this out because he didn’t have YouTube, he had to sit down.
Adam: And think.
Don: And think about something. Yeah. He couldn’t just scroll a bunch of silly videos. I…
Adam: Been smarter than the average person in general. I don’t think if I was back then, I’d be like, “Well…”
Don: Think he was even smarter than- Probably. Yeah, probably.
The Record Is 0.88, Shannon Said 0.6
Adam: But okay, here’s the crazy thing, right? So this is my benchmark of all the things we ran. So run-length encoding, the actual record for and the Hutter Prize…
Don: Is under a bit, hey?
Adam: It’s under a bit, it’s at point eight eight. But in nineteen fifty, Claude Shannon, he’s like, “I think this is the range on English his range was point six to, like, one point two.
Don: He’s like, “That’s the floor. You can’t get any lower than that?” Is that what he’s saying?
Adam: That’s his theory about English language and the amount of information that’s embedded in it based on, humans’ ability to pattern match. But it seems to be holding, right? Nobody’s gotten past his 0.6 intentionally this AGI guy created this Hutter Prize. He’s trying to say, “Can you make something that will understand English?” Because he said, “Oh, it’s really hard to measure how smart something is, but it’s very easy to measure the size of a file.” It’s very definitive.
Don: Yeah.
Adam: And so if you can get past all of these levels and it keeps getting smaller and it starts getting towards Shannon’s range, that means that whatever’s doing that zipping must understand English language.
Don: Yeah, it must be very smart.
Adam: Must be very smart. Turns out compression is very related to intelligence, at least in this case where you’re compressing English language.
Don: Based on your ability to predict what the next letter is gonna be in the English language. Yeah.
Adam: I think I found a way around it so that we can win our contest.
Don: Let’s get that money.
Adam: Yeah, let’s get that money, man.
The Trick That Compressed It 486,000 Times
Adam: I made this file basically, I generated a file and a compressor for it, and this is a sampled file. We could text. Open it, but it’s just…
Don: 4.1.
Adam: Yeah, it’s 4.1 megs, and it’s full of just, like, random…
Don: Megs. Hexadecimal?
Adam: Yeah, I mean, this is in hexadecimal, so it’s not, and then I, I tried to compress it. So zip file, compressed it 0%. In fact, it got a little bit larger. Arithmetic coding, like the zstd, got it to zero. But then my algorithm, here’s where we claim the prize. How did my…
Don: Algorithm. It got it a lot smaller. Was that 486,000 times? Well, there you go. The, the question mark, question mark, question mark algorithm.
Adam: Yeah. But it’s a, it’s a trick obviously right? I, I used the random number generator and just generated a whole bunch of binary that I wrote to a file…
Don: Okay.
Adam: And then my compressor, basically it takes that number it finds what the seed is that was used, and it writes that to a file and then so all my decoder does is read what the seed is and run the generator function again?
def gen(seed, n):
"""n pseudo-random bytes from a tiny seed. Deterministic — anyone with
the seed reproduces the exact same bytes."""
return random.Random(seed).randbytes(n)
def compress(data, seed=42):
"""One bet: "this file is my generator's output." If the bet WINS, the whole
file becomes 9 bytes. If it LOSES, the file is stored verbatim plus a flag —
it GROWS by one byte."""
if data == gen(seed, len(data)):
return b"\x01" + struct.pack(">II", seed, len(data)) # bet won: 9 bytes
return b"\x00" + data # bet lost: n+1 bytes
def decompress(blob):
"""Read the flag: 1 = replay the generator, 0 = the rest is the file itself."""
if blob[:1] == b"\x01":
seed, length = struct.unpack(">II", blob[1:9])
return gen(seed, length)
return blob[1:]
The whole cheat — and it is a real, total, lossless compressor.
seed 42, the 4.1 MB file 4,299,161 bytes
gzip -9 4,300,482 bytes (it GREW)
compress() 9 bytes 477,685x
rebuild IDENTICAL sha256 686d964e0c4feaa0...
the same trick at 1 GB 1,073,741,824 bytes
gzip -9 1,074,069,387 bytes (grew)
zstd -19 1,073,766,414 bytes (grew)
the whole file, written out: python3 seed.py 42 1G — 21 characters
It wins on exactly one file in the universe and grows every other file by a byte. That isn’t a bug in the trick — the counting argument says every compressor is shaped like this. The good ones just make a broader bet.
Don: But it’s a random generator function from the same seed? Yeah. Oh, well, that’s how Minecraft works.
Adam: Mm.
Don: Anybody with the same seed can generate the same Minecraft world as long as they know the seed.
Adam: So this is the same trick I’ve done here. They– I’ve made a file full of…
Don: Minecraft already figured it out, man.
Adam: I can reduce it just…
Don: To the seed, yeah.
Adam: And then I can re-expand it to its seed. And so it– out of all of the possible data in the world, there’s like one very specific set of data that this thing dominates, it makes it, it makes it like…
Don: It’s very hyper-specific to one thing. If you could make one that’s hyper-specific to that one file, we can win.
Adam: It’s sort of an example, you know, if you just had this file and you tried all these algorithms on it and you saw it never got smaller, you would think, “Oh, this data is actually not able to be compressed,” There’s no patterns in it. But in fact, there is a pattern. You just don’t know what it is.
Kolmogorov Complexity and the Sloot Story
Adam: So Kolmogorov complexity, invented by Kolmogorov, it has this idea that you can measure the information in a piece of data by the length of the smallest program that could possibly describe it, so in my example here, right, I have this crazy amount of seemingly random data, but actually it can be described by this program that’s just like use Generator seed 89. But that’s true of a million things, but it can also be shown that there’s no way to figure out if you’ve determined that that’s the shortest program. You just can’t know, but there’s no way to prove that it doesn’t exist. But it sets a bound on things, and that could be your compressed form. Like instead of coming up with a special format, you just send over the program that if run reproduces it…
Don: And reproduces the entire document? Yeah.
Adam: But this is all going somewhere, I promise you.
Don: Does it end with me getting 5,000 euros?
Adam: Well, we gotta split it, don’t we?
Don: Yes. No, that’s true. That’s true.
Adam: So there’s a– I did an episode about this guy named Sloot. It’s a great episode if, if you haven’t listened to it. But, Sloot had this idea for a movie playing system so people could watch movies in their homes. It was, like, in an earlier era, and he said he could compress videos, you know, into I think it was eight kilobytes. That would be the, the size of the movie. He was trying to explain how his invention worked, ‘cause they’re like, “Yeah, you can’t store a movie in eight kilobytes. Like, it’s just not possible.” And he said, “Oh, it works like this. If I were to send you, you know, a picture of the Mona Lisa, there’s a lot of data there, you know, a lot of different pixels.
Adam: But if you and I had the same, art history book and I wanted to send you the Mona Lisa, I could just say like, ‘Hey, look.
Don: Page.
Adam: 76,’ and there it is.”
Don: So his, what was his source though for movies? Just like a collection of pictures?
Adam: Yeah, I mean…
Don: Yeah…
Adam: Not enough data to encode all movies. It’s actually a clear problem in compression to say, like, eight kilobytes, even as a number, is not that big of a number. There’s more movies than even, even if you just were storing, like, where to go get the DVD and put it in your machine, you would run out of numbers. And then he had some demos. He had, like, some sort of home entertainment system where you could take a movie and you could play it.
Don: Oh.
Adam: Kilobytes. And it became this big thing. People invested in it. And then, you know, he ended up dying, and they never found how the system worked. But the idea makes sense, right? He’s saying, like, “If we have some shared information, then I don’t need to transmit every single detail because we share it.” And the, you know, the Don thing sort of does that, right? Because you’re.
Don: Similar to like a cipher? ‘Cause a cipher is you don’t understand this text, but if we both share a common key, then we can reconstruct what the message would be.
Adam: Yeah, like… I think it is, right? But it, it presents a problem to the whole prize, if Wikipedia is…
Don: Yeah, we’ll just store the link to the Wikipedia URL and I feel like this, they have to have something in the rules that prevents that from happening. They’re not gonna give you money for that.
Adam: Specifically what they have is that, it was that weird math that you had at the beginning, which is, the program, its size counts too…
Don: Yeah, the size, the size of your, of your program S1 compresses the file to the archive EXE of the size S2. So yeah, it’s included.
Adam: Yeah. So if your program gets too big and complex, you need to make that up in the advantage of compressing.
LLMZip Breaks the Record and the Rules
Adam: So if we’re thinking of this guessing game we did where we had some text and then we have to guess what the next words are, can you think of anything that’s good at that?
Don: Like all of our phones.
Adam: Yeah. Yeah, like predictive text. And predictive text does, you know, it has a dictionary of some sort that’s shared, right?
Don: ‘Cause it knows English and knows the, it knows grammar to a certain extent, and it’s all been kinda programmed into this common database that they all share. So whenever you’re typing, it makes a predictive, suggestion.
Adam: Yeah. So then whatever the size of that dictionary is, right, you need to pay that off in, in smaller, compression. Or, yeah, like a smaller file. But what else?
Don: Like what else makes predictive text?
Adam: Yeah.
Don: AI?
Adam: Yeah, an LLM.
Don: Yeah.
Adam: Exactly this where you give it “Here’s the characters I have so far, like give me some more.” And so his idea– I mean, the, the, the contest is 20 years old, but this is what’s super cool to me. He thought, “Hey, this will reveal something about, AGI and human understanding.” And I assume people were like, “Dude, we, we’re just zipping files. I don’t know what you’re talking about.”
Don: I mean, yeah, that’s exactly what I think I said at the beginning of the podcast. It’s like, yeah, it’s just zipping files. I mean, it’s probably, something that’s required, right, in the grand scheme of things, but it’s not gonna be something that directly relates. And now it does, yeah.
Adam: But here it does directly relate right? So the, this research group, used an LLM so, to make a zip file. So they made something called LLMZip. And instead of using this idea of like a dictionary of common words, they just had an LLM in there. And so you can understand exactly how this would work, right? So they’re using, instead of having a Don.
Don: They have an LLM to do it. Right.
Adam: They LLM do it. So they can say like, “Hey, we have this text, guess the next character.” And when it’s right, then that’s easy, right? And when it’s wrong…
Don: Guess again.
Adam: Again until they get it. And if the LLM is good at predicting that type of text, they now have a Don on both sides that can decode the thing. And this LLMZip was able to beat all kinds of records, and I think it did well on image compression as well. It blew all kinds of standards out of the water, except, the problem is that that LLM base file is like gigs and gigs of data.
Don: Oh, okay.
Adam: It’s like, 17 gigs of data or something.
Don: Like the S1 in the algorithm there would mean that they wouldn’t get any money.
Adam: So they wouldn’t get any money because of the size of it. But what they did find is that intelligence is helpful for compressing things. They proved that Claude Shannon’s theory works out, so we’re looking at a table of different compression sizes.
Adam: So our, our run length encoding made files bigger. Zip files made it two point eight two point seven four times smaller. Arithmetic coding, which was our ZST, it gets almost to four, the record is here at nine. This is LLMZip, so LLMZip used a thirteen gigabyte.
Training an LLM While You Decompress
Adam: Decompressor, you needed to give it one of these early LLM models. But if you ignore that, it got eleven point two seven.
Don: Oh, okay. So it’s by far the smallest. Now.
Adam: Yeah. So it made the file way smaller because it has way more knowledge of English language, it’s like a, it’s Don. It understands how English language works, maybe not as well as you.
Don: But if you need a 13 gigabyte file to decompress a one gigabyte file, you haven’t really gained anything. I c…
Adam: Exactly.
Don: You’ve just kind of offset all of that information inside your decompressor.
Adam: But there’s all kinds of ways that you could think it would be useful, not for this contest, but I mean…
Don: Yeah.
Adam: You could– we could all have a 13 gigabyte file on our machines and use it to compress and decompress anything English text and it would…
Don: Yeah, if it was a common thing that everybody had, right?
Adam: Very well. But…
Don: Yeah.
Adam: Have to have the same version, right? It has to be the digital twin. So the– this guy made something called, TensorFlow Compress. So TensorFlow Compress, it doesn’t really violate any of the clear rules.
Adam: It takes the Wikipedia file, and as it’s decoding the file, it trains an LLM on it, and then it uses that LLM to do the trick. The problem is, it needs, a very expensive cluster of GPUs and has to run for, like, days.
Don: Oh my God.
Adam: And… And violates the theory, and it’s very impractical, to take your one gigabyte file and to spend seven days on the hundreds of thousands of dollars worth of equipment to decompress it.
Don: And so… It’ll be a couple days and we’ll… But so the, the current record for the contest is this cmix, and that’s the one that’s at nine. And in it, it uses this same idea of trying to predict what the data is but in much simpler fashion. And it has actually 2,000 different little algorithms that try to predict what character’s gonna go next, and then it has them all vote. And so some of them are really good at understanding, like, Wikipedia, markup language, some are good at understanding this or that, and they all vote.
Should the Prize Be Modernized?
Adam: I don’t know, I went deep on this, Don. There’s people who, say that this Hutter guy should change the prize because, you know, he came up with this test for AGI.
Don: To like modernize it…
Adam: To modernize it because these limits like LLMZip doesn’t pass the test because, the files are too big. But you could imagine changing it, right? You could imagine that he says, “Okay, here’s– I have 10, I have 10 separate one gigabyte files of Wikipedia. I’m only gonna give you one of them. Run your thing on that, and then I’ll test it on all 10, and the cost amortizes over all 10,” right? No, I guess that wouldn’t work ‘cause it’s 13 gigabytes.
Don: Like maybe- if the amount of data that you’re using is bigger than 13 gigabytes.
Adam: Then you might be able to pay it.
Don: Yeah, if it’s like a petabyte of data.
Adam: We’re creating AIs now, and they’re just at a different scale.”
Don: Yeah.
Adam: Not one CPU, there’s like thousands of GPUs and, and it’s not, it’s petabytes and petabytes of data.
Don: Yeah.
Adam: And you came up with this very cool, very specific can’t cheat it test because a file size is a file size, but you put the constraints as such that nobody takes it seriously.
Don: Outdated. Yeah.
Adam: Yeah.
Don: Yeah, no, I think that modernizing the test would be right? Because then it gets people thinking about, things in the modern context.
Adam: And when we, when we talked earlier, about the pre-training wall and how, the LLMs had consumed all of the internet and they were out. You know, this is in some ways a different view of things because here he’s saying every piece of data counts, you can’t just use all of the internet to answer this question. You need to learn the structure from just this, and every extra byte you add of looking things up is, cost you. So he’s on the other side of the coin of what is the maximum information that we can suck out of this data? Same as that Claude Shannon was saying like, “What is the minimum?” we can send and extract the maximum from?” Compression turns out to have a lot to do with extracting, the maximum amount of data from…
Don: The minimum amount of instructions. Yeah. Yeah.
Adam: It’s also the challenge just that it’s very hard to explain why getting better at file comprehension has to do with intelligence. It’s very, obscure, really, or, obtuse. Actually figuring out how to make a file smaller, somehow bumps up against intelligence. That, that’s a very odd thing. I, I don’t know.
The Confession: It Was Always a Ruse
Don: Initially you wouldn’t come up with that, but then after you explain that, oh, well, we can actually make things a lot smaller if we just knew how to predict what would, what would be the next, you know, the next piece of data.
Adam: Yeah…
Don: Then you’re using the brain, right? You’re using some kind of intelligence to come up with, to make the prediction.
Adam: Yeah. And I don’t think we’re actually gonna make any money, Don.
Don: No, I… I didn’t think we were gonna make any money when you texted me.
Adam: It’s a, it’s a, it’s a ruse. I brought you over here because the thing I wanted to talk about was this idea, yeah, that, that compressing documents is basically predicting, and that that requires intelligence. This is why the guy running this Hutter Prize is not, in fact a high-performance computing guy. He’s a AI person, and so he said, 20 years ago that he would put, yeah, half a million dollars on anyone that can compress Wikipedia.
Don: ‘Cause he had already come to the conclusion that a requirement of being able to compress English Wikipedia would be, some kind of command of the English language, some kind of intelligence behind it.
Adam: Yeah.
Don: Yeah.
Adam: In fact, he was making this bet, you know, that compression and understanding are the same thing in a way. That to make a file smaller, you need to understand the patterns in it, if you understand the patterns in a giant swath of Wikipedia, like how is that different than, than actual intelligence?
Don: You took me on this wild goose chase. I learned a lot about compression, but I didn’t get any euros.
Adam: Right? There’s no euros involved.
Don: Euros involved.
Maybe I Need a Better Hobby
Don: I’m very upset that we didn’t get any money.
Adam: But I don’t know, it’s super cool. If you haven’t listened to the two episodes, one about Sloot, one about Yann Collet. You know, one legitimately rocked the world of compression. One, you know, thought he did and but it’s cool how we can take just, idea that seems simple and something you use every day, and if, if you start pulling on it, it feels like in every area, if you, if you look into it, there’s actually a surprising amount there, and it will connect to a lot of other things, and there’s just areas you can learn about. I don’t know. Maybe I need a better hobby. Sorry we didn’t make any money.
Don: No, it’s fine. I got a coffee out of it. That’s good enough for me.
Adam: Yeah, and until next time, thank you so much for listening.
Support CoRecursive
Hello,
I make CoRecursive because I love it when someone shares the details behind some project, some bug, or some incident with me.
No other podcast was telling stories quite like I wanted to hear.
Right now this is all done by just me and I love doing it, but it's also exhausting.
Recommending the show to others and contributing to this patreon are the biggest things you can do to help out.
Whatever you can do to help, I truly appreciate it!
Thanks! Adam Gordon Bell
