Transformata Burrowsa-Wheelera – 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ę dowolną metodą kompresji bezstratnej, np. algorytmem Huffmana.
Algorytm transformaty Na początku mamy blok danych o rozmiarze N bajtów, np.:
Polska Wikipedia
Generujemy wszystkie N rotacji kompresowanego bloku. Wymaga to jedynie O(N) pamięci, nie zaś O(N²), ponieważ generujemy indeksy, a nie kopiujemy.
S0 Polska Wikipedia S1 olska WikipediaP S2 lska WikipediaPo S3 ska WikipediaPol S4 ka WikipediaPols S5 a WikipediaPolsk S6 WikipediaPolska S7 WikipediaPolska S8 ikipediaPolska W S9 kipediaPolska Wi S10 ipediaPolska Wik S11 pediaPolska Wiki S12 ediaPolska Wikip S13 diaPolska Wikipe S14 iaPolska Wikiped S15 aPolska Wikipedi
Sortujemy łańcuchy leksykograficznie, czyli najpierw według wartości pierwszego bajta, następnie drugiego itd.
F L Pozycja 0S6 WikipediaPolska Pozycja 1S0 Polska Wikipedia Pozycja 2S7 WikipediaPolska Pozycja 3S5 a WikipediaPolsk Pozycja 4S15 aPolska Wikipedi Pozycja 5S13 diaPolska Wikipe Pozycja 6S12 ediaPolska Wikip Pozycja 7S14 iaPolska Wikiped Pozycja 8S8 ikipediaPolska W Pozycja 9S10 ipediaPolska Wik Pozycja 10S4 ka WikipediaPols Pozycja 11S9 kipediaPolska Wi Pozycja 12S2 lska WikipediaPo Pozycja 13S1 olska WikipediaP Pozycja 14S11 pediaPolska Wiki Pozycja 15S3 ska WikipediaPol
Zachowujemy ostatni bajt każdej rotacji, w kolejności ich leksykograficznego wystąpienia (kolumna L), oraz pozycję, na której w L znajduje się pierwszy znak kompresowanego bloku danych (indeks P), czyli po prostu pozycję, na której jest łańcuch S1. W tym przypadku indeksem P jest numer 13 oraz blok:
aa kiepdWksioPil
Z bloku oraz indeksu P można odtworzyć pierwotne dane.
Algorytm transformaty odwrotnej Mamy indeks P = 13 i blok L. 0123456789101112131415 L aa kiepdWksioPil Należy w tym momencie zauważyć, że sortując bajty w L uzyskamy F, czyli pierwszą kolumnę posortowanej macierzy łańcuchów. 0123456789101112131415 F PWaadeiiikklops
Ponieważ bajt przyjmuje 256 możliwych wartości, a bajtów zwykle jest kilkaset tysięcy, najłatwiej zrobić to za pomocą sortowania kubełkowego lub podobnego algorytmu o liniowym czasie wykonywania.
Następnie konstruujemy wektor sąsiedztw T, który posłuży nam do odzyskania pierwotnego ciągu. Wektor T jest to tablica przejść taka, że L[i] i L[T[i]] są kolejnymi znakami pierwotnego ciągu. Dla przykładu:
F L T Pozycja 0S6 WikipediaPolska S6→S72 Pozycja 1S0 Polska Wikipedia S0→S113 Pozycja 2S7 WikipediaPolska S7→S88 Pozycja 3S5 a WikipediaPolsk S5→S60 Pozycja 4S15 aPolska Wikipedi S15→S01 Pozycja 5S13 diaPolska Wikipe S13→S147 Pozycja 6S12 ediaPolska Wikip S12→S135 Pozycja 7S14 iaPolska Wikiped S14→S154 Pozycja 8S8 ikipediaPolska W S8→S911 Pozycja 9S10 ipediaPolska Wik S10→S1114 Pozycja 10S4 ka WikipediaPols S4→S53 Pozycja 11S9 kipediaPolska Wi S9→S109 Pozycja 12S2 lska WikipediaPo S2→S315 Pozycja 13S1 olska WikipediaP S1→S212 Pozycja 14S11 pediaPolska Wiki S11→S126 Pozycja 15S3 ska WikipediaPol S3→S410
Posiadając wektor T, L, oraz index P, możemy odtworzyć ciąg: i = P
dopóki nie odzyskamy całej długości ciągu: wypisz L[i] i = T[i]
Przykład: i = P → 13 L[i] = L → 'P' i = T[i]= T → 12 L → 'o' i = T → 15 L → 'l' ...
Aby wygenerować wektor T z L, należy poprzez sortowanie utworzyć również wektor F. Następnie dla każdego kolejnego elementu F wyznaczyć pozycję elementu odpowiadającego w L. Wówczas index elementu F będzie indeksem T, a index wyznaczonego elementu L jego wartością. Wyznaczony element z L zaznaczamy jako użyty.Najlepiej zobrazować to na przykładzie pięciu kroków algorytmu (kropką • zaznaczone użyte elementy):
Krok Algorytmu012345 FLTFLTFLTFLTFLTFLT Pozycja 0 a2 a2 a2 a2 •2 •2 Pozycja 1 Pa Pa13Pa13Pa13Pa13P•13 Pozycja 2 W W• W•8W•8W•8W•8 Pozycja 3 ak ak ak ak0ak0ak0 Pozycja 4 ai ai ai ai ai1ai1 Pozycja 5 de de de de de de7 Pozycja 6 ep ep ep ep ep ep Pozycja 7 id id id id id id Pozycja 8 iW iW iW i• i• i• Pozycja 9 ik ik ik ik ik ik Pozycja 10 ks ks ks ks ks ks Pozycja 11 ki ki ki ki ki ki Pozycja 12 lo lo lo lo lo lo Pozycja 13 oP oP o• o• o• o• Pozycja 14 pi pi pi pi pi pi Pozycja 15 sl sl sl sl sl sl
Z tak otrzymanego wektora T i indeksu P, z łatwością uzyskujemy pierwotny blok danych.
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; 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)
buckets[i] = j; // it will get fake values if there is no i in F, but // that won't bring us any problems while (i>=F[j] && j<size) ++j;
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; }
Zobacz też Kompresja danych (informatyka) Program do kompresji plików Kompresja bezstratna oraz kompresja stratna Kodowanie arytmetyczne Kodowanie Huffmana Słowo Lyndona
Linki zewnętrzne M. Burrows and D.J. Wheeler: A Block-sorting Lossless Data Compression Algorithm
Burrowsa-Wheelera Kategoria:Transformaty