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.

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,)