3 ms·

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 in

• 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