LZW

Metoda Lempel-Ziv-Welch (LZW)

Lempel-Ziv-Welch (LZW) to bezstratna metoda kompresji słownikowej, będąca modyfikacją algorytmu LZ78, opracowana w 1984 roku przez Abraham Lempela, Jacob Ziva i Welch. Charakteryzuje się prostotą implementacji i wysoką efektywnością, co sprawia, że jest szeroko stosowana w różnych aplikacjach, takich jak formaty GIF, PDF, PostScript oraz w modemach V.42bis. W przeszłości algorytm był objęty patentem, co przyczyniło się do rozwoju formatu PNG.

Zmiany w stosunku do LZ78

W algorytmie LZW, w przeciwieństwie do LZ78, na wyjściu generowany jest tylko indeks słowa z słownika, co prowadzi do skrócenia długości kodu. Słownik jest wstępnie wypełniany alfabetem, co gwarantuje znalezienie dopasowania dla co najmniej jednoliterowych słów.

Algorytm kompresji

Algorytm kompresji działa w kilku krokach:

1. Wypełnij słownik alfabetem źródła informacji.
2. c := pierwszy symbol wejściowy.
3. Dopóki są dane na wejściu:
• Wczytaj znak s.
• Jeżeli ciąg c + s znajduje się w słowniku, przedłuż c.
• Jeżeli nie, wypisz kod dla c, dodaj c + s do słownika i przypisz c := s.
4. Na końcu wypisz kod związany z c.

Algorytm dekompresji

Dekompresja jest bardziej złożona, ponieważ dekoder musi radzić sobie z przypadkami, w których ciągi są nieznane w słowniku. Proces przebiega następująco:

1. Wypełnij słownik alfabetem źródła informacji.
2. pk := pierwszy kod skompresowanych danych.
3. Wypisz ciąg związany z pk.
4. Dopóki są jeszcze kody:
• Wczytaj kod k.
• Jeżeli k jest w słowniku, dodaj do słownika ciąg (pc + pierwszy symbol ciągu słownik[k]) i wypisz ciąg.
• W przeciwnym razie dodaj do słownika (pc + pierwszy symbol pc) i wypisz ten ciąg.
• Uaktualnij pk := k.

Modyfikacje algorytmu

• LZMW – dodaje do słownika pełne słowo zamiast tylko przedłużonego.
• LZAP – dodaje wszystkie prefiksy bieżącego słowa, co przyspiesza powiększanie słownika.

Przykład kompresji

Zakodowany ciąg „abccd_abccd_acd_acd_acd_” generuje 15 indeksów: 1, 2, 3, 3, 4, 5, 6, 8, 10, 1, 9, 11, 16, 15, 10. Przy 3 bitach na symbol i 4 na indeks, współczynnik kompresji wynosi około 15%.