4 ms·

I believe here "bijective" is being used with the implicit assumption that we're talking about the same finite sets, "byte-strings up to a fixed length". From

• nicoburns 6y ago
  "any possible string of bytes could be decoded" still doesn't seem like the right criteria though. Gzipping is lossless/bijective, but an arbitrary byte stream won't necessarily be a valid gzip archive.
  • 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 ago
      I 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 ago
        That 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