AlgorytmyTeoriaSortowanieNumeryczneSzyfrowanieKompresjaGrafikaLiczby kontrolneTurbo PascalC++JavaVisual Basic 6 Aplikacje internetowe MySQL Excel DOS

Algorytmy: Algorytmy kompresji

Kompresja to zmniejszenie rozmiaru pliku za pomocą odpowiedniego algorytmu kompresującego. Kompresja danych przeprowadzana jest poprzez ich zagęszczenie dzięki procesowi ponownego matematycznego kodowania ich struktury. Aby kompresja miała sens zagęszczanie danych powinno być w pełni odwracalne.

Kompresja bezstratna (zwana też ilościową) - rodzaj kompresji danych, w której po rozkompresowaniu danego zbioru jest on identyczny z jego wcześniejszą wersją (przed spakowaniem) czyli nie wystąpiła utrata jakichkolwiek informacji. Metody kompresji bezstratnej dzieli się na probalistyczne i słownikowe.

Kompresja stratna (zwana też jakościową) - rodzaj kompresji danych, w której po rozpakowaniu danego zbioru nastąpiła utrata części informacji.

Dekompresja to proces przywracający skompresowane pliki danych do ich pierwotnej postaci w jakiej zostały utworzone.

Kodowanie Huffmana należy do najprostszych algorytmów kompresji danych.

Mamy zbiór n symboli, z którego każdy występuje określoną ilość razy w kodowanym ciągu (zbiorze).

Pierwszym krokiem jest określenie częstości wystąpienia każdego symbolu w kodowanym ciągu (zbiorze).

Kolejnym krokiem jest wybranie z tej listy dwóch symboli o najmniejszych wagach i zastąpienie ich symbolem, dla którego stają się one odpowiednio lewą i prawą gałęzią drzewa. Nowy (połączony) symbol przyjmuje częstotliwość (wagę) równą sumie częstotliwości (wag) symboli, z których został utworzony. Otrzymujemy więc zbiór symboli o liczebności o 1 mniejszej od zbioru wyjściowego.
Następnie powtarzamy powyższą operację dla nowo otrzymanego zbioru symboli. Zastępowanie par elementów o najmniejszych częstotliwościach trwa do chwili, gdy na liście pozostanie dokładnie jeden element - korzeń drzewa kodów.
Częstotliwość (waga) korzenia jest równa sumie częstotliwości (wagom) wszystkich symboli w kodowanym ciągu.

Następnym krokiem jest znalezienie kodów dla każdego symbolu występującego w ciągu. Robimy to w następujący sposób: podczas przechodzenia drzewa od góry do dołu przy każdym skręcie w lewo do kodu dołączamy 0, a przy skręcie w prawo - 1.
Długość kodu każdego symbolu zależy więc od ilości jego wystąpień w kodowanym ciągu (zbiorze): im większa ilość wystąpień tym krótszy kod i odwrotnie.

Ostatnim krokiem jest kompresja polegająca na zastąpieniu każdego symbolu ciągu jego kodem zapisanym w postaci zer i jedynek na kolejnych bitach.

Dekompresja wymaga posiadania drzewa kodów, a odtworzenie danych polega na czytaniu kolejnych bitów ze strumienia danych i jednoczesnym przechodzeniu drzewa zgodnie z przejętą konwencją (lewo/prawo). Po dojściu do pojedynczego symbolu zapisujemy go do ciągu wynikowego i powracamy do korzenia drzewa.

W opisie algorytmu celowo użyte jest słowo symbol. Nie musi to być bowiem znak (bajt). Symbolem może być dowolny podciąg, słowo, struktura - słowem coś, co dla kompresowanych danych jest charakterystyczne.

Przykład:
Poniższy rysunek przedstawia schemat kodowania ciągu, w którym występują symbole:
        A - 1 raz,
        B - 2 razy,
        C - 3 razy,
        D - 4 razy.



Tabela kodów przedstawia się więc następująco:
        symbol kod  długość kodu [bity]
          A    000      3
          B    001      4
          C    01       2
          D    1        1
Jak widać symbol D (występujący najczęściej) kodujemy za pomocą jednego tylko bitu.

Kodowanie RLE jest stosowane do kompresji danych, w których kolejno występuje wiele identycznych znaków.

Opis algorytmu kodowania:

1. Ustal symboliczny znacznik lub znajdź najrzadziej występujący znak w ciągu i zapamiętaj go jako znacznik oraz zapisz w kodowanym ciągu.
    
2. Odczytuj z ciągu kolejne znaki i zliczaj ilość ich wystąpień tak długo, jak długo czytane znaki są identyczne.
    
   1. Jeżeli znakiem jest znacznik, to zapisz: znacznik, liczba wystąpień, znak.
       
   2. Jeżeli ilość wystąpień jest mniejsza niż 3, to zapisz cały ciąg.
       
   3. Jeżeli ilość wystąpień jest większa niż 2, to zapisz w postaci: znacznik, liczba wystąpień, znak.
       
3. Powtarzaj punkt 2, aż dojdziesz do końca kompresowanego łańcucha (pliku).
    

Opis algorytmu dekodowania:

1. Odczytaj znacznik lub - jeżeli ustalony - może być na stałe zakodowany.
    
2. Odczytaj znak zakodowanego ciągu.
    
   1. Jeżeli jest to znacznik, to odczytaj następną liczbę n oraz kolejny znak c i zapisz n razy znak c.
       
   2. Jeżeli jest to inny znak, to zapisz go.
       
3. Powtarzaj punkt 2, aż dojdziesz do końca kompresowanego łańcucha (pliku).
    

Przykład:
Kodowany łańcuch znaków:
	aaabaaa#bbbxxzbtttttwwwwwssssss#####bbbbbaaaaababatttttyaaaaaq##

Ustalony znacznik:
	#

Zakodowany łańcuch:
	#3ab#3a#1##3bxxzb#5t#5w#6s#5##5b#5ababa#5ty#5aq#2#