Space Efficient Algorithms for the Burrows-Wheeler Backtransformation

1 Introduction The Burrows-Wheeler transformation (BWT) [6] is at the heart of modern, veryeffective data compression algorithms and programs, e.g., bzip2 [13]. BWT-based compressors usually work in a block-wise manner, i.e., the input iThe Burrows-Wheeler transformation is used for effective data compression, e.g., in the well known program bzip2. Compression and decompression are done in a block-wise fashion; larger blocks usually result in better compression rates. With the currently used algorithms for decompression, 4n bytes of auxiliary memory for processing a block of n bytes are needed, 0 < n < 232. This may pose a problem in embedded systems (e.g., mobile phones), where RAM is a scarce resource.\ud In this paper we present algorithms that reduce the memory need without sacrificing speed too much. The main results are: Assuming an input string of n characters, 0 < n < 2^32, the reverse Burrows-Wheeler transformation can be done with 1.625 n bytes of auxiliary memory and O(n) runtime, using just a few operations per input character. Alternatively, we can use n / t bytes and 256 t n operations. The theoretical results are backed up by experimental data showing the space-time tradeoff. s divided intoblocks and compressed block by block. Larger block sizes tend to result in better compression results, thus bzip2 uses by default a block size of 900,000 bytes andin its low memory mode still 100,000 bytes. The standard algorithm for decompression (reverse BWT) needs auxiliary memory of 4 bytes per input character,assuming 4-byte computer words and thus n < 232. This may pose a problem inembedded systems (say, a mobile phone receiving a software patch over the ai