Transformata Burrowsa-Wheelera

BWT: Reorganizacja bez utraty danych

Kodowanie Huffmana wykorzystuje częstość symboli, a metody z rodziny Lempel-Ziv odwołują się do powtórzonych ciągów. Oba podejścia zachowują dane, lecz wykorzystują różne rodzaje redundancji. Transformata Burrowsa-Wheelera porządkuje blok według kontekstu znaków, przygotowując go do dalszego kodowania statystycznego.

Transformata Burrowsa-Wheelera (BWT) porządkuje rotacje bloku według ich kolejności leksykograficznej. Opisana przez Michaela Burrowsa i Davida Wheelera w 1994 roku BWT nie zmniejsza rozmiaru danych. Jest odwracalną permutacją bloku, która grupuje znaki występujące w podobnych kontekstach. Wynik można następnie przetwarzać przez RLE, MTF i kodowanie entropijne. BWT jest jednym z etapów archiwizatora bzip2. Jego dokumentacja opisuje zwykle lepszy wynik niż dla klasycznych kompresorów LZ, lecz współczynnik zależy od rodzaju danych. Sortowanie całego bloku zwiększa koszt i zapotrzebowanie na pamięć. Praktyczne formaty ograniczają więc rozmiar bloków wejściowych.

Transformata BWT: Rotacje, sortowanie i wyjście

Transformata działa na całym bloku, więc nie jest kodowaniem strumieniowym bajt po bajcie. Użyjmy ciągu ANANAS$. Znak '$' oznacza koniec ciągu i jest leksykograficznie mniejszy od pozostałych znaków. Takie oznaczenie nadaje każdej rotacji jednoznaczne położenie.

Krok 1: Utwórz Wszystkie Rotacje Cykliczne

Najpierw tworzymy wszystkie przesunięcia cykliczne ciągu wejściowego. Każde kolejne przesunięcie przenosi pierwszy znak na koniec.

Krok 2: Posortuj Leksykograficznie Rotacje

Następnie sortujemy rotacje leksykograficznie. sortowanie leksykograficzne porównuje znaki od lewej do prawej, tak jak w porządku słownikowym. W implementacji nie trzeba materializować całej macierzy, ponieważ rotacje można reprezentować przez indeksy albo tablicę sufiksową.

Krok 3: Wyodrębnij wyjście, ostatnią kolumnę

Wyjściem BWT jest sekwencja znaków z ostatniej kolumny posortowanej tabeli. Oznaczamy ją jako $L$.

L = S$NNAAA

Ciąg "ANANAS$" daje wynik "S$NNAAA". Znaki 'A' tworzą serię, którą może skutecznie kodować RLE. Grupowanie kontekstów jest powodem stosowania tej transformacji przed kodowaniem właściwym.

Krok 4: Zapisz Indeks Pierwotny

Do odwrócenia transformacji zapisujemy wiersz, w którym znajduje się oryginalny ciąg. W przykładzie "ANANAS$" jest to wiersz 1, więc indeks pierwotny $I$ ma wartość 1.

Kompletny wynik prostej transformaty Burrowsa-Wheelera dla "ANANAS$" to para: ("S$NNAAA", $1$).

Dla porównania blok bez jawnego znacznika końca może zawierać ciąg "BANANA". Po sortowaniu rotacje mają kolejność "ABANAN", "ANABAN", "ANANAB", "BANANA", "NABANA", "NANABA". Wynik to $L =$ "NNBAAA", a indeks pierwotny $I = 3$.

Odwrotna Transformata BWT: Odtwarzanie Oryginału

Do odtworzenia wystarczają ostatnia kolumna i indeks pierwotny. Potrzebna jest własność łącząca pierwszą i ostatnią kolumnę posortowanej macierzy.

Właściwość Mapowania Ostatni-do-Pierwszego (LF-Mapping)

Spójrzmy ponownie na naszą posortowaną macierz. Nazwijmy pierwszą kolumnę $F$, a ostatnią $L$.

Kolumna $F$ jest posortowaną wersją znaków ciągu ($-A-A-A-N-N-S). Możemy odtworzyć $F$ przez sortowanie znaków $L$.

Własność zapewniająca odwracalność BWT to mapowanie ostatni do pierwszy (LF-mapping):

Mapowanie prowadzi od znaku w $L$ do odpowiadającej pozycji w $F$. Każdy znak w $F$ rozpoczyna posortowaną rotację, więc kolejne przejścia odtwarzają ciąg od końca. Numer wystąpienia znaku jest istotny, ponieważ powtarzające się litery zajmują różne wiersze. Stabilne ponumerowanie wystąpień wyznacza jednoznaczną krawędź LF.

Kroki odwrotnej transformacji

Odtwórzmy "ANANAS$" z informacji $L =$ "S$NNAAA" i $I = 1$.

