Ordbogskodning

Refererer gentagne mønstre med forskydning og længde.

Glidende vindue

Holder et bevægeligt vindue til mønstergenkendelse.

Grundalgoritme

Danner grundlaget for ZIP, GZIP, DEFLATE og PNG.

Sådan fungerer LZ77

LZ77 holder et glidende vindue over nyligt sete data. For hver position søger algoritmen i vinduet efter den længste matchende streng. Hvis der findes et match, udskrives en reference (forskydning, længde, næste tegn). Hvis ikke, udskrives et bogstaveligt tegn (0,0,tegn). Gentagelser erstattes dermed af korte referencer og giver tabsfri 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,)