## Space Efficient Algorithms for the Burrows-Wheeler Backtransformation

Ulrich Lauther, Tamás Lukovszki

#### Abstract

The 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, 4*n* bytes
of auxiliary memory for processing a block of *n* bytes are needed,
0 < *n* < 2^{32}.
This may pose a problem in embedded systems (e.g., mobile phones), where RAM
is a scarce resource.

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.