Hacker News Reader

Comment by unnah | Hacker News Reader

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.

View on HN

> There is no general compression theory in which BWT could be described as a special case.

I would not really say this is true. BWT is spiritually similar to the various Prediction by Partial Matching (PPM) algorithms, except that instead of needing to decide how much context (i.e., preceding symbols) to use to model the next symbol, and carefully learning the probabilities for each unique context, it naturally sorts symbols with the same context (of _any_ length) so they appear next to each other, and relies on adaptation to update your learned statistics as you move from one context to the next, without ever explicitly tracking context boundaries [0].

[0] N.J. Larsson, "The Context Trees of Block Sorting Compression," 1998. https://ieeexplore.ieee.org/abstract/document/672147

Thanks for the reference, looks interesting.

It definitely is related to prediction by partial match (PPM).

BWT sorts rotated data and what is achieved is that same suffixes group together:

  ...
  "Bzip2 and Bzip3 are simply combining more"
  "Bzip3 are simply combining moreBzip2 and "

The preceding (to suffix) character goes to end and then gets outputted. This is much like PPM going backward. There is a PPM* algorithm (unbounded context length) where authors considered reconstruction of contexts from data, utilizing something like LZSS seach. Same idea is in BWT - context is reconstructed from data.

BWT also breaks near dependencies in data, this is why move-to-front with Huffman or arithmetic encoding works well there.

Wow, thanks. As always, the best way to learn more on the internet is to be confidently and totally wrong!

Can BWT be combined with zstd, which uses asymmetric numeral systems?

Yes, it would actually be interesting to just have a bwt pass which does no compression, so we can then try lots of post compression options.

I've been thinking about adding support for this kind of stacking to DACT [0].

[0] http://dact.rkeene.org/

> BWT be combined with zstd

BWT can be combined with anything which does RLE and get a benefit.

What does it does is give RLE more to work with.

I think you would just need ANS, not the rest of zstd.

I don’t know enough to evaluate that, but it sounds plausible. Apparently modifying or integrating zstd into custom solutions was a common path in submissions to, at the very least, the GDCC 2021 T2 contest. This is all well outside of my learned competence so I’m just here to learn and ask naive questions.

Zstd is basically LZ77 + FSE. There are some other pieces to it, but they’re minor. FSE is a form of entropy coding that you can swap out with other entropy coding techniques, like Huffman or arithmetic coding. For most objectives, FSE is the clear winner of those three.

As people mentioned elsewhere in the thread, Burrows-Wheeler isn’t really composable with other systems. Nobody has figured out a reasonable way to combine LZ77 and Burrows-Wheeler. That’s why zstd + bzip2 does not work. But you do need an entropy coding system to go with Burrows-Wheeler… and FSE fits the bill.

Reply on news.ycombinator.com