Nowa Strategia Znajdowania Redundancji: Poza Pojedyncze Symbole

W naszej eksploracji kompresji bezstratnej przeanalizowaliśmy metody statystyczne, takie jak kodowanie Huffmana, które osiągają kompresję poprzez skupienie się na częstotliwości występowania poszczególnych symboli. To podejście jest bardzo skuteczne, ale pomija bardziej ustrukturyzowany, a często i bardziej znaczący rodzaj nadmiarowości w rzeczywistych danych: powtarzanie się całych sekwencji, fraz i wzorców bajtów.

Rozważmy prosty plik tekstowy zawierający zdanie: "W Szczebrzeszynie chrząszcz brzmi w trzcinie". Kompresor statystyczny zauważyłby wysoką częstotliwość znaków 'z', 's' i 'r', przypisując im krótkie kody. Jednakże nie wykorzystałby on faktu, że cała sekwencja liter "rz" pojawia się wielokrotnie. Intuicyjnie wydaje się to nieefektywne, aby ponownie kodować tę powszechną zbitkę znak po znaku przy jej kolejnym wystąpieniu. Dlaczego nie powiedzieć po prostu: "powtórz sekwencję, którą widzieliśmy wcześniej"? Ta prosta idea jest kamieniem węgielnym kompresji słownikowej, prawdopodobnie najbardziej wszechstronnej i szeroko stosowanej rodziny algorytmów kompresji bezstratnej obecnie. Te algorytmy, których pionierami byli Jacob Ziv i Abraham Lempel w latach 70., stały się silnikami napędzającymi uniwersalne standardy, takie jak ZIP, GZIP i PNG.

Algorytm LZ77: Kompresja z Przesuwnym Oknem

Opublikowany w 1977 roku algorytm LZ77 jest pierwszą z dwóch fundamentalnych prac Lempela i Ziva. Jego geniusz tkwi w prostocie i wydajności. Zamiast budować ogromny, jawny słownik każdej napotkanej frazy, używa on sprytnej, stale aktualizowanej "pamięci" danych, które właśnie przetworzył.

Mechanizm Działania: Przesuwne Okno

Algorytm działa przy użyciu koncepcji zwanej przesuwnym oknem, które jest symboliczną ramką poruszającą się nad danymi wejściowymi. Okno to jest podzielone na dwie części:

• Bufor Wyszukiwania: To "historia" lub "niejawny słownik". Jest to bufor o stałym rozmiarze (np. kilka kilobajtów), zawierający najświeżej zakodowane dane. Algorytm będzie przeszukiwał ten bufor w poszukiwaniu powtarzających się sekwencji.
• Bufor Wejściowy: Jest to mniejszy bufor zawierający następny blok danych, który ma zostać zakodowany. Algorytm pobiera znaki z tego bufora i próbuje znaleźć dopasowanie w buforze wyszukiwania.

Proces Kodowania LZ77 w Szczegółach

Kodowanie przebiega w ciągłej pętli:

1. Algorytm patrzy na znaki na początku bufora wejściowego.
2. Następnie starannie przeszukuje cały bufor wyszukiwania, od początku do końca, aby znaleźć najdłuższe możliwe dopasowanie dla sekwencji rozpoczynającej się w buforze wejściowym.
3. Na podstawie wyniku wyszukiwania podejmuje decyzję i wypisuje jeden z dwóch rodzajów tokenów:
   • Jeśli NIE znaleziono dopasowania: (lub dopasowanie jest krótsze niż minimalny próg, np. 3 znaki), algorytm wypisuje token literału. Jest to zazwyczaj nieskompresowany znak z bufora wejściowego, często poprzedzony flagą bitową w celu odróżnienia go od wskaźnika.
   • Jeśli dopasowanie ZOSTANIE znalezione: Algorytm wypisuje token wskaźnika. To nie są same dane, ale zwarty odnośnik, który mówi "wróć i skopiuj z przeszłości". Wskaźnik ten zazwyczaj składa się z trzech części: flagi bitowej, przesunięcia (lub odległości) i długości. Na przykład: $(0, \text{odległość}, \text{długość})$.
     • Odległość wskazuje, ile bajtów należy cofnąć się w buforze wyszukiwania, aby znaleźć początek dopasowania.
     • Długość wskazuje, ile bajtów należy skopiować od tego miejsca.
