3 ms·
FYI, 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 309
by esjeon 5y ago
FYI, 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.
- pornel 5y agoFilters in PNG are not too bad for what could be done with an off-the-shelf gzip and a few lines of code, but as a compression mechanism they work poorly. All compression is prediction + entropy coding. The entropy coding part is a solved problem. Inserting LZ77 between your predictor and the entropy coder just makes it harder to communicate the exact symbols and probabilities you have predicted. If you're building a rocket: you can strap a rocket engine to a car, and it will still go faster than the car itself, but it's easier not to build it on top of a car.
- user-the-name 5y agoNo. People are pushing the envelope for these algorithms constantly, as part of the various competitions in data compression, and they don't get anywhere close.
- jopsen 5y agoIt's still an amazing research result. Demonstrating a novel compression scheme with a high compression ratio is worthwhile. It might inspire something else.