3 ms·

Run your file through every compression algorithm (that doesn't utilize too much prior knowledge i.e. not LLMs) that you can get your hands on. After a certain

Run your file through every compression algorithm (that doesn't utilize too much prior knowledge i.e. not LLMs) that you can get your hands on. After a certain point it won't be able to get compressed further. It's a good approximation for the limit I think.

ElFitz 3y ago
I wouldn’t have thought of that. I was more interested in learning about the possible theory behind such a limit, to see if we had a way to actually know how far such optimisations can go. Basically, for any given file, what would be the absolute best we could hope for (without resorting to losing information).
- MauranKilom 3y ago
  That question makes pretty little sense without fixing some constraints like "what other files exist" and "what language are you allowed to reproduce them". In a world where every single file is exactly "abcd", it takes zero bits to represent the file - you don't need any information to know that the file contains "abcd" because all files do. In theory, the language you use to output the file could have a one-bit coding '0' for "produce the file 'there are comments on HN'" (and all other commands starting with '1...'). So in the world we live in, the smallest a file can be compressed to is 1 bit - if you just use the right language. None of these are practical in general, but the point is that Kolmogorov Complexity is not meaningful without specifying more assumptions/priors.
  - ElFitz 3y ago
    Absolutely, that is part of what I have come to understand while diving into the topic. That I first needed to answer quite a few other questions for that one to even make sense. Thank you for the examples; they are much clearer and straightforward than most of those I’ve come across.
  - guimplen 3y ago
    This is a misconception. The main result in the Kolmogorov complexity theory that there is precisely the "universal prior" that comes simply from the notion of computability.
    - Ono-Sendai 3y ago
      It's a misconception the "universal prior" is at all helpful.
      - guimplen 3y ago
        This universal prior is both theoretically useful and help conceptualize the real-world compression techniques.
- oh_sigh 3y ago
  Not to be pedantic, but for any given file the answer is 0% compression, due to the pigeonhole principle.
  - ElFitz 3y ago
    Not at all! Having basically no knowledge in that area, aside from a vague understanding of the purpose and uses of information theory, it is more than welcome! For those interested also unfamiliar with it: - https://eprint.iacr.org/2021/1333.pdf https://eprint.iacr.org/2021/1333.pdf - https://matt.might.net/articles/why-infinite-or-guaranteed-file-compression-is-impossible/ https://matt.might.net/articles/why-infinite-or-guaranteed-f...
jsenn 3y ago
This might give a decent estimate of the entropy of the file, but it is a poor approximation of the Kolmogorov complexity in general. All major compression libraries that I know of essentially work by "factoring out" statistical regularities in the input string--i.e. repeating patterns. But many strings have regularity that can't be captured statistically. For example, the sequence 1, 2, 3, 4, ... has an entropy rate of 1, because all digits and all subsequences of digits occur with equal frequency, so most modern compression libraries are going to be unable to compress it to any significant degree [1]. However, it obviously has a very compact representation as a program in your favourite language. If you want to go down a bit of a rabbit hole, this video from a researcher in this field gives an overview, as well as some proposed methods for approximating Kolmogorov Complexity in a reasonable way (even though in a technical sense approximating it with known, fixed bounds is I believe impossible): https://www.youtube.com/watch?v=HXM3BUXsY4g https://www.youtube.com/watch?v=HXM3BUXsY4g. This paper also discusses a theory that decomposes KC into a statistical part (Shannon entropy) and a "computational part": https://csc.ucdavis.edu/~cmg/compmech/pubs/CalcEmergTitlePage.htm https://csc.ucdavis.edu/~cmg/compmech/pubs/CalcEmergTitlePag.... [1]: Note that if you encode it as ASCII or even N-bit integers there will be significant redundancy in the encoding. To properly test it you'd have to encode the numbers in a packed binary encoding with no padding.
- Panzer04 3y ago
  Thus is how some video encoding algorithms ans the like sort of work, iirc - you encode interface differences under the assumption that any particular part of the screen isn't likely to change much. Encoding algorithms end up getting specialised for particular types of data because different data exhibits different patterns.

ElFitz 3y ago

I wouldn’t have thought of that. I was more interested in learning about the possible theory behind such a limit, to see if we had a way to actually know how far such optimisations can go. Basically, for any given file, what would be the absolute best we could hope for (without resorting to losing information).

MauranKilom 3y ago
That question makes pretty little sense without fixing some constraints like "what other files exist" and "what language are you allowed to reproduce them". In a world where every single file is exactly "abcd", it takes zero bits to represent the file - you don't need any information to know that the file contains "abcd" because all files do. In theory, the language you use to output the file could have a one-bit coding '0' for "produce the file 'there are comments on HN'" (and all other commands starting with '1...'). So in the world we live in, the smallest a file can be compressed to is 1 bit - if you just use the right language. None of these are practical in general, but the point is that Kolmogorov Complexity is not meaningful without specifying more assumptions/priors.
- ElFitz 3y ago
  Absolutely, that is part of what I have come to understand while diving into the topic. That I first needed to answer quite a few other questions for that one to even make sense. Thank you for the examples; they are much clearer and straightforward than most of those I’ve come across.
- guimplen 3y ago
  This is a misconception. The main result in the Kolmogorov complexity theory that there is precisely the "universal prior" that comes simply from the notion of computability.
  - Ono-Sendai 3y ago
    It's a misconception the "universal prior" is at all helpful.
    - guimplen 3y ago
      This universal prior is both theoretically useful and help conceptualize the real-world compression techniques.
oh_sigh 3y ago
Not to be pedantic, but for any given file the answer is 0% compression, due to the pigeonhole principle.
- ElFitz 3y ago
  Not at all! Having basically no knowledge in that area, aside from a vague understanding of the purpose and uses of information theory, it is more than welcome! For those interested also unfamiliar with it: - https://eprint.iacr.org/2021/1333.pdf https://eprint.iacr.org/2021/1333.pdf - https://matt.might.net/articles/why-infinite-or-guaranteed-file-compression-is-impossible/ https://matt.might.net/articles/why-infinite-or-guaranteed-f...

jsenn 3y ago

This might give a decent estimate of the entropy of the file, but it is a poor approximation of the Kolmogorov complexity in general. All major compression libraries that I know of essentially work by "factoring out" statistical regularities in the input string--i.e. repeating patterns. But many strings have regularity that can't be captured statistically. For example, the sequence 1, 2, 3, 4, ... has an entropy rate of 1, because all digits and all subsequences of digits occur with equal frequency, so most modern compression libraries are going to be unable to compress it to any significant degree [1]. However, it obviously has a very compact representation as a program in your favourite language. If you want to go down a bit of a rabbit hole, this video from a researcher in this field gives an overview, as well as some proposed methods for approximating Kolmogorov Complexity in a reasonable way (even though in a technical sense approximating it with known, fixed bounds is I believe impossible): https://www.youtube.com/watch?v=HXM3BUXsY4g https://www.youtube.com/watch?v=HXM3BUXsY4g. This paper also discusses a theory that decomposes KC into a statistical part (Shannon entropy) and a "computational part": https://csc.ucdavis.edu/~cmg/compmech/pubs/CalcEmergTitlePage.htm https://csc.ucdavis.edu/~cmg/compmech/pubs/CalcEmergTitlePag.... [1]: Note that if you encode it as ASCII or even N-bit integers there will be significant redundancy in the encoding. To properly test it you'd have to encode the numbers in a packed binary encoding with no padding.

Panzer04 3y ago
Thus is how some video encoding algorithms ans the like sort of work, iirc - you encode interface differences under the assumption that any particular part of the screen isn't likely to change much. Encoding algorithms end up getting specialised for particular types of data because different data exhibits different patterns.