4. Na koniec algorytm przesuwa okno. Przesuwa przetworzone dane (pojedynczy znak literału lub całą dopasowaną sekwencję o długości $L$) z bufora wejściowego do bufora wyszukiwania, a nowe dane z pliku wejściowego są odczytywane, aby uzupełnić bufor wejściowy. Proces powtarza się.

Magia Samonakładających się Dopasowań

Prawdziwie potężną cechą LZ77 jest jego zdolność do niezwykle wydajnego kodowania serii powtarzających się wzorców. Rozważmy ciąg "abababababab". Po przetworzeniu początkowego "ab", które znajdzie się w buforze wyszukiwania, bufor wejściowy widzi "ababababab". Algorytm może znaleźć sekwencję "ab" w buforze wyszukiwania, ale może wydać wskaźnik, który mówi "wróć o 2 bajty i skopiuj 10 bajtów".

Naiwny dekompresor mógłby się pogubić, ale dekompresor LZ77 działa bajt po bajcie. Wraca o 2 bajty, kopiuje 'a', potem 'b'. Zanim będzie musiał skopiować trzeci bajt, pierwsze 'a', które właśnie zapisał, jest już w historii i dostępne do skopiowania. To pozwala dekompresorowi na replikację długich serii przy użyciu pojedynczego, krótkiego wskaźnika, co czyni LZ77 niezwykle skutecznym dla danych z prostymi powtórzeniami.

Dekompresja: Prosta i Szybka

Piękno LZ77 tkwi w jego szybkiej i prostej dekompresji. Dekompresor również utrzymuje bufor wyszukiwania (który jest po prostu historią tego, co już zapisał na wyjściu). Kiedy otrzymuje token:

• Jeśli to token literału, po prostu dołącza znak literału do swojego wyjścia.
• Jeśli to token wskaźnika (odległość, długość), cofa się o 'odległość' znaków w swoim własnym wyjściu i kopiuje 'długość' znaków na koniec.

Ten proces jest niezwykle szybki, ponieważ obejmuje tylko proste kopiowanie pamięci do pamięci, co jest głównym powodem popularności schematów opartych na LZ77.

Rodzina LZ78 i LZW: Użycie Jawnego Słownika

Drugi fundamentalny algorytm, LZ78 (opublikowany w 1978 r.), oraz jego niezwykle udany następca, LZW (Lempel-Ziv-Welch, opracowany w 1984 r.), przyjmują inne podejście. Zamiast używać ostatnich wyników jako niejawnego słownika, budują one jawną tabelę fraz napotkanych do tej pory.

Mechanizm Działania: Budowanie i Odwoływanie się do Księgi Fraz

Omówiliśmy algorytm LZW szczegółowo w jego własnej, dedykowanej sekcji. Podsumujmy jego główną filozofię i porównajmy ją z LZ77:

1. Inicjalizacja: Algorytm zaczyna od słownika wstępnie wypełnionego wszystkimi możliwymi pojedynczymi symbolami.
2. Budowanie Fraz: Odczytuje dane wejściowe i znajduje najdłuższą sekwencję znaków, która aktualnie znajduje się w słowniku.
3. Wyjście i Aktualizacja: Wypisuje na wyjście kod słownikowy dla tej najdłuższej znalezionej sekwencji. Następnie tworzy nowy wpis w słowniku składający się z tej sekwencji plus kolejnego znaku z wejścia.

LZ77 a LZW: Kluczowe Różnice w Podejściu

