Hacker News Reader

Comment by nullc | Hacker News Reader

GPT-2 is not just a dictionary, it's enormous non-linear function. This compressor gets compression levels which are unachievable with a dictionary.

Alas, its arithmetic coder isn't bijective-- so you can't just decompress encrypted input back into english.

View on HN

> GPT-2 is not just a dictionary, it's enormous non-linear function.

Dictionaries are non-linear functions.

> This compressor gets compression levels which are unachievable with a dictionary.

I don't see why this is the case, care to elaborate?

A dictionary doesn’t give a prediction about what the next word in string will be. GPT-2 does and those predictions can be used so save space.

A dictionary of n-grams does, which I think is what he is describing.

A dictionary of n-grams does not change its probabilities based on "text seen so far", so you'd need an unbounded n. In practice, n-gram dictionaries don't encode for more than very low values of n, so while yes, abstractly we can say that GPT-2 is equivalent to an n-gram dictionary with some high n, those dictionary cannot be constructed, let alone used, leaving the equivalency is purely theoretical.

GPT-2 is not a dictionary.

>GPT-2 is not a dictionary.

I was only responding to the statement that dictionary methods don't give a prediction of the next word in a string will be. I wasn't in any way saying GPT-2 is a dictionary.

GPT is way better at next-word predictions than n-grams. However, I agree with OP that the resulting compression scheme is probably not very practical all things considered.

"Alas, its arithmetic coder isn't bijective-- so you can't just decompress encrypted input back into english."

OP calls it a lossless encoder. What makes you say it's not bijective?

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/

> 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.

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.

"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.

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.

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.

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

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.

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

"[T]he transform we present is bijective, in that the inverse transformation exists for all strings."

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.

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#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.

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)

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.

Yes, you can decompress a random string. Might be garbage, but arithmetic coding won’t “fail”.

Not all random strings decompress, also termination is an explicit symbol that can only happen once, so for most random inputs it only consumes a tiny amount of the input.

Reply on news.ycombinator.com