Algoritmul lui Huffman este utilizat pentru a comprima sau codifica date. În mod normal, fiecare caracter dintr-un fișier text este stocat ca opt biți (cifre, fie 0, fie 1) care se mapează cu acel caracter folosind o codificare numită ASCII. Un fișier codat Huffman descompune structura rigidă pe 8 biți, astfel încât cele mai frecvent utilizate caractere sunt stocate în doar câțiva biți („a” ar putea fi „10” sau „1000” mai degrabă decât ASCII, care este „01100001”). Cele mai puțin frecvente caractere, atunci, vor ocupa adesea mult mai mult de 8 biți („z” ar putea fi „00100011010”), dar pentru că apar atât de rar, codificarea Huffman, în ansamblu, creează un fișier mult mai mic decât originalul.
Pași
Partea 1 din 2: Codificare
Pasul 1. Numărați frecvența fiecărui caracter din fișierul care va fi codat
Includeți un personaj fals pentru a marca sfârșitul fișierului - acest lucru va fi important mai târziu. Deocamdată, numiți-l EOF (sfârșitul fișierului) și marcați-l ca având o frecvență de 1.
De exemplu, dacă doriți să codificați un fișier text care să citească „ab ab cab”, veți avea „a” cu frecvența 3, „b” cu frecvența 3, „(spațiu) cu frecvența 2,„ c”cu frecvența 1 și EOF cu frecvența 1
Pasul 2. Stocați caracterele ca noduri de copac și puneți-le într-o coadă prioritară
Veți construi un arbore binar mare cu fiecare caracter ca o frunză, așa că ar trebui să stocați caracterele într-un format astfel încât să poată deveni noduri ale arborelui. Plasați aceste noduri într-o coadă de prioritate cu frecvența fiecărui caracter ca prioritate a nodului său.
- Un arbore binar este un format de date în care fiecare bucată de date este un nod care poate avea până la un părinte și doi copii. Este deseori desenat ca un copac ramificat, de unde și numele.
- O coadă este o colecție de date numită în mod adecvat, în care primul lucru care intră în coadă este, de asemenea, primul lucru care iese (cum ar fi așteptarea la coadă). Într-o coadă de prioritate, datele sunt stocate în ordinea priorității lor, astfel încât primul lucru care trebuie să fie cel mai urgent lucru, cel cu cea mai mică prioritate, mai degrabă decât primul lucru pus în stânga.
- În exemplul „ab ab cab”, coada de prioritate ar arăta astfel: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Pasul 3. Începeți să vă construiți copacul
Eliminați (sau scoateți din coadă) cele două lucruri cele mai urgente din coada de prioritate. Creați un nou nod de copac pentru a fi părintele acestor două noduri, stocând primul nod ca fișierul său stâng și al doilea drept copilul său drept. Prioritatea noului nod ar trebui să fie suma priorităților copilului său. Apoi puneți acest nou nod în coada de prioritate.
Coada prioritară arată acum: {'': 2, nod nou: 2, 'a': 3, 'b': 3}
Pasul 4. Finalizați construirea copacului:
repetați pasul de mai sus până când există un singur nod în coadă. Rețineți că, pe lângă nodurile pe care le-ați creat pentru caractere și frecvențele acestora, veți fi, de asemenea, stoarcerea, transformarea în copaci și reîncodarea nodurilor părinte, noduri care sunt deja ele însele copaci.
- Când ați terminat, ultimul nod din coadă va fi rădăcina arborelui de codificare, cu toate celelalte noduri ramificându-se din acesta.
- Cele mai frecvent utilizate caractere vor fi frunzele cele mai apropiate de vârful copacului, în timp ce caracterele rare utilizate vor fi poziționate în partea de jos a copacului, mai departe de rădăcină.
Pasul 5. Creați o hartă de codificare. Mergeți prin copac pentru a ajunge la fiecare personaj. De fiecare dată când vizitați copilul stâng al unui nod, acesta este un „0”. De fiecare dată când vizitați copilul potrivit al unui nod, acesta este un „1”. Când ajungeți la un personaj, stocați caracterul cu secvența de 0 și 1 pe care a fost nevoie pentru a ajunge acolo. Această secvență este ceea ce caracterul va fi codat ca în fișierul comprimat. Stocați personajele și secvențele lor pe o hartă.
- De exemplu, începeți de la rădăcină. Vizitați copilul stâng al rădăcinii, apoi vizitați copilul stâng al acelui nod. Deoarece nodul în care vă aflați acum nu are copii, ați atins un caracter. Aceasta este ' '. Din moment ce ați plecat de două ori la stânga pentru a ajunge aici, codarea pentru '' este „00”.
- Pentru acest arbore, harta va arăta astfel: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Pasul 6. În fișierul de ieșire, includeți harta de codificare ca antet
Aceasta va permite decodarea fișierului.
Pasul 7. Codificați fișierul
Pentru fiecare caracter din fișier care trebuie codat, scrieți secvența binară pe care ați stocat-o pe hartă. După ce ați terminat codarea fișierului, asigurați-vă că adăugați EOF la final.
- Pentru fișierul „ab ab cab”, fișierul codat va arăta astfel: „1011001011000101011011”.
- Fișierele sunt stocate ca octeți (8 biți sau 8 cifre binare). Deoarece algoritmul Huffman Encoding nu folosește formatul pe 8 biți, fișierele codate nu vor avea adesea lungimi care sunt multipli de 8. Restul cifrelor vor fi completate cu 0s. În acest caz, două 0 ar fi adăugate la sfârșitul fișierului, care arată ca un alt spațiu. Aceasta ar putea fi o problemă: cum ar ști decodorul când se va opri din citire? Cu toate acestea, deoarece am inclus un caracter de sfârșit de fișier, decodorul va ajunge la acest lucru și apoi se va opri, ignorând orice altceva care a fost adăugat după.
Partea 2 din 2: Decodare
Pasul 1. Citiți într-un fișier codat Huffman
Mai întâi, citiți antetul, care ar trebui să fie harta de codificare. Utilizați acest lucru pentru a construi un arbore de decodare în același mod în care ați construit arborele pe care l-ați folosit pentru a codifica fișierul. Cei doi copaci ar trebui să fie identici.
Pasul 2. Citiți în binar câte o cifră la rând
Parcurgeți arborele în timp ce citiți: dacă citiți într-un „0”, mergeți la copilul din stânga al nodului în care vă aflați și, dacă citiți într-un „1”, mergeți la copilul potrivit. Când ajungeți la o frunză (un nod fără copii), ați ajuns la un personaj. Scrieți caracterul în fișierul decodat.
Datorită modului în care sunt stocate caracterele în arbore, codurile pentru fiecare caracter au o proprietate de prefix, astfel încât codificarea binară a niciunui caracter nu poate apărea vreodată la începutul codării unui alt caracter. Codificarea pentru fiecare personaj este total unică. Acest lucru face decodarea mult mai ușoară
Pasul 3. Repetați până ajungeți la EOF
Felicitări! Ați decodat fișierul.
