Dezumfla
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ă alte blocuri după
-
- Bit-2/3: descrierea metodei de codificare
-
00
: Blocul nu este comprimat -
01
: Block utilizează 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:
- În prima, o variantă a algoritmului LZ77 este utilizată pentru a înlocui șirurile duplicate cu pointeri ;
- În al doilea, blocul este codat, dacă este necesar, cu codificarea Huffman .
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.