(Timp citire: 4 minute)

Comprimarea fişierelor se referă la reducerea spaţiului ocupat de acestea pe mediul de stocare. Dar fişierele nu sunt bureţi, pe care să-i comprimăm  supunându-i unei forţe. Fişierele sunt formate din biţi. Să luăm, de pildă, formatul zip. Orice utilizator de calculator este familiar cu acest tip de comprimare. Ce se întâmplă atunci când cerem utilitarului de comprimare să transforme un fişier în format zip? Imaginile pot fi comprimate ușor, reducând numărul de pixeli și astfel spațiul ocupat pe mediul de stocare de fişierul comprimat, dar în cazul fișierelor de tip text nu este așa de ușor. Nu putem șterge litere din text, cum am șterge pixeli din imagini, întrucât textul nu ar mai fi lizibil.

În acest articol, vom prezenta algoritmul dezvoltat de David A. Huffman pentru comprimarea fișierelor text.


Citiţi mai multe despre comprimarea fişierelor aici: Cum funcţionează compresia fişierelor?


Principala limitare a fișierelor text este aceea că fiecare literă/caracter este reprezentată, în cod binar, de opt biți de informație (în cazul caracterelor din tabelul ASCII, care conține toate literele din alfabetul latin și cele mai folosite semne de punctuație). De exemplu, litera "A", în cod binar, va fi 01000001, litera "B", 01000010, litera "C", 01000011 șamd.

După cum puteți observa, majoritatea biților sunt inutili în aceste exemple. Totuși, dacă am încerca să înlăturăm acești biți nefolositori, "A" ar deveni 1 (dacă am elimina cei 7 biţi de la stânga la dreapta: 01000001), "B" ar deveni 10 (eliminând primii 6 biţi), "C" ar deveni 11 șamd. Acum fiecare literă va ocupa un spațiu mai mic, dar calculatorul nu va putea ști unde se termină o literă și începe alta (pentru calculator trecerea la bitul nr. 9 înseamnă trecerea la un nou caracter; biţii sunt unul după altul, fără indicatori de demarcaţie între semne). Calculatorul ar putea înțelege "C", de exemplu, care este, după eliminarea biţilor inutili - 11, ca fiind de două ori "A".

În 1952, David A. Huffman a publicat o articol care conținea soluția acestei probleme.


Algoritmul lui Huffman


Să luăm următorul exemplu de text "bara_are_ceara" (caracterele "_" vor fi tratate ca fiind spațiul gol dintre cuvinte).

În primul rând, vom pune toate literele din text într-o listă, conform frecvenței lor în text (prima literă din listă va fi cea mai frecventă din text, iar ultima literă din listă va fi cea mai rară din text). Pentru exemplul nostru, vom avea lista următoare:



Acum că avem lista ordonată în funcţie de frecvenţa literelor, vom lua ultimele două litere din listă (cele mai rare) și le vom conecta, punând suma frecvențelor lor într-un pătrat, deasupra.





Mai departe vom pune gruparea obținută înapoi în listă, în funcție de numărul din pătrat, în acest caz 2. Aşadar, bc va avea asociat numărul 2.





Vom repeta acest pas (luarea ultimelor două elemente din şir, adunarea lor şi punerea sumei în listă) până vom rămâne cu un singur element în listă. Acel element va arată așa:





În final, vom stabili cum vor fi literele reprezentate în cod binar. Vom stabili ca direcţii de deplasare stânga (stânga dumneavoastră) şi dreapta (dreapta dumneavoastră). Pe drumul de la start până la literă, pentru fiecare deplasare la stânga  (cum ar fi de la Start la numărul 5) va fi 0, iar pentru fiecare deplasare la dreapta (cum ar fi de la 9 la litera a) va fi 1.

Acesta va fi rezultatul final:



Astfel, spațiul ocupat de text va fi redus foarte mult (în exemplul de mai sus, am redus textul de la 112 biți la 34 de biți), iar când calculatorul va încerca să transforme codul binar în litere, tot ce va trebui să facă este să urmeze drumul până la literă. Când va găsi litera, va ști că următorul bit va fi începutul unei noi litere, deci nu va fi nicio confuzie.

Iată cum interpretează calculatorul şirul de biţi de mai sus. Citeşte 0 (o ia la stânga, de la start), verifică dacă este o literă şi găseşte un număr (nu o literă). Citeşte bitul următor, 1. Verifică dacă 01 este o literă şi găseşte un număr din nou. Citeşte următorul bit, 0 (avem acum 010). Verifică dacă 010 este o literă şi găseşte că este litera b. Se întoarce la start, citeşte următorul bit din şir, adică 1. Vă las pe dumneavoastră să citiţi mai departe...