A student’s desire to get out of a exam led to a compression algorithm
quantamagazine.org
A student’s desire to get out of a exam led to a compression algorithm
1–10 of 132 posts
Re: A student’s desire to get out of a exam led to a compression algorithm
#2missed opportunity to explain how compression and prediction are related, and that the better you can predict the next token the better your compression gets, then your article gets to mention GPT hey
Re: A student’s desire to get out of a exam led to a compression algorithm
#3missed opportunity to explain how compression and prediction are related, and that the better you can predict the next token the better your compression gets, then your article gets to mention GPT hey
Apparently compression and intelligence are synonymous:
Re: A student’s desire to get out of a exam led to a compression algorithm
#4missed opportunity to explain how compression and prediction are related, and that the better you can predict the next token the better your compression gets, then your article gets to mention GPT hey
Apparently compression and intelligence are synonymous: https://mattmahoney.net/dc/rationale.html
I think in a sense compression is worse - because not only you want to correctly predict the next token, you also want to do it fast, with a minimal but efficient algorithm that also doesn't require much space / a big dictionary.
You could think of it as taking a "snapshot" if an AI and then optimizing the hell out of it for a specific case and you end up with a good compression algorithm.
Re: A student’s desire to get out of a exam led to a compression algorithm
#5> The first step involves yet another clever strategy for identifying repetition and thereby compressing message size, but the second step is to take the resulting compressed message and run it through the Huffman process.
I wonder if this "first step" is Burrows-Wheeler Transform?
Side note: In Silicon Valley (the show), I'm pretty sure that Richard has a picture of David Huffman by his bedside.
Re: A student’s desire to get out of a exam led to a compression algorithm
#6> The first step involves yet another clever strategy for identifying repetition and thereby compressing message size, but the second step is to take the resulting compressed message and run it through the Huffman process. I wonder if this "first step" is Burrows-Wheeler Transform? Side note: In Silicon Valley (the show), I'm pretty sure that Richard has a picture of David Huffman by his bedside.
No, BWT is largely unused in modern compression codecs.
Lempel-Ziv is the basis for almost all modern general purpose compression, and works more like having a hash table mapping 3 or 4 byte fragments to their positions, and walking through the input byte by byte checking the hash table for matches and inserting the latest fragments&positions into the hash table.
BWT has nearly identical speed compressing and decompressing, but searching for matches to compress is much slower than simply copying data according to instructions to decompress.
Re: A student’s desire to get out of a exam led to a compression algorithm
#7Huffman trees are really cool and a neat little example program to put together.
Re: A student’s desire to get out of a exam led to a compression algorithm
#8Quanta magazine and all these pop science websites need to be stopped.
(Not because popular science is bad, but because they do it badly, and the clickbait is insufferable)
Re: A student’s desire to get out of a exam led to a compression algorithm
#9Caches drive the internet.
They are orders of magnitude more important than compression. 99.99% of requests hit a local cache. (1)
Compression is important too.
(1) I worked in a telco. Check it out for yourself!
Re: A student’s desire to get out of a exam led to a compression algorithm
#10> The first step involves yet another clever strategy for identifying repetition and thereby compressing message size, but the second step is to take the resulting compressed message and run it through the Huffman process. I wonder if this "first step" is Burrows-Wheeler Transform? Side note: In Silicon Valley (the show), I'm pretty sure that Richard has a picture of David Huffman by his bedside.
I came here to find Silicon Valley references and wasn't disappointed.