Sözlük kodlama

Tekrarlanan desenleri ofset ve uzunluk referanslarıyla temsil eder.

Kayan pencere

En uzun eşleşmeyi bulmak için hareketli bir pencere kullanır.

Temel algoritma

ZIP, GZIP, DEFLATE ve PNG gibi modern sıkıştırma biçimlerinin temelini oluşturur.

LZ77 nasıl çalışır?

LZ77, son görülen verilerden oluşan kayan bir pencere tutar. Her konum için algoritma, pencerede en uzun eşleşen alt diziyi arar. Eşleşme bulunduğunda (ofset, uzunluk, sonraki karakter) referansı çıkışa yazılır. Eşleşme yoksa (0,0,karakter) biçiminde literal üretilir. Böylece tekrar eden desenler kısa referanslarla değiştirilerek kayıpsız sıkıştırma elde edilir.

LZ77 örneği

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