Kompresja LZ77: Znajdowanie Powtórzeń W Przesuwającym Się Oknie

Zastąp powtarzające się sekwencje wskazówkami do przeszłości

LZ77, opublikowana przez Abrahama Lempela i Jakoba Ziva w 1977 roku, kompresuje dane poprzez zastępowanie powtarzających się podsekwencji małymi odniesieniami wstecznymi do ich wcześniejszych wystąpień – to założenie stojące u podstaw gzipa, zliba, PNG, DEFLATE i pośrednio większości współczesnych kompresorów. Algorytm przesuwa dwukomorowe okno przez dane wejściowe: bufor poszukiwań zawierający już widziane dane za kursorem oraz bufor przedglądowy zawierający nadchodzące dane do zakodowania.

Podobnie jak w przypadku kodowania Huffmana, celem jest redukcja redundancji. Zastępowanie powtarzających się sekwencji krótkimi odniesieniami pozwala na efektywniejsze wykorzystanie bitów podczas kompresji. Wartość odniesienia wskazuje na miejsce w danych wejściowych, gdzie dana sekwencja wystąpiła wcześniej, co umożliwia jej ponowne użycie bez konieczności ponownego kodowania.

[........search buffer........][cursor][...look-ahead buffer...]
at each step: find the LONGEST match between look-ahead and search buffer
emit token (distance, length, next-literal)  then slide the window forward

Token (odległość, długość, literal)

W każdym kroku LZ77 emitowany jest jeden token: odległość cofająca się do początku najlepszego dopasowania znalezionego w buforze wyszukiwania, długość odpowiadająca liczbie bajtów dopasowanych oraz jeden bajt literalny następujący po dopasowaniu (potrzebny do zagwarantowania postępu nawet wtedy, gdy nie ma dopasowania, w takim przypadku odległość i długość są równe zero). Standardowo stosowane jest greedy wyszukiwanie najdłuższego dopasowania – zawsze wybierane jest najdłuższe dostępne dopasowanie na kursorze, nawet jeśli krótsze dopasowanie mogłoby umożliwić jeszcze dłuższe natychmiast po nim; niektóre rzeczywiste kompresory wykorzystują lazy matching, sprawdzając jeden bajt z wyprzedzeniem przed podjęciem decyzji, aby odzyskać część utraconego wskaźnika tanim sposobem.

example:  "the cat sat on the mat"
encoding "the mat" late in the string can reference "the " from position 0:
token: (distance=19, length=4, literal='m') + literals "at"

Dlaczego dopasowanie może się nakładać

Cienkie spostrzeżenie, które wprowadza w błąd naiwne implementacje: długość dopasowania może legalnie przekraczać aktualną odległość. Jeśli odległość wynosi 3 a długość 8, dekoder nie zawodzi – kopiuje bajty pozycją wstecz o 3 miejsca, a ponieważ każdy skopiowany bajt natychmiast staje się źródłem dla kolejnej kopii, powstaje powtarzający się wzorzec. To jedno zasady pozwala na kompresję LZ77 długich przebiegów powtarzanego krótkiego wzoru (np. 'aaaaaaaa' lub powtarzającego się tekstu tapetowego) do jednego małego tokenu zamiast potrzebnego pojedynczego tokena dla każdej powtórki.

Rozmiar okna to cała sztuka

Wielkość bufora poszukiwań ogranicza odległość, na jaką można znaleźć dopasowanie, więc bezpośrednio wpływa na stopień kompresji danych o długotrwałym powtarzaniu: DEFLATE (używany przez gzip, zlib i PNG) ustala go na 32 KB, a nowsze formaty posuwają się znacznie dalej – Brotli pozwala na do 16 MB, a tryb "długodystansowego dopasowywania" w Zstandard może obejmować cały plik. Większe okno łapie więcej powtórzeń, ale wymaga więcej pamięci i, co oczywiste, więcej czasu na poszukiwanie; produkcyjne kodery używają tabeli hash o kluczach w kolejnych kilku bajtach, dzięki czemu wyszukiwanie dopasowań jest średnio O(1) zamiast przeszukiwania całego okna liniowo.

LZ77 to tylko połowa potężnej magistrali

Surowe wyjście z LZ77 – strumień tokenów (odległość, długość, znak dosłowny) – nie jest samo w sobie najbardziej zwarty, ponieważ krótkie odległości, częste długości i często występujące znaki literalne powinny kosztować mniej bitów niż rzadkie odległości, długości i znaki literalne; dlatego DEFLATE przetwarza wyjście z LZ77 na drugą fazę, kodowanie Huffmana, które przypisuje krótsze kody bitowe do najczęściej występujących tokenów; ten dwufazowy projekt (dopasowywanie słownika, a następnie kodowanie entropii) jest szablonem, którego niemal każda ogólnego przeznaczenia kompresor od 1977 roku podążał za nim, w tym LZMA, Brotli i Zstandard, które zasadniczo różnią się tylko tym, jak sprytnie przeszukują po dopasowania i z jakim kodem entropii je łączą.

LZ77 w porównaniu z LZ78

Algorytm LZ78 (1978), będący bratem algorytmu LZ77, zastępuje okno przesuwa się słowotwornikiem wyraźnikiem rosnącym słownikiem wcześniej widzianych fraz, odwoływując się do niego po indeksie zamiast przez (odległość, długość) — podstawa LZW, używanej w GIF i starych systemach Unix kompresja. Zaletą LZ77 jest to, że nie wymaga wyrazistego struktury słownika do przesyłania lub synchronizacji; jego wadą jest to, że dopasowanie może szukać tylko tak daleko wstecz, jak pozwala okno, podczas gdy słownik LZ78 koncepcyjnie obejmuje cały dotychczas widziany wejście.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz LZ77 Compression i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.