An analysis of the Burrows—Wheeler transform

ABSTRACT

The Burrows—Wheeler Transform (also known as Block-Sorting) is at the base of compression algorithms that are the state of the art in lossless data compression. In this paper, we analyze two algorithms that use this technique. The first one is the original algorithm described by Burrows and Wheeler, which, despite its simplicity outperforms the Gzip compressor. The second one uses an additional run-length encoding step to improve compression. We prove that the compression ratio of both algorithms can be bounded in terms of the kth order empirical entropy of the input string for any k ≥ 0. We make no assumptions on the input and we obtain bounds which hold in the worst case that is for every possible input string. All previous results for Block-Sorting algorithms were concerned with the average compression ratio and have been established assuming that the input comes from a finite-order Markov source.

REFERENCES

• 1: ARNOLD, R., AND BELL, T. 2000. The Canterbury corpus home page. http://corpus.canterbury. ac.nz.
• 2: Jon Louis Bentley , Daniel D. Sleator , Robert E. Tarjan , Victor K. Wei, A locally adaptive data compression scheme, Communications of the ACM, v.29 n.4, p.320-330, April 1986 [doi>10.1145/5684.5688]
• 3: BURROWS, M., AND WHEELER, D. J. 1994. A block sorting lossless data compression algorithm. Tech. Rep. 124. Digital Equipment Corporation, Palo Alto, Calif.
• 4: CLEARY,J.G.,AND TEAHAN, W. J. 1997. Unbounded length contexts for PPM. Comput. J. 40, 2/3, 67-75.
• 5: G. V. Ormack , R. N. S. Horspool, Data compression using dynamic Markov modelling, The Computer Journal, v.30 n.6, p.541-550, Dec. 1987
• 6: Michelle Effros, Universal Lossless Source Coding with the Burrows Wheeler Transform, Proceedings of the Conference on Data Compression, p.178, March 29-31, 1999
• 7: FENWICK, P. 1996a. Block sorting text compression-final report. Tech. Rep. 130, Dept. of Computer Science, The University of Auckland, New Zealand.
• 8: FENWICK, P. 1996b. The Burrows-Wheeler transform for block sorting text compression: principles and improvements. Computer J. 39,9,731-740.
• 9: P. Ferragina , G. Manzini, Opportunistic data structures with applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.390, November 12-14, 2000
• 10: Paolo Ferragina , Giovanni Manzini, An experimental study of an opportunistic index, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.269-278, January 07-09, 2001, Washington, D.C., United States
• 11: Paul G. Howard , Jeffrey Scott Vitter, Analysis of arithmetic coding for data compression, Information Processing and Management: an International Journal, v.28 n.6, p.749-763, Nov.–Dec. 1992 [doi>10.1016/0306-4573(92)90066-9]
• 12: HOWARD, P., AND VITTER, J. 1992b. Practical implementations of arithmetic coding. In Image and Text Compression, J. A. Storer, ed. Kluwer Academic, pp. 85-112.
• 13: HUFFMAN, D. A. 1952. A method for the construction of minimum redundancy codes. Proc. IRE 40 (Sept.), 1098-1101.
• 14: S. Rao Kosaraju , Giovanni Manzini, Compression of Low Entropy Strings with Lempel--Ziv Algorithms, SIAM Journal on Computing, v.29 n.3, p.893-911, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539797331105]
• 15: N. J. Larsson, The Context Trees of Block Sorting Compression, Proceedings of the Conference on Data Compression, p.189, March 30-April 01, 1998
• 16: MOFFAT, A. 1990. Implementing the PPM data compression scheme. IEEE Trans. Commun. COM-38, 1917-1921.
• 17: A. Moffat , R. Neal, Arithmetic coding revisited, Proceedings of the Conference on Data Compression, p.202, March 28-30, 1995
• 18: NELSON, M. 1996. Data compression with the Burrows-Wheeler transform. Dr. Dobb's J. Softw. Tools 21,9,46-50, http://www.dogma.net/markn/articles/bwt/bwt.htm.
• 19: RYABKO, B. Y. 1980. Data compression by means of a 'book stack'. Prob. Inf. Transm. 16,4, 265-269.
• 20: K. Sadakane, Text Compression using Recency Rank with Context and Relation to Context Sorting, Block Sorting and PPM, Proceedings of the Compression and Complexity of Sequences 1997, p.305, June 11-13, 1997
• 21: K. Sadakane, On Optimality of Varients of the Block Sorting Compression, Proceedings of the Conference on Data Compression, p.570, March 30-April 01, 1998
• 22: Michael Schindler, A Fast Block-Sorting Algorithm for Lossless Data Compression, Proceedings of the Conference on Data Compression, p.469, March 25-27, 1997
• 23: SEWARD, J. 1997. The BZIP2 home page. http://sourceware.cygnus.com/bzip2/in-dex. html.
• 24: Jeffrey Scott Vitter, Design and analysis of dynamic Huffman codes, Journal of the ACM (JACM), v.34 n.4, p.825-845, Oct. 1987 [doi>10.1145/31846.42227]
• 25: WHEELER, D. 1995. An implementation of block coding. Computer Laboratory. Cambridge University, Cambridge, UK, ftp://ftp.cl.cam.ac.uk/users/djw3/bred.ps.
• 26: WHEELER, D. 1997. Upgrading bred with multiples tables. Computer Laboratory. Cambridge University, Cambridge, UK, ftp://ftp.cl.cam.ac.uk/users/djw3/bred3.ps.
• 27: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Keywords:
Burrows—Wheeler transform, block sorting, move-to-front encoding, worst-case analysis of compression