> bwt | transformuj | kompresuj <
// Burrows-Wheeler Transform - odwracalne przekształcenie tekstu poprawiające efektywność kompresji
>> funkcje
Całkowicie odwracalna
Bezstratna transformacja, która pozwala dokładnie odzyskać tekst źródłowy.
Grupowanie znaków
Grupuje podobne znaki, dzięki czemu kolejne etapy kodowania lepiej kompresują dane.
Rdzeń bzip2
Podstawa wielu algorytmów kompresji z rodziny bzip2.
>> informacje techniczne
Jak działa BWT
Transformacja Burrowsa-Wheelera generuje wszystkie cykliczne rotacje ciągu wejściowego, sortuje je leksykograficznie i zwraca ostatnią kolumnę posortowanej macierzy wraz z indeksem oryginalnego wiersza. Dzięki temu podobne znaki pojawiają się obok siebie, co pozwala skutecznie kompresować dane za pomocą RLE, Move-to-Front i innych koderów entropijnych.
Przykład BWT
Input: "banana$" Rotations: 0: banana$ 1: anana$b 2: nana$ba 3: ana$ban 4: na$bana 5: a$banan 6: $banana Sorted: 0: $banana 1: a$banan 2: ana$ban 3: anana$b 4: banana$ 5: na$bana 6: nana$ba Last column: annb$aa Original index: 4 Output: annb$aa|4
Dlaczego warto używać BWT
- Poprawia kompresowalność danych tekstowych
- Jest całkowicie odwracalna i bezstratna
- Grupuje podobne konteksty w zwarte bloki
- Stanowi podstawę algorytmu kompresji bzip2
- Jest skutecznym etapem wstępnym przed dalszym kodowaniem
>> najczęstsze pytania
Czym jest transformacja Burrowsa-Wheelera?
Transformacja Burrowsa-Wheelera (BWT) to odwracalny algorytm, który przekształca ciąg znaków tak, aby tworzył długie sekwencje powtarzających się symboli. Została zaproponowana w 1994 roku przez Michaela Burrowsa i Davida Wheelera i jest używana jako etap wstępny w kompresorach takich jak bzip2 w celu poprawy współczynnika kompresji.
Dlaczego BWT poprawia kompresję?
BWT grupuje znaki pojawiające się w podobnych kontekstach, dzięki czemu w wyniku wiele wystąpień tego samego symbolu znajduje się obok siebie. Takie sekwencje bardzo dobrze kompresują się z użyciem kodowania długości serii, transformacji Move-to-Front oraz kodowania entropijnego, takiego jak Huffman.
Czym jest znacznik EOF?
Znacznik EOF (End Of File), zazwyczaj symbol '$' lub inny unikalny znak, gwarantuje, że wszystkie rotacje są rozróżnialne i pozwala odtworzyć pozycję oryginalnego wiersza. Bez niego niektóre ciągi nie miałyby jednoznacznej reprezentacji. W trakcie odwrotnej transformacji znacznik EOF jest usuwany.
Czy BWT jest samodzielnym algorytmem kompresji?
Nie. BWT samo w sobie nie kompresuje danych, lecz przekształca je do postaci bardziej przyjaznej dla kompresji. W praktyce łączy się ją z transformacją Move-to-Front, RLE oraz kodowaniem Huffmana w schematach podobnych do bzip2.