Nowe Podejście do Redundancji: Poza Pojedyncze Symbole

W naszej eksploracji kompresji bezstratnej przeanalizowaliśmy metody statystyczne, takie jak kodowanie Huffmana, które w genialny sposób redukują rozmiar danych poprzez przypisywanie krótszych kodów do częściej występujących symboli. To podejście jest potężne, ale skupia się na prawdopodobieństwie pojedynczych znaków. Jednakże, dane w świecie rzeczywistym zawierają inny, bardziej ustrukturyzowany rodzaj nadmiarowośi: powtarzanie się całych sekwencji, fraz i wzorców. Rozważmy polskie zdanie "Król Karol kupił królowej Karolinie korale koloru koralowego"; zbitka liter "król" pojawia się dwukrotnie, a "koral" aż trzykrotnie. Metoda statystyczna skompresowałaby każdą z tych instancji na podstawie wysokiej częstotliwości liter k, r, ó, l, ale straciłaby okazję do zauważenia, że cała czteroliterowa sekwencja powróciła.

Aby wykorzystać ten rodzaj redundancji strukturalnej, potrzebujemy innej klasy algorytmów, znanych jako kompresja słownikowa. Filozofia stojąca za tymi metodami jest prosta i intuicyjna: po co pisać tę samą długą frazę w kółko, skoro można po prostu wskazać na miejsce, w którym napisaliśmy ją po raz pierwszy? Jednym z najbardziej eleganckich i historycznie znaczących algorytmów w tej rodzinie jest algorytm Lempel-Ziv-Welch, czyli LZW.

Algorytm LZW: Budowanie Słownika w Locie

Opracowany przez Terry'ego Welcha w 1984 roku, LZW jest ulepszeniem wcześniejszego algorytmu LZ78 stworzonego przez Abrahama Lempela i Jacoba Ziva. Jego geniusz tkwi w zdolności do adaptacyjnego budowania słownika powtarzających się fraz podczas przetwarzania danych wejściowych. Oznacza to, że wymaga on tylko jednego przebiegu przez dane i, co kluczowe, nie musi przesyłać samego słownika wraz ze skompresowanym wynikiem. Dekompresor jest w stanie idealnie odtworzyć dokładnie ten sam słownik na podstawie samych skompresowanych danych.

Mechanizm Działania

Algorytm LZW utrzymuje tablicę ciągów znaków, czyli słownik, który mapuje sekwencje znaków na kody numeryczne. Proces działa następująco:

1. Inicjalizacja Słownika: Słownik jest wstępnie zapełniony wszystkimi możliwymi pojedynczymi znakami. W przypadku standardowych danych 8-bitowych oznacza to, że słownik początkowo zawiera 256 wpisów, mapujących każdy znak od kodu 0 do 255.
2. Przetwarzanie Strumienia Wejściowego: Algorytm odczytuje dane wejściowe znak po znaku, próbując znaleźć najdłuższą możliwą sekwencję, która już istnieje w jego słowniku.
3. Główna Pętla: Załóżmy, że najdłuższa znaleziona do tej pory sekwencja to P. Algorytm odczytuje następny znak, C. Następnie sprawdza, czy połączona sekwencja P + C istnieje w słowniku.
   • Jeśli TAK: Sekwencja jest rozpoznana. Algorytm aktualizuje P do postaci P + C i czeka na następny znak, kontynuując poszukiwania jeszcze dłuższej znanej sekwencji.
   • Jeśli NIE: Osiągnięto koniec rozpoznanej sekwencji. Algorytm wykonuje dwie czynności:
     1. Wypisuje na wyjście kod numeryczny dla ostatniej znanej sekwencji, P.
     2. Dodaje nową, nierozpoznaną sekwencję P + C do słownika z następnym dostępnym kodem numerycznym.
4. Reset i Powtórka: Następnie algorytm resetuje się, rozpoczynając nowe poszukiwania od pojedynczego znaku C jako nowej początkowej sekwencji P. Pętla jest kontynuowana, aż cały strumień wejściowy zostanie przetworzony.

Kodowanie LZW: Szczegółowy Przykład

Abstrakcyjne zasady stają się znacznie jaśniejsze dzięki szczegółowemu przykładowi. Skompresujmy znane polskie łamańce językowe: KRÓL KAROL KUPIŁ KRÓLOWEJ.

Nasz słownik na początku zawiera wpisy dla każdego znaku z naszego alfabetu. Przypiszmy następne dostępne kody, zaczynając od 256. Dla uproszczenia wymieńmy tylko znaki, których będziemy używać: K, R, Ó, L, spacja, A, O, U, P, I, W, E, J.

Będziemy śledzić stan kodera krok po kroku.