1. Krok 1: Odtwórz Pierwszą Kolumnę (F): Posortuj znaki $L$ alfabetycznie. Sortowanie "S$NNAAA" daje nam $F =$"$AAANNS".
2. Krok 2: Zacznij od Indeksu Pierwotnego: Nasz indeks $I=1$ mówi nam, że oryginalny ciąg kończył się znakiem z $L[1]$. Patrząc na nasz ciąg $L = (S_0, \$_1, N_2, N_3, A_4, A_5, A_6)$, $L[1]$to '$'. Zatem ostatnim znakiem naszego oryginalnego ciągu jest '$'.
3. Krok 3: Zastosuj Mapowanie LF: Znak, który właśnie znaleźliśmy ('$') jest pierwszym '$' w kolumnie L. Zgodnie z właściwością mapowania LF, odpowiada on pierwszemu '$' w kolumnie F. Pierwszy '$' w $F = (\$_0, A_1, A_2, A_3, N_4, N_5, S_6)$ jest pod indeksem 0. To mówi nam, jaki jest następny krok. Następnym wierszem, na który musimy spojrzeć, jest wiersz 0.
4. Krok 4: Wstecz - Iteracja 2: Przejdź do wiersza 0. Znak w $L[0]$ to 'S'. To przedostatni znak naszego oryginalnego ciągu. Jak dotąd mamy: S$ (czytając od końca).
5. Krok 5: Powtórz Mapowanie LF:Znak, który właśnie znaleźliśmy ('S'), jest pierwszym 'S' w kolumnie L. Odpowiada on pierwszemu 'S' w kolumnie F, które jest pod indeksem 6. Nasz następny wiersz to 6.
6. Krok 6: Kontynuuj Iteracje (odtwarzając wstecz):
   1. $i = 1$. Weź $L[1]$ = '$'. To ostatni znak. Pierwsze '$' w L mapuje się na pierwsze '$' w F (indeks 0). Nowe $i = 0$. Odtworzony ciąg: $.
   2. $i = 0$. Weź $L[0]$ = 'S'. To przedostatni znak. Pierwsze 'S' w L mapuje się na pierwsze 'S' w F (indeks 6). Nowe $i = 6$. Odtworzony ciąg: S$.
   3. $i = 6$. Weź $L[6]$ = 'A'. To trzeci znak od końca. Trzecie 'A' w L mapuje się na trzecie 'A' w F (indeks 3). Nowe $i = 3$. Odtworzony ciąg: AS$.
   4. $i = 3$. Weź $L[3]$ = 'N'. To czwarty znak od końca. Drugie 'N' w L mapuje się na drugie 'N' w F (indeks 5). Nowe $i = 5$. Odtworzony ciąg: NAS$.
   5. $i = 5$. Weź $L[5]$ = 'A'. To piąty znak od końca. Drugie 'A' w L mapuje się na drugie 'A' w F (indeks 2). Nowe $i = 2$. Odtworzony ciąg: ANAS$.
   6. $i = 2$. Weź $L[2]$ = 'N'. To szósty znak od końca. Pierwsze 'N' w L mapuje się na pierwsze 'N' w F (indeks 4). Nowe $i = 4$. Odtworzony ciąg: NANAS$.
   7. $i = 4$. Weź $L[4]$ = 'A'. To siódmy znak od końca. Pierwsze 'A' w L mapuje się na pierwsze 'A' w F (indeks 1). Nowe $i = 1$. Odtworzony ciąg: ANANAS$.

Etapy potoku bzip2 po transformacji BWT

BWT jest etapem przygotowującym dane do dalszych transformacji. W formacie bzip2 występuje także wstępne RLE, a po BWT wykonywane są MTF, kolejne RLE i kodowanie Huffmana.

• Etap 1: RLE i Transformata Burrowsa-Wheelera (BWT): Format bzip2 stosuje wstępne RLE, następnie przetwarza dane blokami i tworzy kolumnę L oraz indeks, grupując znaki o podobnym kontekście.
• Etap 2: Transformata Move-to-Front (MTF): Wynik BWT, który teraz ma długie serie identycznych znaków, jest przetwarzany przez transformatę MTF. MTF utrzymuje listę alfabetu. Dla każdego przetwarzanego znaku wypisuje jego obecną pozycję na liście, a następnie przesuwa ten znak na początek listy. Rezultatem jest strumień małych liczb (głównie zer, jedynek i dwójek), który jest jeszcze bardziej statystycznie redundantny.
• Etap 3: Kodowanie Długości Serii (RLE): Strumień wartości z MTF jest kodowany przez kolejne RLE, między innymi w celu skrócenia serii zer.
• Etap 4: Kodowanie Entropijne: Ostateczny strumień symboli z etapu RLE jest kompresowany za pomocą kodowania Huffmana w bzip2. Inne potoki BWT mogą w tym miejscu używać kodowania arytmetycznego.

W praktyce MTF zapisuje pozycję znaku w aktualnej liście alfabetu i przenosi ten znak na początek. Po BWT często pojawiają się małe pozycje, szczególnie zera, więc RLE może kodować ich serie krótszym opisem. Huffman nadaje tym symbolom kody zależne od częstości. Każdy etap ma własną funkcję i może zostać odwrócony podczas dekompresji w kolejności odwrotnej. Indeks pierwotny jest przechowywany razem z blokiem wejściowym i pozwala wybrać właściwą rotację deterministycznie.

Rola transformacji BWT

BWT jest odwracalną permutacją, która wykorzystuje kontekst znaków do przygotowania bloku dla RLE, MTF i kodowania entropijnego. Sortowanie zwiększa koszt obliczeń i wymaga pracy na całym bloku. Wynik kompresji zależy od danych oraz od kolejnych etapów potoku, dlatego BWT nie jest samodzielnym miernikiem redukcji rozmiaru. Ten sam porządek rotacji może służyć także do budowy indeksów tekstowych, lecz w bzip2 służy przede wszystkim jako etap przygotowania danych.