Ordbokskodning

Återanvänder upprepade mönster via referenser med offset och längd.

Glidande fönster

Håller ett rörligt fönster för att hitta längsta matchning.

Grundalgoritm

Utgör grunden för ZIP, GZIP, DEFLATE och PNG.

Hur LZ77 fungerar

LZ77 håller ett glidande fönster över nyligen lästa data. För varje position söker algoritmen i fönstret efter den längsta delsträng som matchar. Om den hittar en matchning skrivs en referens (offset, längd, nästa tecken) ut. I annat fall skrivs ett bokstavligt tecken (0,0,tecken) ut. På så sätt ersätts upprepade mönster med korta referenser och man får förlustfri komprimering.

LZ77-exempel

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