The Burrows-Wheeler Transform: Theory and Practice

1 Introduction It seems that there is no limit to the amount of data we need to store in ourcomputers, or send to our friends and colleagues. Although the technology is providing us with larger disks and faster communication networks, the needof faster and more efficient data compression algorithms seems to be always increasing. Fortunately, data compression algorithms have continued to evolvein a continuous progress which should not be taken for granted since there are well known theoretical limits to how much we can squeeze our data (see [31] fora complete review of the state of the art in all fields of data compression). Progress in data compression usually consists of a long series of small im-provements and fine tuning of algorithms. However, the field experiences occasional giant leaps when new ideas or techniques emerge. In the field of losslesscompression we have just witnessed to one of these leaps with the introduction of the Burrows-Wheeler Transform [7] (BWT from now on). Loosely speaking,the BWT produces a permutatio