[treffer]

This looks really good, I remember looking into BWT ad a kid. It's a true "wat" once you understand it.

And once you understand it, why does it compression so well? Because suffixes tend to have the same byte preceeding them.

Bzip2 is still highly useful because it is block based and can thus be scaled nearly linearly across cou cores (both on compress and decompress)! Especially at higher compression levels. See e.g. lbzip2.

Bzip2 is still somewhat relevant if you want to max out cores. Although it has a hard time competing with zstd.

[nathell]

Kamila Szewczyk is working on a bzip3 to improve the state-of-the-art in the domain of compressors based on Burrows-Wheeler:

https://github.com/kspalaiologos/bzip3

I’m keeping fingers crossed for the project. Especially given that the author is 19 and her best work is yet to come.

[adrian_b]

When I have first heard about bzip3, a few months ago, I have run a series of tests, comparing it with zstd and other compression programs.

In the beginning, I had been extremely impressed, because with the test archives that I happened to use bzip3 had outperformed zstd in all cases, at all possible settings for both, either in compression time at the same compressed size, or in the compressed size at the same compression time.

Nevertheless, later my initial enthusiasm had to be tempered, because I have found other test archives where the compression ratio achieved by bzip3 was more modest, falling behind other compression programs.

Therefore, the performance of bzip3 seems a little hard to predict, at least for now, but there are circumstances when it has excellent performance, with a much better compromise between compression speed and compressed size than the current alternatives.

[bonki]

Someone posted this [1] here recently which I found extremely informative. Unless I've missed something zstd outperforms bzip2 in all cases there?

[1] https://insanity.industries/post/pareto-optimal-compression/

[treffer]

There is one thing you can't with most algorithms: prallelize decompression. That's because most compression algorithms use sliding windows to remove repetitive sections.

And decompression speed also drops as compression ratio increases.

If you transfer over say a 1GBit link then transfer speed is likely the bottleneck as zstd decompression can reach >200MB/s. However if you have a 10GBit link then you are CPU bound on decompression. See e.g. decompression speed at [1].

Bzip2 is not window but block based (level 1 == 100kb blocks, 9 == 900kb blocks iirc). This means that, given enough cores, both compression and decompression can parallelize. At something like 10-20MB/s per core. So somwhere >10 cores you will start to outperform zstd.

Granted, that's a very very corner case. But one you might hit with servers. That's how I learned about it. But so far I've converged on zstd for everything. It is usually not worth the hassle to squeeze these last performance bits out.

[1] https://gregoryszorc.com/blog/2017/03/07/better-compression-...

[queuebert]

There are three kinds of people in my experience:

1. bzip2 -1

2. bzip2 -9

3. What's bzip2?

A huge amount of time is spent optimizing for #3. Maybe instead we should offer descriptive commands that convey the goals. Say, "squash", "speedup", and "deflate", or some such.

[Retr0id]

I still struggle to get my head around BWT. I understand what it does conceptually and why it helps, and I can read code that implements it, but I don't fully get it - there's a mental disconnect for me somewhere. Mainly, I can't convince myself that computing the inverse transform is possible.

It's one of those algorithms that I can say for sure I'd never have been able to come up with on my own.

[jgbyrne]

I think it really helps to stop thinking about the string as a linear sequence with a beginning and end, and instead consider an unbroken loop of characters. Literally imagine the string written into a circle like the letters on an Enigma rotor.

Then you can consider the construction of all the substrings of length 2, length 3, and so on. You may also wish to consider the same induction, but working backwards from its conclusion. Start by considering the set of n length substrings, then the n-1 length substrings, etc.

Either way, your objective should be to convince yourself that you can reconstruct the whole ring from the BWT. At this point it is not hard to make the final leap to understand how it can be applied to regular strings.

[queuebert]

It's one of those things you saturate your brain with for a few days, then put it down, and two weeks later in the shower you figure it out.

[upofadown]

Being block based means that recovery from file damage is easy. Bzip2 ships with such a recovery utility.