how does the speed compare?

Ehhh, it's the decompressor that's specified, and there's considerable wiggle room a'la Trellis modulation in radio line coding, due to the interplay of the dictionary coder with the entropy coder. Basically, there are many moments the dictionary coder has to make non-obvious decisions about how to code a sequence, and what matters is that the whole content overall has the least entropy, not the least length when fed to the entropy coder.

For simple codings like the TLV bitstream in QR codes (the L field bit length depends on the T and the QR code size (i.e., the max bitstream length possible))[0], you can afford to solve for all possibilities via e.g. dynamic programming with some mild heuristics to terminate search branches that can't possibly code shorter due to the TL overhead.

But with an entropy coder like zstd's fst/tANS, that's not remotely as trivial. Making a choice will change the symbol/byte histogram for the entropy coder's input sequence, which, if after quantization by tANS still different, can change the length of the coded bitstream. The problem is the non-local effect on a symbol's coding size from making any individual residency coding decision.

BTW, friendly reminder that all-caps URLs will code shorter into QR codes, so the code will have larger pixels or be smaller.

[0]: there are 5 main modes (i.e., T values): ([0-9])+ coded by stuffing 3 digits into 10 bit and trailing 2/1 digits into 7/4 bits, respectively; ([0-9]|[A-Z]|[:space:]|[\$\%*\+\−\/\.,\:])+ coded by stuffing 2 characters into 11 bits; ISO-8859-1 coded by stuffing one character into 8 bits; Kanji by stuffing each into 13 bits; and a ECI mode for iirc generic Unicode codepoints. I think the other 3 code points in T are used for legacy barcode FNC1 and FNC2, as well as an end-of-content marker.

I think the compression ratio will be a bit better, but the compression and decompression time will be a bunch better.

You can turn any lossy compression scheme into a lossless scheme by encoding the error... The lossy scheme should be aiming for low error, making the error encoding progressively smaller as the lossy scheme improves.

What's harder to deal with from a measurement perspective is sematic equivalence. calling some kinds of errors zero-cost, but not having a great way to categorize what the loss of, exactly. But it's kinda what you want for really extreme compression: the content is equivalent at a high level, but may be a very different byte stream.

I tend to agree, but is that really a fatal flaw? A lossy compression scheme that gets it 90% right only has to encode the delta for the remaining 10%. Which is a big cost, sure, but the alternative is evaluating how important the thrown-away stuff is, and that evaluation is rife with subjective value judgements. There are no right answers, only differing flavors of wrong ones. It's the question of what is important to generalize over, and nobody is ever going to agree on that.

Your issue applies equally to GPT-3 (and afaik its successors): the log likelihood loss which the GPT base model was trained on is exactly the "lossless compression" length of the training set (up to trivial arithmetic-coding overhead).

The question I'd raise is why the route that got traction used more ad-hoc regularization schemes instead of the (decompressor + compressed) length from this contest and the book I linked.

> Intelligence is just as much about knowing what to throw away as what to keep.

Sure, but you can see it as two steps. Decide what doesn't matter at all, and throw it away. Then compress the rest losslessly (according to how surprising it is, basically the only way)

I think a theory of mind based on data compression is backwards, for this reason. When you have "data", you've already decided what's important. Every time you combine "A" and "B" into a set, you have already decided

1. That they are similar in some way you care about

2. That they're distinct in some way you care about (otherwise, it would be the same element!)

... and you do this every time you even add two numbers, or do anything remotely more interesting with "data". There is no "data" without making a-scientific statements about what's important, what's interesting, what's meaningful, what matters etc.

You could throw away 95% of enwiki without losing anything of value. This sounds like a joke but it would make the result worth reading which sounds like it is worth the exercise.

Not useless. That’s most of mathematics right there.

For such low-bandwidth applications, you'll usually want to do the key exchange while you have a faster connection, as well as build a dictionary of expected recipients etc.

Once you have a pre-exchanged symmetric key pair and IVs etc., encryption can be done with zero overhead, and you can choose your own trade-off between authentication security and message size. Even 4 bytes go a long way (an attacker would need to send 2^31 messages over a very bandwidth-constrained channel to impersonate you), and 8 bytes make it safe enough for practically all applications.

That way, you can keep the authentication overhead very small (on the order of a few bytes), similar to how it's done for e.g. SRTP.