3 ms·

Googling the term will confirm that I didn't just invent the notion of bijective compression. That "the domain and range are the same set" is a given for compr

Googling the term will confirm that I didn't just invent the notion of bijective compression. 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 https://arxiv.org/abs/1201.3077 "[T]he transform we present is bijective, in that the inverse transformation exists for all strings."

jkhdigital 6y ago
So... are we using the term “compression” loosely here? Because a bijective function (domain = range) over strings has an average compression ratio of 0. There are significantly fewer short strings than long strings, and for every long input that produces a short output there is a short input that produces a long output.
- fubfubdjng 6y ago
  We're using the term compression in its usual CS meaning. As you say, it's well known that a compression algorithm can't compress every input. https://en.wikipedia.org/wiki/Lossless_compression#Limitations 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.

jkhdigital 6y ago

So... are we using the term “compression” loosely here? Because a bijective function (domain = range) over strings has an average compression ratio of 0. There are significantly fewer short strings than long strings, and for every long input that produces a short output there is a short input that produces a long output.

fubfubdjng 6y ago
We're using the term compression in its usual CS meaning. As you say, it's well known that a compression algorithm can't compress every input. https://en.wikipedia.org/wiki/Lossless_compression#Limitations 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.