Hacker News Reader

Comment by ElFitz | Hacker News Reader

I was curious as to wether or not there is a way to determine the actual amount of information in a given file (say, an image), and thus a theoretical limit to lossless compression, which is apparently called "Kolmogorov Complexity" [1], and this came up.

[1]: https://en.m.wikipedia.org/wiki/Kolmogorov_complexity

View on HN

If you have a probability distribution over patterns you are likely to find in a file, then the Shannon entropy gives you the best losslessly compressed filesize you can achieve.

Kolmogorov complexity is the length of the shortest computer program in some programming language that can generate your file. It gives the same number across different programming languages, up to an uncomputable and likely very large additive constant. It’s a more universal notion of compressibility than Shannon entropy, because it doesn’t depend on a probability distribution, but it is uncomputable.

The concepts are related because for any programming language, you can see it as corresponding to a probability distribution such that p(x) \propto 2^-(length of the program that generates x).

A practical way I used to grok this is to try to zip up an mp4 or a jpeg. You’ll notice the size doesn’t really change. That’s because these formats already applied entropy coding compression techniques and have compressed the information very close to the Shannon entropy limit.

JPEG XL supports reversible JPEGs transcoding in ~20% less space, which wouldn't be possible if JPEG was very close to the Shannon entropy limit.

JPEG is lossy though - I'm pretty sure these theorems only really apply to lossless compression, because if you allow lossy compression you can do all kinds of things to different t types of data (pictures being the classic case of permitting pretty lossy compression without much noticeable quality degradation)

Maybe I wasn't clear enough: JPEG -> JPEG XL -> JPEG is not lossy, you get exactly the same bits back, but the JPEG XL file is 20% smaller.

Oh, very interesting. I'll have to look into it.

There's a distinction to be made here, order-0 entropy versus higher order entropy. Order here just means how long a chain of symbols that is considered, where order-0 means just count each symbol at a time, versus eg order-1 where you consider chains of two symbols. Like the other commenter says, JPEGXL can recompress JPEGs losslessly to be around 20% smaller by exploiting higher order patterns (eg via move-to-front, lz77-ish matches, and the MANIAC tree context modeling, versus JPEG's RLE (which is "sort of beyond order-0") combined with Huffman coding (which is order-0))

Entropy doesn't make much sense for a single instance. There trivially exists a codec that will translate any particular file into any other. To get a real idea how much information is in a file you'll need some statistical model about how it may have been generated (thankfully the model doesn't have to be perfect).

You will also want to be a bit careful what assumptions you allow this model to make. In a very real sense a hash is mostly enough information to recover a file if you know it exists somewhere, as torrents and magnet links prove.

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.

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).

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.

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.

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.

It's a misconception the "universal prior" is at all helpful.

This universal prior is both theoretically useful and help conceptualize the real-world compression techniques.

Not to be pedantic, but for any given file the answer is 0% compression, due to the pigeonhole principle.

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://matt.might.net/articles/why-infinite-or-guaranteed-f...

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. 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/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.

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.

The formula for entropy and the source coding theorem discussed in the article describe exactly that.

beyond, in fact, since they're lossy formats

Reply on news.ycombinator.com