LZ77 și LZ78

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

LZ77 și LZ78 sunt algoritmi de compresie fără pierderi publicate de Abraham Lempel și Jacob Ziv în 1977 și, respectiv, 1978 . Acești algoritmi stau la baza multor variante precum LZW sau LZSS .

Metoda folosește compresia de date, texte sau imagini eterogene și nu necesită informații a priori asupra datelor care trebuie comprimate.

LZ77

Comprimarea are loc prin înlocuirea părților de date cu altele deja procesate. Dacă algoritmul de codificare întâlnește o dată repetată, aceasta este înlocuită cu un indicator de lungime-distanță care indică în esență copierea unei anumite lungimi de date de la o anumită distanță .

Atât algoritmul de codificare, cât și cel de decodare trebuie să țină evidența unei anumite cantități de date întâlnite. Aceasta este denumită de obicei o fereastră și din acest motiv LZ77 este denumită și compresie de fereastră.

Pe baza acestui algoritm, Memory eXpansion Technology (MXT) a fost implementată de IBM .

LZ78

Comprimarea are loc într-un mod similar cu LZ77, dar în acest caz este creat un dicționar cu părțile de date deja întâlnite. Algoritmul de codificare înlocuiește datele deja din dicționar cu o referință la acesta.

În primele câteva decenii după introducere, a fost acoperit de brevete în Statele Unite care au subminat utilizarea pe scară largă, deși a fost populară de la apariția sa. Cea mai populară formă de compresie LZ78 rămâne LZW , o variantă realizată de Terry Welch în 1984 și utilizată în fișiere grafice GIF .

Elemente conexe

Alte proiecte

linkuri externe

Informatică Portal IT : accesați intrările Wikipedia care se ocupă cu IT