Hacker News Reader

Comment by altairprime | Hacker News Reader

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