Kompresja Słownikowa

Powtórzenia sekwencji w kompresji słownikowej

Metody statystyczne, takie jak kodowanie Huffmana, wykorzystują częstotliwość pojedynczych symboli. Dane zawierają także powtarzające się sekwencje, frazy i wzorce bajtów. Koder słownikowy zapisuje takie fragmenty jako odwołania do wcześniejszych wystąpień. Słownik może być jawny i przechowywać frazy pod indeksami albo niejawny i obejmować historię strumienia. Odwołanie daje oszczędność tylko wtedy, gdy jego zakodowany koszt jest mniejszy niż koszt zapisu fragmentu.

Rozważmy zdanie: "W Szczebrzeszynie chrząszcz brzmi w trzcinie". Koder statystyczny może nadać krótkie kody częstym znakom, takim jak 'z', 's' i 'r'. Osobnym źródłem oszczędności jest wielokrotna sekwencja liter "rz". Jej kolejne wystąpienie można zastąpić informacją "powtórz wcześniej zapisany fragment". Ta idea jest podstawą . Rodzina obejmuje między innymi algorytmy opracowane przez Jacoba Ziva i Abrahama Lempela w latach 70. Jej odmiany są używane w formatach takich jak ZIP i GZIP, a DEFLATE stosuje się także w PNG.

W krótkim rekordzie koszt odwołania może przewyższyć uzyskaną oszczędność.

Algorytm LZ77 i przesuwne okno

Opublikowany w 1977 roku LZ77 jest pierwszą z dwóch prac Ziva i Lempela, od których wywodzi się rodzina algorytmów LZ. Zamiast przechowywać pełny, jawny słownik fraz, algorytm używa stale aktualizowanej historii niedawno przetworzonych danych.

Mechanizm przesuwnego okna

Algorytm korzysta z przesuwnego okna, czyli ograniczonego obszaru historii i danych oczekujących na kodowanie. Okno dzieli się na dwie części. Jego rozmiar wyznacza maksymalną odległość odwołania, a rozmiar bufora wejściowego ogranicza długość rozpatrywanego dopasowania:

Bufor wyszukiwania: To historia albo niejawny słownik. Bufor ma stały rozmiar, na przykład kilka kilobajtów, i zawiera ostatnio zakodowane dane. Koder szuka w nim powtarzających się sekwencji.
Bufor wejściowy: Mniejszy bufor zawiera następny fragment danych oczekujący na kodowanie. Koder pobiera z niego symbole i szuka dopasowania w buforze wyszukiwania.

Proces kodowania LZ77

Kodowanie przebiega w powtarzanej pętli:

Algorytm analizuje symbole na początku bufora wejściowego.
Następnie przeszukuje bufor wyszukiwania w celu znalezienia najdłuższego dopasowania dla sekwencji rozpoczynającej się w buforze wejściowym. Sposób wyszukiwania zależy od implementacji.
Na podstawie wyniku wyszukiwania podejmuje decyzję i wypisuje jeden z dwóch rodzajów tokenów:
- Brak użytecznego dopasowania: Gdy dopasowanie nie występuje albo jest krótsze od progu, na przykład 3 znaków, koder emituje token literału. Token zawiera symbol z bufora wejściowego, a w wielu formatach także znacznik rozróżniający go od odwołania. Próg ogranicza sytuacje, w których zapis wskaźnika byłby dłuższy od literału.
- Znalezione dopasowanie: Koder emituje token wskaźnika, który odwołuje się do historii. W typowej reprezentacji zawiera on znacznik, przesunięcie albo odległość oraz długość. 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.
Na koniec algorytm przesuwa okno. Przenosi przetworzone dane, czyli literał albo dopasowaną sekwencję długości $L$ , do historii i pobiera nowe dane do bufora wejściowego. Proces jest powtarzany.

Dopasowania nakładające się

LZ77 może kodować długie powtórzenia jednym odwołaniem. Rozważmy ciąg "abababababab". Po umieszczeniu początkowego "ab" w historii bufor wejściowy zawiera "ababababab". Koder może odwołać się 2 bajty wstecz i wskazać długość 10 bajtów.

Dekoder LZ77 kopiuje dopasowanie kolejno. Wraca o 2 bajty, kopiuje 'a', potem 'b'. Przed skopiowaniem trzeciego bajtu pierwsze 'a' jest już częścią historii i może zostać użyte ponownie. Mechanizm obsługuje nakładanie źródła i celu, dzięki czemu jeden krótki wskaźnik odtwarza długą serię.

Dekompresja

Dekoder utrzymuje bufor wyszukiwania złożony z danych zapisanych na wyjściu. Po otrzymaniu tokena wykonuje jedną z dwóch operacji:

Dla tokena literału dołącza symbol do wyjścia.
Dla tokena wskaźnika (odległość, długość) cofa się o podaną odległość i kopiuje podaną długość bajtów, także z uwzględnieniem nakładania.

Dekodowanie wymaga głównie odwołań do historii i kopiowania danych. Prosta ścieżka dekodera jest jednym z powodów stosowania schematów opartych na LZ77. Dekoder musi jednak sprawdzać zakres odległości, długość oraz granice bufora, aby odrzucić uszkodzony token.

Rodzina LZ78 i LZW z jawnym słownikiem

