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 dei caratteri cambia di valore perché la trasformazione permuta soltanto il loro ordine. Se la stringa originale contiene molte ripetizioni di caratteri, allora nella stringa trasformata vi saranno molti 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

La trasformata consiste nell'ordinare lessicograficamente tutte le possibili rotazioni verso destra del testo (un carattere alla volta) e poi prendendo soltanto l'ultimo carattere di ogni rotazione. Per esempio, il testo "^BANANA@" viene trasformato in "BNN^AA@A" attraverso i passi di seguito riportati (i caratteri rossi ^ e @ indicano rispettivamente il puntatore di inizio stringa, e quello di fine stringa o EOS -- end of string):

Trasformata
Input	Matrice delle possibili rotazioni	Rotazioni in ordine lessicografico	Si considera l'ultima colonna della matrice	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 di fine stringa (EOS) 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 'EOS'

La trasformata inversa

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. A partire dalla stringa trasformata è possibile ottenere la prima colonna della tabella utilizzata nella trasformazione diretta, utilizzando l'ordinamento lessicografico dei caratteri. In questo modo la prima e l'ultima colonna della tabella precedente sono note e insieme sono in grado di fornire tutte le coppie di caratteri successivi nel testo: ad ogni passaggio, con l'ordinamento si ottiene la parte finale del testo al quale va aggiunto in testa il carattere della stringa di input. Applicando ciclicamente l'algoritmo per un numero di volte pari al numero di caratteri presenti nella stringa trasformata (tranne l'EOS) è possibile ricostruire l'intero elenco delle possibili rotazioni della stringa e la riga che termina con il carattere EOS è quella cohe rappresenta il testo originale. Di seguito sono riportati i passi dell'algoritmo descritto per attuare la trasformata inversa dell'esempio:

Trasformata inversa
Input
BNN^AA@A
Aggiunta 1	Ordinamento 1	Aggiunta 2	Ordinamento 2
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 @^
Aggiunta 3	Ordinamento 3	Aggiunta 4	Ordinamento 4
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
Aggiunta 5	Ordinamento 5	Aggiunta 6	Ordinamento 6
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
Aggiunta 7	Ordinamento 7	Aggiunta 8	Ordinamento 8
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 l'algoritmo venga eseguito in maniera più efficiente senza cambiare il risultato. Ad esempio, non c'è alcuna necessità di tenere l'intera tabella in memoria: ogni riga della tabella può essere rappresentata mediante un semplice puntatore al primo carattere della stessa.

L'ordinamento può essere effettuato una sola volta, memorizzando lo spostamento di ogni singolo carattere. Nell'agoritmo descritto, un "carattere" può essere rappresentato da un byte, un bit o da qualsiasi altro gruppo di bit.

Non è necessario avere un vero e proprio carattere di fine stringa (EOS), poiché si può usare un puntatore che indichi la sua posizione. In questo approccio, l'output del BWT deve includere sia la stringa trasformata che il valore del puntatore (la posizione dell'EOS). Ciò significa che il BWT espande leggermente il testo prodotto con la trasformazione diretta. La trasformata inversa lo riporta alla dimensione originale: partendo da una stringa e un puntatore e fornisce in output solo una stringa.

Una descrizione completa dell'algoritmo è disponibile nell'articolo di Burrows e Wheeler o in diverse fonti online.^[1] Gli algoritmi variano leggermente a seconda che venga utilizzato un EOS e in quale direzione venga effettuato l'ordinamento. La formulazione dell'algoritmo originale, infatti, non utilizzava un EOS.^[2]

Implementazione d'esempio

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";
}