LZ77 și LZ78 sunt algoritmi de compresie fără pierderi publicate în lucrări ale matematicienilor israelieni Abraham Lempel și Yaakov Ziv în 1977 și 1978 . Acești algoritmi sunt cele mai cunoscute variante din familia LZ* , care include și LZW , LZSS , LZMA și alți algoritmi.
Ambii algoritmi sunt metode de dicționar, spre deosebire de alte metode de reducere a redundanței, cum ar fi RLE și compresia aritmetică . LZ77 este un algoritm de „fereastră glisante”, care este echivalent cu utilizarea implicită a abordării dicționarului propusă pentru prima dată în LZ78.
Putem spune că algoritmii familiei LZ* reprezintă o generalizare mai complexă a metodei simple și intuitive de compresie a datelor utilizate în RLE . Pentru a înțelege acest algoritm, este necesar să înțelegem cele două componente ale sale: principiul ferestrei glisante și mecanismul de codare a coincidențelor .
Metoda de codare, conform principiului ferestrei glisante, ia în considerare informațiile care au fost deja întâlnite, adică informațiile care sunt deja cunoscute codificatorului și decodorului (a doua apariție și apariția ulterioară a unui șir de caractere din mesaj sunt înlocuite prin link-uri către prima sa apariție).
Din cauza acestui principiu, algoritmii LZ* sunt uneori denumiți metode de compresie cu ferestre glisante. O fereastră glisantă poate fi considerată ca un buffer (sau o structură de date dinamică mai complexă) care este organizată pentru a reține și a accesa informațiile „spuse” anterior. Astfel, însuși procesul de codificare prin compresie conform LZ77 amintește de scrierea unui program ale cărui comenzi vă permit să accesați elementele „ferestrei glisante”, iar în loc de valorile secvenței comprimate, introduceți referințe la aceste valori. în „fereastra glisantă”. Dimensiunea ferestrei glisante poate fi modificată dinamic și poate fi de 2, 4 sau 32 kilobytes. De asemenea, trebuie remarcat faptul că dimensiunea ferestrei decodorului poate fi mai mică sau egală cu dimensiunea ferestrei decodorului, dar nu invers.
Comparația de mai sus a procesului de codificare cu „programare” poate duce la concluzia prematură că algoritmul LZ77 aparține metodelor de modelare a contextului . Prin urmare, trebuie remarcat faptul că algoritmul LZ77 este de obicei clasificat ca o metodă de comprimare a datelor din dicționar , atunci când termenul „dicționar dinamic” este folosit în locul conceptului de „fereastră glisante”.
Înainte de a trece la luarea în considerare a mecanismului de codificare, să clarificăm conceptul de potrivire (din engleză match ). Se consideră o succesiune de N elemente. Dacă toate elementele unei secvențe sunt unice, atunci o astfel de secvență nu va conține un singur element care se repetă sau, cu alte cuvinte, nu vor exista cel puțin două elemente egale sau care coincid în secvență.
În algoritmul standard LZ77, potrivirile sunt codificate ca o pereche:
În continuarea analogiei deja prezentate cu programarea, observăm că în majoritatea articolelor dedicate algoritmului LZ77, perechea codificată este interpretată tocmai ca o comandă pentru a copia caractere dintr-o fereastră glisantă dintr-o anumită poziție sau literalmente ca: „Reveniți la valoarea offset- ului din bufferul de caractere și copiați valoarea lungimii caracterului începând de la poziția curentă.
Deși această interpretare poate părea intuitivă pentru programatorii imperativi , ea spune puțin despre natura algoritmului LZ77 ca metodă de compresie. Particularitatea acestui algoritm de compresie este că utilizarea unei perechi codificate lungime-offset este nu numai acceptabilă, ci și eficientă în cazurile în care valoarea lungimii depășește valoarea offset-ului.
Exemplul cu comanda copy nu este în întregime evident: „Întoarceți 1 caracter în buffer și copiați 7 caractere, începând de la poziția curentă”. Cum poți copia 7 caractere din buffer când există doar 1 caracter în buffer în acest moment? Cu toate acestea, următoarea interpretare a perechii de codificare poate clarifica situația: fiecare 7 caractere ulterioare sunt aceleași (echivalente) cu 1 caracter înaintea lor.
Aceasta înseamnă că fiecare caracter poate fi determinat fără ambiguitate prin deplasarea înapoi în buffer - chiar dacă caracterul dat nu se află încă în tampon în momentul în care perechea curentă de compensare a lungimii este decodificată . O astfel de pereche codificată ar fi o repetare multiplă (specificată prin valoarea offset) a unei secvențe (specificată prin valoarea lungimii) de caractere, care este o formă mai generală a RLE .
Caracterele selectate nu sunt în secvența de codare.
Spre deosebire de LZ77, care funcționează cu date deja primite, LZ78, propus în 1978 [1] , se concentrează pe datele care vor fi doar primite (LZ78 nu folosește o fereastră „glisantă”, el stochează un dicționar de fraze deja vizualizate). Algoritmul citește caracterele mesajului până când subșirul acumulat este inclus în întregime într-una dintre frazele din dicționar. De îndată ce acest șir nu mai corespunde cu cel puțin o frază din dicționar, algoritmul generează un cod format din indexul șirului din dicționar care a conținut șirul de intrare până la ultimul caracter introdus și caracterul care a încălcat potrivirea. Apoi subșirul introdus este adăugat în dicționar. Dacă dicționarul este deja plin, atunci expresia cel mai puțin folosită în comparații este eliminată preliminar din el.
Să fie dat șirul ACAGAATAGAGA.
| Dicţionar | Citiți conținutul rândului | Codul |
|---|---|---|
| A | <0,A> | |
| A=1 | C | <0,C> |
| A=1 C=2 |
AG | <1,G> |
| A=1, C=2 AG=3 |
AA | <1,A> |
| A=1, C=2 AG=3, AA=4 |
T | <0, T> |
| A=1, C=2, AG=3 AA=4, T=5 |
AGA | <3,A> |
| A=1, C=2, AG=3 AA=4, T=5, AGA=6 |
G | <0,G> |
| A=1, C=2, AG=3, AA=4 T=5, AGA=6, G=7 |
A | <1,EOF> |
Rezultatul lucrării va fi succesiunea: <0, A><0, C><1, G><1, A><0, T><3, A><0, G><1, EOF> .
| Metode de compresie | |||||||
|---|---|---|---|---|---|---|---|
| Teorie |
| ||||||
| Fara pierderi |
| ||||||
| Audio |
| ||||||
| Imagini |
| ||||||
| Video |
| ||||||