Large Text Compression Benchmark

http://www.mattmahoney.net/dc/text.html

by redeux • 2 years ago

97 55 2 years ago

hyperpape• 2 years ago

It's worth noting that the benchmark has not been updated as frequently for the past several years, and some versions of compressors are quite far behind the current implementations (http://www.mattmahoney.net/dc/text.html#history).

The one instance I double-checked (zstd) I don't recall it making a massive difference, but it did make a difference (iirc, the current version was slightly smaller than what was listed in the benchmark).

pella• 2 years ago

agree,

- in the benchmark "zstd 0.6.0" ( Apr 13, 2016 )

- vs. latest zstd v1.5.6 ( Mar 30, 2024 https://github.com/facebook/zstd/releases )

londons_explore4• 2 years ago

Only really worth updating if the results are meaningfully different though.

Since zstd's format is fixed, I doubt there will be massive changes in compression ratio.

shaicoleman• 2 years ago

- zstd v0.6.0 -22 --ultra: 215,674,670 bytes

- zstd v1.5.6 -22 --ultra: 213,893,168 bytes (~0.826% smaller)

pmayrgundter• 2 years ago

The very notable thing here is that the best method uses a Transformer, and no other entry does

wmf2• 2 years ago

Text compression and text generation are both based on modeling so the best approach to text modeling works for both.

sfink4• 2 years ago

Not if part of your definition of "best" includes codebook/model size. The best text generator will use a massive model. That won't help compression beyond a certain point, since the cost of lookup indexes grows with the size of the model. "Monkey #384714...872 typewriter output" doesn't help when the monkey number is longer than the input.

londons_explore4• 2 years ago

Transformers run well on GPU's or other hardware accelerators. This benchmark doesn't allow GPU's.

That makes it more of a "can I use unsuitable hardware to get the job done fast and accurately enough" challenge, rather than a pure math puzzle of how to encode data with fewer bytes.

I suspect that's why there is only 1 Transformer entry, and to me raises the question whether the rules should be updated to allow GPU's now they are fairly commonplace.

HybridCurve• 2 years ago

I think it might be a moot point since the transformer run times scale very poorly and the algorithm has a symmetric run time.

pama• 2 years ago

It would be nice to also have a competition of this type where within ressonable limits the size of the compressor does not matter and the material to be compressed is hidden and varied over time. For example up to 10GB compressor size and the dataset is a different random chunk of fineweb every week.

stephantul• 2 years ago

That’s an interesting idea. I wonder whether it would actually lead to radically different solutions, bit with bigger codebooks.

nick238• 2 years ago

Double your compression ratio for the low, low price of 100,000x slower decompression (zstd: 215GB, 2.2 ns/byte vs. nncp: 106GB, 230 µs/byte)!

The neural network architectures are technically impressive, but unless there's some standard compression dictionary that works for everything (so the training/compression costs amortize down to nil), and silicon architecture dramatically changes to compute-on-memory, I don't know if this would ever take off. Lossy compression would probably provide huge advantages, but then you need to be domain specific, and can't slap it on anything.

lxgr2• 2 years ago

One interesting application could be instant messaging over extremely bandwidth constrained paths. I wouldn’t be surprised if Apple were doing something like this for their satellite-based iMessage implementation.

Of course it could also just be a very large “classical” shared dictionary (zstd and brotli can work in that mode, for example).

londons_explore4• 2 years ago

Unfortunately, while you want to have encryption on your messages, the required encryption signature eclipses the message size.

Without signing the messages (and just using a stream cipher), you could do it, but an adversary can send garbage pretending to be you, which I don't think is acceptable in the modern world.

Also, the message headers (message length, from, to) also start to dominate and compressing them is hard (usually depending on various hardware tricks like differing CDMA keys).

jeffbee• 2 years ago

It does seem as though the training cost of these models ought to be included in their times, because the compressors are useless for any purpose other than compressing English Wikipedia.

gwern• 2 years ago

In these cases, the models are so small, and have to run on very limited CPU, that the training time is going to be fairly negligible. The top-listed program, nncp, is just 0.06b parameters! https://bellard.org/nncp/nncp_v2.pdf#page=4

gliptic• 2 years ago

The training cost is included because these NN compressors are running the training while they are compressing. They are general compressors, although the specific variants submitted here may be tuned a little to Wikipedia (e.g. the pre-processors).

Xcelerate4• 2 years ago

unless there's some standard compression dictionary that works for everything

There is, at least for anything worth compressing. It’s called the halting sequence. And while it exists, it’s also uncomputable unfortunately haha.

Vecr2• 2 years ago

Apparently there's ways of getting the first few binary digits, but it's useless at that length.

abecedarius2• 2 years ago

The point of the contest was not compression tech for communication and storage. It was a belief that minimizing log loss on large corpora (i.e. message length) was key to AI progress. That should remind you of some pretty hot more-recent developments.

Here was someone else with a similar pov in the 2000s: https://danburfoot.net/research.html

optimalsolver• 2 years ago

The issue with this paradigm (see also: Hutter Prize) was its insistence on lossless compression.

Intelligence is just as much about knowing what to throw away as what to keep. Any nontrivial cognitive system operating in a nontrivial physical environment will necessarily have a lossy model of the world it's embedded in.

Also of interest, compressionism, a theory of mind based on data compression:

https://ceur-ws.org/Vol-1419/paper0045.pdf

GaggiX• 2 years ago

Read: https://opus-codec.org/demo/opus-1.5/

londons_explore4• 2 years ago

Imagine if we didn't have dedicated hardware for say caching - every CPU instruction or bit of data has to be read from SSD every use.

We'd see a 100,000x slowdown I expect.

But dedicated hardware (RAM, various cache levels) solved this.

We could do the same for neural net compression if we needed to. But the question is do enough people care enough about a 2x data size reduction?

wmf2• 2 years ago

Dedicated hardware isn't magic because there's an intrinsic cost that cannot be reduced. In the case of neural nets you have to store the weights somewhere and you have to perform the multiplications.

geysersam• 2 years ago

Depends on the application! For long term storage of rarely accessed text it might make sense

ezekiel68• 2 years ago

This is a good point, and yet -- as high as position 24 (out of 208) in the list, we have "bsc-m03 0.4.0" at only ~160ns per byte compressed (compared with most above it being two or three orders of magnitude slower). Below position 24, there's one in the 20s of ns per byte. Looks like the cost was in the size of the compression program. Not sure if there was any "cheating" going on, hunting for benchmark scores with these two famous test bodies of text.

By comparison, the top contender clocks in at ~240,000 ns per byte (making your point).

wqweto• 2 years ago

We use bsc and nanozip for archiving DB backups (usually 1-100GB files) and have not found anything remotely close to these as CPU usage vs compression ratio.

    c:> bsc.exe e "%~1" "%~1.bsc" -b1000 -m4e1t -M4H20

This uses 3GB of RAM and compresses w/ about 300MB/s but is slow on decompression while

    c:> nz.exe a -cd -p2 -m1024m "%~1.nz" "%~1"

uses about 1GB of RAM and compresses w/ about 250MB/s to worse compression ratios but is much faster than bsc on decompression.

Both of these smash zstd and 7-zip on compression and speed -- something like 2x better and 10x faster.

sfink4• 2 years ago

I'd kind of like to see some sample LLM entries in the list (as in, at the bottom of the list). Not because they'd ever be competitive, but because it would underscore how they burn massive amounts of space for the model with little concern for how much of it is "necessary" for predicting text.

(I'm not sure how you would optimally use an LLM for a lossless compression task. I guess you could convert the input to a stream of single-bit "yes, it guessed right" tokens and multi-bit "no, the actual token is X" tokens, and then compress that stream with a more traditional entropy encoder? That way the LLM decompressor would always be working off a valid prefix. But there are probably more clever ways.)

Sesse__• 2 years ago

I'm not sure how you would optimally use an LLM for a lossless compression task.

You have the model output probabilities for each token, and then use arithmetic encoding using that model. (This uses optimally few bits per token, under the assumption that your model is right.) This is how all the winning models work, AFAIK, except they frequently work per-bit instead of per-token.

sfink4• 2 years ago

Oh duh, that makes a lot more sense. Thanks!

jonas21• 2 years ago

The top entry is based on a Transformer architecture. It's basically an LLM, but trained on the input instead.

stjo• 2 years ago

The current best solution is written by Fabrice Bellard, probably more famous for his other works like FFMPEG, QEMU and TCC - https://bellard.org/. Check him, pretty much everything coming from him is pure gold.

TacticalCoder• 2 years ago

When people say there are no 10x programmer, I name Fabrice Bellard. Him being a 100x programmer invalidates the logic of those trying to explain there aren't 10x programmers.

Large Text Compression Benchmark

Related Stories