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

121–130 of 132 posts

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

#121

Post by nico »

malisper wrote: post #120
nico wrote: post #110

In the article the compression doesn’t make sense If you are only sending one word, and the recipient already needs to know the word, then you only need 1 bit, essentially just signaling that you are saying that specific word If you want a richer vocabulary, you could create an index of about 300k words (from the English dictionary), shared between the parties Then to send any word you only need to send one number, a…

> 27 bits for just one word seems wasteful Where did you get that you need 27 bits for one word? > Then to send any word you only need to send one number, and in binary it would have between 1 and at most 19 bits Yep! By sorting by frequency, you are able to make it so the majority of words have shorter bit strings. By my calculations, common words such as "the", "of", and "and" will have ~4-6 bits associated with th…

About the 27 bits. This is from the article:

> Fano’s balancing approach starts by assigning the O and one other letter to the left branch, with the five total uses of those letters balancing out the five appearances of the remaining letters.

> The resulting message requires 27 bits.

I didn’t calculate it, the author of the article did

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

#122

Post by sr-latch »

ninkendo wrote: post #84
bhickey wrote: post #65

Earlier quoted context omitted.

Tell me you've never worked on a CDN without telling me you've never worked on CDN. Compared to transit, last mile bandwidth is effectively limitless and free. Cache fill at the edge is important, last mile caching not so much.

You didn’t need the first paragraph there, the snark is a bit uncalled for.

I felt it was a fair reaction to suggesting that we undo years of work in transitioning to https

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

#124

Post by mxmlnkn »

jrockway wrote: post #99
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 constr…

Your link seems to compare GNU gzip with zstd. When comparing file formats, I would compare the best software for that file format. igzip: https://github.com/intel/isa-l can decompress consistently faster than GNU gzip. Depending on the file, it decompresses 2-3x faster making it almost as fast as zstd decompression. I have less experience with compression benchmarks. A quick benchmark on Silesia shows igzip to be ~7x faster but it sacrifices 10% of compression ratio for that even on its highest compression setting. It seems to be optimized for speed.

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

#125

Post by ta93754829 »

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…

Once ChatGPT was trained on "the internet of 2021", how big is the remaining model? Is ChatGPT effectively a compressed version of the internet?

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

#126

Post by UncleMeat »

throwaway892238 wrote: post #64
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!

This is why I was flabbergasted by the nonsense internet takeover of HTTPS. You can't cache it. Probably 99% of web traffic is generic public content, but we can't cache any of it, because 1% of it needs to be private. So then people complain "oh but The Illuminati can see what websites I'm going to!" Yeah, and they still can with HTTPS, it's called statistical network traffic analysis. Decades of research papers sho…

I think the only website I visit with any regularity where my traffic does not contain some session information is Wikipedia. The transition to the web being largely for web applications and services happened before the transition to HTTPS everywhere. That's when you get stuff like Firesheep just stealing the Facebook sessions of hundreds of people at once.

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

#127

Post by themoonisachees »

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.

Most serverside processors will only compile pages once they're hit and cache thz results. As the xkcd goes "there's a lot of caching"

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

#128

Post by oikawa_tooru »

ot wrote: post #97
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...

Hi I am a neophyte interested in compression. It's difficult to find communities regarding compression online. I am looking for a guide. Is there any place that I can dm you?

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

#129

Post by adgjlsfhk1 »

Isamu wrote: post #76
jhallenworld wrote: post #74

I thought Huffman coding was obsolete, arithmetic coding replaced it. It allows for fractional number of bits per symbol, so is more efficient.

It’s still used in PNG, it is part of the spec. There’s a trade off, Huffman is relatively fast and easier to get right, and the gains from increased compression may be considered marginal. This is a classic engineering trade off.

PNG is also obsolete :)

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

#130

Post by adgjlsfhk1 »

ixwt wrote: post #75
jhallenworld wrote: post #74

I thought Huffman coding was obsolete, arithmetic coding replaced it. It allows for fractional number of bits per symbol, so is more efficient.

My understanding why arithmetic coding isn't used as much as Huffman coding is because of the patents that IBM had on arithmetic coding. I'm not familiar with any actively used compression algorithm that uses arithmetic coding. I have explored using arithmetic coding on some data at work (mainly large amounts of XYZ points). My attempts did not work better than standard zip compression.

The patents all expired in ~2013ish. ZSTD uses arithmetic encoding and is well on it's way to replacing gzip since it's usually faster and smaller.
Post reply on HN