LZ77 și LZ78
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
- Compresie de date fără pierderi
- Compresie pierderea datelor
- Comprimarea datelor
- Tehnologie Memory eXpansion
Alte proiecte
- Wikimedia Commons conține imagini sau alte fișiere despre LZ77 și LZ78
linkuri externe
- O implementare C ++ a algoritmului LZSS, surselor și articolului autorului. , la oldwildweb.com .