Trasformata di Burrows-Wheeler

La trasformata di Burrows-Wheeler (abbreviata con BWT) è un algoritmo usato nei programmi di compressione dati come bzip2. È stata inventata da e David Wheeler. Quando una stringa di caratteri viene sottoposta alla BWT, nessuno di questi cambia di valore perché la trasformazione permuta soltanto l'ordine dei caratteri. Se la stringa originale contiene molte ripetizioni di certe sottostringhe, allora nella stringa trasformata troveremo diversi punti in cui lo stesso carattere si ripete tante volte. Ciò è utile per la compressione perché diventa facile comprimere una stringa in cui compaiono lunghe sequenze di caratteri tutti uguali. Per esempio, la stringa: TRENTATRE.TRENTINI.ANDARONO.A.TRENTO.TUTTI.E.TRENTATRE.TROTTERELLANDO verrebbe trasformata nella seguente: OIIEEAEO..LDTTNN.RRRRRRRTNTTLEAAIOEEEENTRDRTTETTTTATNNTTNNAAO....OU.T