New LTCB record

[Matt Mahoney]

Dmitry Shkarin broke his own record on LTCB, improving compression from .1280 to .1277 with a new dictionary for durilca'kingsize. It is also faster than the next 13 compressors. I did not test it myself because it requires 64 bit Windows and 13 GB memory.

http://mattmahoney.net/dc/text.html#1277

[ddfox]

Congratulatation Dmitry!
Nice work!

[Rugxulo]

It is designed to work only on this benchmark and not in general.

No kidding??!?!?!?!?!?!

[Matt Mahoney]

The top 3 on LTCB are all tuned to the benchmark. That's going to happen with any public benchmark and I expected it. There are 3 ways (that I know of) to benchmark, but none of them really answer the question "what is the best compressor?" Otherwise zip would be top ranked because that's what everyone uses.

1. Use private test data.
2. Use public data and add the decompresser size.
3. Use a cryptographic random data generator (like generic benchmark).

I don't like 1 because nobody else can submit or check results. It is more work for the evaluator, but maybe you can automate it like sportsman's metacompressor site. Even so, when the evaluator gets tired of it, the benchmark dies.

2 has problems like tuning, but it does eliminate tricks like BARF that compress the Calgary corpus to 1 byte, or less blatant like dictionary from world95.txt, special filter for rafale.bmp, etc. You can't compress smaller than the (unknown) Kolmogorov complexity, and it it well tested (Calgary challenge).

3 solves the problems of (1) without decompresser size, but only gives an approximate measurement. But creating truly generic data is a hard theoretical problem. The distribution is very sensitive to the choice of programming language for the random programs that generate the test data.

[Rugxulo]

The top 3 on LTCB are all tuned to the benchmark. That's going to happen with any public benchmark and I expected it.

Sorry, I think you missed the joke. I thought it was extremely obvious and redundant that a 64-bit 13 GB compressor wasn't general use.

[Matt Mahoney]

Yeah I saw the smilies. I'm waiting for someone to run a 10,000 model version of PAQ on a Jaguar XT5 with 224,000 cores and 299 TB of memory. http://www.nccs.gov/jaguar/

[Shelwien]

Cores?.. Is there a parallel paq version?
Also, what kind of models? Something like paq8k?

[Rugxulo]

Sorry, I think you missed the joke. I thought it was extremely obvious and redundant that a 64-bit 13 GB compressor wasn't general use.

Actually, I joke, but now I've seen the Black Friday ads with several computers sporting anywhere from 1 GB RAM (netbooks) to 3 GB laptops to one desktop with 8 GB, and actually most of them run 64-bit Win7, even with only 3 GB of RAM. So I guess it's not that far-fetched (if still extremely silly to my mind).

[Matt Mahoney]

Yes, in a few years it will be common for computers to have 16 GB. LTCB has no hardware limits for that reason. Anyone can submit results run on any computer.

An approach like paq8k could be made fast on a parallel computer. All of the models can be executed in parallel. They have to be mixed but that can be done using a mixer tree in O(log n) time with all mixers at the same level executed in parallel. Then the SSE and arithmetic coding are serial but the SSE can be moved down the tree like in PAQAR to be done in parallel.

For text compression there are probably better algorithms that are even more parallel. Remember that the model is doing the same thing your brain is doing when you guess what word will be next in some text. It does this with 10^11 processors each with 1 KB memory running at 300 Hz.

[m^2]

10^11 processors each with 1 KB memory running at 300 Hz.

Thanks Matt, I never looked at it this way.
I think I'll go through complexity theory again and see how it works.

[ddfox]

I can compress the compressed file to 127,377,411-->127,377,288

[Matt Mahoney]

It only counts if your decompresser is smaller than 123 bytes.

[ddfox]

It only counts if your decompresser is smaller than 123 bytes.

60K,