> lz77 | sliding | window <
// LZ77 – kompresja z użyciem przesuwającego się okna i słownika
Kodowanie słownikowe
Wykorzystuje odwołania z przesunięciem i długością do powtarzających się wzorców.
Przesuwające się okno
Utrzymuje ruchome okno do wyszukiwania najdłuższych dopasowań.
Algorytm bazowy
Stanowi podstawę formatów ZIP, GZIP, DEFLATE i PNG.
>> informacje techniczne
Jak działa LZ77:
LZ77 utrzymuje przesuwające się okno ostatnio widzianych danych. Dla każdej pozycji algorytm szuka w oknie najdłuższego pasującego fragmentu. Jeśli znajdzie dopasowanie, wypisuje referencję (przesunięcie, długość, następny znak). Jeśli nie, wypisuje dosłowny znak (0,0,znak). Dzięki temu powtarzające się wzorce są zastępowane krótkimi referencjami, co daje bezstratną kompresję.
Przykład LZ77:
Text: "ABCABCABC" Window=4, Lookahead=4 Position 0: 'A' - no match → (0,0,A) Position 1: 'B' - no match → (0,0,B) Position 2: 'C' - no match → (0,0,C) Position 3: 'ABC' - matches at offset 3 → (3,3,A) Position 7: 'BC' - matches at offset 3 → (3,2,) Output: (0,0,A)(0,0,B)(0,0,C)(3,3,A)(3,2,)
Dlaczego warto używać LZ77?:
- ▸Bezstratna kompresja danych
- ▸Brak wymaganej wcześniejszej wiedzy o formacie danych
- ▸Dopasowuje się do wzorców w danych
- ▸Stosunkowo prosta implementacja
- ▸Podstawa wielu nowoczesnych algorytmów kompresji
>> najczęściej zadawane pytania
Czym jest LZ77?
LZ77 to uniwersalny, bezstratny algorytm kompresji danych opublikowany w 1977 roku przez Abrahama Lempela i Jacoba Ziva. Zastępuje powtarzające się fragmenty strumienia danych odwołaniami do wcześniejszych wystąpień w strumieniu niezakompresowanym.
Jak działa przesuwające się okno?
Przesuwające się okno składa się z bufora wyszukiwania (dane już przetworzone) oraz bufora lookahead (dane do kompresji). Algorytm szuka w buforze wyszukiwania najdłuższego dopasowania z początkiem bufora lookahead, a następnie wypisuje referencję lub znak dosłowny.
LZ77 a nowoczesne algorytmy kompresji?
LZ77 jest podstawą wielu współczesnych algorytmów kompresji. DEFLATE, używany w ZIP i GZIP, łączy LZ77 z kodowaniem Huffmana. LZSS redukuje nadmiarowość LZ77, a LZ78 i LZW budują słownik w inny sposób, bazując jednak na podobnych ideach.
Jakie rozmiary okna są zalecane?
Typowe rozmiary okna dla danych ogólnych to 32–64 KB. Większe okna znajdują więcej dopasowań, ale wymagają więcej pamięci i czasu. DEFLATE używa 32 KB. Bufor lookahead to zwykle 256–512 bajtów. Optymalny rozmiar zależy od wzorców powtórzeń w danych.
// Przykład krok po kroku
| # | Offset | Length | Next | Output |
|---|---|---|---|---|
| 1 | 0 | 0 | a | a |
| 2 | 0 | 0 | b | b |
| 3 | 0 | 0 | r | r |
| 4 | 3 | 1 | c | a + c |
| 5 | 2 | 1 | d | a + d |
| 6 | 7 | 4 | — | abra |
// Przykłady kodu
Input abracadabra (positions 0..10)
Token (offset, length, next)
offset = distance back into the window, length = bytes copied
Decode copy `length` bytes starting `offset` back, then append `next`
(the copy may overlap its own output, e.g. (1,5,x) repeats a byte)
Window the sliding search buffer; deflate/gzip use 32 KiB
>> Więcej pytań
P: Co oznacza trójka (przesunięcie, długość, znak)?
O: Przesunięcie mówi, ile wstecz w już widzianym oknie, długość — ile bajtów skopiować, a znak to następny nowy bajt. Dekoder odtwarza w ten sposób wyjście krok po kroku.
P: Dlaczego kopia może się nakładać?
O: Gdy przesunięcie jest mniejsze niż długość, kopia czyta bajty, które właśnie zapisała. Tak powstają powtórzenia: (1, 5, x) daje pięć razy poprzedni znak.
P: Gdzie używa się LZ77?
O: LZ77 to rdzeń DEFLATE (gzip, zlib, PNG, ZIP), a jego warianty są w LZ4, Snappy, Zstandard i Brotli. Rozmiar okna i strategia wyszukiwania wpływają na stopień kompresji i szybkość.