Comments URL: https://news.ycombinator.com/item?id=49549778

Points: 88

# Comments: 11

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.

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.

Regarding your first remark: high ratio data compression has its time and place, and I personally understand that to many people it is not very desirable. In a lot of scenarios something as plain and simple as LZ4 generally suffices.

On the other hand, there is an unofficial (= unsupported) port of bzip3 to older (386+) machines that run MS-DOS6.22. I have prepared it for a retrocomputing meeting in Ontario that I attended a while back. Let me know what you think :).

https://github.com/kspalaiologos/dev-urandom/blob/main/dos/B...

Almost every single open source compression tool contains a clause like this. For example, the one in the README that you see has been directly lifted from the bzip2 README. Almost all open source projects come with such a no-warranty scheme. 7-Zip, zstandard, xz-utils, etc; as exemplified by a quote from the license text of the MIT license:

> THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

If you were willing to sign a commercial support contract with me on terms that we negotiated, I would be willing to provide you warranty.

If you were not aware, this is essentially the business model of WinRAR. The reason why tools like 7-Zip are not used by the public sector or companies (at least here) is that they provide no warranty in case of data loss. However, if you actually buy WinRAR, then you can hold them liable for damage to your archives. The "infinite 40 day trial" of WinRAR does not entitle you to compensation for damages and thus corporate entities and public entities have to buy WinRAR licenses. WinRAR has never cared about personal customers.

In general, having to cope with mild reliability of software is what you have to live with - you already get more than you paid for. Not to say that my tool is unreliable - I put a lot of effort into it, but it would put you in bad light to complain about something that you generously received for free :).

As for the compression: probably an artifact of a bigger block size and a closer-to-optimal entropy coding stage in bzip3 (simple model + binary arithmetic coding; fast suffix sorting due to research of Ilya Grebnov) vs bzip2's suboptimal implementation of what could have been Package-Merge that currently assigns excessively long Huffman codes (as I discovered while doing research for my data compression book); also probably the RLEs everywhere that Seward considers a mistake, small BWT blocks, etc. You could try the tool https://pastebin.com/6DUKs4q9, which eliminates the redundancy associated with the Malbolge encoding (which bzip3 kind of catches on without any preprocessing, while bzip2 not entirely) and drastically improves performance of all other compressors:

    % ./a d blc.n
    % bzip3 -vfb50 blc.n
      blc.n:  48175489 -> 647179 bytes, 1.34%, 0.11 bpb
    % bzip3 -vfb50 blc.mb
      blc.mb: 48175489 -> 1025582 bytes, 2.13%, 0.17 bpb

I also don't see robust error handling in your code, which usually costs lines of code (especially in C) too.

The difference in delta technique is certainly not negligible, as my code still uses Colin Percival's algorithm, while you seem to have settled on something else. It's also important to point out that being "better than xdelta" means pretty much the same as "having more than nothing", because xdelta has already been superseded 20 years ago by bsdiff[1], which in turn would ideally be superseded by my project.

  [1]: https://www.daemonology.net/bsdiff/

Comments URL: https://news.ycombinator.com/item?id=34460258

Points: 26

# Comments: 4

  time ./bsc e ../linux.tar linux.bsc -e2 -b16 -T
  68.69s user 1.14s system 99% cpu 117M memory 1:09.84 total

  % bzip3 -e -j 6 -b 50 corpus/calgary.tar
  % bzip3 -j 6 -b 50 corpus/calgary.tar
  bzip3 - A better and stronger spiritual successor to bzip2.
  Copyright (C) by Kamila Szewczyk, 2022. Licensed under the terms of GPLv3.
  Usage: bzip3 [-e/-d/-t/-c] [-b block_size] input output
  Operations:
    -e: encode
    -d: decode
    -t: test
  Extra flags:
    -c: force reading/writing from standard streams
    -b N: set block size in MiB
    -j N: set the amount of parallel threads

  % cat corpus/calgary.tar | bzip3 -b 10 -e -c | wc -c
  807959

% wc -c linux.tar.zst linux.bz3 134980904 linux.tar.zst 129255792 linux.bz3