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 filesiz

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