We present a technique for proving lower bounds on the compression ratio of algorithms which are based on the
Burrows-Wheeler Transform (BWT). We study three well known BWT-based compressors: the original algorithm suggested by Burrows and Wheeler; BWT with
distance coding; and BWT with run-length encoding. For each compressor, we show a Markov source such that for asymptotically-large
text generated by the source, the compression ratio divided by the entropy of the source is a constant greater than 1. This
constant is 2 −
ε, 1.26, and 1.29, for each of the three compressors respectively. Our technique is robust, and can be used to prove similar
claims for most BWT-based compressors (with a few notable exceptions). This stands in contrast to statistical compressors
and Lempel-Ziv-style dictionary compressors, which are long known to be optimal, in the sense that for any Markov source,
the compression ratio divided by the entropy of the source asymptotically tends to 1.
We experimentally corroborate our theoretical bounds. Furthermore, we compare BWT-based compressors to other compressors and
show that for “realistic” Markov sources they indeed perform bad and often worse than other compressors. This is in contrast
with the well known fact that on English text, BWT-based compressors are superior to many other types of compressors.