English
Wpisy na blogu
18:56
Transformata Burrowsa-Wheelera
Transformata Burrowsa-Wheelera wykorzystywana jest przy bezstratnej kompresji danych. Przetworzone w ten sposób dane ulegają zazwyczaj znacznie lepszej kompresji, niż w przypadku samodzielnych algorytmów. Została opracowany przez Michaela Burrowsa i Davida Wheelera w 1994 roku.
Bazuje na wcześniej, nigdzie nie publikowanej transformacie Wheelera z 1983 roku. Na wejście algorytmu podaje się dane (ciąg znaków) w kodzie ASCII. Rezultatem transformaty jest posortowany blokowo ciąg znaków.
Algorytm
Algorytm operuje na blokach. Im bloki są większe (więcej danych), tym algorytm jest skuteczniejszy. Na wejście algorytmu wprowadzamy ciąg bitów, które są przetwarzane przez algorytm według schematu:
Schemat blokowy algorytmu Burrowsa-Wheelera.
W pierwszej kolejności generowane są wszystkie rotacje kompresowanego bloku. Kolejnym krokiem jest posortowanie leksykograficzne wygenerowanych łańcuchów. Aby otrzymać ciąg wyjściowy zapamiętujemy ostatni bajt każdej rotacji po sortowaniu. Aby umożliwić rozkodowanie takiego ciągu znaków należy w wyniku przekazać pozycję z posortowanej tablicy rotacji, na której znajduje się kodowana informacja.
Funkcje wewnętrzne
Przedstawiony wyżej algorytm posiada dwie funkcje wewnętrzne odpowiadające za generowanie rotacji, oraz ich sortowanie. Poniżej zaprezentowana jest struktura wewnętrzna funkcji realizująca te zadania.
Funkcja generująca - GenerateRotations
Funkcja sortująca - SortRotations
W wyniku wywołania funkcji generującej otrzymamy tablicę wielowymiarową przechowującą wszystkie rotacje bloku o rozmiarach {n} x {n}, gdzie n jest długością (length) kompresowanego bloku. Funkcja sortująca realizuje prosty algorytm sortowania leksykograficznego (ciągi znaków są sortowane rosnąco, gdzie A < Z < a < z).
Algorytm transformaty odwrotnej
Algorytm transformaty odwrotnej pozwala na odkodowanie przekształconej informacji, w taki sposób, aby otrzymać dane wejściowe. Do tego celu wymagane są zaszyfrowane dane, oraz uzyskana podczas szyfrowania pozycja na której znajduje się prawidłowe trafienie. W czasie dekodowania danych odtwarzane są wszystkie wygenerowane rotacje. Przebiega to w kilku krokach, w zależności od długości danych wejściowych. W każdym kroku dodawana jest najpierw kolumna z zakodowanym ciągiem (po znaku dla każdej rotacji), a następnie dane są sortowane leksykograficznie podobnie jak w przypadku kodowania.
Funkcja dodająca kolumnę dla bloku rotacji – AddColumn.
Na koniec wybierany jest ostateczny rezultat na podstawie przekazanego do algorytmu numeru wiersza N.
Zastosowanie
Transformata Burrowsa-Wheelera sama w sobie nie jest metodą kompresji. Wygenerowany w ten sposób ciąg bitów ma taki sam rozmiar, jak dane wejściowe. Jest on jednak często podstawą przy kompresji bezstratnej. Aby dodatkowo obniżyć poziom entropii wygenerowanych danych używa się innego algorytmu transformacji – Move To Front. Następnie kompresuje się to wszystko wybraną metodą kompresji bezstratnej. Przykładem takiej kompresji jest algorytm Huffmana, który połączony z wymienionymi transformacjami w takiej kolejności tworzy algorytm BZIP2.
Komentarze:
18:37
gardenona Dziękuję za ten opis. Właśnie piszę wstęp do projektu zespołowego i szukałąm czegoś konkretnego o Transformacie Burrowsa-Wheelera i kodowaniu move to front. Jeszcze raz dzięki :) Pozdrawim (studentka informatyki 3 roku)
Dodaj komentarz:
Nazywam się Tomasz Chudyk i witam na mojej stronie. Jestem studentem piątego roku informatyki. Moje zainteresowania krążą głównie wokół open-source, Linuksa i technologi internetowych.
