Lossless Compression of English Short Messages | Hacker News Reader

Lossless Compression of English Short Messages

bellard.org

53 pointstosh61 comments

Just to give a comparisson, this website can compress to about 15% size, the current state of the art compressing English text (for a large chunk of wikipedia) is about the same http://prize.hutter1.net/ (15%).

The hutter prize has the advantage it gets more input, but the disadvantage that you must include the uncompression program (GPT2 is huge, so you wouldn't want to include it).

It's closer to 11% with the large model. I assume it would be the hutter prize leader if the prizes' challenge were large enough to amortize the model.

The entire of wikipedia's English text is only about 15GB, and GPT-2 is 5GB -- so it couldn't "win". Also, other techniques might get better as size increases.

Even worse, the Hutter challenge is based on just a 1GB fragment of (one particular snapshot of) English Wikipedia. Further highlighting what has been said elsewhere in this thread, that as far as compression goes this is basically just a variation on compression-via-giant-dictionary

Thus the "if the prizes' challenge were large enough". :)

I'd bet that a shallow transformer that was distilled on gpt2, possibly with quantized weights, would easily win. GPT2 isn't optimized for size at all, but there are tons of ways to do so.

Also the compression algorithm seems to be too computationally intensive for poor server to be hammered by Hacker News crowd.

> The compression is achieved by using the probability of the next word computed by the GPT-2 language model released by OpenAI.

