Bzip3: A better and stronger spiritual successor to BZip2

Thank you for the reference. I learned something new today. That algorithm is wild. If you had shown me the transform and asked if it had an inverse, I would have said of course it doesn't, it's too weird.

The Burroughs-Wheeler transform has been described as a unique algorithm idea in that there are no non-trivial variations or related algorithms, unlike more conventional compression algorithms, which can be tweaked and improved in so many ways. There is no general compression theory in which BWT could be described as a special case.

It looks to me that the above still holds: Bzip2 and Bzip3 are simply combining more conventional compression algorithms with the BWT, which itself is still the same old transform. Bzip2 does Huffman coding after BWT, and Bzip3 does arithmetic coding.

I remember the lecturer commenting on what sort of sick and twisted mind could come up with such a ridiculous convoluted notion when I was taught it at university.

Did a test on a 1.3G text file (output of `find -f -printf ...`); Macbook Pro M3 Max 64GB. All timings are "real" seconds from bash's builtin `time`.

    files.txt         1439563776
    bzip2 -9 -k       1026805779 71.3% c=67 d=53
    zstd --long -19   1002759868 69.7% c=357 d=9
    xz -T16 -9 -k      993376236 69.0% c=93 d=9
    zstd -T12 -16      989246823 68.7% c=14 d=9
    bzip3 -b 256       975153650 67.7% c=174 d=187
    bzip3 -b 256 -j12  975153650 67.7% c=46 d=189
    bzip3 -b 511       974113769 67.6% c=172 d=187
    bzip3 -b 511 -j12  974113769 67.6% c=77s d=186

(edited to add 12 thread runs of bzip3 and remove superfluous filenames)

My standard test is compressing a "dd" disc image of a Linux install (I use these for work), with unused blocks being zeroed. Results:

    Uncompressed:      7,516,192,768
    zstd:              1,100,323,366
    bzip3 -b 511 -j 4: 1,115,125,019

To make your comment more useful you’ll want to include compression and decompression time.

Using the results from the readme, seems like bzip3 performs competitively with zstd on both counts.

A 4x improvement over lzma is an extraordinary claim. I see the author has also given a result after applying lrzip (which removes long-range redundancies in large files), and the difference isn’t so great (but bzip3 still wins). Does the amazing result without lrzip mean bzip3 is somehow managing to exploit some of that long-range redundancy natively?

I’d be astonished if such a 4x result generalized to tarballs that aren’t mostly duplicated files.

In Linux source benchmark results are interestingly more equal, LZMA still holding up well.

What makes Perl source benchmark special? Deduplication?

Why -T12 for zstd and T16 for xz? How many threads is bzip3 using?

...using zstd level 16, when zstd goes up to 22. And without turning on zstd's long-range mode.

I had bzip2 eat some files some years back and ended up loosing them. I don't trust bzip2 for backup files and I wouldn't trust bzip3 either as a result.

Simple enough to be safe, at the cost of performance: uncompress and compare to the original.

A shell script to run a checksum on the original file, compress, uncompress, and verify output integrity should be trivial.

Honestly I think this may be part of why compression in flight has been a growth area in compression lately. If your transport encoding becomes garbled people notice immediately. If you manage to serve a few billion compressed requests without any incident reports then maybe you can trust it for data at rest.

I mean, hosting downloads that have been compressed with this seems fine. I have the original, I just want a smaller version for those downloading.

zstd is faster and provides better compression than gzip at every point on the curve. There is no reason to use gzip these days other than backwards compatibility.

Same here. Storage is not that expensive so I do NOT care to squize every byte out of archive. Also, im more into retro, so portability and memory usage is more importand for me :)

what do you mean??

usually this signifies the year some article was finalized and published.

and this is a GitHub repo with recent commits so this is not correct here.

this is the way.

If they have to be incompatible then it's better to not conceal that. Generalized file formats require you to implement more stuff to support them, and we can't tell the format by looking at the file name.

Yeah I'm sick of this. Did you know you can't even use ext2/3/4 together on the same partition? What a mess.

The format gets a new major version precisely because it is incompatible.