5 ms·
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 con
by unnah 2y ago
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.
- altairprime 2y agoCan BWT be combined with zstd, which uses asymmetric numeral systems?
- klodolph 2y agoI think you would just need ANS, not the rest of zstd.
- altairprime 2y agoI 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.
- klodolph 2y agoZstd 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.
- CJefferson 2y agoYes, 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.
- rkeene2 2y agoI've been thinking about adding support for this kind of stacking to DACT [0]. [0] http://dact.rkeene.org/ http://dact.rkeene.org/
- gopalv 2y ago> 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.
- derf_ 2y ago> 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 https://ieeexplore.ieee.org/abstract/document/672147
- unnah 2y agoThanks for the reference, looks interesting.
- thesz 2y agoIt 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.
- unnah 2y agoWow, thanks. As always, the best way to learn more on the internet is to be confidently and totally wrong!