If it was bijective, any possible string of bytes could be decoded, even a random string.
Here's an example of a bijective compression system—one of the first AFAIK:
Here's an example of a bijective compression system—one of the first AFAIK:
Is that true? Couldn't it is also just have a different output domain. For example the function:
f: non-zero positive integers -> even non-zero positive integers
f(x) = 2x
> 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
I thought you were talking about a bijective function (one that defines a 1-to-1 correspondence from one set to another).
But it seems like you're talking about 'bijective compression' as requiring not only a 1-to-1 mapping between elements in the domain and range of the compression function, but also that the domain and range are the same set.
I'm not familiar with the term 'bijective compression', so perhaps this is a common thing. But it seems clear we're talking about different meanings of bijective.
That "the domain and range are the same set" is a given for compression programs which operate on strings or files. It's the bijective property which is added to that here.
So it's not that we're dealing with alternative meanings of "bijective", rather that it's understood in the work on bijective compression that compression/decompression are fundamentally functions from strings to strings.
(So compression is not conceptualized as a function from arbitrary strings to some more restricted set of "well-formed" or syntactically valid compressed strings.)
See for example: https://arxiv.org/abs/1201.3077
"[T]he transform we present is bijective, in that the inverse transformation exists for all strings."
https://en.wikipedia.org/wiki/Lossless_compression#Limitatio...
For a program to be credibly called a compression algorithm, it just has to work well in compressing a certain class of expected inputs. The issue of whether it's bijective or not doesn't really have anything to do with this.
To try to explain it one last time: a bijective decompressor makes no assumptions about file format or well-formedness of the compressed data. It will happily "decompress" any file. That's what the term means. The name might not be self-explanatory but it makes good sense, just like "homomorphic encryption".
As a mapping from files to files, a bijective compressor is surjective (as well as being injective like any other lossless codec). The consequence of this is that any file is a possible output of the compressor. And so on.
...and I'm done here.
When the goal is a codec for English, there is no fault in them not making a universally bijective codec.
(and that's with a bit of handwaving, because there is no such thing as a true universally bijective codec. The pigeonhole principle still applies)