6 ms·

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

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: http://www3.sympatico.ca/mt0000/bicom/ http://www3.sympatico.ca/mt0000/bicom/

nicoburns 6y ago
> If it was bijective, any possible string of bytes could be decoded 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 is bijective.
- snakeboy 6y ago
  I believe here "bijective" is being used with the implicit assumption that we're talking about the same finite sets, "byte-strings up to a fixed length". From the link on BiCom: > 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.
  - nicoburns 6y ago
    "any possible string of bytes could be decoded" still doesn't seem like the right criteria though. Gzipping is lossless/bijective, but an arbitrary byte stream won't necessarily be a valid gzip archive.
    - lidjfsljbn 6y ago
      Lossless is not equivalent to bijective. Gzip is not bijective. The definition of bijective compression is that an arbitrary bytestream is valid for decompression. 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.
      - jkhdigital 6y ago
        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 input and output is equal. Ergo, no compression on average. This is basic information theory; you can’t compress all strings with a single function.
        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
TheRealPomax 6y ago
Yeah but the claim is "Alas, its arithmetic coder isn't bijective-- so you can't just decompress encrypted input back into english." which is an odd thing to say: this can decompress anything that it compressed. 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)
- jkhdigital 6y ago
  Exactly, there are twice as many strings of length n+1 as there are strings of length n, for all n. You can’t compress everything, this is basic information theory.
rahimnathwani 6y ago
From the other replies below, it seems like we may be talking about two different two different senses of bijective: 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.
- gkbdibfj 6y ago
  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.

nicoburns 6y ago

> If it was bijective, any possible string of bytes could be decoded 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 is bijective.

snakeboy 6y ago
I believe here "bijective" is being used with the implicit assumption that we're talking about the same finite sets, "byte-strings up to a fixed length". From the link on BiCom: > 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.
- nicoburns 6y ago
  "any possible string of bytes could be decoded" still doesn't seem like the right criteria though. Gzipping is lossless/bijective, but an arbitrary byte stream won't necessarily be a valid gzip archive.
  - lidjfsljbn 6y ago
    Lossless is not equivalent to bijective. Gzip is not bijective. The definition of bijective compression is that an arbitrary bytestream is valid for decompression. 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.
    - jkhdigital 6y ago
      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 input and output is equal. Ergo, no compression on average. This is basic information theory; you can’t compress all strings with a single function.
      - 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

TheRealPomax 6y ago

Yeah but the claim is "Alas, its arithmetic coder isn't bijective-- so you can't just decompress encrypted input back into english." which is an odd thing to say: this can decompress anything that it compressed. 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)

jkhdigital 6y ago
Exactly, there are twice as many strings of length n+1 as there are strings of length n, for all n. You can’t compress everything, this is basic information theory.

rahimnathwani 6y ago

From the other replies below, it seems like we may be talking about two different two different senses of bijective: 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.

gkbdibfj 6y ago
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.