LZ78, opublikowany w 1978 r., oraz LZW (Lempel-Ziv-Welch, opracowany w 1984 r.) używają jawnej tabeli fraz. W odróżnieniu od LZ77 odwołania wskazują wpisy słownika utrzymywanego przez koder i dekoder. Wpisy są dodawane w tej samej kolejności po obu stronach, a format może ograniczać liczbę bitów kodu albo okresowo resetować słownik.

Mechanizm LZW. Budowanie i odwołania

Procedura LZW obejmuje inicjalizację, wyszukiwanie fraz i aktualizację słownika:

Inicjalizacja: LZW zaczyna od słownika zawierającego wszystkie symbole jednoznakowe.
Budowanie fraz: Odczytuje wejście i znajduje najdłuższą sekwencję znaków obecną w słowniku.
Wyjście i aktualizacja: Emituje kod słownikowy najdłuższej znalezionej sekwencji, a następnie dodaje nowy wpis złożony z tej sekwencji i kolejnego znaku wejścia.

LZ77 i LZW. Różnice podejścia

Oba są koderami słownikowymi, lecz używają innych odwołań. LZ77 zastępuje powtórzenia parą (odległość, długość) wskazującą historię strumienia. LZW emituje kod całkowitoliczbowy odnoszący się do wpisu jawnego słownika. LZW korzysta z powtarzających się wieloznakowych fraz, a LZ77 może znaleźć lokalne dopasowania, które nie tworzą stałych słów.

Współczesne hybrydy

Współczesne kompresory bezstratne często łączą dopasowania słownikowe z kodowaniem entropijnym. Pierwszy etap opisuje powtórzenia, a drugi nadaje krótsze kody często występującym literałom i parametrom dopasowań.

DEFLATE w ZIP, GZIP i PNG

DEFLATE łączy wyszukiwanie powtórzeń typu LZ77 z kodowaniem Huffmana. Format ZIP może przechowywać strumień DEFLATE, GZIP opakowuje taki strumień w format gzip, a PNG używa strumienia zlib z kompresją Deflate dla danych obrazu.

Etap 1. Dopasowania LZ77: Koder skanuje dane w oknie o maksymalnej odległości 32 KiB i zastępuje powtarzające się ciągi wskaźnikami (długość, odległość). Znak bez użytecznego dopasowania trafia do strumienia jako literał.
Etap 2. Kodowanie Huffmana: Wynik pierwszego etapu zawiera literały oraz pary długość i odległość. DEFLATE koduje literały i długości jednym drzewem Huffmana, a odległości drugim. W bloku dynamicznym drzewa są opisane w strumieniu, co pozwala dopasować kody do częstości elementów.

Pierwszy etap usuwa powtórzenia strukturalne, a drugi zmniejsza koszt statystycznie częstych literałów i wskaźników. Podział pracy wyjaśnia, dlaczego DEFLATE łączy oba rodzaje kodowania. Strumień jest dzielony na bloki. Blok może być zapisany bez kompresji, używać stałych kodów Huffmana albo zawierać opis dynamicznych drzew Huffmana. Odległość odwołania jest ograniczona przez format, więc dalsze powtórzenia trafiają do kolejnych bloków lub jako literały.

LZ4 i priorytet szybkości

Wyszukiwanie dopasowań i budowa drzew w DEFLATE mogą zwiększać koszt kodowania. W zastosowaniach z dużymi zbiorami w pamięci ważna jest przepustowość dekodera. LZ4 zaprojektowano z naciskiem na prostotę i szybkość.

LZ4 jest wariantem LZ77, który ogranicza złożoność formatu i ścieżki dekodowania. Implementacje mogą używać tablicy haszującej do szybkiego wyszukiwania kandydatów, zamiast skanowania całego bufora. Zwykle oznacza to mniejszy współczynnik niż w metodach nastawionych na rozmiar, przy krótkim czasie dekompresji. LZ4 jest stosowany między innymi w bazach danych, systemach plików, na przykład w ZFS, oraz przy ładowaniu zasobów gier. Format bloku LZ4 i format ramki LZ4 to odrębne warstwy. Ramka może przenosić rozmiar danych, sumę kontrolną i informacje o blokach, a blok opisuje literały oraz operacje kopiowania. W strumieniu używanym przez sieć trzeba przekazać także granice bloków i dane potrzebne dekoderowi. LZ77 i LZ4 nie definiują samego kontenera dla każdego zastosowania, dlatego format ramki ma znaczenie dla przenośności. LZ78 opisuje wpisy jako indeks i symbol, natomiast LZW emituje indeksy po rozbudowaniu tabeli. Wszystkie te schematy wymagają zgodnego stanu słownika po stronie kodera i dekodera. Przy zmianie parametrów okna lub rozmiaru kodu dekoder musi odczytać ustawienia z nagłówka albo otrzymać je z kontekstu strumienia. Narzut tych informacji jest istotny dla krótkich fragmentów. Wybór dopasowania wpływa na liczbę odwołań, lecz także na koszt wyszukiwania podczas kodowania. Ta decyzja powinna być mierzona razem z czasem dekodowania. Dekoder może odtworzyć wpisy w tej samej kolejności tylko wtedy, gdy reguły resetu i słownik początkowy są identyczne. W DEFLATE typ bloku i opisy drzew są częścią strumienia, więc dekoder może wybrać właściwe drzewa Huffmana. LZ4 utrzymuje prostą gramatykę bloku, lecz ramka określa obsługę rozmiaru danych i sum kontrolnych. Dlatego benchmark powinien wskazywać konkretny kontener, implementację i ustawienia. Wpływa to także na interoperacyjność narzędzi.