Retrieve full article in PDF (223497 bytes)
Lecture Notes in Computer Science
Volume 1672, pages. 34-47
© Springer Verlag, 1999
Abstract. In this paper we describe the Burrows-Wheeler Transform (BWT) a completely new approach to data compression which is the basis of some of the best compressors available today. Although it is easy to intuitively understand why the BWT helps compression, the analysis of BWT-based algorithms requires a careful study of every single algorithmic component. We describe two algorithms which use the BWT and we show that their compression ratio can be bounded in terms of the k-th order empirical entropy of the input string for any k>0. Intuitively, this means that these algorithms are able to make use of all the regularity which is in the input string. Finally, we discuss some of the algorithmic issues which arise in the computation of the BWT, and we describe two variants of the BWT which promise interesting developments.
Retrieve full article in PDF (223497 bytes)
Retrieve full article in compressed PostScript (55004 bytes)