Czestina LZ 77 TNT's HomePage Algoritmy komprese dat

LZ 77

Podstatou tohoto typu komprese je tzv. posuvné okno (sliding window), které obsahuje konec (několik KB) již přečteného (a zkomprimovaného) textu. V tomto okně se snažíme nalézt co nejdelší opakování aktuálního vstupu a ten pak zakódovat jako offset v okně a délku.

Účinnost této metody je srovnatelná s LZ78. Výsledný kód se často dále komprimuje pomocí statistických metod.

Komprese

Posuvné okno:
Prohlížecí okno Aktuální okno
Již zapomenutá část Zpracovaná část, která je stále v paměti Aktuální část Ještě nepřečtená část

Posuvné okno obsahuje dvě části: prohlížecí okno a aktuální okno (look ahead buffer). Na začátku nastavíme posuvné okno tak, aby začátek vstupu byl v aktuálním okně, na obsahu prohlížecího okna nezáleží (jen musí být stejný při dekompresi). Potom pokaždé v posuvném okně najdeme co nejdelší předponu slova z aktuálního okna začínající v prohlížecím okně, tu pak zakódujeme jako offset v prohlížecím okně, délku předpony a první znak, který již není v předponě.

Způsobem kódování výstupu se liší následující modifikace algoritmu.

while (aktuální okno není prázdné) {
  najdi offset, délku
  if (délka > minimální délka)
    write (1, offset, délka)
  else for (i=0; i<délka; i++)
    write (0, znak)
  posuň posuvné okno o délka znaků doleva
  read (chybějící část okna)
}

Last change Mar 24 1997 by TNT