3 ms·

Data Compression Explained (2012)

193 points by mtdewcmu 4mo ago

dang 4mo ago
Related: Data Compression Explained (2011) - https://news.ycombinator.com/item?id=40631931 https://news.ycombinator.com/item?id=40631931 - June 2024 (1 comment) Data Compression Explained - https://news.ycombinator.com/item?id=5931493 https://news.ycombinator.com/item?id=5931493 - June 2013 (14 comments) Data Compression Explained by Matt Mahoney - https://news.ycombinator.com/item?id=1179242 https://news.ycombinator.com/item?id=1179242 - March 2010 (1 comment)
rurban 4mo ago
The leader boards are from the pre Fabrice Bellard days, btw. Neural network modeling helped finding better patterns in text. Also, you could say the same for the related data search problem. How to prepare data, so that it can most efficiently searched. Smallest encoding vs fastest search. Databases are mostly very, very stupid compared to more data-specific tuned algorithms. Like factor 1000 slower and bigger.
- TiredOfLife 4mo ago
  https://mattmahoney.net/dc/text.html https://mattmahoney.net/dc/text.html is the one with Bellard
blobbers 4mo ago
Matt is a great guy to explain this kind of stuff. He's very helpful.
- phrotoma 4mo ago
  Yeah this was way more interesting than I anticipated.
NooneAtAll3 4mo ago
does anyone have any sources to read about ai-based compression? I remember hearing a lot about "compression is a lot about prediction", but I don't remember reading any practical result
- Karliss 4mo ago
  It can and has been done just not very practical. Having a dozen GB language model just to squeeze out few more percent on plaintext compression which already compresses well and is tiny in comparison of images or video is not worth it outside benchmarks. Even superior traditional conpression algorithms are often not used due to insufficient software support. Multigabyte decompressor as big as rest of your OS installation is not practical to distribute or standardize. It would also take a lot of memory at runtime for decompressing thus shadowing the efficiency gains in everyday use. Only if you have huge archival scale of data it might be worth the gains. But for long term archival fragile formats which depend on huge arbitrary extra knowledge isnt a good idea. I am not quite sure if ai based compression would make it more robust by allowing to fix corruption based on context or make it worse by having single bitflip produce completely opposite but still plausible looking text. At least with traditional compression its usually obvious when corruption causes gibberish. And then you have problem of versioning, you need to have exactly the same version of dozen GB model for decompression as was used for compression. Just one of them is questionable now imagine having to store few dozen of them. Most computers have code for supporting at least half a dozen compression formats, and many of those are parametrized allowing single algorithm to handle multiple varations of the compression scheme, and then many apps bundle their own copies of compression library.
  - eru 4mo ago
    I mostly agree, however: > But for long term archival fragile formats which depend on huge arbitrary extra knowledge isnt a good idea. This doesn't need to be a problem: you can and should layer an error correcting code on top.
- sltkr 4mo ago
  compression = prediction + entropy coding was already an insight from Claude Shannon in the 1950s Since LLM are inherently token predictors, that makes using them for losless compression almost trivial. For something close to the state of the art see e.g. Fabrice Bellard (of course) ts_zip: https://bellard.org/ts_zip/ https://bellard.org/ts_zip/ I think some of the confusion comes from the fact that there is a pretty big difference between the techniques employed by compressors that optimize compression ratio at the cost of nearly everything else, like ts_zip above, and practical tools that intend to balance compression ratio with limitation on CPU speed / memory, like zstd. When optimizing for compression ratio, the prediction + entropy coding paradigm dominates. Practical tools, even modern ones like zstd, are mostly based around sliding window compression à la LZ77 (unzip/deflate), with the main selling point of more modern tools being that they scale up to larger window sizes and run really really fast. Some of these (like LZO) don't even have an entropy coding step to save time. zstd has both Huffman coding and FSE: Huffman coding is suboptimal but presumably it's an option because it's faster, and on lower compression levels it's preferable to be fast. Anyway, the bottom line is: don't get confused between the state of the art in terms of compression ratio, and practical tools. Those are quite different things.