Does this mean that as the model evolves (I assume it's not static) there could be a chance of decompressing a blob of text and having it say something different to the original?

It is static.

Yes. Neural compression requires a combination of a model and a compressed message.

In the future, my guess is that (some) compression protocols may end up pretty static, and mainly consist of a simple message protocol and a way to check that you've got the correct version of the model for the messages you want to decompress.

The trained model parameters are effectively the coding dictionary. Changing the parameters is like using Huffman compression but sending a different Huffman tree along with the compressed text—of course it will decompress to something different.

> I assume it's not static

Why? It is static.

Because I naively assumed the strength of an AI model would mean it would evolve to best match/understand your specific input (ala classical custom dictionaries or even just personalised models ala swiftkey) but I've obviously entirely misunderstood what's going on :\

That would require distributing the trained AI model weights with your compressed text, entirely defeating the space gains for all but extremely large passages of text.

Sure; this would be the equivalent of a "lossy" compression algorithm which encodes the result in terms of a question using semantics related to the respondent's knowledge to produce a specific response.

Anyone who has been through elementary school should understand this is the basic objective of a "short answer" question. Also "Jeopardy" is a fair example of this.

I'm disappointed he isn't releasing the source for these or LibNC. We definitely need non-academic, non-Python machine learning implementations. Anyone know what's up with that?

TensorFlow and PyTorch fit the bill, their underlying implementations are C++/CUDA/hand-optimized kernels and the APIs are all reachable without Python. They're kind of monsters to deal with in terms of scale, speed of change, weird build systems in the case of TF, but the code is there.

Oh definitely true. And they have done a killer job of building out all the bells and whistles and making it all quite fast.

But as someone interested in the guts, or understanding how to implement new types of systems, it can be quite overwhelming!

> I'm disappointed he isn't releasing the source for these or LibNC.

Arithmetic coding with LM conditioned probability has been done before and it's not a particularly complex idea to implement, I don't think it is critical that the code be released.

> We definitely need non-academic, non-Python machine learning implementations

There are two things here: training and serving/inference. We already have non-Python implementations for the latter and I don't think we're in "definite" need of the former.

Any reason this is based on GPT-2 instead of GPT-3? (Given that the world's been going nuts over 3, I'd imagine its probabilistic model is significantly better)

Probably because there’s no way to get access to or run GPT-3 unless you’re super well-connected and lucky, to be allowed to pay OpenAI for the privilege? GPT-3 is exciting in that it shows what’s possible if we push the transformer architecture farther, but it’s not really practical for much when it’s so walled off like it currently is

Previously posted as https://news.ycombinator.com/item?id=23618465

This is just compression with a monster dictionary. It would be faster to just use a giant word and phrase file as such.

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.

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

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.

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.

"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

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.

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.

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.

> This is just compression with a monster dictionary.

Are there any compression methods based on this? E.g. a browser or OS that ships with huge lists of common words and sentence fragments?

Huffman coding [1] and all derived algorithms do. They find the most common "words" and assign them shorter codes.

Language models, among which GPT-2, do essentially the same: they learn what is likely to appear in the text, albeit in a much more elaborated way.

[1] https://en.wikipedia.org/wiki/Huffman_coding

Yep, but you have to send the created dictionary to the client. I'm asking if there's compression setups that rely on the client already having a massive dictionary downloaded that's reused to decompress downloads from different sources.

Brotli!

A few months ago I was looking for strings in random binaries and was very confused when I found that my Node.js binary came with tons of fragments of English and HTML. I looked through the Node.js source on GitHub and was horrified when I didn't see any of the text, so I compiled it from scratch and breathed a sigh of relief when my new binary included the text fragments.

Turns out Brotli was included as a dependency, and it ships with a list of common fragments that are frequent enough that they justify hardcoding.

> Turns out Brotli was included as a dependency, and it ships with a list of common fragments that are frequent enough that they justify hardcoding.

How big? I know from coding word games that typical English word dictionaries only take up around 3MB example.

I think about 120 KB: https://github.com/google/brotli/blob/ee2a5e1540cbd6ef883a89...

Small sample:

    three-dimensionalChurch of Englandof North Carolinasquare kilometres.addEventListenerdistinct from thecommonly known asPhonetic Alphabetdeclared that thecontrolled by theBenjamin Franklinrole-playing gamethe University ofin Western Europepersonal computerProject Gutenbergregardless of thehas been proposedtogether with the></li><li class="in some countriesmin.js"></script>of the populationofficial language<img src="images/identified by thenatural resourcesclassification ofcan be consideredquantum mechanicsNevertheless, themillion years ago</body>                                           Ελληνικά                                              take advantage ofand, according toattributed to theMicrosoft Windowsthe first centuryunder the controldiv class="headershortly after thenotable exceptiontens of thousandsseveral differentaround the world.reaching militaryisolated from theopposition to thethe Old TestamentAfrican Americansinserted into theseparate from themetropolitan areamakes it possibleacknowledged thatarguably the mosttype="text/css">                         the InternationalAccording to the pe="text/css" />    coincide with thetwo-thirds of theDuring this time,during the periodannounced that hethe internationaland more recentlybelieved that theconsciousness andformerly known assurrounded by thefirst appeared inoccasionally usedposition:absolute;" target="_blank" position:relative;text-align:center;jax/libs/jquery/1.background-color:#type="application/anguage" content="<meta http-equiv="Privacy Policy</a>e("%3Cscript src='" target="_blank">On the other hand,.jpg|thumb|right|2</div><div class="<div style="float:nineteenth century</body>      </html>                                               <img src="http://s;text-align:centerfont-weight: bold; According to the difference between" frameborder="0" " style="position:link href="http://html4/loose.dtd"> during this period</td></tr></table>closely related tofor the first time;font-weight:bold;input type="text" <span style="font-onreadystatechange    <div class="cleardocument.location. For example, the a wide variety of <!DOCTYPE html>

No it isn't. The encoding is conditional on all previously generated characters in the context window.

What would the size be of the equivalent dictionary to GPT-2?

The training data is around 40GiB: https://d4mucfpksywv.cloudfront.net/better-language-models/l...

Consider the compression ratio for such text, and you need 2-word / 3-word to 1000-word dictionary, and at 1000-word length, it will be very sparse. I would guess an accelerated structure for such lookup would take around 60GiB. It would require quite a bit of engineering to get it right otherwise can easily blow-up pass that.

I've done a bit of dictionary compression if anyone has a use for it.

https://pastebin.com/CS6JrKQt

https://robots-everywhere.com/re_wiki/pmwiki.php?n=Main.Word...

For texts sent in English, it squishes to about 50%.

...which is not exactly great, considering that English text has about 1 bit of information per character (i.e. byte) and should allow compression down to about 12% of the original.

Reply on news.ycombinator.com