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.