4 ms·

What future work can we see here? Is this sort of approach really pushing the state of the art or is it just an attempt squeeze another few percent out of brotl

by phrh8 8y ago

What future work can we see here? Is this sort of approach really pushing the state of the art or is it just an attempt squeeze another few percent out of brotli at the expense of more CPU. My understanding is the main novel idea here is splitting compression into independent subproblems. Is there potential for this idea to become the basis for all new modern (lossless) codecs (e.g. redesigns of FLAC or PNG)?

coderdude 8y ago
The state of the art in data compression most often involves squeezing out a few extra percent. Entropy encoding is essentially a solved problem from a theoretical standpoint. Aside from runtime speed and so forth, the real gains come from better modeling, which is an unsolvable problem. For anyone who wants a great primer on the topic: http://mattmahoney.net/dc/dce.html http://mattmahoney.net/dc/dce.html "Compression = modeling + coding. Coding is a solved problem. Modeling is provably not solvable." I don't think splitting compression into subproblems is particularly novel. It sounds like something PAQ has been doing for quite some time and the Fairytale project seems to be somewhat similar to this one. But don't quote me! Many data compression geniuses hang out here, btw: https://encode.ru https://encode.ru If you really want to get into this topic, a good read is "Information Theory, Inference and Learning Algorithms" by David J. C. MacKay. Mr. MacKay does a superb job of explaining every facet of this topic. Edit: in my excited rambling I don't think I addressed your question. The impression that I got was that this represents a fast implementation of ANS coupled with better modeling, in a framework that makes it easier to experiment with transformations and other algorithms in the pipeline. The author stopped by, so maybe they can correct me.

4 ms·

What future work can we see here? Is this sort of approach really pushing the state of the art or is it just an attempt squeeze another few percent out of brotl

by phrh8 8y ago

coderdude 8y ago
The state of the art in data compression most often involves squeezing out a few extra percent. Entropy encoding is essentially a solved problem from a theoretical standpoint. Aside from runtime speed and so forth, the real gains come from better modeling, which is an unsolvable problem. For anyone who wants a great primer on the topic: http://mattmahoney.net/dc/dce.html http://mattmahoney.net/dc/dce.html "Compression = modeling + coding. Coding is a solved problem. Modeling is provably not solvable." I don't think splitting compression into subproblems is particularly novel. It sounds like something PAQ has been doing for quite some time and the Fairytale project seems to be somewhat similar to this one. But don't quote me! Many data compression geniuses hang out here, btw: https://encode.ru https://encode.ru If you really want to get into this topic, a good read is "Information Theory, Inference and Learning Algorithms" by David J. C. MacKay. Mr. MacKay does a superb job of explaining every facet of this topic. Edit: in my excited rambling I don't think I addressed your question. The impression that I got was that this represents a fast implementation of ANS coupled with better modeling, in a framework that makes it easier to experiment with transformations and other algorithms in the pipeline. The author stopped by, so maybe they can correct me.