Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A student’s desire to get out of a exam led to a compression algorithm

quantamagazine.org

Post reply on HN
Print view View original

91–100 of 132 posts

Re: A student’s desire to get out of a exam led to a compression algorithm

#91

Post by ninkendo »

Timon3 wrote: post #87
ninkendo wrote: post #83

Earlier quoted context omitted.

You could sign the content with the same CA architecture we already use to encrypt it, but leave it plain text (just a thought.) A browser could render a similar security warning to what it already does, if the signature doesn’t match or if the hash is wrong.

Right, I didn't thank about that part. They could technically replace it with another valid certificate, but if you're looking for specific certificates you will notice immediately.

Well, an ISP that wants to MITM your traffic today can present another valid certificate too, nothing changes there. It’s just that they couldn’t use a valid certificate that has the same Common Name (FQDN) as the site you’re connecting to, without having their root CA in your browser’s store (so, same behavior as we already have with TLS.) Presenting a cert with a different FQDN already causes a browser warning.

Re: A student’s desire to get out of a exam led to a compression algorithm

#92

Post by Timon3 »

ninkendo wrote: post #91
Timon3 wrote: post #87

Earlier quoted context omitted.

Right, I didn't thank about that part. They could technically replace it with another valid certificate, but if you're looking for specific certificates you will notice immediately.

Well, an ISP that wants to MITM your traffic today can present another valid certificate too, nothing changes there. It’s just that they couldn’t use a valid certificate that has the same Common Name (FQDN) as the site you’re connecting to, without having their root CA in your browser’s store (so, same behavior as we already have with TLS.) Presenting a cert with a different FQDN already causes a browser warning.

Yep, you're right, I had a brainfart there. Thanks for being nice and explaining it! :)

Re: A student’s desire to get out of a exam led to a compression algorithm

#94

Post by brookst »

MauranKilom wrote: post #82
twotwotwo wrote: post #20

There was a series of articles on lossless and lossy and compression techniques in, I think, PC Magazine that I read as a kid and made a big impression on me. I didn't, like, end up ready to write code to build Huffman trees or anything, but it did change it from a total black box into a bunch of smaller pieces each of which a mere mortal can understand. The compression rabbit hole can be a rewarding one to go down i…

Another interesting facet is that, according to some schools of thought, compression and AI are equivalent problems: The better you understand something, the less you need to memorize to reproduce it. https://en.wikipedia.org/wiki/Hutter_Prize (and https://en.wikipedia.org/wiki/AIXI ) Of course, large language models are (by definition) currently going the other direction, but it remains to be seen whether that leads…

Maybe a naive question: are LLMs really going the other way? My intuition is that the model weights are much smaller than the information encoded in them.

Re: A student’s desire to get out of a exam led to a compression algorithm

#95

Post by brookst »

anvuong wrote: post #39
sgt101 wrote: post #9

Caches 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!

Yeah it's cache all the way down. CPU has L1, L2, L3 for instructions cache. Server has ramcache, then SSD cache. Then apps with SQL almost always use redis/memcache as first level cache. Then for network side we have CDN which is basically a glorified webcache, even at router/switch there is cache for all the stuffs.

Indeed. And ultimately human neurons cache and we only scroll back, reload the page, or go back to the website when our cache ages out or the request isn’t cached yet.

Re: A student’s desire to get out of a exam led to a compression algorithm

#96

Post by klyrs »

iforgotpassword wrote: post #48

Interesting refresher. I do remember in college we had to build the lookup tree for some word as an exercise. Obviously the name Huffman stuck in my brain. But for the love of god, I can't even remember if the lecture mentioned Fano. Seems he was just as important in the design process of what we only refer to as Huffman encoding today.

Mathematicians are familiar with the name Fano, but for Roberto's dad Gino, whose name adorns the first finite projective plane.

Re: A student’s desire to get out of a exam led to a compression algorithm

#97

Post by ot »

twotwotwo wrote: post #20

There was a series of articles on lossless and lossy and compression techniques in, I think, PC Magazine that I read as a kid and made a big impression on me. I didn't, like, end up ready to write code to build Huffman trees or anything, but it did change it from a total black box into a bunch of smaller pieces each of which a mere mortal can understand. The compression rabbit hole can be a rewarding one to go down i…

