Back Burrowsova–Wheelerova transformace Czech Burrows-Wheeler-Transformation German Burrows–Wheeler transform English Compresión de Burrows-Wheeler Spanish تبدیل باروز-ویلر Persian Transformée de Burrows-Wheeler French התמרת בורווס-וילר HE Burrows–Wheeler-transzformáció Hungarian ブロックソート Japanese 버로우즈-휠러 변환 Korean
La trasformata di Burrows-Wheeler (abbreviata con BWT) è un algoritmo usato nei programmi di compressione dati come bzip2. È stata inventata da Michael Burrows e David Wheeler.[1]
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
- ^ Burrows M and Wheeler D, A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, 1994.