wps 4mo ago
This is the guy who created Zpaq btw. Super interesting but niche backup/archive software.
usernametaken29 4mo ago
Isn’t the idea of AI precisely to find universal compression from arbitrary input data, at least with LLMs?
- briansm 4mo ago
  I think so, specifically lossy compression though. A modern version of the book would include an extra section in the 'Lossy compression' chapter - 'Text' (alongside Images/Video/Audio) that would discuss LLM's.
  - eru 4mo ago
    No, it's not for lossy compression only. An LLM can give you a probability distribution for the next token. You can pair that with arithmetic coding to get a lossless compression/decompression algorithm. See https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding
    - adrian_b 4mo ago
      In the way that you say, you can do lossless data compression, but then the LLM is used in a very distinct way than it is used in applications like chat or coding assistance. In the latter applications, you do queries which aim to extract information from the training data set, but which may return hallucinated content instead of correct content. If you use an LLM just to provide an estimation for the frequencies of tokens in an input data stream, and then you use the estimated frequencies to encode the input data, then you do not care about which were the tokens predicted by the LLM, because they are not used. The worst effect of any wrong predictions by the LLM is a slightly worse data compression ratio than the optimum. When it is said that LLMs do a lossy data compression, that refers to the compression from the training data set to sequences of output tokens.
      - eru 4mo ago
        > If you use an LLM just to provide an estimation for the frequencies of tokens in an input data stream, [...] Why would you use an LLM for that? The whole point is to encode contextual probabilities. So basically: given this prefix of text, what's are the probabilities for next tokens? You can use this conditional probability distribution to sample from to create plausible text, or you can use it for lossless compression. The math is very similar.
brownpoints 4mo ago
I say transformers are the best compression systems
firesteelrain 4mo ago
Matt Mahoney is one of the best when it comes to compression. He is retired now.
- mtdewcmu 4mo ago
  Really nice guy, also.
blastro 4mo ago
i was told that middle-out was best
Bnjoroge 4mo ago
I wonder what if anything has changed ever since this article. Is llm-based compression more mainstream?
- mtdewcmu 4mo ago
  Fabrice Bellard did something with neural nets and a transformer model [1] that was very successful. I suspect that LLMs wouldn't be ideal to use as compressors, because they are large, consume a lot of resources, and are constantly changing. You need the model to produce exactly the same output at encoding and decoding time, or else you get gibberish. [1] https://bellard.org/nncp/ https://bellard.org/nncp/

193 points by mtdewcmu 4mo ago

dang 4mo ago

Related: Data Compression Explained (2011) - https://news.ycombinator.com/item?id=40631931 https://news.ycombinator.com/item?id=40631931 - June 2024 (1 comment) Data Compression Explained - https://news.ycombinator.com/item?id=5931493 https://news.ycombinator.com/item?id=5931493 - June 2013 (14 comments) Data Compression Explained by Matt Mahoney - https://news.ycombinator.com/item?id=1179242 https://news.ycombinator.com/item?id=1179242 - March 2010 (1 comment)

rurban 4mo ago

The leader boards are from the pre Fabrice Bellard days, btw. Neural network modeling helped finding better patterns in text. Also, you could say the same for the related data search problem. How to prepare data, so that it can most efficiently searched. Smallest encoding vs fastest search. Databases are mostly very, very stupid compared to more data-specific tuned algorithms. Like factor 1000 slower and bigger.

TiredOfLife 4mo ago
https://mattmahoney.net/dc/text.html https://mattmahoney.net/dc/text.html is the one with Bellard

blobbers 4mo ago

Matt is a great guy to explain this kind of stuff. He's very helpful.

phrotoma 4mo ago
Yeah this was way more interesting than I anticipated.

NooneAtAll3 4mo ago

does anyone have any sources to read about ai-based compression? I remember hearing a lot about "compression is a lot about prediction", but I don't remember reading any practical result

