PL 
EnglishDomyślny
Українська💾 Kompresja LZ77
Zobacz, jak algorytm kompresji LZ77 z przesuwnym oknem koduje dane, wyszukując powtarzające się wzorce.
O kompresji LZ77
LZ77, opublikowany przez Abrahama Lempela i Jacoba Ziva w 1977 roku, to bezstratny algorytm kompresji oparty na słowniku, który zastępuje powtarzające się podciągi odniesieniami wstecznymi do przesuwnego okna wcześniej widzianych danych. Każdy zakodowany token to trójka (przesunięcie, długość, następny-znak): przesunięcie wskazuje wstecz w buforze przeszukiwania, długość mówi, ile znaków skopiować, a następny-znak to pierwszy znak, który nie pasuje. Ten schemat „analizuj, a potem odwołaj się” nie wymaga wstępnie zbudowanego słownika — zarówno kompresor, jak i dekompresor odtwarzają ten sam niejawny słownik z samego strumienia danych, co czyni LZ77 adaptacyjnym i uniwersalnie stosowalnym.
LZ77 stanowi podstawę niektórych najczęściej używanych formatów kompresji w informatyce: DEFLATE (używany wewnątrz ZIP i gzip) łączy LZ77 z kodowaniem Huffmana, LZSS to udoskonalony wariant używany w wielu systemach wbudowanych, a nowoczesne formaty, takie jak LZ4 i Zstandard, wywodzą się bezpośrednio z idei Lempela-Ziva. Ten symulator pozwala wpisać dowolny tekst, dostosować rozmiary bufora przeszukiwania i okna wyprzedzenia oraz obserwować, jak koder skanuje znak po znaku, podświetlając dopasowane regiony, wygenerowane tokeny oraz zmieniający się współczynnik kompresji.
Najczęściej zadawane pytania
Jak działa przesuwne okno LZ77?
Algorytm utrzymuje dwa bufory obok siebie: bufor przeszukiwania (historia), zawierający ostatnie S znaków już zakodowanych, oraz bufor wyprzedzenia, zawierający kolejne L znaków do zakodowania. W każdym kroku koder znajduje najdłuższy prefiks wyprzedzenia, który pojawia się także w buforze przeszukiwania, zapisuje odniesienie wsteczne (przesunięcie, długość), a następnie przechodzi za dopasowane znaki plus jeden literał następnego znaku. Oba bufory przesuwają się razem do przodu — stąd „przesuwne okno”.
Jaki współczynnik kompresji może zwykle osiągnąć LZ77?
Współczynnik kompresji silnie zależy od redundancji danych wejściowych. Typowy tekst angielski kompresuje się do około 30–40% oryginalnego rozmiaru przy użyciu LZ77 + Huffman (DEFLATE). Sekwencje DNA, które często się powtarzają, mogą osiągnąć redukcję 60–80%. Prawdziwie losowe dane w ogóle nie mogą zostać skompresowane — każde wyszukiwanie odniesienia wstecznego zawodzi, a każdy znak musi zostać wypisany jako literał, sprawiając, że wyjście jest nieco większe od wejścia z powodu narzutu tokenów.
Jaka jest różnica między LZ77 a LZ78?
LZ77 wykorzystuje przesuwne okno o stałym rozmiarze w niedawnym wyjściu jako swój niejawny słownik. LZ78 (1978) zamiast tego buduje jawny słownik fraz, który rośnie w miarę kodowania, używając tokenów indeks + nowy-znak zamiast przesunięcie + długość. LZW (Welch, 1984), podstawa formatu GIF i wczesnego uniksowego compress, jest udoskonaleniem LZ78, które pomija literalny znak. Warianty LZ77 zwykle osiągają lepszą kompresję dla języka naturalnego; warianty LZ78 analizują bardziej regularnie i mogą być szybsze na pewnym sprzęcie.
Dlaczego większy bufor przeszukiwania poprawia kompresję?
Większy bufor przeszukiwania daje koderowi więcej historii do przeszukania w poszukiwaniu dopasowań, zwiększając prawdopodobieństwo znalezienia długiego powtarzającego się podciągu. Teoretyczna granica kompresji LZ77 zbliża się do empirycznej entropii źródła, gdy rozmiar okna dąży do nieskończoności. W praktyce DEFLATE używa okna przeszukiwania 32 KB; LZ4 może używać okien do 64 KB; Zstandard obsługuje okna do 2 GB, dlatego osiąga znacznie lepsze współczynniki dla dużych plików z redundancją długiego zasięgu, takich jak archiwa kodu źródłowego.
Czy LZ77 jest bezstratny i jak odzyskiwane są oryginalne dane?
Tak, LZ77 jest całkowicie bezstratny. Dekompresja jest prosta: skanuj strumień tokenów, a dla każdej trójki (przesunięcie, długość, znak) kopiuj długość znaków zaczynając od pozycji (bieżąca_pozycja_wyjścia − przesunięcie) z już zdekodowanego bufora wyjściowego, a następnie dołącz znak. Nie jest potrzebny żaden słownik ani informacja dodatkowa poza samym strumieniem tokenów. Dekompresor działa więc w czasie O(n), zwykle znacznie szybciej niż koder, który musi przeszukiwać okno dla każdej pozycji.
Czym jest LZSS i jak ulepsza LZ77?
LZSS (Storer i Szymanski, 1982) dodaje pojedynczy bit flagi przed każdym tokenem, by wskazać, czy jest to odniesienie wsteczne, czy surowy literał. LZ77 zawsze wypisuje trójkę, nawet dla niepasujących znaków (przesunięcie=0, długość=0, znak), marnując bity. LZSS wypisuje jedynie bajt znaku, gdy nie istnieje użyteczne dopasowanie, i pomija pole następnego znaku w odniesieniach wstecznych. Redukuje to narzut dla danych wejściowych o niskiej redundancji i jest wariantem używanym w klasycznych formatach archiwów, takich jak LHA i starsze metody PKZIP.
Jak DEFLATE łączy LZ77 z kodowaniem Huffmana?
DEFLATE (RFC 1951, używany w ZIP, gzip, PNG, zlib) uruchamia LZ77 z 32-kilobajtowym oknem przeszukiwania, by wytworzyć strumień literałów i odniesień wstecznych, a następnie dalej kompresuje ten strumień dwoma drzewami Huffmana: jednym dla wartości literał/długość (0–285) i jednym dla wartości odległości (1–32768). Same drzewa Huffmana są kompresowane kodem trzeciego poziomu. To dwuetapowe podejście jest powodem, dla którego gzip konsekwentnie przewyższa czysty LZ77: etap Huffmana wychwytuje redundancję częstości symboli, którą LZ77 pozostawia niewykorzystaną.
Dlaczego losowe dane nie mogą być skompresowane przez LZ77?
Losowe dane, z definicji, mają maksymalną entropię: każdy bajt jest jednakowo prawdopodobny niezależnie od kontekstu, więc prawdopodobieństwo znalezienia dopasowania w buforze przeszukiwania jest bardzo niskie. Większość tokenów redukuje się do (0, 0, znak) — czystych literałów — a pola przesunięcia/długości dodają narzut zamiast oszczędzać miejsce. Nie jest to ograniczenie specyficzne dla LZ77, lecz fundamentalna konsekwencja teorii informacji: żaden bezstratny kompresor nie może zredukować oczekiwanej długości sekwencji pochodzącej ze źródła o maksymalnej entropii.
Jaka jest złożoność czasowa kodowania LZ77?
Naiwne kodowanie LZ77 ma złożoność O(n·W), gdzie n to długość wejścia, a W to rozmiar okna przeszukiwania, ponieważ na każdej pozycji koder skanuje całe okno w poszukiwaniu najdłuższego dopasowania. Przy użyciu tabeli haszującej (jak w zlib) średnia złożoność spada do O(n), choć najgorszy przypadek pozostaje kwadratowy. Tablice sufiksowe i automaty sufiksowe mogą osiągnąć optymalne parsowanie O(n log n) lub O(n) w najgorszym przypadku, jak stosowane w kompresorach klasy badawczej, takich jak wewnętrzna faza LZ w brotli.
Jak LZ77 radzi sobie z danymi binarnymi, takimi jak pliki wykonywalne czy obrazy?
Pliki binarne wykonywalne zawierają powtarzające się sekwencje instrukcji, tabele importu i literały tekstowe, więc LZ77 osiąga umiarkowaną kompresję (zwykle redukcja rozmiaru o 40–60%). Nieskompresowane obrazy rastrowe z jednolitymi regionami kompresują się dobrze (PNG używa DEFLATE). Jednak już skompresowane dane (JPEG, MP3, MPEG) zawierają niemal losowe rozkłady bajtów po własnym kodowaniu entropijnym, więc ponowne zastosowanie LZ77 daje pomijalne lub ujemne zyski kompresji — większość narzędzi archiwizujących wykrywa to i przechowuje takie pliki nieskompresowane.
Jakie nowoczesne formaty wywodzą się z LZ77?
LZ4 (2011) priorytetyzuje prędkość dekompresji nad współczynnikiem, osiągając dekompresję rzędu wielu GB/s na współczesnych procesorach dzięki prostemu dopasowywaniu haszy 4-bajtowych. Zstandard (Facebook, 2016, RFC 8878) dodaje kodowanie entropijne o skończonych stanach (nowoczesny koder asymetrycznych systemów numeralnych) na wierzchu dopasowywania LZ77 i osiąga współczynniki konkurencyjne wobec bzip2 przy prędkościach zbliżonych do LZ4. Brotli (Google, 2015, RFC 7932), używany w kodowaniu treści HTTP, łączy LZ77 ze 120-wpisowym statycznym modelem kontekstowym i współdzielonym słownikiem dla zasobów webowych.