Was it maybe Dr Dobb's? Mark Nelson had an excellent series of articles about compression which opened up that world for me. I ended up working on compression for my PhD many years later.

I can't find any archives for Dr Dobb's, but some articles are in his personal site, for example this one about arithmetic coding: https://marknelson.us/posts/1991/02/01/arithmetic-coding-sta...

Re: A student’s desire to get out of a exam led to a compression algorithm

#98

Post by floobertoober »

MauranKilom wrote: post #82
twotwotwo wrote: post #20

There was a series of articles on lossless and lossy and compression techniques in, I think, PC Magazine that I read as a kid and made a big impression on me. I didn't, like, end up ready to write code to build Huffman trees or anything, but it did change it from a total black box into a bunch of smaller pieces each of which a mere mortal can understand. The compression rabbit hole can be a rewarding one to go down i…

Another interesting facet is that, according to some schools of thought, compression and AI are equivalent problems: The better you understand something, the less you need to memorize to reproduce it. https://en.wikipedia.org/wiki/Hutter_Prize (and https://en.wikipedia.org/wiki/AIXI ) Of course, large language models are (by definition) currently going the other direction, but it remains to be seen whether that leads…

> Of course, large language models are (by definition) currently going the other direction ...

How so? Aren't the networks' weights orders of magnitude smaller than the training data?

Re: A student’s desire to get out of a exam led to a compression algorithm

#99

Post by jrockway »

joshsabol46 wrote: post #11

Please pardon my ignorance... My understanding is that there are 1000s of different compression algorithms, each with their own pros/cons dependent on the type and characteristics of the file. And yet we still try to pick the "generically best" codec for a given file (ex. PNG) and then use that everywhere. Why don't we have context-dependent compression instead? I'm imagining a system that scans objects before compre…

There are a variety of use cases that dictate which algorithm is going to perform best. For example, you might use Zstandard -19 if you are compressing something once and transferring it over a slow network to millions of people. You might use LZ4 if you are generating a unique large piece of data interactively for thousands of concurrent users, because it compresses faster than Zstandard. Basically, if you're constrained by network bandwidth, Zstandard; if you're constrained by CPU, LZ4.

There are then legacy formats that have stuck around long past their sell-by date, like gzip. People are used to using gzip, so you see it everywhere, but it's slower and compresses worse than Zstandard, so there is no reason why you'd ever use it except for compatibility with legacy systems. (bzip2, 7z, xz, snappy, etc. also live in this "no reason to use in 2023" space.)

Take a look at performance measurements here: https://jolynch.github.io/posts/use_fast_data_algorithms/. For example, gzip can get a compression ratio of 0.41 at 21MiB/s, while Zstandard does 0.38 (better) at 134MiB/s. (Meanwhile, lz4 produces outputs nearly twice as large as Zstandard, but compresses almost 3x faster and decompresses 2.5x faster.)

Lossy compression is even more complicated because the compression algorithms take advantage of "nobody will notice" in a way that's data dependent; so music, video, and photographs all have their own special algorithms.

Re: A student’s desire to get out of a exam led to a compression algorithm

#100

Post by govg »

floobertoober wrote: post #98
MauranKilom wrote: post #82

Earlier quoted context omitted.

Another interesting facet is that, according to some schools of thought, compression and AI are equivalent problems: The better you understand something, the less you need to memorize to reproduce it. https://en.wikipedia.org/wiki/Hutter_Prize (and https://en.wikipedia.org/wiki/AIXI ) Of course, large language models are (by definition) currently going the other direction, but it remains to be seen whether that leads…

> Of course, large language models are (by definition) currently going the other direction ... How so? Aren't the networks' weights orders of magnitude smaller than the training data?

I interpreted that statement as saying the current practice is to make LLMs larger and larger (so they effectively memorize more and more data) to make them more powerful, but from the perspective of information theory, if models were powerful and "understanding", then models could stay the same size and become more and more powerful as they get increasingly better at compressing the available information. I am not sure if this interpretation was what was meant though.
Post reply on HN