7 ms·

So the one thing this article doesn't explicitly justify is whether the ten-byte zlib string is truly the shortest possible. You could imagine that it might be

So the one thing this article doesn't explicitly justify is whether the ten-byte zlib string is truly the shortest possible. You could imagine that it might be possible to hand-craft a DEFLATE block which is only three bytes instead of four, and yet still decompresses to at least two bytes (the minimum decompressed size of a PNG scanline). But by exhaustive search of all DEFLATE blocks that are one to three bytes in length, I can confirm the article is correct. All of them decompress to (at most) one byte of data. Which isn't a surprising result, but I wasn't actually sure of it before trying it out.

nayuki 3y ago
> this article doesn't explicitly justify is whether the ten-byte zlib string is truly the shortest possible I know the DEFLATE standard intimately and implemented a decoder and encoder (open source on my website/GitHub). We know that the smallest image requires 2 bytes - 1 for the row filter and 1 for the pixel(s). For simplicitly, we'll assume the data is (hex) 00 00. A DEFLATE compressed stream must have at least one block. There are three choices for each block's type - uncompressed, fixed Huffman code, and custom Huffman code. Uncompressed requires 1 byte for {type (2 bits), finality (1 bit), padding (5 bits)} and 4 bytes for the length. So that uses 5 bytes already. Using a fixed Huffman code block lets us encode those 2 bytes as 4 bytes. Using a custom Huffman code requires many, many bytes just to specify the Huffman table. Hence, the OP article's approach is justified.