7 ms·
Adventures with compression
- d_burfoot 3y agoYes, compression is definitely a rabbit hole - essentially an infinite rabbit hole. Optimal compression requires perfect understanding of the underlying material. So to compress English text well, you need to understand English very well - it's grammar, morphology, semantics, etc. I crawled very deep into this particular rabbit hole. I built text compressors that exploited linguistic structure. I was able to quantify improvements in my understanding of text by observing improvements in the compression rate. The beautiful aspect of this project is its rigor: lossless compression is such a demanding challenge that you cannot possibly deceive yourself. If you have a bug in your code, you will either decode the wrong result or fail to get a codelength reduction. Using this methodology I was able to build a statistical parser without using any labeled training data. Unfortunately for me, the advent of GPT and other DNN-based LLMs made this research obsolete. It may still be interesting for humans to build theories of syntax and grammar, but GPT has this information encoded implicitly in its neural weights in a much more sophisticated way than linguistic theories can achieve.
- xnx 3y ago> GPT has this information encoded implicitly in its neural weights in a much more sophisticated way than linguistic theories can achieve "More data beats clever algorithms" strikes again.
- bawolff 3y agoIsn't gpt like 800gb big? I can compress a 1gb file to 0 bytes if i am allowed 1gb of additional data.
- ChadNauseam 3y agoYou can't if you have to pick the 1gb of additional data before you see the 1gb file you're supposed to compress (which is the situation gpt is in)
- bawolff 3y agoAlthough in this case, we know the data comes from wikipedia and i assume gpt was trained on wikipedia, so it really does seem unfair.
- _a_a_a_ 3y agoBut the parent was talking about lossless, GPT presumably is anything but.
- d_burfoot 3y agoGPT, and probably any LLM, can be hooked up to an encoder to produce a lossless data compressor. Patrice Bellard has done this, HN discussion here: https://news.ycombinator.com/item?id=23618465 https://news.ycombinator.com/item?id=23618465
- pizza 3y agoSure it is, just use a probability distribution over the entire vocabulary of possible tokens to do arithmetic/range coding of the original text.
- _a_a_a_ 3y agoUh? GPT is an neural net, right?Which is a bunch of weights, surely, so how can you get lossless compression from that? (Complete newbie here BTW)
- pizza 3y agoThe model can either generate probable outputs or score the likelihood of given inputs.
- _a_a_a_ 3y agoHow does one produce 'lossless' from 'probable' or 'likelihood'?
- sp332 3y agoBy running the decoder during encoding. If the decoder already produces the right output, which it will most of the time, then you don’t need to store anything in the file. If it produces the wrong output, store a correction, then continue from there. The final file only needs to include the corrections.
- refset 3y agoCompression is, ultimately, AI. https://news.ycombinator.com/item?id=38399753 https://news.ycombinator.com/item?id=38399753 https://news.ycombinator.com/item?id=31923231 https://news.ycombinator.com/item?id=31923231
- DeathArrow 3y agoNot really. Your task might be to compress random weather data or historical stock info or historical lottery results.
- lifthrasiir 3y agoThey are not random (e.g. weather data should have a daily or seasonal pattern). And the fact that there does exist a random-looking data doesn't refute the original claim because AI can conclude that the data has a close-to-maximal entropy (i.e. "incompressible") instead.
- ivancho 3y agoIn those datasets you could improve compression by adding apriori knowledge about their context in the real world - if the compression program knows about historical S&P500 prices, it will be pretty good at compressing all historical stock info. Kolmogorov complexity is indistinguishable from AI
- rcthompson 3y agoRandom compression-related story time: I once had to run a program hundreds of times and capture all the stack traces to help the author catch a stochastic bug. I zipped up all the stack traces and sent the resulting file to the author. The compressed file was only a few dozen MB, and the uncompressed stack traces all together were only a few hundred MB... on my ZFS filesystem with compression enabled. When the author unzipped the file on their end, they were surprised to find around 10 GB of very repetitive stack traces.
- waltbosz 3y agoMy favorite uncompressed file size surprise comes from the world of Dreamcast game piracy. Pirates would publish game disc images in a ZIP file that was say 100mb. When uncompressed the iso file would be 750mb. The reason for the huge compression ratio was because the iso would contain a 600mb empty file, which compressed down to almost nothing. The purpose was so the when the image was burned to a cdr, the game data would be burned on the outer part of the physical media, and the empty file burned to the inner. The goal was to speed up read times when playing a game.
- crazygringo 3y agoThat’s really clever!
- ac2u 3y agoMemories flooding back of so many useless CD-Rs thrown in the bin until I could perfect the procedure of getting bootable CD-Rs with DiscJuggler/Nero
- pitdicker 3y agoFrom http://prize.hutter1.net/ http://prize.hutter1.net/: Being able to compress well is closely related to intelligence as explained below. While intelligence is a slippery concept, file sizes are hard numbers. Wikipedia is an extensive snapshot of Human Knowledge. If you can compress the first 1GB of Wikipedia better than your predecessors, your (de)compressor likely has to be smart(er). The intention of this prize is to encourage development of intelligent compressors/programs as a path to AGI. The Task: Losslessly compress the 1GB file enwik9 to less than 114MB. More precisely: - Create a Linux or Windows compressor comp.exe of size S1 that compresses enwik9 to archive.exe of size S2 such that S:=S1+S2 < L := 114'156'155 (previous record). - If run, archive.exe produces (without input from other sources) a 10^9 byte file that is identical to enwik9. - If we can verify your claim, you are eligible for a prize of 500'000€×(1-S/L). Minimum claim is 5'000€ (1% improvement). - Restrictions: Must run in ≲50 hours using a single CPU core and <10GB RAM and <100GB HDD on our test machine.
- tromp 3y ago> compressor comp.exe of size S1 that compresses enwik9 to archive.exe of size S2 such that S:=S1+S2 < L That criterion is rather more complicated than just taking the size S2 of archive.exe There is no logical meaning to the sum of the size of a compressor and its output that I can see. Disregarding the compressor size would make this contest easier to understand as simply trying to determine the Kolmogorov Complexity (i.e. information content) of enwik9. I looked for the motivation of including compressor size and only found this in the FAQ: > By just measuring L(D)+L(A), one can freely hand-craft large word tables (or other structures) used by C and D, and place them in C and either D or A. By counting both, L(C) and L(D), such tables become 2-3 times more expensive, and hence discourages them. Discouraging word tables seems like a weak and somewhat arbitrary justification for complicating the measure of merit. I don't think the contest would be any less interesting if the nature of the compression would be disregarded. One could even argue that compression of Wikipedia taking way more resources than decompression is justified by having to perform it only once, while its result could be decompressed millions of times.
- viraptor 3y ago
- sdenton4 3y agoSo has anyone tried lossless compression with an LLM? Method: create a list of next token predictions, ordered by describing probability, and encode the actual token as its position in the ordered list (so, eg, the most likely token is encoded as zero, second most likely as 1, etc). If the LLM is good, this should provide an excellent encoding.
- atorodius 3y agoYes, next token prediction is exactly what you need for compression. Many papers on this, recent one https://arxiv.org/pdf/2309.10668.pdf https://arxiv.org/pdf/2309.10668.pdf
- sdenton4 3y agoLovely paper, thanks!
- duskwuff 3y ago> If the LLM is good, this should provide an excellent encoding. For the purposes of compression "contests" like this one, the size of the model would count against your compressed data size. You're going to have a hard time fitting a useful model into <100 MB.
- sdenton4 3y agoThe thing is, we typically have three parts of a compression scheme: the data, the model (dictionary, Huffman tree, etc), and the program. The model is typically learned from the data at compression time. The program itself is general, however, and as far as I know, doesn't count against the total. Ie, the size of the gzip binary isn't part of the total for the purposes of the contest. So if an LLM is genuinely useful without fine tuning on the target data, you should make it part of the program. The data-specific model could be a self-prompt produced from reading and summarizing the data, which would help with the initial context-free predictions... {Edit} Ha, looking at the competition, it does indeed include the full size of the gzip binary in the metric. Weird.
- Dwedit 3y agoBrotli itself has a pre-filled dictionary, which was designed specifically for whatever was most common for internet traffic at the time. So lots of stuff to make XML headers tiny, along with a lot of common English words.
- yu3zhou4 3y agoNice curiosity driven exploration! I share the positive sentiment towards such project-based learning as well. It was a good read James, thank you. One thing you might consider to include is more quantitative data in terms of compression progress for methods you applied I’m interested about how the future exploring of methods you suggested at the end would work out, especially treating text compression like image compression
- esafak 3y agoI think the author should study probability- and information theory if he's serious about compression. It is mathematically deep, and goes into interesting tangents like information geometry and quantum information theory. https://www.wiley.com/en-us/Elements+of+Information+Theory%2C+2nd+Edition-p-9780471241959 https://www.wiley.com/en-us/Elements+of+Information+Theory%2...
- jrochkind1 3y ago> got the number 1024, I had a problem. Space could be saved if coffee was 1. Sounds like OP is encoding as ascii encoded digits? Seems like there should be space to be saved there by encoding as actual numeric bytes instead, although of course since you will need more than 256 numbers, you'll have to have an encoding for variable-width numbers similar to what UTF-8 does. Or if you don't need more than 65K, maybe just two-byte-width numbers would still save you significant space over ascii digits (where anything over 9 is already two bytes!) I don't entirely understand the exersize. Like, if the size of the compressing software and data (such as the dictionary) are taken into account too. And it seems unlikely this kind of naive reinventing the wheel approach is going to beat, say, gzip in the first place? (or am I really wrong there?) But it is fun and educational to invent new DIY compressions!
- hgs3 3y agoHow much research has been done on lossy text compression? As in, would it be possible to rewrite text with fewer words that conveys the same meaning? I'd imagine AI could do it.
- gwern 3y agoThis is one of the most common reactions, and the answer is, there's no real difference: lossy compression is the same thing as lossless. You simply store some extra bits to correct the errors or lost data (typically in an arithmetic encoding framework where you can plug in arbitrary predictors or combinations of predictors), and now it's back to the lossless setting. So all real compression algorithms are effectively 'lossy' already, and making the distinction gains you nothing. You instead spend your time thinking about how to predict better at all.