10 ms·

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

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.