Woordenboekcodering

Gebruik offset- en lengtereferenties voor herhaalde patronen.

Sliding-window

Houdt een bewegend venster bij om de langste match te vinden.

Kernalgoritme

Vormt de basis voor ZIP, GZIP, DEFLATE en PNG.

Hoe LZ77 werkt

LZ77 houdt een sliding-window bij met recent geziene data. Voor elke positie zoekt het algoritme in het venster naar de langste overeenkomende substring. Bij een match wordt een referentie (offset, lengte, volgend teken) uitgegeven; anders een literal (0,0,teken). Zo worden herhalingen vervangen door korte referenties en ontstaat verliesloze compressie.

LZ77-voorbeeld

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