Spisu treści:
- Definicja - Co oznacza transformacja Burrowsa-Wheelera (BWT)?
- Techopedia wyjaśnia Burrows-Wheeler Transform (BWT)
Definicja - Co oznacza transformacja Burrowsa-Wheelera (BWT)?
Transformacja Burrowsa-Wheelera (BWT) to algorytm, który bierze bloki danych, takie jak łańcuchy, i przestawia je na ciągi podobnych znaków. Po transformacji blok wyjściowy zawiera te same dokładne elementy danych przed jego uruchomieniem, ale różni się kolejnością. Algorytm ma tendencję do umieszczania podobnych znaków obok siebie, co ułatwia kompresowanie wynikowej kolejności danych. Dlatego jest stosowany w wielu algorytmach kompresji.
Techopedia wyjaśnia Burrows-Wheeler Transform (BWT)
Algorytm transformacji Burrowsa-Wheelera to stosunkowo nowy algorytm wynaleziony w 1994 r. Przez Michaela Burrowsa i Davida Wheelera, oparty na niepublikowanej transformacji odkrytej przez Wheelera w 1983 r., Opublikowanej w artykule „Sortowanie według bloków bezstratnego algorytmu kompresji danych”.
W najbardziej podstawowym BWT pobiera blok danych, taki jak łańcuch, dodając znak EOF, a następnie sortując wszystkie obroty tego łańcucha w kolejności leksykograficznej. Poniższy pseudokod lub kroki ilustrują algorytm:
- Utwórz tabelę zawierającą wiersze reprezentujące wszystkie możliwe obroty ciągu o jeden przyrost.
- Posortuj wszystkie wiersze alfabetycznie.
- Wyprowadza ostatnią kolumnę tabeli.
Na przykład: słowo „banan”; dodanie znaku EOF zamienia go w „banana $”, a następnie zastosujemy algorytm:
1. Utwórz tabelę z rzędami reprezentującymi wszystkie możliwe obroty:
banan $
anana $ b
nana $ ba
ana $ ban
na $ bana
$ banan
$ banan
2. Posortuj wiersze alfabetycznie / leksykograficznie na podstawie pierwszej kolumny:
$ banan
$ banan
ana $ ban
anana $ b
banan $
nana $ ba
na $ bana
3. Wróć ostatnią kolumnę jako wynik BWT: annb $ aa
Powstały ciąg jest łatwiejszy do kompresji, ponieważ powtarzające się znaki są grupowane obok siebie. Ale muszą być przechowywane dodatkowe dane z transformowanymi danymi, aby można było wykonać odwrotną transformację. Mimo że powstałe przekształcone dane są większe niż ich pierwotna postać, ale jego charakterystyka ściśliwości jest wielokrotnie zwiększana, co zasadniczo czyni ją „bezpłatną” metodą poprawy wydajności metod kompresji.
