11 ms·
NNCP: Lossless Data Compression with Neural Networks (2019)
- londons_explore 5y agoFabrice Bellard picks up one more side project, and beats state of the art in text compression by a substantial margin...
- rhaps0dy 5y agoIt’s a very cool achievement (a NN in 200KB, to compress? Wow) but the CMIX compression program performs better in the 1st benchmark, and is competitive in the 2nd. So he does not beat the SoTA “by a substantial margin”. Your comment is overstating the case.
- rndgermandude 5y agoTrue. Aside from the compression efficiency, I'd like to see other metrics too, like the work it takes to compute the compression (in units of energy, time, or whatever), to get more of a sense on what kind of workloads using something like that would make sense. These super-efficient compressors often only make sense in long term archival and compress-once-transmit-often scenarios. It appears http://www.mattmahoney.net/dc/text.html http://www.mattmahoney.net/dc/text.html (that Bellard links to on the NNCP page) has some information: - NNCP (w/GPU) used 161812 nanoseconds/byte to compress, 158982 nanoseconds/byte to decompress, on an Intel Xeon E3-1230 v6, 3.5 GHz, RTX 3090 GPU, using about 6GB of RAM, to compress enwik9 down to 110,034,293 bytes - CMIX used 602867 nanoseconds/byte to compress, 601569 nanoseconds/byte to decompress, on an Intel Core i7-7700K, 32 GB DDR4 using about 25GB of RAM, to compress enwik9 down to 115,714,367 bytes - gzip -9 used 101 nanoseconds/byte to compress, 17 nanoseconds/byte to decompress, on an... Athlon-64 3500+ in 32-bit mode running XP, to compress enwik9 down to 322,591,995 bytes - 7zip 9.20 used 1031 nanoseconds/byte to compress, 42 nanoseconds/byte to decompress, on a Gateway M-7301U laptop with 2.0 GHz dual core Pentium T3200 (1MB L2 cache), 3 GB RAM, Vista SP1, 32 bit, to compress enwik9 down to 227,905,645 bytes These benchmarks are not directly comparable, as vastly different machines were used, but it still gives a trend at the very least. As expected, these super-efficient algorithms are slow, really slow. Honestly, I'd think at least today too slow to make sense even for long term archival, and far too slow for compress-once-transmit-often scenarios, as the decompression rate is almost as slow as the compression rate. Still, it's impressive work, don't get me wrong.
- rogerb 5y agoEvery time I see a Fabrice Bellard submission here - it's like a little cake that you found in your fridge unexpectedly. Great stuff!
- mercer 5y agoIt's like checking out the freezer and realizing you bought ice cream a while back.
- etaioinshrdlu 5y agoI suspect his neural net library used in this could become quite useful and propagate far and wide if it were open-sourced: https://bellard.org/libnc/ https://bellard.org/libnc/
- londons_explore 5y agoIt's a lightweight ML library... But I'm not sure if it makes sense for anything with CUDA as a dependency to be lightweight.
- justinclift 5y agoFor reference, this is what it's License section says: The LibNC library is free to use as a binary shared library. Contact the author if access to its source code is required. https://bellard.org/libnc/libnc.html#License https://bellard.org/libnc/libnc.html#License
- xxs 5y agoCompression ratio/speed Program or model size: bytes rato: bpb speed: KB/s xz -9 24 865 244 1.99 1020 LSTM (small) 20 500 039 1.64 41.7 Transformer 18 126 936 1.45 1.79 (!) LSTM (large2) 16 791 077 1.34 2.38 Note the decompression is not faster than compression (unlike xz)
- bckr 5y agoOkay. Stupid question. What in the world do the ratio numbers mean? I get that "bpb" means "byte-per-byte". Is it input bytes per output bytes? Or the other way around? And why do some of the ratios go below 1.0? e.g. NNCP v2 (Transformer) 0.914
- tromp 5y agoCompression achieved on the first billion bytes of English Wikipedia is only 0.88 bits per byte (bpb). Even when the decompressing program is large at almost 200KB, that is... wow!
- londons_explore 5y agoNote that it is an XML formatted version of Wikipedia, so some of that data is very predictable XML tags.
- IcePic 5y agoTrue, but that would hold true for all common compressors, so beating them is still a huge win.
- kzrdude 5y agoI hope he's eligible for the Hutter prize for this improvement, should be a pretty nice sum.
- londons_explore 5y agoSadly not because it only works well on enwiki9 but not the smaller enwiki8. I would guess that's down to neural networks poor performance with small training sets.
- userbinator 5y agoAccording to http://prize.hutter1.net/#prev http://prize.hutter1.net/#prev he might actually be eligible.
- yalok 5y agoTrue story: long time ago, I was once interviewing a guy, and wanted to check his coding skills. Asked him to write some simple C function, doing some simple algorithm. Let the guy use my PC as I watched him (did I say it was very long time ago?). To my surprise, instead of writing C code right away, the guy went to Far on my PC, with a blink of an eye, with hot keys, found some existing files on my disk, glanced through them, returned to file editor and wrote that function. When I asked what that was, why did he have to dive into my C files, he admitted he doesn’t care to remember C syntax, and just had to look it up quickly to write his function. It turned out he was mostly writing all of his code in x86 assembly, and a pretty complex code. His main project in assembly was a compressor that was faster and more efficient than RAR, which at that time was at the top. I tried it and that was true. Many year later, the guys went on to win Hutter prize, and kept improving his own record year after year. I admire his grit and persistence, and how he keeps discovering new ways to improve his algorithms. And I wouldn’t be surprised if he maintains them in pure assembly (he did originally). I did hire the guy, and enjoyed working with him.
- ZephyrBlu 5y agoSo what's the Weissman score of this baby?
- xxs 5y agoExtremely low - it's a very slow algorithm. Think of xz being slow and takes forever... that's 3 orders of magnitude worse.
- linkdd 5y agoIn the TV show "Silicon Valley", the Weissman score measure the compression, not the speed. In reality, the Weissman score does not exist. I highly recommend this serie if you haven't seen it :)
- xxs 5y ago>the Weissman score measure the compression, not the speed This is false, it uses both - hence the 'middle out' was suitable for video chat and all kind of enterprise software (incl. a custom appliance box). Overall - a be it all compression. The score is so popular, it has its own wikipedia page[0]. It compares both required time and compression ratio of measured applications, with those of a de facto standard according to the data type. [0]: https://en.wikipedia.org/wiki/Weissman_score https://en.wikipedia.org/wiki/Weissman_score
- eps 5y agoCompression speed is around 2 KB/sec. The figure is given in nncp_v2.1.pdf. This is 1000x slower than xz, which in turn is 1000x slower than gzip. I have always wondered if a compression service could be a viable commercial offering and with NNCP rates and its compression speed, it looks like it could! That's for cases when you need to really compress the heck out of something, e.g. prior to distributing a large static piece of data to a very large number of recipients. I think there was a service like this, used by AAA game developers for distributing patches, but it didn't take because it had a very slow decompression... and, now reading further through the paper, it looks like an issue with NNCP too - The NNCP v2 decompression speed is similar to its compression speed. So it's a no-go for my brilliant and lazy startup idea, but fascinating stuff nonetheless.
- xxs 5y agoYup, it isn't a dictionary based compression. Nonetheless that's a fascinating take
- thesz 5y agoWith preprocessing it is a dictionary based compression. It uses a fixed dictionary to improve on compression.
- raverbashing 5y agoFor real I know shipping speeds are important, but it seems game developers could try harder with delta compressing their updates, because it's hard to believe a tens-of-GBs download is the best they could do when you already have a BluRay disk or something (unless it's new content, of course) I wonder how much their bandwidth costs are and how quickly a reduction would pay itself.
- xxs 5y agoWhat would pay for itself is p2p, e.g. bittorrent... alas.
- 5y ago
- ivoras 5y agoDid anyone manage to use the provided Windows binary to succesfully compress anything? For me, it exits producing a 0-byte "compressed" file.
- logicchains 5y agoFabrice Bellard is proof that 10x programmers exist. Or even more than 10x; he single-handled wrote a software 4G LTE base station (https://bellard.org/lte/ https://bellard.org/lte/), something that would normally take a team of hundreds to develop due to the complexity of the specification.
- deleted 5y ago[deleted]
- vanderZwan 5y agoHe's pretty much the programmer's John von Neumann of our time, isn't he? Or at least one of the few contenders for that title
- amelius 5y agoVon Neumann was more a mathematician/scientist than an engineer.
- vanderZwan 5y agoWell yes, but a 10x mathematician/scientist. Plus important enough to the field of computing to be comparable I think
- deleted 5y ago[deleted]
- yalok 5y agoTotally. Plus FFmpeg…
- logicchains 5y agoAnd QEMU...
- 5y ago
- esjeon 5y agoFYI, the compression speed numbers from the paper: gzip = 17 MB/s xz = 1 MB/s CMIX = 1.6 kB/s NNCP = 2~3 kB/s (Note that NNCP is using RTX 3090 here.) Not only this is unacceptable for hot/warm data, also it's still impractical for cold data. It takes 10~16 years to compress or decompress 1 TB data.
- vanderZwan 5y agoIt does make me wonder: if we wrote an LZ77-based algorithm (like gzip and xz) with that time-budget in mind, could we match NNCP?
- pornel 5y agoI don't know enough about xz, but for gzip I can tell you that definitely not. Even with an infinite amount of computation there's a hard limit to how good gzip can compress, and it's not very good. For example, let's say you've decoded a stream that so far contained: 123456 a clever algorithm can make a guess that "7890" will be next (compression is all about making good guesses about the future data). LZ77 just can't — it has no way to express such prediction. This is general problem for LZ77 with data that has a predictable structure, but isn't a literal repetition of previous data.
- vanderZwan 5y agoWell, isn't that what PNG filters do? So in that sense one could build an algorithm on top of LZ77 that tries to reversibly transform data into repeating sequences.
- vidarh 5y agoLZ77 is basically the "scaffolding" for every compression method that uses symmetric compressor and decompressors to replicate state so you don't need to transmit it. So the moment you add a function on top that does more complex prediction than copying from the existing stream, you have a general framework that is far more powerful than basic LZ77. NNCP is such an algorithm on top of that general idea.
- dariosalvi78 5y agoWhen I was a student at the university I thought it could be possible to combine quantisation used in lossy compression like JPEG and NN in some way..
- fabioyy 5y agoFabrice Bellard is a legend!
- ballenf 5y agoCould this work on an M1, if optimized for its ML cores?
- agustinbena 5y agoIs there a church to go and pray God Bellard
- fit2rule 5y agoYou're in it.
- kdmdmdmmdmd 5y agoThis is some of the dumbest shit I’ve ever seen. There’s literally no qualified people commenting on this board any longer. If you have any idea what the fuck neural network is or how compression works you’ll know why this is a bad idea I would elaborate but I’d probably get banned for eing negitive
- kdmdmdmmdmd 5y agoLol dumb
- GistNoesis 5y agoI'd like to highlight the Introduction of nmcp.pdf which explains in a very compressed form how it works which encompass all the magic. "The lossless data compressor employs the traditional predictive approach: at each time t, the encoder uses the neural network model to compute the probability vector p of the next symbol values t knowing all the preceding symbols s0 up to st−1. The actual symbol value st is encoded using an arithmetic encoder with approximately −log2 ( pst ) bits. Then the model is updated knowing the symbol st. The decoder works symmetrically so there is no need to transmit the model parameters. It implies both encoder and decoder update their model identically. When no preprocessing is done, st represents the byte at position t. Hence there are Ns= 256 different symbol values from 0 to Ns−1." For those usually familiar with Huffman coding this is using an Arithmetic coding https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding It allows adaptive coding (i.e. changing the probabilities of symbols dynamically). Here these probabilities are modelled dynamically using a neural network. The magic is that the neural network parameters are defined implicitly : You don't need to transmit the neural network parameters, therefore you can use as big as you want neural network. During the decoding the from scratch network is continuously trained using the freshly decoded data, in the same way that it was during the encoding. The more data you compress, the more you train the internal neural network parameters, and the better the prediction for next character gets. You decode 20 bytes, you update the model with this new data, you decode 20 new bytes with the new model, you update the model,... , every 1000000 bytes you can even update your model multiple times using all currently available data to make the network converge faster. Of course this only works if everything is exactly deterministic, which Fabrice Bellard took great effort in guaranteeing, which is no small engineering feat.
- debbiedowner 5y agoWhat is the probability that there are no collisions by the encoder?
- pkhuong 5y ago100%.
- 5y ago
- telesilla 5y agoCould this address lower file sizes for lossless video and audio?
- riffraff 5y agoIt seems too slow for real time decompression
- telesilla 5y agoReal time decompression isn't the only requirement, for example media storage has massive needs now studio production is moving to the cloud. If a new lossless codec is possible even if it needs a day to compress or decompress there are still huge benefits in some applications.
- layoutIfNeeded 5y agoNo.
- legulere 5y agoI often wonder where Fabrice Bellard finds the time for all of his projects
- alecco 5y agoIf you remove all the time wasters and you do strict 40h of work you'd be surprised how much time you have left. Remove wasting time on HN/reddit/watercooling and then compensating by working more hours, and cut the "cord" for all/most entertainment. Instead, read technical stuff. Even if you do it for just a couple of hours a day you'll leave most people behind. Same with programming. Ideally do it in the morning before work. So go to sleep very early.
- ZephyrBlu 5y agoFor me, I think social media on the whole quite has been quite valuable use of time. It feels less like a waste and more like research or learning. The serendipity of HN, Reddit and Twitter have exposed me to a lot of ideas and information I would have otherwise never known about.
- opsy2 5y agoMaybe it's an explore/exploit thing, social media is good for exploring but to build depth we should switch off the socials and hit the books every other week.
- alecco 5y agoSure. I *try* to limit my HN/Wikipedia/etc usage because it's interesting but it gets me very distracted from my goals. For example, my monkey brain hears a song and I suddenly need to get the lyrics, the story behind it, etc. The monkey brain is very creative at finding ways to avoid doing difficult tasks. Reddit and Twitter are mostly a waste of time nowadays due to the signal to noise ratio. I dropped my reddit addiction and I'm working on eliminating Twitter. I wish there were a social network system where people pool and share what they are expected to be doing and help each other. Or at least encourage each other to focus. But this goes against the advertisement paradigm where they want us to be impulsive and stupid. Sad, sad, sad.
- alecco 5y agoThis is very interesting but for people who are not from the field note 1. The compressors he is comparing to *are* neural networks themselves (PAQ) 2. He is using a rather small corpus enwik8 (100,000,000 bytes), instead of the common enwik9 3. He is not publishing the amount of RAM or hardware he used http://mattmahoney.net/dc/dce.html http://mattmahoney.net/dc/dce.html (seems down) https://web.archive.org/web/20210216231934/http://mattmahoney.net/dc/dce.html#Section_436 https://web.archive.org/web/20210216231934/http://mattmahone... It seems Bellard is starting to play with these. I bet he will find interesting things and I would love to see him interact in the Russian compression webforum (please don't link). Big names in compression like Yann Collet, Matt Mahoney, and Jarek Duda used to hang out there.
- merricksb 5y agoOriginal 2019 discussion for those curious: https://news.ycombinator.com/item?id=19589848 https://news.ycombinator.com/item?id=19589848
- Bulat_Ziganshin 5y agoThere is long NNCP thread on the forum dedicated to compression algos: https://encode.su/threads/3094-NNCP-Lossless-Data-Compression-with-Neural-Networks https://encode.su/threads/3094-NNCP-Lossless-Data-Compressio...
- smel 5y agoGuys are you sure that bellard is human ?
- amcoastal 5y agoThis seems like an old school and specific way of describing a much larger goal using NNs and auto encoders. To take data and reduce its dimensionality, while getting a (near) perfect reconstruction of the original input from the latent space data. Reducing (haha pun) this broad effort to just "data compression" leaves a lot of nuance and use out of sight.
- rurban 5y agopaq also has a similar NN encoder, but a much better and much faster one. In asm though, but open source. LibNC is closed
- mpfundstein 5y agoBellard is so awesome. But can someone please explain to me how this guy finds the time to build all those amazing things? It's so much non trivial stuff in his list. I wonder... Does he have kids? A family? Is he rich? Does he get millions to build quantum computers? I really wanna know :-) Thanks
- TynanSigg 5y agoOh hey I did something like this a while ago, but much less polished. I basically made an rANS encoder and hooked it up to GPT-2 (via the excellent transformers library from HuggingFace) to see what compression ratio I could get. Bellard's approach seems to use a custom model, which is probably advisable as big language models like I used are very slow. I didn't try to optimize much and only ever tested on my little personal laptop with just CPU, but I only got encoding speeds of ~0.1 Kb/s (limited mostly by available memory). However I was able to get very good compression factors of 6.5x using standard GPT-2 and 7.3x using the medium version. Here's the code if anyone's interested: https://github.com/trsigg/lm-compression https://github.com/trsigg/lm-compression . I haven't looked at it in a while except for updating it today to work with more recent versions of the transformers library, but I think it should still function and is pretty easy to try out with different models. I thought about using something like a hidden Markov model instead which would be much faster (even more so because it would enable using tabled rather than range-based ANS), but I haven't gotten around to it.
- meiji163 5y agoUsing a pretrained model is a little bit cheating, you would have to include the size of the weights in the ratio
- TynanSigg 5y agoThose two metrics will converge as the size of the text being compressed goes to infinity. It's necessary to include model size for things like the Hutter prize that involve compressing a fixed text (to avoid hard-coding) but isn't usually a useful metric for compression, especially because it will cause the compression ratio to depend on the size of the data being compressed. Edit: I thought the model in the above paper was pre-trained, but apparently it's only trained on the data as it arrives! That's indeed a very interesting approach, I wouldn't have expected that neural network models would converge quickly enough for it to be useful.
- TynanSigg 5y agoAfter a bit more digging, it seems Bellard also has a version using GPT-2: https://bellard.org/libnc/gpt2tc.html https://bellard.org/libnc/gpt2tc.html Looks much cleaner and faster than my little winter break project, cool to see this implemented properly!