5 ms·

> The file is a mere 512 bytes, and unpacks to a 26kb file, which again unpacks to 3Mb. My brain hurts when thinking about that. How could 512 bytes be enough

> The file is a mere 512 bytes, and unpacks to a 26kb file, which again unpacks to 3Mb. My brain hurts when thinking about that. How could 512 bytes be enough to store ~3 million bytes? I know that compression is basically about finding patterns and this sequences should be very compressible.

kevinventullo 1y ago
In some sense, the program itself is a ~512 byte compression of an infinite stream of bytes.
- gylterud 1y ago
  This is the idea behind Kolmogorov complexity[0], that the complexity of a string (finite or infinite) can be measured, relative to a programming language, as the the length of shortest program which produces it. Precisely computing the Kolmogorov complexity of a given string could be very difficult, though. In general, it is uncomputable because we cannot decide if a given program will output a given string. [0]: https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity
  - suddenlybananas 1y ago
    It's also always relative to some specific programming language, it's not an intrinsic property of strings. (You can of course, convert to another programming language where it's simpler, but then you incur the (constant) cost of the transpiler from language 1 to language 2.)
    - gylterud 1y ago
      And by adding a constant to the specification of your programming language, any sequence can have complexity 1! (But of course not every sequence can have its own constant.)
gylterud 1y ago
If it was a file filled entirely with one character, the compression could simply be to write a file saying "this character copied 3 million times", which is less than 512 bytes. This is not exactly what happens here, but many compression algorithms work by recognising that certain substrings are very common, and give them a "shorter code". In this game, there are some quite long such strings, giving a good compression rate. Furthermore, because of the recursive nature, it can find such patterns again after the common substrings are replaced by shorter codes, because these codes again form patterns with repeated substrings. This goes on until there is almost just a bit of meta data and an "ur-pattern". Compression is fascinating in many ways. For instance, since there are a fixed number of files of a certain size and some bigger files are made smaller, some smaller files must be made bigger by the compression! Of course, this could be as simple as attaching a header or flag which says "I could not compress this. Here is the old file verbatim." But that is still a bit longer than the original!
seanhunter 1y ago
You can think about the compressed size of some file as approximating the amount of information (in the Shannon sense[1]) there is in the file. A perfect compression would reduce the file to exactly the size of the amount of information it contains. [1] https://arxiv.org/pdf/1612.09316 https://arxiv.org/pdf/1612.09316
deleted 1y ago
[deleted]

kevinventullo 1y ago

In some sense, the program itself is a ~512 byte compression of an infinite stream of bytes.

gylterud 1y ago
This is the idea behind Kolmogorov complexity[0], that the complexity of a string (finite or infinite) can be measured, relative to a programming language, as the the length of shortest program which produces it. Precisely computing the Kolmogorov complexity of a given string could be very difficult, though. In general, it is uncomputable because we cannot decide if a given program will output a given string. [0]: https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity
- suddenlybananas 1y ago
  It's also always relative to some specific programming language, it's not an intrinsic property of strings. (You can of course, convert to another programming language where it's simpler, but then you incur the (constant) cost of the transpiler from language 1 to language 2.)
  - gylterud 1y ago
    And by adding a constant to the specification of your programming language, any sequence can have complexity 1! (But of course not every sequence can have its own constant.)

gylterud 1y ago

If it was a file filled entirely with one character, the compression could simply be to write a file saying "this character copied 3 million times", which is less than 512 bytes. This is not exactly what happens here, but many compression algorithms work by recognising that certain substrings are very common, and give them a "shorter code". In this game, there are some quite long such strings, giving a good compression rate. Furthermore, because of the recursive nature, it can find such patterns again after the common substrings are replaced by shorter codes, because these codes again form patterns with repeated substrings. This goes on until there is almost just a bit of meta data and an "ur-pattern". Compression is fascinating in many ways. For instance, since there are a fixed number of files of a certain size and some bigger files are made smaller, some smaller files must be made bigger by the compression! Of course, this could be as simple as attaching a header or flag which says "I could not compress this. Here is the old file verbatim." But that is still a bit longer than the original!

seanhunter 1y ago

You can think about the compressed size of some file as approximating the amount of information (in the Shannon sense[1]) there is in the file. A perfect compression would reduce the file to exactly the size of the amount of information it contains. [1] https://arxiv.org/pdf/1612.09316 https://arxiv.org/pdf/1612.09316

deleted 1y ago

[deleted]