Karliss 4mo ago
It can and has been done just not very practical. Having a dozen GB language model just to squeeze out few more percent on plaintext compression which already compresses well and is tiny in comparison of images or video is not worth it outside benchmarks. Even superior traditional conpression algorithms are often not used due to insufficient software support. Multigabyte decompressor as big as rest of your OS installation is not practical to distribute or standardize. It would also take a lot of memory at runtime for decompressing thus shadowing the efficiency gains in everyday use. Only if you have huge archival scale of data it might be worth the gains. But for long term archival fragile formats which depend on huge arbitrary extra knowledge isnt a good idea. I am not quite sure if ai based compression would make it more robust by allowing to fix corruption based on context or make it worse by having single bitflip produce completely opposite but still plausible looking text. At least with traditional compression its usually obvious when corruption causes gibberish. And then you have problem of versioning, you need to have exactly the same version of dozen GB model for decompression as was used for compression. Just one of them is questionable now imagine having to store few dozen of them. Most computers have code for supporting at least half a dozen compression formats, and many of those are parametrized allowing single algorithm to handle multiple varations of the compression scheme, and then many apps bundle their own copies of compression library.
- eru 4mo ago
  I mostly agree, however: > But for long term archival fragile formats which depend on huge arbitrary extra knowledge isnt a good idea. This doesn't need to be a problem: you can and should layer an error correcting code on top.
sltkr 4mo ago
compression = prediction + entropy coding was already an insight from Claude Shannon in the 1950s Since LLM are inherently token predictors, that makes using them for losless compression almost trivial. For something close to the state of the art see e.g. Fabrice Bellard (of course) ts_zip: https://bellard.org/ts_zip/ https://bellard.org/ts_zip/ I think some of the confusion comes from the fact that there is a pretty big difference between the techniques employed by compressors that optimize compression ratio at the cost of nearly everything else, like ts_zip above, and practical tools that intend to balance compression ratio with limitation on CPU speed / memory, like zstd. When optimizing for compression ratio, the prediction + entropy coding paradigm dominates. Practical tools, even modern ones like zstd, are mostly based around sliding window compression à la LZ77 (unzip/deflate), with the main selling point of more modern tools being that they scale up to larger window sizes and run really really fast. Some of these (like LZO) don't even have an entropy coding step to save time. zstd has both Huffman coding and FSE: Huffman coding is suboptimal but presumably it's an option because it's faster, and on lower compression levels it's preferable to be fast. Anyway, the bottom line is: don't get confused between the state of the art in terms of compression ratio, and practical tools. Those are quite different things.

wps 4mo ago

This is the guy who created Zpaq btw. Super interesting but niche backup/archive software.

usernametaken29 4mo ago

Isn’t the idea of AI precisely to find universal compression from arbitrary input data, at least with LLMs?

briansm 4mo ago
I think so, specifically lossy compression though. A modern version of the book would include an extra section in the 'Lossy compression' chapter - 'Text' (alongside Images/Video/Audio) that would discuss LLM's.
- eru 4mo ago
  No, it's not for lossy compression only. An LLM can give you a probability distribution for the next token. You can pair that with arithmetic coding to get a lossless compression/decompression algorithm. See https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding
  - adrian_b 4mo ago
    In the way that you say, you can do lossless data compression, but then the LLM is used in a very distinct way than it is used in applications like chat or coding assistance. In the latter applications, you do queries which aim to extract information from the training data set, but which may return hallucinated content instead of correct content. If you use an LLM just to provide an estimation for the frequencies of tokens in an input data stream, and then you use the estimated frequencies to encode the input data, then you do not care about which were the tokens predicted by the LLM, because they are not used. The worst effect of any wrong predictions by the LLM is a slightly worse data compression ratio than the optimum. When it is said that LLMs do a lossy data compression, that refers to the compression from the training data set to sequences of output tokens.
    - eru 4mo ago
      > If you use an LLM just to provide an estimation for the frequencies of tokens in an input data stream, [...] Why would you use an LLM for that? The whole point is to encode contextual probabilities. So basically: given this prefix of text, what's are the probabilities for next tokens? You can use this conditional probability distribution to sample from to create plausible text, or you can use it for lossless compression. The math is very similar.

brownpoints 4mo ago

I say transformers are the best compression systems

firesteelrain 4mo ago

Matt Mahoney is one of the best when it comes to compression. He is retired now.

mtdewcmu 4mo ago
Really nice guy, also.

blastro 4mo ago

i was told that middle-out was best

Bnjoroge 4mo ago

I wonder what if anything has changed ever since this article. Is llm-based compression more mainstream?

mtdewcmu 4mo ago
Fabrice Bellard did something with neural nets and a transformer model [1] that was very successful. I suspect that LLMs wouldn't be ideal to use as compressors, because they are large, consume a lot of resources, and are constantly changing. You need the model to produce exactly the same output at encoding and decoding time, or else you get gibberish. [1] https://bellard.org/nncp/ https://bellard.org/nncp/