Compresia datelor (1) - Codificarea Huffman

Publicat de pe

Descrierea algoritmului

Algoritmul Huffman este un algoritm de compresie a datelor care a fost dezvoltat de către David A. Huffman în 1952. Scopul său este de a reduce dimensiunea datelor prin asignarea de coduri de lungime variabilă fiecărui simbol din setul de date, astfel încât simbolurile care apar mai des să aibă coduri mai scurte, iar cele care apar mai rar să aibă coduri mai lungi.

Procesul începe prin analizarea frecvenței de apariție a fiecărui simbol din setul de date. Apoi, se construiește un arbore binar în care simbolurile cu frecvențe mai mici sunt situate în partea inferioară a arborelui, iar cele cu frecvențe mai mari sunt situate în partea superioară. Codurile binare sunt atribuite prin parcurgerea acestui arbore: adăugând un "0" pentru fiecare muchie stângă și un "1" pentru fiecare muchie dreaptă.

Prin asignarea de coduri de lungime variabilă în funcție de frecvența simbolurilor, se realizează o compresie eficientă a datelor. În plus, deoarece fiecare cod este unic pentru fiecare simbol, decodificarea este simplă și eficientă.

Algoritmul Huffman este utilizat în numeroase aplicații de compresie a datelor, cum ar fi formatele de fișiere comprimate, arhivele, și în alte domenii în care economisirea spațiului de stocare este esențială.

Mod de funcționare

Iată o descriere pas cu pas a modului în care funcționează algoritmul Huffman:

  • Calcularea frecvenței: Algoritmul Huffman începe prin calcularea frecvenței de apariție a fiecărui simbol din setul de date care trebuie comprimat. Aceasta poate fi, de exemplu, numărul de apariții al fiecărui caracter dintr-un text sau numărul de apariții al fiecărei culori într-o imagine.

  • Crearea arborelui Huffman: După ce frecvențele au fost calculate, algoritmul începe să construiască un arbore Huffman. Arborele este construit folosind un proces iterativ care începe cu toate simbolurile inițiale ca noduri și le combine treptat în noduri mai mari, luând în considerare frecvențele lor.

    • Se creează un nod pentru fiecare simbol și se etichetează cu frecvența sa.
    • Nodurile sunt sortate în funcție de frecvență și sunt combinate într-un arbore astfel încât se  minimizează lungimea totală a codurilor binare. (stânga se codifică cu 1, iar dreapta cu 0)

     Sursa: Huffman Coding
  • Atribuirea codului binar: Pe măsură ce arborele este construit, se atribuie coduri binare unice fiecărui simbol din setul de date. Când se merge în jos pe arbore, un bit '0' este adăugat la cod atunci când se merge pe ramura stângă și un bit '1' atunci când se merge pe ramura dreaptă. Codurile atribuite sunt făcute astfel încât niciun cod să nu fie prefixul altui cod, ceea ce face posibilă decodificarea fără ambiguități.
  • Generarea tabelului Huffman: După ce toate simbolurile au fost atribuite cu coduri binare, se construiește un tabel care mapează fiecare simbol la codul său Huffman.
  • Compresia datelor: Utilizând tabela Huffman, datele inițiale sunt comprimate prin înlocuirea fiecărui simbol cu codul său corespunzător. Astfel, datele comprimate sunt o secvență de biți, care ocupă în general mai puțin spațiu decât datele originale, mai ales atunci când există simboluri care apar frecvent și pot fi reprezentate printr-un număr mic de biți.
  • Decompresia datelor: La decodificare, arborele Huffman este reconstruit folosind aceleași frecvențe și coduri binare. Datele comprimate sunt parcurse bit cu bit, iar în funcție de secvența de biți, se folosește arborele pentru a reconstrui datele originale.
  • Salvarea datelor comprimate: În fișierul comprimat se vor salva datele comprimate împreună cu arborele de decodificare.

Algoritmul Huffman este utilizat într-o varietate de aplicații de compresie de date, cum ar fi în formatele de fișiere cu compresie fără pierderi, precum ZIP, GIF și PNG. Este eficient în compresia datelor în cazul în care există anumite simboluri care apar mult mai frecvent decât altele.

Exemplu grafic


Implementarea

  • https://github.com/SimedruF/Simple_HuffmanCodes/tree/main
  • Pentru debug am folosit Visual studio code cu configurația de mai jos din fișierul launch.json (cppvsdbg): 
     
  {
    // Use IntelliSense to learn about possible attributes.
    // Hover to view descriptions of existing attributes.
    // For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387
    "version": "0.2.0",
    "configurations": [
        {
            "name": "(Windows) Launch",
            "type": "cppvsdbg",
            "request": "launch",
            "program": "${workspaceFolder}/Debug/SimpleHuffmanApp.exe",
            "args": [],
            "stopAtEntry": false,
            "cwd": "${fileDirname}",
            "environment": [],
            "console": "externalTerminal"
        }    
    ]
}

  • Debug session

  • Variabilele și watch window sunt vizibile în imaginea de mai jos , unde se poate observa arborele binar generat pe baza frecvenței caracterelor.

Documentație proiect

Mulțumesc pentru atenție!

Pentru întrebări și/sau consultanță tehnică vă stau la dispoziție pe blog mai jos în secțiunea de comentarii sau pe email simedruflorin@automatic-house.ro.
O zi plăcută tuturor !
Back to top of page

Etichete

Afișați mai multe

Arhiva

Afișați mai multe