First page Back Continue Last page Overview Graphics

Podstawowe kompresje

LZW – najskuteczniejsza kompresja bezstratna, działa na zasadzie budowy słownika ciągów pikseli: każdy ciąg w słowniku jest identyfikowany przez wartość kodu, a rezultatem działania operacji jest lista kodów ze słownika. Innymi słowy zmniejszamy rozmiar pliku poprzez skrócony opis poziomej linii pikseli tego samego koloru (informacja o długości sekwencji i kolorze).

Notes:

LZW-kiedy kompresor czyta piksele, znajduje najdłuższy ciąg pikseli, który może dopasować do słownika. Zawsze ma więc „próbne dopasowanie” ciągu pikseli, które już zostały wczytane, ale dla których kod nie został jeszcze wysłany na wyjście. Za każdym razem, gdy kompresor wczytuje piksel wykonuje kilka operacji:
Dodaje piksel do próbkowanego ciągu dopasowanego i sprawdza, czy w słowniku istnieje dopasowanie do nowego ciągu próbnego. Jeśli tak, to zapamiętuje kod odpowiadający nowemu próbnemu ciągowi dopasowanemu i przechodzi do następnego piksela.
Jeśli nowy próbny ciąg nie znajduje się w słowniku, wysyłany jest na wejście kod starego ciągu. Następnie nowy ciąg próbny, czyli stary ciąg plus wczytany piksel jest umieszczany w słowniku dla przyszłego użytku. Stary ciąg jest usuwany ze słownika i proces rozpoczyna się od nowa z nowym próbnym ciągiem dopasowanym, składającym się z jednego, ostatnio przeczytanego piksela.
Kompresor kontynuuje ten proces, aż przeczyta wszystkie dane wejściowe, na koniec zapisuje kod ostatniego próbnego dopasowywania i kod końca pliku.