Ordbokkoding

Bruker referanser med forskyvning og lengde for gjentatte mønstre.

Glidende vindu

Holder et bevegelig vindu for å finne lengste treff.

Grunnalgoritme

Danner grunnlaget for ZIP, GZIP, DEFLATE og PNG.

Hvordan LZ77 fungerer

LZ77 holder et glidende vindu over nylig sett data. For hver posisjon søker algoritmen i vinduet etter den lengste matchende delstrengen. Når den finner en, skriver den ut en referanse (forskyvning, lengde, neste tegn). Hvis det ikke finnes noen match, skriver den et bokstavelig tegn (0,0,tegn). Dette erstatter repeterte mønstre med korte referanser og gir tapsfri komprimering.

LZ77-eksempel

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