> bwt | transformuj | kompresuj <
// Burrows-Wheeler Transform - odwracalne przekształcenie tekstu poprawiające efektywność kompresji
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.