11 ms·
A student’s desire to get out of a exam led to a compression algorithm
- gfody 3y agomissed opportunity to explain how compression and prediction are related, and that the better you can predict the next token the better your compression gets, then your article gets to mention GPT hey
- optimalsolver 3y agoApparently compression and intelligence are synonymous: https://mattmahoney.net/dc/rationale.html https://mattmahoney.net/dc/rationale.html
- valenterry 3y agoI think in a sense compression is worse - because not only you want to correctly predict the next token, you also want to do it fast, with a minimal but efficient algorithm that also doesn't require much space / a big dictionary. 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.
- mxkopy 3y agoIn today's post-GPT world it's important to recognize the role of embodiment in intelligence as well.
- qumpis 3y agoWhy?
- mxkopy 3y agoThe modality of the data contains an amount of information comparable to the data itself. Telling ChatGPT that it's hearing music rather than a story would probably help it reason about it a lot. On a lower level, you can't tell ChatGPT to reason about an image when its only input is a microphone.
- cubefox 3y agoAIXI / Solomonoff prediction uses lossless compression, which may lead to massive overfitting. If anything, some degree of lossy compression would be "equivalent" to intelligence. Ockham's razor also says that the simplicity of a hypothesis can outweigh another hypothesis which better describes the available evidence. It's a trade-off, and AIXI doesn't make that trade-off, but insists on perfect compression/prediction of the available data. 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.
- tgv 3y agoSynonymous, according to one person, taking a liberal view of a only vaguely related result.
- ozr 3y agoThat being said: the best results currently on the large text compression benchmark utilize ML: http://www.mattmahoney.net/dc/text.html http://www.mattmahoney.net/dc/text.html
- denvaar 3y ago> 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.
- Scaevolus 3y agoNo, BWT is largely unused in modern compression codecs. 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.
- pseudotrash 3y agoI came here to find Silicon Valley references and wasn't disappointed.
- devsegal 3y agoBoth of us have been satisfied
- hinkley 3y agoat the same time?
- ThrowawayTestr 3y agoI 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.
- 3y ago
- hackcasual 3y agoHuffman trees are really cool and a neat little example program to put together.
- delosrogers 3y agoAgreed, I had a lot of fun putting a toy one together, even if my compression format was worse in every way than a real format and my implementation quite inefficient
- fguerraz 3y agoQuanta 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)
- sn41 3y agoI 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: 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/56609.html http://www.iri.upc.edu/people/thomas/Collection/details/5660... [2] http://www.personal.psu.edu/sot2/kvant_preface1.pdf http://www.personal.psu.edu/sot2/kvant_preface1.pdf [3] https://www.quantamagazine.org/surprise-computer-science-proof-stuns-mathematicians-20230321/ https://www.quantamagazine.org/surprise-computer-science-pro...
- dieselgate 3y agoYeah 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 researchers/experts and are higher quality in my opinion. Interesting to hear about Kvant!
- sgt101 3y agoCaches 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!
- asah 3y agoboth are correct. The internet is "driven" by web/mobile which is driven by multimedia, which lives and dies on compression / codecs.
- Solvency 3y agoOk how do they work then?
- parl_match 3y agoThere's lot of information about this on the open web, and tons of resources for varying levels of skill.
- deleted 3y ago[deleted]
- astrange 3y agoIronically, this answer is a cache miss.
- esafak 3y agoThey store frequently-requested items in a place that permits faster retrieval. https://en.wikipedia.org/wiki/Cache_(computing) https://en.wikipedia.org/wiki/Cache_(computing)
- psychphysic 3y agoWait 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?
- joshsabol46 3y agoPlease 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.
- deepsun 3y ago> 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.
- U2EF1 3y agoI 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.
- LoganDark 3y agoAnd then, when nobody wants to implement all the compression algorithms in a compressor or decompressor, we end up with files out in the wild that only pick one of them anyway.
- alpaca128 3y agoIt 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.
- twotwotwo 3y agoThere 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.
- deleted 3y ago[deleted]
- Folcon 3y agoI 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 https://www.pcmag.com/encyclopedia/term/data-compression
- twotwotwo 3y agoIt 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=PA305 https://books.google.com/books?id=gCfzPMoPJWgC&lpg=PP1&pg=PA... https://books.google.com/books?id=eX8w8B-OhIIC&lpg=PA371&pg=PA371 https://books.google.com/books?id=eX8w8B-OhIIC&lpg=PA371&pg=...
- MauranKilom 3y agoAnother 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 https://en.wikipedia.org/wiki/Hutter_Prize (and https://en.wikipedia.org/wiki/AIXI 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).
- yawaramin 3y agoOn 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?
- adgjlsfhk1 3y agoBrotli and ZSTD are both a bunch better (~20% file size while being faster to decompress). Brotli does especially well on javascript/html because they hard-code some of the keywords in the spec.
- jgrahamc 3y agoIt does. That's why we're turning it on automatically. We've supported it since 2017 and we have made a bunch of changes recently that make it better. https://blog.cloudflare.com/results-experimenting-brotli/ https://blog.cloudflare.com/results-experimenting-brotli/ https://blog.cloudflare.com/brotli-compression-using-a-reduced-dictionary/ https://blog.cloudflare.com/brotli-compression-using-a-reduc...
- powturbo 3y agoI'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 https://github.com/powturbo/TurboBench [1] https://sites.google.com/site/powturbo/home/web-compression https://sites.google.com/site/powturbo/home/web-compression [2] https://encode.su/threads/2333-TurboBench-Back-to-the-future-(incl-LzTurbo)?p=78754&viewfull=1#post78754 https://encode.su/threads/2333-TurboBench-Back-to-the-future...
- verall 3y ago> to the ubiquitous software utility PKZip Huh? Ubiquitous?
- quesera 3y agoThe utility program might vary between platforms, but the algorithm is definitely ubiquitous.
- iforgotpassword 3y agoInteresting 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.
- dmurray 3y agoA nice reversal of the meme where "the supervising professor takes all the credit and the army of grad students do the real work".
- amemisoglu 3y agoThis algorithm is known as Huffman encoding.
- yccs27 3y agoYes, and it's named after graduate student Huffman (at the time) instead of after his supervisor/teacher Fano.
- bsenftner 3y agoWhich strikes me as either rare honesty, or an example of how our values have slid over time because today the professor would claim the algorithm for himself, and the student would get a B- for some spelling mistake in his write up, none the wiser the professor it making fame from their work.
- klyrs 3y agoMathematicians are familiar with the name Fano, but for Roberto's dad Gino, whose name adorns the first finite projective plane.
- thesz 3y agoHere's Shannon-Fano coding: https://en.wikipedia.org/wiki/Shannon%E2%80%93Fano_coding https://en.wikipedia.org/wiki/Shannon%E2%80%93Fano_coding It is used in PKZip Deflate algorithm. Fano's work is as famous and as useful as Huffman's.
- jhallenworld 3y agoI thought Huffman coding was obsolete, arithmetic coding replaced it. It allows for fractional number of bits per symbol, so is more efficient.
- ixwt 3y agoMy 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.
- zulban 3y agoHuh? I thought you cannot patent an algorithm, mathematical process, number, game design, etc.
- cesarb 3y ago> I'm not familiar with any actively used compression algorithm that uses arithmetic coding. I believe some popular video codecs use arithmetic coding (and IIRC, some other video codecs use the related range coding to avoid these patents).
- adgjlsfhk1 3y agoThe 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.
- Isamu 3y agoIt’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.
- adgjlsfhk1 3y ago
- amelius 3y agoWhat would be interesting is something like an LLM attempting to compress some piece of data, and see how it gets better at it over time.
- vjerancrnjak 3y agoI think there’s a contest for this compressing Wikipedia. LMs are winning.
- amelius 3y agoInteresting. Do you mean [1]? [1] https://en.wikipedia.org/wiki/Hutter_Prize https://en.wikipedia.org/wiki/Hutter_Prize
- nextmove 3y agoGreat read for beginners. I've read about Robert Fano being the creator of Project MAC that turned into MIT's AI lab (CSAIL). I'm sure AI will end up the winner in compression in the end.
- nico 3y agoIn 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, 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
- malisper 3y ago> 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
- nico 3y agoAbout 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
- dekhn 3y agoThe 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 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.
- deleted 3y ago[deleted]
- ftxbro 3y agogpt uses huffman coding for tokenization