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 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
La trasformata
[modifica | modifica wikitesto]La trasformata è fatta ordinando tutte le rotazioni del testo e poi prendendo soltanto l'ultima colonna. Per esempio, il testo "^BANANA@" viene trasformato in "BNN^AA@A" attraverso questi passi (i caratteri rossi ^ e @ indicano rispettivamente il puntatore di inizio stringa, e quello di fine stringa o 'EOF'):
| Trasformata | ||||
|---|---|---|---|---|
| Input | Tutte le rotazioni |
Linee in ordine
lessicografico |
Si prende
l'ultima colonna |
Output |
^BANANA@ |
^BANANA@ @^BANANA A@^BANAN NA@^BANA ANA@^BAN NANA@^BA ANANA@^B BANANA@^ |
ANANA@^B ANA@^BAN A@^BANAN BANANA@^ NANA@^BA NA@^BANA ^BANANA@ @^BANANA |
ANANA@^B ANA@^BAN A@^BANAN BANANA@^ NANA@^BA NA@^BANA ^BANANA@ @^BANANA |
BNN^AA@A |
Il seguente pseudocodice mostra un metodo, inefficiente, per calcolare la BWT e la sua inversa. Assume che la stringa di input s contenga un carattere speciale 'EOF' che è sempre l'ultimo carattere e che non appare mai nel testo, e che quindi è ignorato durante l'ordinamento.
funzione BWT (string s)
crea una lista di tutte le possibili rotazioni di s
metti ciascuna rotazione su una riga di una grande tabella quadrata
ordina alfabeticamente le righe della tabella, trattando ogni riga come una stringa
riporta la colonna più a destra della tabella
funzione BWTinversa (string s)
crea una tabella vuota senza righe o colonne
ripeti lunghezza_di(s) volte
inserisci s come nuova colonna sul lato sinistro della tabella
ordina alfabeticamente le righe della tabella
riporta la riga che finisce con il carattere 'EOF'
La trasformata inversa
[modifica | modifica wikitesto]La cosa più interessante della BWT non è che questa genera un output più facilmente comprimibile dell'originale, anche perché ciò si potrebbe ottenere mettendo semplicemente in ordine alfabetico i caratteri, ma è la sua reversibilità: il documento originale si ricostruisce a partire dai soli caratteri dell'ultima colonna.
L'inversa può essere compresa in questo modo. Prendi la tabella finale dell'algoritmo BWT ed elimina tutto a parte l'ultima colonna. Data soltanto quest'informazione puoi facilmente ricostruire la prima colonna. L'ultima colonna ti dice quali sono tutti i caratteri del testo, basta metterli in ordine per ottenere la prima colonna. Adesso la prima e l'ultima colonna sono note e insieme ti danno tutte le coppie di caratteri successivi nel documento, dove le coppie danno, ciclicamente, sempre prima l'ultimo e poi il primo carattere della coppia nel documento originale. Ordinando la lista delle coppie ottieni la prima e la seconda colonna. Continuando in questo modo puoi ricostruire l'intera lista, quindi, la riga con il carattere 'EOF' alla fine è il testo originale. La trasformata inversa dell'esempio sopra viene fatta così:
| Trasformata inversa | |||
|---|---|---|---|
| Input | |||
BNN^AA@A
| |||
| Aggiungi | Ordina | Aggiungi | Ordina |
B
N
N
^
A
A
@
A
|
A
A
A
B
N
N
^
@
|
BA NA NA ^B AN AN @^ A@ |
AN AN A@ BA NA NA ^B @^ |
| Aggiungi | Ordina | Aggiungi | Ordina |
BAN NAN NA@ ^BA ANA ANA @^B A@^ |
ANA ANA A@^ BAN NAN NA@ ^BA @^B |
BANA NANA NA@^ ^BAN ANAN ANA@ @^BA A@^B |
ANAN ANA@ A@^B BANA NANA NA@^ ^BAN @^BA |
| Aggiungi | Ordina | Aggiungi | Ordina |
BANAN NANA@ NA@^B ^BANA ANANA ANA@^ @^BAN A@^BA |
ANANA ANA@^ A@^BA BANAN NANA@ NA@^B ^BANA @^BAN |
BANANA NANA@^ NA@^BA ^BANAN ANANA@ ANA@^B @^BANA A@^BAN |
ANANA@ ANA@^B A@^BAN BANANA NANA@^ NA@^BA ^BANAN @^BANA |
| Aggiungi | Ordina | Aggiungi | Ordina |
BANANA@ NANA@^B NA@^BAN ^BANANA ANANA@^ ANA@^BA @^BANAN A@^BANA |
ANANA@^ ANA@^BA A@^BANA BANANA@ NANA@^B NA@^BAN ^BANANA @^BANAN |
BANANA@^ NANA@^BA NA@^BANA ^BANANA@ ANANA@^B ANA@^BAN @^BANANA A@^BANAN |
ANANA@^B ANA@^BAN A@^BANAN BANANA@^ NANA@^BA NA@^BANA ^BANANA@ @^BANANA |
| Output | |||
^BANANA@
| |||
Certe ottimizzazioni possono far sì che questi algoritmi vengano eseguiti in maniera più efficiente senza cambiare il risultato; non c'è nessuna necessità di tenere l'intera tabella in memoria, tanto meno su disco e non è necessario ripetere i continui ordinamenti dell'esempio. Ogni riga della tabella è rappresentata in memoria con un semplice puntatore al carattere d'inizio della stessa.
Implementazione d'esempio
[modifica | modifica wikitesto]Nota: Scritta in C
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>
typedef unsigned char byte;
byte *rotlexcmp_buf = NULL;
int rottexcmp_bufsize = 0;
int rotlexcmp(const void *l, const void *r)
{
int li = *(const int*)l, ri = *(const int*)r, ac=rottexcmp_bufsize;
if(li == ri) return 0;
while (rotlexcmp_buf[li] == rotlexcmp_buf[ri])
{
if (++li == rottexcmp_bufsize)
li = 0;
if (++ri == rottexcmp_bufsize)
ri = 0;
if (!--ac)
return 0;
}
if (rotlexcmp_buf[li] > rotlexcmp_buf[ri])
return 1;
else
return -1;
}
void bwt_encode(byte *buf_in, byte *buf_out, int size, int *primary_index)
{
int indices[size];
int i;
for(i=0; i<size; i++)
indices[i] = i;
rotlexcmp_buf = buf_in;
rottexcmp_bufsize = size;
qsort (indices, size, sizeof(int), rotlexcmp);
for (i=0; i<size; i++)
buf_out[i] = buf_in[(indices[i]+size-1)%size];
for (i=0; i<size; i++)
{
if (indices[i] == 1) {
*primary_index = i;
return;
}
}
assert (0);
}
void bwt_decode(byte *buf_in, byte *buf_out, int size, int primary_index)
{
byte F[size];
int buckets[256];
int i,j,k;
int indices[size];
for (i=0; i<256; i++)
buckets[i] = 0;
for (i=0; i<size; i++)
buckets[buf_in[i]] ++;
for (i=0,k=0; i<256; i++)
for (j=0; j<buckets[i]; j++)
F[k++] = i;
assert (k==size);
for (i=0,j=0; i<256; i++)
{
while (i>F[j] && j<size)
j++;
buckets[i] = j; // it will get fake values if there is no i in F, but
// that won't bring us any problems
}
for(i=0; i<size; i++)
indices[buckets[buf_in[i]]++] = i;
for(i=0,j=primary_index; i<size; i++)
{
buf_out[i] = buf_in[j];
j=indices[j];
}
}
int main()
{
byte buf1[] = "Polska Wikipedia";
int size = strlen((const char*)buf1);
byte buf2[size];
byte buf3[size];
int primary_index;
bwt_encode (buf1, buf2, size, &primary_index);
bwt_decode (buf2, buf3, size, primary_index);
assert (!memcmp (buf1, buf3, size));
printf ("Result is the same as input, that is: <%.*s>\n", size, buf3);
// Print out encode/decode results:
printf ("Input : <%.*s>\n", size, buf1);
printf ("Output: <%.*s>\n", size, buf2);
return 0;
}
implementazione in Perl:
#!/usr/bin/perl
# an Oromis92's implementation
while ( $text = <> ) {
chomp $text;
@text = split //, $text;
$length = length($text);
@array = ($text);
for ( $j = 0 ; $j < $length ; $j++ ) {
for ( $i = 0 ; $i < $length ; $i++ ) {
$string .= $text[ ( $i - ( $j + 1 ) ) ];
}
$array[ $j + 1 ] = $string;
$string = "";
}
pop(@array);
@array = sort(@array);
$text = "";
for ( $k = 0 ; $k <= $#array ; $k++ ) {
$text .= substr( $array[$k], ($length) - 1, 1 );
}
print "$text\n";
}
Note
[modifica | modifica wikitesto]- ^ Burrows M and Wheeler D, A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, 1994.
