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.

  • $\begingroup$ Have you looked at the obvious characteristics, i.e. runtime and compression rate (on different kinds of data)? $\endgroup$ – Raphael Feb 16 '15 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 Feb 16 '15 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 Feb 16 '15 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 Feb 16 '15 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 Feb 17 '15 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.