Chociaż oba są koderami słownikowymi, ich strategie są odmienne. LZ77 zastępuje powtórzenia parą `(odległość, długość)` wskazującą wstecz w surowym strumieniu danych. LZW zastępuje powtórzenia pojedynczym kodem całkowitoliczbowym, który odnosi się do wpisu w oddzielnie zarządzanym słowniku fraz. Oznacza to, że LZW może być bardziej zwięzły, jeśli dokładnie te same wieloznakowe "słowa" pojawiają się często w całym pliku, podczas gdy LZ77 może być skuteczniejszy w wychwytywaniu przypadkowych powtórzeń, które niekoniecznie tworzą spójne "słowa".

Nowoczesne Warianty i Hybrydy: Najlepsze z Obu Światów

Dzisiejsze najskuteczniejsze i najczęściej używane uniwersalne kompresory bezstratne rzadko są czystymi implementacjami tych wczesnych algorytmów. Zamiast tego są to zaawansowane hybrydy, które łączą siłę dopasowywania fraz koderów słownikowych z finezją statystyczną koderów entropijnych.

DEFLATE: Koń Roboczy Internetu (ZIP, GZIP, PNG)

Algorytm DEFLATE jest prawdopodobnie najbardziej udanym algorytmem kompresji w historii. Jest to silnik napędzający wszechobecne formaty plików ZIP i GZIP oraz używany do kompresji bezstratnej w formacie obrazów PNG. DEFLATE to genialne połączenie LZ77 i kodowania Huffmana.

1. Etap 1: Eliminacja Duplikatów LZ77: Pierwszym etapem DEFLATE jest standardowy kompresor LZ77. Skanuje on dane za pomocą przesuwnego okna (zazwyczaj 32KB) i zastępuje powtarzające się ciągi wskaźnikami `(długość, odległość)`. Każdy znak, który nie jest częścią powtarzającej się sekwencji, jest przekazywany jako literał, nieskompresowany znak.
2. Etap 2: Kodowanie Entropijne Huffmana: Wyjście etapu LZ77 to mieszany strumień literałów i wskaźników. Ten strumień sam w sobie jest wysoce redundantny. Na przykład pewne długości dopasowań są znacznie częstsze niż inne, a pewne literały (jak 'e' i spacja) będą bardzo częste. DEFLATE wykorzystuje to, przepuszczając ten mieszany strumień przez etap kodowania Huffmana. Dynamicznie buduje dwa drzewa Huffmana: jedno do kompresji literałów i długości dopasowań, a drugie do kompresji odległości dopasowań.

To dwuetapowe podejście jest niezwykle skuteczne. Etap LZ77 radzi sobie z powtórzeniami strukturalnymi na dużą skalę, podczas gdy etap Huffmana radzi sobie z redundancją statystyczną na małą skalę pozostałych danych i samych wskaźników.

LZ4: Pogoń za Ostateczną Szybkością

Chociaż DEFLATE zapewnia doskonałą kompresję, jego poszukiwanie najdłuższego dopasowania może być czasochłonne. W wielu nowoczesnych zastosowaniach, zwłaszcza tych zajmujących się ogromnymi ilościami danych w pamięci, szybkość dekompresji jest czynnikiem najważniejszym. Dla tej potrzeby opracowano algorytmy takie jak LZ4.

LZ4 jest wariantem LZ77, który priorytetowo traktuje szybkość. Osiąga prędkości dekompresji, które są często o rząd wielkości wyższe niż w DEFLATE. Osiąga to dzięki kilku optymalizacjom, w tym użyciu tablicy haszującej do szybkiego znajdowania potencjalnych dopasowań (zamiast skanowania całego bufora wyszukiwania) i posiadaniu bardzo prostego, szybkiego do parsowania formatu wyjściowego. Jego współczynnik kompresji nie jest tak wysoki jak w bardziej złożonych algorytmach, ale w scenariuszach takich jak kompresja w bazach danych, systemach plików w czasie rzeczywistym (np. ZFS, Btrfs) i ładowaniu zasobów gier, jego niewiarygodna prędkość jest przełomowa.