Kolmogorov complexity and data compression revisited

Question

The question of the relationship between Kolmogorov complexity and data compression is rather difficult. However, at the heuristic level, the complexity of an object and the rate of its compression by known algorithms are related.
I used the built-in function Compress[] of Mathematica to estimate the compression ratio of various data reducing to a character string.
Not for the entire string, but rather gradually, observing how the compression ratio changes with the growth of data volume.

Here's what happened with: Pi digits, some text, Thue-Morse sequence, differences between primes and built-in RNG:

I believe that a significant estimate of data complexity isn't just degree of compression of a whole data, but the parameters of changing it with increasing data length.

But to get these parameters (by fitting eg), we need to know what is the hypothetical shape of the curve?
Power, exponential, linear-fractional or it's combination?

We see that the law is there, but what is the form?

Answer 1

There is no one answer for the shape of the curve. It depends on the data you are trying to compress.

• For the string 00000..., with a sufficiently good compression algorithm, we can expect the compression function to behave asymptotically like $f(x) \approx c/n$ for large enough $n$, when compressing the $n$-length prefix of this string, where $c$ is some constant.

• For pi, with a sufficiently good compression algorithm, we can expect the compression function to behave like asymptotically like $f(x) \approx c$ for large enough $n$, when compressing the $n$-length prefix of this string, where $c$ is some constant.

• For other strings, there might be some other function for the compression ratio, depending on the specific string you are compressing.

The relationship between Kolmogorov complexity and data compression is quite simple. The Kolmogorov complexity of a string $x$ is at most $\text{len}(C(x)) + \text{len}(D)$, i.e., at most the length of the compressed version of $x$ plus the length of the decompression algorithm. This upper bound is true for every lossless compression algorithm.