4 ms·
Lossless is not equivalent to bijective. Gzip is not bijective. The definition of bijective compression is that an arbitrary bytestream is valid for decompressi
by lidjfsljbn 6y ago
Lossless is not equivalent to bijective. Gzip is not bijective. The definition of bijective compression is that an arbitrary bytestream is valid for decompression.
To put it another way: because there are some output files that gzip compression can never create (whatever the input), it's a not surjective function from the set of possible inputs to the set of possible outputs. For this reason it is not bijective.
- jkhdigital 6y agoI still don’t get it... a bijection doesn’t actually compress anything, on average. If the input and output sets are the same, then the average length of the input and output is equal. Ergo, no compression on average. This is basic information theory; you can’t compress all strings with a single function.
- nullc 6y agoThat isn't true. A bijective function will map all inputs to distinct outputs and its inverse will also map all inputs to distinct outputs. They don't need to be the same length. For a toy example, I could give you a compressor which: If the input begins with a billion copies of "HurrahHackerNews!" output a one bit then the rest of the input (if there is any more input). Otherwise it outputs a zero bit, then the input (but if the input begins with a billion copies of HurrahHackerNews! except last one ends with " instead of ! it skips that last bit, so the encoding isn't redundant). The decompressor just perfectly reverses this process. This format is a bijection, and if you often have inputs that begin exactly with a billion copies of HurrahHackerNews! it will get pretty good compression. :P