Wynik Końcowy:Początkowo wyjście składa się z kodów pojedynczych znaków. Jednak w miarę jak algorytm przetwarza tekst, jego słownik wzbogaca się o coraz dłuższe, powtarzające się sekwencje (jak "KRÓL" czy "OWEJ"). Przy drugim i kolejnym wystąpieniu tych fraz algorytm wypisze już pojedynczy kod, reprezentujący całą sekwencję, co prowadzi do znaczącej kompresji. Kody numeryczne byłyby reprezentowane binarnie za pomocą zmiennej liczby bitów; gdy słownik przekroczy 511 wpisów, na przykład kody zmienią się z 9-bitowych na 10-bitowe.

Proces Dekompresji LZW

Elegancja LZW w pełni ujawnia się podczas dekompresji. Dekoder otrzymuje sekwencję kodów i, zaczynając z tym samym początkowym słownikiem pojedynczych znaków, idealnie odtwarza oryginalny tekst. Robi to poprzez wnioskowanie o nowych wpisach słownikowych z przychodzących kodów.

Ogólna zasada brzmi: dla każdego otrzymanego kodu, wypisz na wyjście ciąg, który on reprezentuje z bieżącego słownika. Następnie utwórz nowy wpis w słowniku, łącząc ciąg, który właśnie wypisałeś, z pierwszym znakiem następnego ciągu, który zaraz wypiszesz.

Istnieje specjalny przypadek, gdy dekoder otrzymuje kod, którego jeszcze nie ma w swoim słowniku. Dzieje się to tylko wtedy, gdy sekwencja jest tworzona, a następnie natychmiast używana przez koder. Dekoder może sobie z tym poradzić, wiedząc, że nieznany znak musi być taki sam jak pierwszy znak poprzednio wypisanego ciągu. To zapewnia, że synchronizacja "krok w krok" między koderem a dekoderem nigdy nie zostaje zerwana.

Zastosowanie w Praktyce: Format Obrazów GIF

LZW stał się powszechnie znany dzięki swojej implementacji w formacie GIF (Graphics Interchange Format). Jest on szczególnie dobrze dopasowany do tego formatu z kilku powodów:

• Ograniczona Paleta Kolorów: Obrazy GIF są ograniczone do maksymalnie 256 kolorów. Algorytm LZW nie operuje na surowych wartościach kolorów, ale na 8-bitowych wartościach indeksów, które wskazują na kolor w palecie. Oznacza to, że początkowy rozmiar słownika jest mały i stały.
• Redundancja Przestrzenna: Obrazy generowane komputerowo, takie jak logotypy czy diagramy, często mają duże obszary jednolitego koloru lub powtarzające się wzory. Gdy dane obrazu są odczytywane linia po linii, te wzory przestrzenne zamieniają się w długie, powtarzalne sekwencje indeksów kolorów w strumieniu wejściowym, które LZW potrafi bardzo skutecznie kompresować.

Mocne Strony, Słabości i Dziedzictwo

Dziedzictwo LZW w świecie kompresji jest znaczące, ale ważne jest również zrozumienie jego kompromisów.

Mocne Strony

• Algorytm Jednoprzebiegowy: Nie musi analizować całego pliku z góry. Buduje swój model adaptacyjnie, co czyni go odpowiednim do zastosowań strumieniowych.
• Brak Transmisji Słownika: Zdolność dekompresora do odbudowy słownika jest główną zaletą, eliminującą znaczący narzut.
• Względna Prostota i Szybkość: Algorytm jest koncepcyjnie prosty i generalnie szybki, zwłaszcza podczas dekompresji.

Słabości

• Problem Pełnego Słownika: Słownik ma stały rozmiar (np. 4096 wpisów dla kodów 12-bitowych). Jeśli dane wejściowe są bardzo zróżnicowane, słownik może się zapełnić. Różne implementacje radzą sobie z tym na różne sposoby: niektóre przestają dodawać nowe wpisy, inne resetują słownik, a jeszcze inne używają bardziej złożonych strategii czyszczenia. Może to wpływać na wydajność kompresji.
• Wrażliwość na Błędy: Pojedynczy błąd bitu w skompresowanym strumieniu kodów może spowodować, że słownik dekompresora straci synchronizację ze słownikiem kodera, co prowadzi do katastrofalnej awarii dekompresji od tego momentu.
• Historia Patentowa: Przez wiele lat algorytm LZW był chroniony patentami, w szczególności patentem należącym do firmy Unisys. Doprowadziło to do kontrowersji i problemów licencyjnych, zwłaszcza dla formatu GIF, i pobudziło rozwój wolnych od patentów alternatyw, takich jak format PNG, który używa algorytmu Deflate (kombinacja LZ77 i kodowania Huffmana).

Choć teraz wolny od ograniczeń patentowych, LZW został w dużej mierze wyparty przez bardziej zaawansowane warianty LZ i inne algorytmy, takie jak Deflate. Jednak jego historyczne znaczenie jest niezaprzeczalne, a jego podstawowe zasady adaptacyjnej kompresji słownikowej pozostają kamieniem węgielnym redukcji danych bezstratnych.