Algorytm LZW

Powtarzające się sekwencje w kompresji bezstratnej

Kodowanie Huffmana skraca reprezentację często występujących symboli, lecz analizuje przede wszystkim pojedyncze symbole. Dane zawierają również powtarzające się sekwencje, frazy i wzorce. W zdaniu "Król Karol kupił królowej Karolinie korale koloru koralowego" zbitka liter "król" pojawia się dwukrotnie, a "koral" dwukrotnie. Kodowanie symboli uwzględnia częstość liter k, r, ó i l, lecz nie opisuje bezpośrednio całej powtarzającej się sekwencji.

Do wykorzystania takiej redundancji służą algorytmy kompresji słownikowej. Zastępują one kolejne wystąpienia sekwencji krótkim kodem wpisu słownika. Jednym z algorytmów tej rodziny jest Lempel-Ziv-Welch, czyli LZW. Kod reprezentuje całą sekwencję, więc jego długość nie zależy bezpośrednio od liczby znaków w zastępowanej frazie.

Algorytm LZW i słownik adaptacyjny

Terry Welch opisał LZW w 1984 roku jako rozwinięcie algorytmu LZ78 autorstwa Abrahama Lempela i Jacoba Ziva. Koder buduje słownik powtarzających się fraz podczas odczytu danych. W typowej konfiguracji wystarcza jeden przebieg wejścia, a słownik nie musi być dołączany do wyniku. Dekoder odtwarza go z kodów, jeśli zna ten sam alfabet początkowy i sposób numerowania wpisów. Nowy wpis ma postać rozpoznanej sekwencji z dołączonym kolejnym znakiem, dzięki czemu obie strony tworzą wpisy w tej samej kolejności.

Mechanizm działania

LZW utrzymuje tablicę sekwencji znaków, czyli słownik mapujący sekwencje na kody numeryczne. Kolejne kroki są następujące.

1. Inicjalizacja słownika: Słownik jest wstępnie zapełniony pojedynczymi znakami alfabetu. Dla danych 8-bitowych może zawierać 256 wpisów o kodach od 0 do 255. Format może rezerwować część kodów na sygnały sterujące, więc szczegóły zależą od formatu strumienia.
2. Przetwarzanie strumienia wejściowego: Algorytm odczytuje dane znak po znaku i szuka najdłuższej sekwencji obecnej w słowniku. Przy powtarzających się danych taka sekwencja szybko obejmuje kilka lub kilkanaście znaków.
3. Główna pętla: Niech rozpoznana sekwencja będzie oznaczona jako P. Po odczytaniu znaku C algorytm sprawdza, czy połączenie P + C znajduje się w słowniku.
   • Jeśli tak: Algorytm zastępuje P przez P + C i odczytuje następny znak.
   • Jeśli nie: Połączenie nie jest jeszcze wpisem słownika. Algorytm wykonuje dwie czynności:
     1. Wypisuje kod numeryczny ostatniej znanej sekwencji, P.
     2. Dodaje sekwencję P + C do słownika pod następnym dostępnym kodem.
4. Przejście do następnej sekwencji: Po tej operacji algorytm ustawia pojedynczy znak C jako nowe P. Pętla trwa do końca strumienia wejściowego. Po zakończeniu wejścia koder wypisuje jeszcze kod ostatniej niepustej sekwencji.

Przykład kodowania LZW

Poniższy przykład pokazuje działanie kodera dla ciągu KRÓL KAROL KUPIŁ KRÓLOWEJ.

Słownik początkowy zawiera wpisy dla znaków alfabetu. Nowe kody numerujemy od 256. Dla uproszczenia wymieniono tylko używane znaki: K, R, Ó, L, spacja, A, O, U, P, I, Ł, W, E, J.

Tabela przedstawia kolejne stany kodera.

Wynik:Początkowo wyjście zawiera kody pojedynczych znaków. Wraz z rozbudową słownika powtarzające się sekwencje, takie jak "KRÓL" i "OWEJ", mogą być reprezentowane jednym kodem. W pokazanej konfiguracji kody mają zmienną szerokość. Po przekroczeniu zakresu kodów 9-bitowych, czyli po wartości 511, szerokość może wzrosnąć do 10 bitów. Tabela pokazuje początkowy fragment przebiegu, a wielokropek oznacza dalsze wpisy tworzone dla reszty zdania. Rzeczywisty zapis bitowy zależy od uzgodnionej szerokości kodu i sposobu pakowania bitów w strumieniu. Przejście z 9 do 10 bitów oznacza większy kod, lecz nie zmienia zasady wyszukiwania sekwencji.

