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

11–20 of 132 posts

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

#11

Post by joshsabol46 »

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 compression, selects the optimal algorithm, and then encodes the file. The selected compression algorithm could be prefixed for easy decompression.

Compare a single black image that's 1x1 to one that's 1000x1000. PNGs are 128bytes and 6KB, respectively. However, Run Length Encoding would compress the latter to a comparable size as the former.

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

#12

Post by deepsun »

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…

> selects the optimal algorithm

Here's the catch: how does the "system" know which algorithm would be the best? It could try encoding it with multiple algorithms and see which one is shorter, but that's extra CPU.

And the "system" can be called acompression algorithm itself.

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

#13

Post by devsegal »

pseudotrash wrote: post #10
denvaar wrote: post #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.

I came here to find Silicon Valley references and wasn't disappointed.

Both of us have been satisfied

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

#14

Post by U2EF1 »

deepsun wrote: post #12
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…

> selects the optimal algorithm Here's the catch: how does the "system" know which algorithm would be the best? It could try encoding it with multiple algorithms and see which one is shorter, but that's extra CPU. And the "system" can be called acompression algorithm itself.

I mean yeah that's basically what high compression solutions like paq have done, depending on the compression level desired apply increasingly speculative and computationally intensive models to the block and pick whichever one worked the best.

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

#16

Post by ThrowawayTestr »

pseudotrash wrote: post #10
denvaar wrote: post #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.

I came here to find Silicon Valley references and wasn't disappointed.

I don't like that show because whenever I watch it I start imagining a world with inside-out compression and I get sad we'll never have it.

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

#17

Post by Solvency »

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!

Ok how do they work then?

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

#18

Post by parl_match »

Solvency wrote: post #17
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!

Ok how do they work then?

There's lot of information about this on the open web, and tons of resources for varying levels of skill.

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

#20

Post by twotwotwo »

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 if you haven't. Besides the tech itself making a lot of things work better (like a Web built on human-readable formats, or more specialized stuff like Parquet or other columnar formats, or video on the lossy side), it can give you some tools or perspective that apply elsewhere, e.g. to other probablistic stuff like caching and predictions for lossless compression, or other signal-processing stuff for lossy compression.

Post reply on HN