Earlier quoted context omitted.
How far back?
How much does that matter? All currently supported releases at least.
Seriously?
There are places still migrating off of Java 8.
And pet servers still exist in the wild.
Bzip3: A spiritual successor to BZip2
81–90 of 181 posts
Re: Bzip3: A spiritual successor to BZip2
#82Highlight (benchmark of Perl source code): The results follow: xz -T16 -9 -k - 2'056'645'240 bytes (c=12m09s, d=4m40s) bzip2 -9 -k - 3'441'163'911 bytes (c=17m16s, d=9m22s) bzip3 -b 256 - 1'001'957'587 bytes (c=7m10s, d=4m6s? Unclear on source page) bzip3 -b 511 - 546'456'978 bytes (c=7m08s, d=4m6s? Unclear) zstd -T12 -16 - 3'076'143'660 bytes (c=6m32s, d=3m51s) edit: Adding times and compression levels
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
Hi, tool author here!
Thank you for your benchmark!
As you may be aware, different compression tools fill in different data type niches. In particular, less specialised statistical methods (bzip2, bzip3, PPMd) generally perform poorly on vaguely defined binary data due to unnatural distribution of the underlying data that at least in bzip3's case does not lend well to suffix sorting.
Conversely, Lempel-Ziv methods usually perform suboptimally on vaguely defined "textual data" due to the fact that the future stages of compression that involve entropy coding can not make good use of the information encoded by match offsets while maintaining fast decompression performance - it's a long story that I could definitely go into detail about if you'd like, but I want to keep this reply short.
All things considered, data compression is more of an art than science, trying to fit in an acceptable spot on the time to compression ratio curve. I created bzip2 as an improvement to the original algorithm, hoping that we can replace some uses of it with a more modern and worthwhile technology as of 2022. I have included benchmarks against LZMA, zstandard, etc. mostly as a formality; in reality if you were to choose a compression method it'd be very dependent on what exactly you're trying to compress, but my personal stance is that bzip3 would likely be strictly better than bzip2 in all of them.
bzip3 usually operates on bigger block sizes, up to 16 times bigger than bzip2. additionally, bzip3 supports parallel compression/decompression out of the box. for fairness, the benchmarks have been performed using single thread mode, but they aren't quite as fair towards bzip3 itself, as it uses a way bigger block size. what bzip3 aims to be is a replacement for bzip2 on modern hardware. what used to not be viable decades ago (arithmetic coding, context mixing, SAIS algorithms for BWT construction) became viable nowadays, as CPU Frequencies don't tend to change, while cache and RAM keep getting bigger and faster.
Re: Bzip3: A spiritual successor to BZip2
#83Earlier quoted context omitted.
I always understood it as working because of the predictability of a symbol/letter/token given the previous one. Sorting all the shifts of a string puts all the characters in order, then looking at the last column shows you all the _preceding_ characters. If there's any predictability there (which there often is), it's now easier to compress. It's sorta like an entropy coder in that way. I've never thought of it as b…
But shouldn't Huffman coding already detect that same predictability and compress it the same? What I don't get isn't the benefits of BWT on its own. It's why BWT should add any additional benefit if you're already doing Huffman.
Hi, tool author here.
Huffman coding is a static minimum-redundancy code. What this means is that it finds an optimal assignment of bit sequences to letters in the input alphabet (commonly US-ASCII or extensions). This however means that Huffman coding can not exploit redundancies that stem from the concrete sequence of characters. For example, you could easily predict that an `e` comes after `Th`, but Huffman coding can not know that.
Hence after applying the Burrows-Wheeler transform you need to have some sort of a higher-order transform (i.e. a transform that considers more than just individual bytes) which somehow reaps from the changed distribution of the result of the algorithm. But we will get to that in a second.
The joke here is that the Burrows-Wheeler transform is closely related to suffix trees and suffix arrays, which are often used in bioinformatics and HPC for full-text search. If you wanted to find a pattern of length `p` in a text of length `n`, if you already have a suffix tree of the original text, the search is linear in the length /of the pattern/ - i.e. O(p). The suffix tree stores all suffixes of a string in a compressed manner (i.e. it has a linear space overhead, approximately O(20n) as given by Gusfield, D. (1997). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press), so you can search for a word in it by simply traversing from the root node to an internal or leaf node by following a sequence of bytes that comprise the word.
As such, a suffix tree (and equivalently suffix array and the BWT, which is trivially computed from a suffix array) form something which can be thought of as a static PPM model. Notably real world implementations of PPM use suffix trees as a part of their main storage data structure (e.g. PPMd). What this all means is that given a suffix tree, we can very cheaply give the probability distribution for the next byte that follows a given fixed-order sequence of bytes. This is nice, because then e.g. an order-2 predictor would be able to tell that `Th` is followed by `e` once enough data has been gathered.
As you can probably guess, the more preceding bytes you know, the better will be your estimate for what is the most likely next byte. But the larger your context, the more expensive the searches and computations become due to pointer chasing in the suffix tree.
So how do we remedy this? We notice that the Burrows-Wheeler transform essentially clusters similar contexts together, meaning that a low order predictor (= faster, simpler) on BWT compresses as well as a high order predictor (= slow, complicated) on the original data, at the cost of an extra transformation. This is viable, because the Burrows-Wheeler transform can be quickly computed and there have been recent advancements in running it on the GPU. So what this means is that bzip3 uses BWT + a low order predictor with an arithmetic coder to encode the bytes, meaning that it can make use of high order statistics for compression and performs comparably at a faster speed.
Re: Bzip3: A spiritual successor to BZip2
#84Earlier quoted context omitted.
I always understood it as working because of the predictability of a symbol/letter/token given the previous one. Sorting all the shifts of a string puts all the characters in order, then looking at the last column shows you all the _preceding_ characters. If there's any predictability there (which there often is), it's now easier to compress. It's sorta like an entropy coder in that way. I've never thought of it as b…
But shouldn't Huffman coding already detect that same predictability and compress it the same? What I don't get isn't the benefits of BWT on its own. It's why BWT should add any additional benefit if you're already doing Huffman.
One way to look at data compression is splitting it into a model and an encoder. The model describes the data, while the encoder encodes (or equivalently predicts) the data according to the model. The compressed output consists of the serialized model and the encoded data. BWT is a model, while Huffman is an encoder.
Huffman takes a probability distribution and a symbol and encodes the symbol according to the distribution. If you encode all symbols independently according to the same distribution, you probably don't get very good compression.
You get a bit better results with a model that has a separate distribution for each context. If the previous symbols were X, Y, and Z, you encode the next symbol according to the distribution for context XYZ. This approach doesn't really scale, because the size of the model grows rapidly (exponentially in a naive implementation) with context length. You get better compression with an adaptive model. You start with a uniform distribution and update the available contexts and distributions after encoding each symbol. On the one hand, you don't have to store the model explicitly. But on the other hand, updating the model is very slow.
Burrows-Wheeler transform is an implicit model. It sorts the symbols according to the context that follows them, and it does that simultaneously for each context length. Because you don't have to store the model explicitly, you can effectively use longer context lengths than with a fixed explicit model. And because you don't have to update an explicit model after encoding each symbol, using the BWT is much faster than using an adaptive model.
Re: Bzip3: A spiritual successor to BZip2
#85Highlight (benchmark of Perl source code): The results follow: xz -T16 -9 -k - 2'056'645'240 bytes (c=12m09s, d=4m40s) bzip2 -9 -k - 3'441'163'911 bytes (c=17m16s, d=9m22s) bzip3 -b 256 - 1'001'957'587 bytes (c=7m10s, d=4m6s? Unclear on source page) bzip3 -b 511 - 546'456'978 bytes (c=7m08s, d=4m6s? Unclear) zstd -T12 -16 - 3'076'143'660 bytes (c=6m32s, d=3m51s) edit: Adding times and compression levels
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 bzi…
Since I only have 12 perf cores on this Mac, I tried the xz test again with 12 threads.
xz -T12 -9 -k 993376236 69.0% c=83 d=9
Re: Bzip3: A spiritual successor to BZip2
#86Earlier quoted context omitted.
How much does that matter? All currently supported releases at least.
Seriously? There are places still migrating off of Java 8. And pet servers still exist in the wild.
Seriously who cares about those who are living in the past? It is on them for not keeping up with the times.
Re: Bzip3: A spiritual successor to BZip2
#87> DO NOT COMPRESS ANY DATA WITH THIS PROGRAM UNLESS YOU ARE PREPARED TO ACCEPT THE POSSIBILITY, HOWEVER SMALL, THAT THE DATA WILL NOT BE RECOVERABLE. I know every open source project (and quite a lot of expensive proprietary ones!) come with a "btw this software might wipe your computer, if it does that's your fault lol" clause in their license but I can't imagine trying to convince anyone else that using this for an…
The author of lzip goes into some degree of excitement on the reliability and recoverability of the lzip format compared to xz. https://www.nongnu.org/lzip/xz_inadequate.html I personally back up about a terabyte each week, and I use 7-zip because it has built-in encryption, which is required because of the HR data in the backup. Thank heavens for xargs -P. I could use "openssl enc" combined with any pure compression…
> https://www.nongnu.org/lzip/xz_inadequate.html
I have replaced all my previous uses of xz with lzip ever since I read that page (via https://news.ycombinator.com/item?id=32210438), but for some reason lzip never seem to rise to the same level of fame as xz. bzip3 also wasn't benchmarked against lzip.
Re: Bzip3: A spiritual successor to BZip2
#88Earlier quoted context omitted.
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
Hi, tool author here! Thank you for your benchmark! As you may be aware, different compression tools fill in different data type niches. In particular, less specialised statistical methods (bzip2, bzip3, PPMd) generally perform poorly on vaguely defined binary data due to unnatural distribution of the underlying data that at least in bzip3's case does not lend well to suffix sorting. Conversely, Lempel-Ziv methods us…
Shouldn't a modern compression tool, targeting a high compression rate, try to switch its compression method on the fly depending on the input data?
I have no idea about compression, just a naive thought.
Re: Bzip3: A spiritual successor to BZip2
#89Highlight (benchmark of Perl source code): The results follow: xz -T16 -9 -k - 2'056'645'240 bytes (c=12m09s, d=4m40s) bzip2 -9 -k - 3'441'163'911 bytes (c=17m16s, d=9m22s) bzip3 -b 256 - 1'001'957'587 bytes (c=7m10s, d=4m6s? Unclear on source page) bzip3 -b 511 - 546'456'978 bytes (c=7m08s, d=4m6s? Unclear) zstd -T12 -16 - 3'076'143'660 bytes (c=6m32s, d=3m51s) edit: Adding times and compression levels
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
A couple other data points:
zstd --long --ultra -2: 1,062,475,298
zstd --long=windowLog --zstd=windowLog=31 --ultra -22: 1,041,203,362
Re: Bzip3: A spiritual successor to BZip2
#90> DO NOT COMPRESS ANY DATA WITH THIS PROGRAM UNLESS YOU ARE PREPARED TO ACCEPT THE POSSIBILITY, HOWEVER SMALL, THAT THE DATA WILL NOT BE RECOVERABLE. I know every open source project (and quite a lot of expensive proprietary ones!) come with a "btw this software might wipe your computer, if it does that's your fault lol" clause in their license but I can't imagine trying to convince anyone else that using this for an…
It reads to me more like: DONT USE EXPERIMENTAL COMPRESSION TOOLS FOR BACKING UP YOUR IMPORTANT DATA. USE IT FOR TRANSFERRING DATA AND CHECK HASHES.