> compression with bicom is completely bijective -- any file is a possible bicom output that can be decompressed, and then recompressed back to its original form.
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.
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