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.

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

1 Answer 1

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).

$\endgroup$

Your Answer

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

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