14
\$\begingroup\$

"A picture is worth a thousand words"—so the old saying goes. The average word is about four characters long, so a picture conveys 4kB of information. But how much entropy, rather than information, can a picture convey?

Your task is to generate an image, exactly 4,000 bytes in size, with the highest entropy possible. You may use any language, libraries, or image format you choose, and you may output to the console or to a file so long as you upload your image here.

Scoring

Your score is the compression ratio (4000 ÷ compressed size) when your image is compressed with GNU tar version 1.28 and gzip version 1.6, using the DEFLATE algorithm and default settings — specifically, the command tar -czvf out.tar.gz image. The smallest compression ratio wins.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ tar includes metadata, including mtime, in output files by default. This affects the final compressed file size - some mtimes compress better than others. Changing the command to gzip -n image would make the output size deterministic regardless of mtime (and input file name). \$\endgroup\$
    – Nnnes
    Aug 13, 2019 at 22:34
  • 2
    \$\begingroup\$ Never mind, gzip -n image cannot produce a file larger than 4023 bytes given a 4000-byte input. It needs 10 bytes for the header, 8 for the footer, 1 for the DEFLATE block header and padding, and 4 for the DEFLATE block size; the rest are just stored as uncompressed bytes. Most files comprised of random bits are stored uncompressed, as they should be. \$\endgroup\$
    – Nnnes
    Aug 13, 2019 at 23:40
  • \$\begingroup\$ I can confirm that. Instead of compression getting worse with increasing entropy, it just flags that the data should be stored uncompressed. Deflate adds 2 bytes to the data. Gzip adds the rest. \$\endgroup\$ Aug 16, 2019 at 21:26

1 Answer 1

4
\$\begingroup\$

0.9514747859 (4204-byte output)

noise

Note: the image above is not the actual file I used, but it is the image.

Here is a hexdump of the file: https://gist.github.com/pommicket/cf2982e8ecf09a4de89d3a849526c64b

The file is in the netpbm format, and can be generated with this C code:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
    if (argc < 2) {
        fprintf(stderr, "Please pass in seed.\n");
        return EXIT_FAILURE;
    }
    srand(atoi(argv[1]));
    FILE *fp = fopen("image.pgm", "w");
    int width = 2, height = 1993;
    fprintf(fp, "P5 %d %d 255 ", width, height);
    for (int i = 0; i < width * height; i++) {
        fputc(rand() & 0xFF, fp);
    }
    fclose(fp);
    return 0;
}

The random seed must be passed into the program. After trying some seeds, I got one which produced a 4204 byte gzipped file. As Nnnes pointed out, tar will include metadata in the file, so your results might differ from mine.

netpbm isn't supported everywhere, but it works with imagemagick's convert (so just do convert image.pgm image.png to turn it into a png).

Why this image/format?

A file which consists of entirely random bytes is very hard to compress (in fact, any possible compression algorithm will do on average, no better than not compressing for random files). The content of the actual file is just P5 2 1993 followed by 3986 random bytes, which is why gzip has such a hard time compressing it.

\$\endgroup\$
4
  • \$\begingroup\$ @KrzysztofSzewczyk it’s not about the seed, it’s about the image format. Your PNGs’ headers include a lot of deterministic bytes, so they compress easily. \$\endgroup\$
    – Grimmy
    Aug 13, 2019 at 19:11
  • 2
    \$\begingroup\$ @KrzysztofSzewczyk There's potentially much more than 8 bytes of non-random data in a random PNG file. The bare minimum is to include the file signature followed by the IHDR, IDAT and IEND chunks, but most PNG generators will include a couple of optional chunks that are likely to compress pretty well -- as Grimy said -- except maybe the CRC's that can be assumed to be pretty random. \$\endgroup\$
    – Arnauld
    Aug 14, 2019 at 11:53
  • \$\begingroup\$ The file you generated has 4KB of entropy, but the image doesn't. (Even the PNG has 785 bytes!) You're filling it with 3990 random bytes, but it's only displaying 3990 random bits, so it can be reduced to this 542-byte PBM file: gist.github.com/Nnnes/7026b7ff3d55a36bdbb01c3582beb80a - Rows in PBM are padded to the end of the byte, so there are a bunch of 0 bits every 14th (though still not enough for gzip to pick up on them, as it works on the byte level). 336 x 95 works for 3990 * 8 bits. [Also see my comment on the main post - the different sizes are not a result of different seeds.] \$\endgroup\$
    – Nnnes
    Aug 15, 2019 at 0:00
  • \$\begingroup\$ @Nnnes Good point! I switched to using a pgm file. The png is now >5000 bytes. If it's not the seed that's changing the size of the output, I'm not sure what in the metadata is doing that, because the file name was the same every time... \$\endgroup\$
    – pommicket
    Aug 15, 2019 at 0:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.