Bzip2 folosește mai multe straturi de tehnici de compresie stivuite una peste alta, care apar în următoarea ordine în timpul comprimării și în ordinea inversă în timpul decompresiei:
- Codificare pe lungime de rulare (RLE) a datelor inițiale.
- Transformarea Burrows – Wheeler (BWT) sau sortarea blocurilor.
- Transformarea Mutare în față (MTF).
- Codare pe lungime de rulare (RLE) a rezultatului MTF.
- Codificare Huffman.
- Selecție între mai multe tabele Huffman.
- Codare unară de bază-1 de selecție a tabelului Huffman.
- Codificare Delta (Δ) a lungimilor de biți ai codului Huffman.
- Matrice de biți rare care arată ce simboluri sunt utilizate.
Initial run-length encodingEdit
Orice secvență de 4 până la 255 simboluri duplicate consecutive este înlocuită de primele 4 simboluri și o lungime repetată între 0 și 251. Astfel secvența AAAAAAABBBBCCCD este înlocuit cu AAAA\3BBBB\0CCCD, unde \3 și \0 reprezintă valorile de octeți 3 și respectiv 0. Rulourile de simboluri sunt întotdeauna transformate după 4 simboluri consecutive, chiar dacă lungimea de rulare este setată la zero, pentru a menține transformarea reversibilă.
În cel mai rău caz, poate provoca o expansiune de 1,25 și în cel mai bun caz, o reducere la < 0,02. În timp ce specificația permite teoretic codificarea rulărilor de lungime 256-259, codificatorul de referință nu va produce o astfel de ieșire.
Autorul bzip2 a declarat că pasul RLE a fost o greșeală istorică și a fost doar intenționat pentru a proteja implementarea originală BWT de cazuri patologice.
Transformarea Burrows – Wheeler
Acesta este tipul de bloc reversibil care se află în centrul bzip2. Blocul este complet autonom, cu tampoane de intrare și ieșire rămase de aceeași dimensiune – în bzip2, limita de funcționare pentru această etapă este de 900 kB. Pentru sortarea în blocuri, se creează o matrice (noțională), în care rândul i conține întregul tampon, rotit pentru a porni de la simbolul i. După rotație, rândurile matricei sunt sortate în ordine alfabetică (numerică). Un indicator de 24 de biți este stocat marcând poziția de pornire pentru momentul în care blocul este netransformat. În practică, nu este necesar să construim matricea completă; mai degrabă, sortarea se efectuează folosind pointeri pentru fiecare poziție din buffer. Tamponul de ieșire este ultima coloană a matricei; acesta conține întregul buffer, dar reordonat astfel încât să conțină probe mari de simboluri identice.
Mutați în față transformEdit
Din nou, această transformare nu modifică dimensiunea blocului procesat. Fiecare dintre simbolurile utilizate în document este plasat într-o matrice. Când un simbol este procesat, acesta este înlocuit de locația sa (index) în matrice și acel simbol este amestecat în partea din față a matricei. Efectul este că simbolurile recurente imediat sunt înlocuite cu simboluri zero (cursele lungi ale oricărui simbol arbitrar devin astfel curse de simboluri zero), în timp ce alte simboluri sunt remapate în funcție de frecvența lor locală.
Multe date „naturale” conține simboluri identice care se repetă într-un interval limitat (textul este un bun exemplu). Deoarece transformarea MTF atribuie valori scăzute simbolurilor care reapar frecvent, acest lucru are ca rezultat un flux de date care conține multe simboluri în domeniul întregului scăzut, multe dintre ele fiind identice (simboluri de intrare recurente diferite pot efectiv să se mapeze la același simbol de ieșire). Astfel de date pot fi codificate foarte eficient prin orice metodă de compresie moștenită.
Codificarea pe lungime de rulare a rezultatului MTF resultEdit
Șiruri lungi de zerouri în ieșirea transformării de mutare în față ( care provin din simboluri repetate în ieșirea BWT) sunt înlocuite cu o succesiune de două coduri speciale, RUNA și RUNB, care reprezintă lungimea de rulare ca un număr binar. Zero-urile reale nu sunt niciodată codate în ieșire; un zero singuratic devine RUNA. (De fapt, acest pas se face în același timp cu MTF; ori de câte ori MTF ar produce zero, crește în schimb un contor pentru a codifica apoi cu RUNA și RUNB.)
Secvența 0, 0, 0, 0, 0, 1 ar fi reprezentat ca RUNA, RUNB, 1; RUNA, RUNB reprezintă valoarea 5 așa cum este descris mai jos. Codul de lungime alergării este terminat prin atingerea unui alt simbol normal. Acest proces RLE este mai flexibil decât pasul RLE inițial, deoarece este capabil să codeze numere întregi arbitrare lungi (în practică, acest lucru este de obicei limitat de dimensiunea blocului, astfel încât acest pas să nu codifice o rulare de mai mult de 900000 de octeți). Lungimea de rulare este codificată în acest mod: atribuirea valorilor de poziție de 1 la primul bit, 2 la al doilea, 4 la al treilea etc. în secvență, înmulțiți fiecare valoare de loc într-un loc RUNB cu 2 și adăugați toate valorile locului rezultate (pentru valorile RUNA și RUNB deopotrivă) împreună. Acest lucru este similar cu numerotarea bijectivă a bazei 2.Astfel, secvența RUNA, RUNB are ca rezultat valoarea (1 + 2 × 2) = 5. Ca exemplu mai complicat:
RUNA RUNB RUNA RUNA RUNB (ABAAB) 1 2 4 8 16 1 4 4 8 32 = 49
Huffman codingEdit
Acest proces înlocuiește simbolurile de lungime fixă în intervalul 0-258 cu coduri de lungime variabilă bazate pe frecvența de utilizare. Codurile utilizate mai frecvent ajung să fie mai scurte (2-3 biți), în timp ce codurile rare pot fi alocate până la 20 de biți. Codurile sunt selectate cu atenție, astfel încât nici o secvență de biți să nu poată fi confundată pentru un cod diferit.
Codul de sfârșit de flux este deosebit de interesant. Dacă există n octeți (simboluri) diferiți utilizați în datele necomprimate, atunci codul Huffman va consta din două coduri RLE (RUNA și RUNB), coduri de simbol n – 1 și un cod de sfârșit de flux. Datorită rezultatului combinat al codificărilor MTF și RLE din cei doi pași anteriori, nu este niciodată nevoie să se facă referire în mod explicit la primul simbol din tabelul MTF (ar fi zero în MTF obișnuit), salvând astfel un simbol pentru sfârșit- marker de flux (și explicând de ce numai n – 1 simboluri sunt codificate în arborele Huffman). În cazul extrem în care se folosește un singur simbol în datele necomprimate, nu vor exista deloc coduri de simboluri în arborele Huffman și întregul bloc va fi format din RUNA și RUNB (repetând implicit octetul unic) și un sfârșit de -marcator de curent cu valoarea 2.
0: RUNA, 1: RUNB, 2–257: valori de octeți 0–255, 258: sfârșitul fluxului, finalizarea procesării (poate fi la fel de mic ca 2).
Multiple Huffman tablesEdit
Mai multe tabele Huffman de dimensiuni identice pot fi utilizate cu un bloc dacă câștigul din utilizarea acestora este mai mare decât costul includerii tabelului suplimentar. Pot fi prezente cel puțin 2 și până la 6 tabele, cel mai potrivit tabel fiind reselectat înainte de fiecare 50 de simboluri procesate. Acest lucru are avantajul de a avea o dinamică Huffman foarte receptivă, fără a fi nevoie să furnizați continuu tabele noi, așa cum ar fi necesar în DEFLATE. Codificarea pe lungimea de rulare din pasul anterior este concepută pentru a avea grijă de codurile care au o probabilitate inversă de utilizare mai mare decât cel mai scurt cod Huffman cod utilizat.
Codificarea unitară a selecției tabelului HuffmanEdit
Dacă sunt utilizate mai multe tabele Huffman, selecția fiecărui tabel (numerotată de la 0 la 5) se face dintr-o listă printr-un bit terminat zero rulat între 1 și 6 biți în lungime. Selecția este într-o listă MTF a tabelelor. Utilizarea acestei caracteristici are ca rezultat o expansiune maximă de aproximativ 1.015, dar în general mai mică. Această expansiune este probabil mult prea umbrită de avantajul de a selecta tabele Huffman mai adecvate, iar cazul obișnuit al continuării utilizării aceleiași tabele Huffman este reprezentat ca un singur bit. Mai degrabă decât codificarea unară, aceasta este efectiv o formă extremă a unui arbore Huffman, unde fiecare cod are jumătate din probabilitatea codului anterior.
Delta encodingEdit
Lungimile de biți ale codului Huffman sunt necesare pentru reconstituirea fiecăruia dintre tabelele canonice Huffman utilizate. Fiecare lungime de bit este stocată ca o diferență codificată față de lungimea de bit a codului anterior. Un bit zero (0) înseamnă că lungimea bitului anterior ar trebui să fie duplicat pentru codul curent, în timp ce un bit (1) înseamnă că ar trebui citit un bit suplimentar și lungimea bitului ar trebui să fie incrementată sau decrementată pe baza valorii respective.
În cazul obișnuit se folosește un singur bit pe simbol pe tabel și cel mai rău caz – trecând de la lungimea 1 la lungimea 20 – ar necesita aproximativ 37 de biți. Ca urmare a codificării MTF anterioare, lungimile codului ar începe de la 2-3 biți (coduri utilizate foarte frecvent) și ar crește treptat, ceea ce înseamnă că formatul delta este destul de eficient, necesitând în jur de 300 de biți (38 octeți) pe tabelul complet Huffman. .
Matricea de biți sparse Editați
O hartă de biți este utilizată pentru a arăta ce simboluri sunt utilizate în interiorul blocului și ar trebui să fie incluse în arborii Huffman. Este posibil ca datele binare să utilizeze toate cele 256 de simboluri reprezentabile cu un octet, în timp ce datele textuale pot utiliza doar un mic subset de valori disponibile, acoperind probabil intervalul ASCII între 32 și 126. Stocarea a 256 de biți zero ar fi ineficientă dacă ar fi în mare parte neutilizate. Se folosește o metodă rară: cele 256 de simboluri sunt împărțite în 16 intervale și numai dacă simbolurile sunt utilizate în acel bloc este inclusă o matrice de 16 biți. Prezența fiecăruia dintre aceste 16 intervale este indicată de o matrice de biți suplimentară de 16 biți în partea din față.
Harta de biți totală utilizează între 32 și 272 de biți de stocare (4-34 octeți). În schimb, algoritmul DEFLATE ar arăta absența simbolurilor prin codificarea simbolurilor ca având o lungime de biți zero cu codare pe lungime de rulare și codare suplimentară Huffman.