Z Wikipedii

Transformata Burrowsa-Wheelera to algorytm użyteczny przy bezstratnej kompresji danych. Dane po przetworzeniu tą transformacją dają się znacznie lepiej skompresować za pomocą klasycznych algorytmów kompresji. Operuje ona na blokach, przy czym jest tym efektywniejsza im bloki te są większe. Zazwyczaj używa się bloków o rozmiarach kilkuset kilobajtów.

Transformata Burrowsa-Wheelera jest podstawą algorytmu BZIP2.

Dla potrzeb kompresji, zwykle po transformacie Burrowsa-Wheelera używa się algorytmu Move To Front, po czym kompresuje się jakąś metodą kompresji bezstratnej, np. algorytmem Huffmana.

[edytuj] Algorytm transformaty

Na początku mamy blok danych o rozmiarze N bajtów, np.:

P

o

l

s

k

a

W

i

k

i

p

e

d

i

a

Generujemy wszystkie N rotacji kompresowanego bloku. Wymaga to jedynie O(N) pamięci, nie zaś O(N²), ponieważ generujemy indeksy a nie kopiujemy.

S0	P	o	l	s	k	a		W	i	k	i	p	e	d	i	a
S1	o	l	s	k	a		W	i	k	i	p	e	d	i	a	P
S2	l	s	k	a		W	i	k	i	p	e	d	i	a	P	o
S3	s	k	a		W	i	k	i	p	e	d	i	a	P	o	l
S4	k	a		W	i	k	i	p	e	d	i	a	P	o	l	s
S5	a		W	i	k	i	p	e	d	i	a	P	o	l	s	k
S6		W	i	k	i	p	e	d	i	a	P	o	l	s	k	a
S7	W	i	k	i	p	e	d	i	a	P	o	l	s	k	a
S8	i	k	i	p	e	d	i	a	P	o	l	s	k	a		W
S9	k	i	p	e	d	i	a	P	o	l	s	k	a		W	i
S10	i	p	e	d	i	a	P	o	l	s	k	a		W	i	k
S11	p	e	d	i	a	P	o	l	s	k	a		W	i	k	i
S12	e	d	i	a	P	o	l	s	k	a		W	i	k	i	p
S13	d	i	a	P	o	l	s	k	a		W	i	k	i	p	e
S14	i	a	P	o	l	s	k	a		W	i	k	i	p	e	d
S15	a	P	o	l	s	k	a		W	i	k	i	p	e	d	i

Sortujemy łańcuchy leksykograficznie, czyli najpierw wg wartości pierwszego bajtu, następnie drugiego itd.

																	L
Pozycja 0	S6		W	i	k	i	p	e	d	i	a	P	o	l	s	k	a
Pozycja 1	S0	P	o	l	s	k	a		W	i	k	i	p	e	d	i	a
Pozycja 2	S7	W	i	k	i	p	e	d	i	a	P	o	l	s	k	a
Pozycja 3	S5	a		W	i	k	i	p	e	d	i	a	P	o	l	s	k
Pozycja 4	S15	a	P	o	l	s	k	a		W	i	k	i	p	e	d	i
Pozycja 5	S13	d	i	a	P	o	l	s	k	a		W	i	k	i	p	e
Pozycja 6	S12	e	d	i	a	P	o	l	s	k	a		W	i	k	i	p
Pozycja 7	S14	i	a	P	o	l	s	k	a		W	i	k	i	p	e	d
Pozycja 8	S8	i	k	i	p	e	d	i	a	P	o	l	s	k	a		W
Pozycja 9	S10	i	p	e	d	i	a	P	o	l	s	k	a		W	i	k
Pozycja 10	S4	k	a		W	i	k	i	p	e	d	i	a	P	o	l	s
Pozycja 11	S9	k	i	p	e	d	i	a	P	o	l	s	k	a		W	i
Pozycja 12	S2	l	s	k	a		W	i	k	i	p	e	d	i	a	P	o
Pozycja 13	S1	o	l	s	k	a		W	i	k	i	p	e	d	i	a	P
Pozycja 14	S11	p	e	d	i	a	P	o	l	s	k	a		W	i	k	i
Pozycja 15	S3	s	k	a		W	i	k	i	p	e	d	i	a	P	o	l

Zachowujemy ostatni bajt każdej rotacji, w kolejności ich leksykograficznego wystąpienia, oraz pozycję na której w L znajduje się pierwszy znak kompresowanego bloku danych, czyli po prostu pozycję, na której jest łańcuch S1. W tym przypadku jest to numer 13 oraz blok:

a

a

k

i

e

p

d

W

k

s

i

o

P

i

l

Z bloku oraz indeksu można odtworzyć pierwotne dane.

[edytuj] Algorytm transformaty odwrotnej

Mamy blok L i indeks P. Sortujemy bajty w L uzyskując F, czyli pierwszą kolumnę posortowanej macierzy łańcuchów. Ponieważ możliwych wartości jest 256, a bajtów zwykle kilkaset tysięcy, najłatwiej zrobić to za pomocą sortowania kubełkowego lub podobnego algorytmu o liniowym czasie wykonywania.

Następnie konstruujemy wektor T, który mówi jak odzyskać pierwotne dane.

W końcu, zaczynając odzyskujemy pierwotne dane za pomocą pętli:

• dla i równego adresom kolejnych komórek danych, od 0 do rozmiar_danych-1:
  • odzyskane_dane[i] = L[P]
  • i = i + 1
  • P=T[P]

[edytuj] Przykładowy kod w 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;
    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(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);
    return 0;
}