Dezumfla

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

Algoritmul Deflate este un algoritm de compresie a datelor care a fost introdus de programul PKZIP și apoi formalizat în RFC 1951 . Este încă utilizat pe scară largă datorită performanțelor sale excelente și absenței brevetelor.

Descriere

Algoritmul Deflate funcționează pe blocuri de date cu o dimensiune maximă de 64 KB. Fiecare bloc este precedat de un antet pe 3 biți:

  • Bit-1: marker pentru ultimul bloc
    • 0 : Blocul este ultimul din serie
    • 1 : Există și alte blocuri după
  • Bit-2/3: descrierea metodei de codificare
    • 00 : Blocul nu este comprimat
    • 01 : Block folosește codificarea Huffman cu un arbore predeterminat
    • 10 : Blocul utilizează codificarea Huffman cu propriul bloc
    • 11 : Rezervat

Majoritatea blocurilor vor folosi codificarea Huffman cu propriul lor arbore, deși cu un nivel ridicat de entropie , algoritmul poate decide să nu comprime deloc blocul. Dacă există un bloc care folosește propriul copac, instrucțiunile pentru construirea arborelui urmează antetul.

Compresia este împărțită în 2 etape:

Diferențe cu algoritmul LZ77

În ceea ce privește varianta LZW , aceasta constă în a nu construi dicționarul în mod explicit, ci în a folosi în locul indicatoarelor înapoi pentru a specifica că un șir de intrare dat este de fapt repetarea altui deja observat în precedență. În acest caz, în loc să emită codul (lui Huffman) asociat cu octetul curent, se scoate (codul lui Hamming) lungimea șirului de copiat și distanța (în trecut) a acestuia. Deci, în practică, în loc să utilizați un cuvânt de cod cu lungime fixă ​​pentru a indexa elementele dicționarului ca și pentru LZW, se folosește un pointer cu lungime variabilă, favorizând copiile subcordului curent cel mai apropiat în timp, sau cele cu un număr mai mare de egal personaje.