Live data from Hacker News

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

quantamagazine.org

111–120 of 132 posts

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

#111

Earlier quoted context omitted.

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…

Numerous people are currently sitting in jail in Saudi Arabia for having posted tweets critical of the regime under their own names. Without HTTPS, jails around the world would be a lot busier if authorities could see everything that their populace reads online in clear text, in order to build dossiers on who is most likely to be a dissident. I don’t think the kind of traffic analysis you mention works as well as you…

First of all, did I say get rid of HTTPS? A protocol that does integrity without privacy doesn't mean HTTPS magically disappears. You can still use it.

Second, totalitarian regimes around the world don't sit on their hands just because you use HTTPS. If they want to know who a dissident is, they go find out. Bribery, tips, intimidation, torture, spy cameras, facial recognition, etc. They also know that everyone who reads a tweet isn't automatically a dissident.

Third, no, it's not hard at all to do statistical traffic analysis, it's part of basic DPI packages shipped with commercial network gear for about a decade. All you need to identify the user is the destination and the source, and the signature of similar connections to specific hosts with specific traffic. You compare the traffic from the target user to the traffic you monitor or simulate with known destinations and content, and highest probability wins. It's child's play.

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

#112
post #8

Quanta 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)

quanta's tone does get mildly annoying at times, but the actual content of the articles is usually excellent, and this one is no exception. I suspect you disliked it simply because you already knew most of what it had to say. (I mean sure, the writer is no Martin Gardner, but then again who is.)

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

#113
The only CS class I ever took was Huffman's "Cybernetics" (undergrad UCSC CS class) and it was a real mind-blower. The very first day he dove right into sphere packing (https://en.wikipedia.org/wiki/Sphere_packing) and the whole course was a great introduction to information theory.

I remember him describing how he wrote the original solution for huffman compression, crumpled it up, threw it away, and then retrieved it from the trash.

I failed the class which led to a huge imposter syndrome in me that pushed me to learn far more CS than I ever needed to know. Huffman was definitely an arrogant bastard, but he certainly taught me a lot of interesting math.

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

#114
post #12

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.

OpenZFS' integration of Zstandard uses LZ4 as a "compression canary" for higher ZStandard compression levels, where they feed the data blocks through LZ4 and if it compresses it enough, feeds it through Zstandard.

This relies on LZ4 being very fast, especially with it's early-exit on incompressible data.

Overall this turns out to be a win, you lose a little bit of compression at a huge decrease in CPU over just using the same Zstandard compression for all the blocks.

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

#115
post #81

Earlier quoted context omitted.

Integrity without confidentiality is trivial.

How so? Your ISP is still the channel over which the integrity information is sent. Why couldn't they just swap the SRI hashes as well?

Well, it still involves some kind of public key infrastructure, but encryption could be optional even in https. Linux distros have been hosting their packages on plain http for two decades, PGP signatures (again, not a great example of "trivial", I admit) were sufficient to ensure integrity.

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

#117
post #23
post #8

Quanta 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)

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…

Quanta articles are usually written by people with at least graduate degrees, if not PhDs in Math/Physics/CS/etc.

They're without question one of the highest quality pop science publications around.

That you had to reach for an old Soviet magazine from the pre-internet era for anything better only speaks to that.

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

#118
post #80

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…

I found their Encyclopedia page[0], but I suspect you meant something better than this? Any further recollections to help drill down and find it? - [0]: https://www.pcmag.com/encyclopedia/term/data-compression

It looks like it was Barry Simon in "Lab Notes" in PC Magazine of June and July 1993:

https://books.google.com/books?id=gCfzPMoPJWgC&lpg=PP1&pg=PA...

https://books.google.com/books?id=eX8w8B-OhIIC&lpg=PA371&pg=...

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

#119
post #97

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...

It looks like the ones I were PC Magazine, https://books.google.com/books?id=gCfzPMoPJWgC&lpg=PP1&pg=PA... and https://books.google.com/books?id=eX8w8B-OhIIC&lpg=PA371&pg=... .

Much appreciation to all the folks who put in the work to make these things interesting and accessible.

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

#120
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 them. That means you can encode a large number of words (googling says those words make up ~1/7 of words based on frequency) with only 4-6 bits each. That's far from the 27 bits you calculated

Post reply on HN