Calculator calculator cod Huffman

Un mic fragment din Wikipedia.

Algoritmul Huffman este un algoritm de adaptare greoi pentru codarea optimă a prefixului alfabetului cu redundanță minimă. A fost dezvoltat în 1952 de către un student absolvent de la Institutul de Tehnologie din Massachusetts, David Huffman, atunci când și-a scris lucrarea. Utilizată în prezent în multe programe de comprimare a datelor.







Această metodă de codificare constă din două etape principale:
Construcția arborelui optim de cod.
Construiți o cartografiere simbolică a codului bazată pe arborele construit.

Ideea algoritmului este următoarea: cunoașterea probabilității simbolurilor în mesaj, puteți descrie procedura de construire a codurilor de lungime variabilă constând dintr-un număr întreg de biți. Simbolurile sunt mai predispuse să asocieze coduri mai scurte. Codurile Huffman au proprietatea prefixului (adică, niciun cuvânt de cod nu este un prefix al celuilalt), ceea ce le permite să fie decodificate în mod unic.






Algoritmul clasic Huffman de la intrare primește un tabel al frecvențelor de apariție a simbolurilor în mesaj. Pe baza acestui tabel, arborele de codificare Huffman (arborele H) este construit.

  1. Simbolurile alfabetului de intrare formează o listă de noduri libere. Fiecare foaie are o greutate care poate fi egală fie cu probabilitatea fie cu numărul de apariții ale caracterului din mesajul comprimabil.
  2. Sunt selectate două noduri libere ale copacului cu cele mai mici greutăți.
  3. Părintele lor este creat cu o greutate egală cu greutatea lor totală.
  4. Parintele este adăugat la lista de noduri libere, iar cei doi descendenți ai acestuia sunt eliminați din această listă.
  5. Un pic din părinte este atribuit biți 1, celălalt bit de biți 0.
  6. Etapele care încep de la cea de-a doua se repetă până când în lista nodurilor libere rămâne un singur nod liber. El va fi considerat rădăcina copacului.

Acest proces poate fi reprezentat ca construirea unui arbore, a cărui rădăcină - un simbol al suma probabilităților de simboluri combinate, obținute prin combinarea simbolurilor din ultima etapă, descendenții lui N0 - caracterele din etapa anterioară, și așa mai departe ..

Pentru a determina codul pentru fiecare dintre caracterele incluse în mesaj, trebuie să mergem tot drumul de la rădăcină la o frunză de copac care corespunde simbolului curent, acumularea de biți vă deplasa prin ramurile copacului (prima ramură din calea corespunde cel mai puțin semnificativ). Astfel obținut este o secvență de biți ai simbolului codului, scrise în ordine inversă.







Articole similare

Pagina anterioară

Pagina următoare

Trimiteți-le prietenilor: