Algorytm LZW

LZW to bezstratny algorytm kompresji, który zastępuje powtarzające się ciągi danych krótkimi kodami. Jego najważniejsza cecha: słownik ciągów buduje się w trakcie kompresji i dekompresji, więc nie trzeba go zapisywać w pliku.

Skąd nazwa

Abraham Lempel i Jacob Ziv opisali w 1977 i 1978 roku dwie metody kompresji słownikowej, LZ77 i LZ78. Terry Welch w 1984 roku uprościł LZ78 do postaci łatwej do zrobienia sprzętowo i programowo. Tak powstało LZW, od nazwisk wszystkich trzech autorów.

Idea

Słownik zaczyna od wszystkich pojedynczych symboli. Kompresor czyta dane i szuka najdłuższego ciągu, który już jest w słowniku. Wysyła jego kod, a do słownika dopisuje ten ciąg przedłużony o następny symbol. Im dłużej trwa kompresja, tym dłuższe ciągi zna słownik i tym więcej danych mieści się w jednym kodzie.

alfabet: A = 0, B = 1 dane: A B A B A B A wynik: 0 1 2 4 słownik po drodze: AB = 2, BA = 3, ABA = 4

Siedem symboli zamieniło się w cztery kody. Szczegółowy przebieg krok po kroku jest na stronach kompresja LZW i dekompresja LZW.

Dlaczego słownika nie trzeba zapisywać

Dekompresor zaczyna od tego samego słownika co kompresor (pojedyncze symbole) i dopisuje do niego wpisy według tej samej reguły, czytając kody. Po każdym kroku oba słowniki są identyczne. Jest jeden wyjątek: kompresor może wysłać kod, który dekompresor dopisze dopiero w tym samym kroku. Ten przypadek, zwany KwKwK, opisuje strona o dekompresji.

Właściwości

Bezstratny: dane po dekompresji są identyczne z oryginałem.
Jednoprzebiegowy: kompresja i dekompresja czytają dane raz, od początku do końca.
Adaptacyjny: nie trzeba wcześniej znać statystyki danych, słownik uczy się ich sam.
Dobry dla powtarzalnych danych: grafiki z płaskimi plamami koloru, tekst. Słaby dla zdjęć i szumu, gdzie ciągi rzadko się powtarzają.
Ograniczony słownik: w GIF najwyżej 4096 wpisów (kody 12-bitowe). Gdy słownik się zapełni, zaczyna się go od nowa (zob. LZW w GIF).

Gdzie się go używa

Format	Uwagi
GIF	kody o zmiennej długości 3..12 bitów, kody specjalne "wyczyść" i "koniec"
TIFF	jedna z metod kompresji, często z predyktorem różnicowym
PDF, PostScript	filtr LZWDecode, dziś wypierany przez Deflate
`compress` w Uniksie	pliki .Z

Patent

Na LZW istniał patent firmy Unisys. W 1994 roku Unisys i CompuServe ogłosiły, że programy zapisujące GIF muszą płacić licencję. W odpowiedzi w 1995 roku powstał format PNG, z kompresją Deflate wolną od patentów. Patent wygasł w USA w 2003 roku, a w Europie i Japonii w 2004. GIF jest od tego czasu wolny, ale PNG zdążył zastąpić go w większości zastosowań poza animacjami.