A student’s desire to get out of a exam led to a compression algorithm
quantamagazine.org
quantamagazine.org
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.
Any further recollections to help drill down and find it?
- [0]: https://www.pcmag.com/encyclopedia/term/data-compression
https://books.google.com/books?id=gCfzPMoPJWgC&lpg=PP1&pg=PA...
https://books.google.com/books?id=eX8w8B-OhIIC&lpg=PA371&pg=...
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 to artificial intelligence (whatever that ends up meaning).
How so? Aren't the networks' weights orders of magnitude smaller than the training data?
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...
Much appreciation to all the folks who put in the work to make these things interesting and accessible.
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.
It is used in PKZip Deflate algorithm.
Fano's work is as famous and as useful as Huffman's.
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!
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?
The internet is "driven" by web/mobile which is driven by multimedia, which lives and dies on compression / codecs.
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's no caching involved anymore, probably not even if I decide to run my site on HTTP only.
Yes, still
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 show you can uniquely identify a client going to a random internet server (and the page they're browsing) just by sniffing a bunch of POPs. It's used by law enforcement and Five Eyes to identify internet users around the world. Even protocols that have countermeasures (TOR) don't stand up to it.
Compared to transit, last mile bandwidth is effectively limitless and free. Cache fill at the edge is important, last mile caching not so much.
Also, a lot of ISPs blackbox caching proxies were buggy and breaking websites.
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.
I don’t think the kind of traffic analysis you mention works as well as you think it does for identifying individual pages e.g. which tweet someone is viewing. Moreover it requires a level of technical sophistication that is beyond all but the most advanced countries, countries that tend to have some measure of rule of law.
Indeed... When one lives in such regimes, to say that appears to be an utter truism.
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.
2. Wasn't there some work on serving presigned HTTPS requests? The one everyone blamed Google (?) for cause they wanted it to put slices of other websites inside the search results. Might make sense to resurrect that work.
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.
Lempel-Ziv is the basis for almost all modern general purpose compression, and works more like having a hash table mapping 3 or 4 byte fragments to their positions, and walking through the input byte by byte checking the hash table for matches and inserting the latest fragments&positions into the hash table.
BWT has nearly identical speed compressing and decompressing, but searching for matches to compress is much slower than simply copying data according to instructions to decompress.
I didn't believe you until about a minute in. LOL
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.
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.
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.
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.
That's the approach used by tools like optipng and pngcrush.
> 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.".
The same idea can be found in the PNG standard itself: "For best compression of truecolor and grayscale images, we recommend an adaptive filtering approach in which a filter is chosen for each scanline. The following simple heuristic has performed well in early tests: compute the output scanline using all five filters, and select the filter that gives the smallest sum of absolute values of outputs. (Consider the output bytes as signed differences for this test.) This method usually outperforms any single fixed filter choice. However, it is likely that much better heuristics will be found as more experience is gained with PNG." (quoted from the PNG specification, version 1.2)
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.
I'm sure AI will end up the winner in compression in the end.
You could think of it as taking a "snapshot" if an AI and then optimizing the hell out of it for a specific case and you end up with a good compression algorithm.
On a lower level, you can't tell ChatGPT to reason about an image when its only input is a microphone.
It's basically the curve-fitting problem: You don't want the simplest curve that fits all the available data points perfectly, you want an even simpler curve that still fits the evidence reasonably well. If you hit the right balance between simplicity and fit, you can expect your model to generalize to unseen data, to make successful predictions. That would be intelligence, or some major part of it.
Huh? Ubiquitous?
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, and in binary it would have between 1 and at most 19 bits, for any word in the index (2^19 is around 500k)
That’s without even sorting the index by frequency of appearance/usage
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
> 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
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.
I believe some popular video codecs use arithmetic coding (and IIRC, some other video codecs use the related range coding to avoid these patents).
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.
https://blog.cloudflare.com/results-experimenting-brotli/
https://blog.cloudflare.com/brotli-compression-using-a-reduc...
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...
(Not because popular science is bad, but because they do it badly, and the clickbait is insufferable)
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:
The Kvant articles were written by professional research mathematicians, trying to present their ideas to an audience that were willing to follow them with pencil and paper in hand.
Quanta magazine articles are written by journalists trying to present advanced science to a lay audience - the articles are very stilted and present the articles in a tone that oversimplifies the problem and gives no idea about the actual solution, and uses hackneyed tropes like : oh look the solvers were just some random unknown guys (in a recent case, the random unknown guy is a tenured faculty at UCLA in theoretical computer science, apparently "a world away from mathematics" [3])
[1] http://www.iri.upc.edu/people/thomas/Collection/details/5660...
[2] http://www.personal.psu.edu/sot2/kvant_preface1.pdf
[3] https://www.quantamagazine.org/surprise-computer-science-pro...
Interesting to hear about Kvant!
I'll just say up front that I am not an academic, and I enjoy the breadth of coverage in the Quanta articles. I would liken them to science articles in American Scientist. (Perhaps you don't like that either.) Yes, they are popularized, but they are still technical.
Are you bored by a description of an algorithm you know well? This article clearly describes the process of Huffmann encoding. It's not one of the most amazing discoveries, but is this topic ever going to be exciting? I'd say it's easier to follow their article than either Wikipedia or the top animation hit [1].
There are two other claims you make that appear baseless.
On the first point:
> Quanta magazine articles are written by journalists
The first bio I checked [2] is a Ph.D. mathematician. If they also write, that does not make them less qualified. I'll grant that the second bio I checked [4] was "only" a journalist, but the third was a professor in a named chair [5]. Just clicking, not searching for examples.
On the second point:
> oversimplifies the problem and gives no idea about the actual solution
In your reference [3], it describes the problem clearly and devotes several paragraphs to what looks like a sketch of a solution. Certainly it outlines the ingredients used. (Search for "To see how they arrived at their new upper limit." and "In their proof [...]".)
[1]: https://cmps-people.ok.ubc.ca/ylucet/DS/Huffman.html [2]: https://www.quantamagazine.org/authors/erica-klarreich/ [4]: https://www.quantamagazine.org/authors/kevin-hartnett/ [5]: https://www.quantamagazine.org/authors/stevenstrogatz/
Quanta is far better than the programmer / bizhacker / SEO blogs that dominate HN.
> “My mind was just blown. Like, wait, have they really done this?” said Sisask, a lecturer at Stockholm University."
> Sisask called it “the biggest result in the area for 20 years.”
> “Meka and Kelley have sort of leapfrogged all this incremental progress,” said Terence Tao, a prominent mathematician at UCLA.
Maybe you're just wrong? I trust the judgement of these people more than yours.
That said, from a skim I wouldn't call this particular article standard pop science: it explains an idea/result rather than spending most of its words on periphera, and the subject is not recent news. It does ask less of the reader than an old Sci Am article would, I think.
glad that someone also shares this opinion, the articles and the art in those two decades was great
The Wikipedia entry on Huffman Coding is impenetrable to me, this article was easy to follow.
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.
Well, then, who does pop science "right"?
There's no shortage, of course, of 30+ page review articles on every scientific topic imaginable. And if someone has a few days, a freshly minted STEM degree or years of related experience, and a compelling interest in the topic, they can just pick up one of these review articles and go to town.
But that isn't going to fly for the general public, not even close. And not just because of the mathematics, dry passive-voice language, lack of context, times new roman, and gratuitous expert jargon. It's just too much.
So, what do you recommend?
I much prefer the treatment from some YouTubers, such as Sabine Hossenfelder (to name just one).
It's far from dry, she has a wicked sense of humour, she tries her best to be impartial (and sometimes fails), and makes it clear when something she says is her opinion.
PBS also has a ton of good content.
Of course, all these actually require the viewer to make an effort, but if you're not ready to do that, then a poorly written clickbait article is likely to do more harm than good anyways.