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

51–60 of 132 posts

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

#51

Post by notRobot »

dieselgate wrote: post #49
sn41 wrote: post #23

Earlier quoted context omitted.

I agree. They have a breathless tone to them that's quite annoying to me (I work in data compression as an academic, and I found this article uninspiring.) By the way, there was an old Soviet magazine called "Kvant" (Russian for Quantum, I think). I do not know Russian, but I have 2 collected volumes of selected articles from them. [1] [2] Their quality is astonishingly good, and high-level. The difference is this: T…

Yeah you have a good point - not sure if there’s a name for what you’re referencing but it’s tough to be an expert in something and read a bunch of cringe pop sci articles on your field. This topic comes up frequently with my partner who is a researcher - Ed Yong recently wrote a piece on some work by their lab and it was “tolerable”. Not a huge fan of Quanta myself but Aeon frequently has articles written by researc…

> "Briefly stated, the Gell-Mann Amnesia effect is as follows. You open the newspaper to an article on some subject you know well. In Murray's case, physics. In mine, show business. You read the article and see the journalist has absolutely no understanding of either the facts or the issues. Often, the article is so wrong it actually presents the story backward—reversing cause and effect. I call these the "wet streets cause rain" stories. Paper's full of them. In any case, you read with exasperation or amusement the multiple errors in a story, and then turn the page to national or international affairs, and read as if the rest of the newspaper was somehow more accurate about Palestine than the baloney you just read. You turn the page, and forget what you know."

https://www.epsilontheory.com/gell-mann-amnesia/

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

#52

Post by pezezin »

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…

WinRAR used to support specialized compression algorithms for specific kinds of files, like uncompressed bitmaps, sounds, executables, or plain text. However, the feature was removed in the RAR5 file format 10 years ago. Maybe it was not worth it?

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

#53

Post by amemisoglu »

dmurray wrote: post #50
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.

A nice reversal of the meme where "the supervising professor takes all the credit and the army of grad students do the real work".

This algorithm is known as Huffman encoding.

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

#54

Post by UglyToad »

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 is some approach you can use sort of like this within PNGs themselves I think. It's been a while so I might be misrembering but effectively each "row" of data that is compressed can be encoded as the difference from the preceding row using 4 or 5 different operations.

You can achieve better compression by brute forcing the possible operations used to encode the rows to find the "most compressible" output. Not quite what you meant but sort of similar in that you try multiple approaches and pick the best.

I gave up before implementing it but in the stub I left this comment to myself " A heuristic approach is to use adaptive filtering as follows: independently for each row, apply all five filters and select the filter that produces the smallest sum of absolute values per row.".

In addition more similar to your approach PDFs support many compression filters for objects internally like RLE and ZIP so you can choose the best algorithm per object but generally it's quicker just to ZIP everything.

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

#55

Post by alex_duf »

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!

It's a bit silly to oppose these two technologies... Caches also rely on compression to be efficient, they work hand in hand.

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

#56

Post by powturbo »

yawaramin wrote: post #25

On a related note, I got an email today saying that Cloudflare will automatically turn on Brotli compression later this month. Does anyone know if Brotli really makes a difference beyond gzip?

I've made a benchmark with real html data including memory usage in [2] and a recent benchmark in [3] with TurboBench [1].

In the speedup plots you can see the best compressors for content providers:

- brotli 11 is best for static content

- brotli 5 is best until 1MB/s network transfer speed

- libdeflate 6 is best from 1MB/s to 6MB/s (followed by brotli,4)

- igzip 1,2 is best for very fast networks > 10MB/s

brotli brings little value at decompression for users

[1] https://github.com/powturbo/TurboBench

[1] https://sites.google.com/site/powturbo/home/web-compression

[2] https://encode.su/threads/2333-TurboBench-Back-to-the-future...

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

#57

Post by alpaca128 »

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.

It would still pay off in many situations. With existing algorithms you can already optimize image files to be compressed as much as possible, which takes quite a bit longer than usual but if it means 30% smaller files for an entire website that has an impact on every visitor.

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

#58

Post by psychphysic »

esafak wrote: post #37
Solvency wrote: post #17

Earlier quoted context omitted.

Ok how do they work then?

They store frequently-requested items in a place that permits faster retrieval. https://en.wikipedia.org/wiki/Cache_(computing)

Wait maybe we should be using the Huffman encoding at the cache level!

I'm not sure what that would mean...

Maybe if you're website is unpopular we move your server to North Korea since no one is accessing it anyways?

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

#59

Post by cm2187 »

iforgotpassword wrote: post #47
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!

Is it still? Afaik now with everything HTTPS, caching proxies on the ISP end are completely useless. We instead now see (proprietary?) cache boxes by big players like YouTube and Netflix that ISPs can install in their DCs, but that seems less elegant, even though it gives the content providers much greater control over what, when and how much gets cached. Still, as a smaller fish, without going with cloudflare, there…

He perhaps meant bandwidth and not requests. Netflix and youtube alone must constitute the bulk of the volume and I believe they are fairly aggressively cached, then you have all the assets stored on CDNs.

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

#60

Post by meinheld111 »

iforgotpassword wrote: post #47
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!

Is it still? Afaik now with everything HTTPS, caching proxies on the ISP end are completely useless. We instead now see (proprietary?) cache boxes by big players like YouTube and Netflix that ISPs can install in their DCs, but that seems less elegant, even though it gives the content providers much greater control over what, when and how much gets cached. Still, as a smaller fish, without going with cloudflare, there…

A CDN is a cache as are the Netflix/fb/etc local boxes. CPUs have three layers of cache before hitting main memory, which could be considered a cache for persistent storage…

Yes, still

Post reply on HN