Dekompresja LZW

Dekoder otrzymuje kody i rozpoczyna pracę z takim samym słownikiem początkowym jak koder. Odtwarza tekst, wyprowadzając znane sekwencje i rekonstruując nowe wpisy na podstawie kolejnych kodów. Pierwszy kod jest obsługiwany jako sekwencja początkowa, a wpis słownikowy można utworzyć dopiero po odebraniu następnego kodu.

Dla każdego kodu dekoder wyprowadza odpowiadającą mu sekwencję. Gdy istnieje poprzednia sekwencja i kolejna sekwencja, tworzy nowy wpis przez połączenie poprzedniej sekwencji z pierwszym znakiem kolejnej. Wpis jest dodawany po przetworzeniu kodu, którego sekwencja dostarcza ten pierwszy znak, więc numeracja pozostaje zgodna z koderem.

W szczególnym przypadku, znanym jako problem KWKWK, dekoder otrzymuje kod następnego wpisu, którego nie zdążył jeszcze dodać. Sytuacja występuje, gdy koder utworzył sekwencję i od razu jej użył. Nieznana sekwencja jest wtedy równa poprzedniej sekwencji z dołączonym jej pierwszym znakiem. Ta reguła pozwala odtworzyć wpis i zachować synchronizację. W formatach z kodem czyszczenia jego odebranie przywraca słownik początkowy i ogranicza skutki utraty synchronizacji.

Zastosowanie: format GIF

LZW jest częścią formatu GIF (Graphics Interchange Format), który zapisuje dane obrazu jako indeksy palety. Właściwości tego formatu sprzyjają kompresji słownikowej.

• Ograniczona paleta kolorów: Obraz GIF może zawierać najwyżej 256 kolorów. LZW przetwarza indeksy palety o szerokości do 8 bitów, więc początkowy alfabet ma mały, stały rozmiar. W strumieniu GIF występują również kod czyszczenia i kod końca informacji, a szerokość kodu kompresji zaczyna się od rozmiaru kodu początkowego powiększonego o 1 i rośnie maksymalnie do 12 bitów. Kod czyszczenia może pojawić się podczas danych obrazu, a kod końca informacji zamyka ich sekwencję.
• Redundancja przestrzenna: Logotypy i diagramy często zawierają duże jednolite obszary lub powtarzalne wzory. Odczyt wierszami zamienia je w powtarzające się sekwencje indeksów, które LZW może zastępować wpisami słownika.

Właściwości i ograniczenia LZW

LZW pozostaje przykładem adaptacyjnej kompresji słownikowej. Jego użyteczność zależy od rodzaju danych i parametrów strumienia.

Zalety

• Jeden przebieg: Koder nie musi analizować całego pliku przed rozpoczęciem pracy. Słownik jest rozbudowywany podczas odczytu, co pasuje do przetwarzania strumieniowego.
• Brak transmisji słownika: Przy zgodnych parametrach początkowych dekoder może odbudować słownik z kodów, więc nie trzeba przesyłać pełnej tablicy.
• Prosta implementacja: Zasada działania jest nieskomplikowana, a dekodowanie wymaga niewielkiej liczby operacji.

Ograniczenia

• Pełny słownik: Rozmiar słownika zależy od formatu. W strumieniach z 12-bitowymi kodami limit wynosi 4096 wpisów. Po jego osiągnięciu implementacja może zatrzymać dodawanie, wyczyścić słownik albo zastosować inną regułę, co wpływa na stopień kompresji. Limit 4096 dotyczy konfiguracji z maksymalnie 12-bitowym kodem, nie każdej implementacji LZW.
• Wrażliwość na błędy: Błąd bitowy może rozbieżnić słownik dekodera i kodera. Uszkodzenie może propagować się do następnego kodu czyszczenia lub innego mechanizmu ponownej synchronizacji.
• Historia patentów: Przez wiele lat LZW podlegał patentom, między innymi patentowi firmy Unisys. Spory licencyjne dotyczyły oprogramowania używającego GIF i LZW. Format PNG stosuje Deflate, czyli połączenie LZ77 i kodowania Huffmana.

Podstawowe patenty LZW wygasły. W wielu zastosowaniach używa się dziś Deflate lub nowszych wariantów LZ, a mechanizm adaptacyjnego słownika pozostaje ważnym przykładem kompresji bezstratnej.