3
$\begingroup$

Why does there seem to be a preference for using Huffman (or Arithmetic) coding instead of a Lempel-Ziv type compression algorithm for Burrows-Wheeler Transformed data?

I noticed that data compressors such as Bzip2 or ZZip use mainly a combination of BWT, RLE and Huffman/Arithmetic coding. I would like to know what are the reasons against using a LZ-type algorithm instead of entropy encoding.

Improve this question
$\endgroup$
6
  • $\begingroup$ Have you looked at the obvious characteristics, i.e. runtime and compression rate (on different kinds of data)? $\endgroup$
    – Raphael
    Commented Feb 16, 2015 at 16:13
  • $\begingroup$ @Raphael No, I have not. This a theoretical question, because I expect the reason for favoring entropy coding to be theoretical. In other words, my intuition tells me that LZ should be just as good, yet I am waiting to see if someone can show that my intuition is wrong. $\endgroup$
    – Log
    Commented Feb 16, 2015 at 16:45
  • $\begingroup$ You reference artifacts of practice, and sometimes developers of such do not follow what is "best" in theory. That's fair, because practice adds additional layers of concern. But looking at the theory can certainly provide a first view on the matter, and I'm certain you can find resource analyses and compression rates in the literature; hence my query. $\endgroup$
    – Raphael
    Commented Feb 16, 2015 at 21:20
  • $\begingroup$ @Raphael I was hoping that I could get an answer with a short proof or link to a study, which shows that BWT "goes well" with LZ algorithms (or doesn't). The "artifacts of practice", as you call them, point to "doesn't" but I'm looking for a (preferably simple) explanation rather than benchmarks. $\endgroup$
    – Log
    Commented Feb 16, 2015 at 22:04
  • 1
    $\begingroup$ Well, there are some articles that contain both terms. Sorry I can't be of more help, but I don't know much in this area. $\endgroup$
    – Raphael
    Commented Feb 17, 2015 at 7:12

1 Answer 1

Reset to default
0
$\begingroup$

LZ-type algorithms are useful for data for which context is predictive, like text consisting of lexemes and following some grammar. That is not so for the output of the BWT (nor of the MTF transform which is performed after BWT).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Specifically, the BWT plays the same role as prediction in LZ-type algorithms: Exploiting the fact that the same symbols tend to follow the same contexts. It's also the same story with PPM or DMC. $\endgroup$
    – Pseudonym ♦
    Commented Dec 16, 2023 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.