Partea teoretică
Algoritmul lui Huffman
Unul dintre primii algoritmi de codificare eficientă a informațiilor a fost propus de Huffman în 1952. Acest algoritm a devenit baza unui număr mare de programe pentru comprimarea informațiilor. De exemplu, codificarea Huffman este folosită în programele de compresie ARJ. ZIP. RAR. în algoritmul de comprimare a imaginilor grafice cu pierderi JPEG. și, de asemenea, încorporate în mașini fax moderne.
Eficient Huffman de codificare este de a prezenta cele mai probabile literele (comune) coduri binare de lungime mai scurt și cel mai puțin probabil - cea mai mare lungimea codurilor (dacă toate cuvintele de cod la lungime au fost epuizate). Aceasta se face astfel încât lungimea medie a codului pentru litera mesajului original să fie minimă.
Înainte de începerea codării, va fi cunoscută probabilitatea apariției fiecărei litere din care va fi compusă mesajul. Pe baza acestei tabele de probabilitate, arborele de cod Huffman este construit, care este folosit pentru a codifica literele.
Construirea unui arbore de cod Huffman
Pentru a ilustra algoritmul Huffman, luați în considerare metoda grafică pentru construirea unui arbore de codificare. Înainte de a face acest lucru, introducem câteva definiții adoptate pentru a descrie algoritmul Huffman utilizând această metodă.
Un grafic este o colecție dintr-un set de noduri și un set de arce direcționate de la un nod la altul.
Un arbore este un grafic cu următoarele proprietăți:- nu mai mult de un arc este inclus în unul dintre noduri;
- Numai un nod nu include nici un arc (acest nod se numește rădăcina copacului);
- care se deplasează prin arce de la rădăcină, puteți ajunge la orice nod.
O frunză a unui copac este un nod din care nu părăsește un arc. Într-o pereche de noduri de copaci conectate printr-un arc, cel de la care apare se numește părinte. celălalt copil.
Două noduri sunt numite frați. dacă au același părinte.
Un arbore binar este un arbore care are exact două arce din toate nodurile, cu excepția frunzelor.
Arborele de codare Huffman este un arbore binar în care fiecare nod are greutate. iar greutatea părintelui este egală cu greutatea totală a copiilor lui.
Algoritmul de construire a arborelui de codificare Huffman este următorul:- Literele alfabetului de intrare formează o listă a nodurilor libere ale arborelui de codificare viitor. Fiecare nod din această listă are o greutate egală cu probabilitatea apariției literei corespunzătoare în mesaj.
- Sunt selectate două noduri libere ale copacului cu cele mai mici greutăți. Dacă există mai mult de două noduri libere cu cele mai mici greutăți, atunci putem lua orice pereche.
- Părintele lor este creat cu o greutate egală cu greutatea lor totală.
- Părintele este adăugat la lista de noduri libere și doi dintre copiii lui sunt eliminați din această listă.
- Un bit din nodul părinte este atribuit biți 1, celălalt este 0.
- Elementele 2, 3, 4, 5 se repetă până când în lista nodurilor libere rămâne un singur nod. Acest nod va fi rădăcina copacului. Greutatea sa este egală cu una - probabilitatea totală a tuturor literelor mesajului.
Acum, deplasând de-a lungul arborelui de cod de sus în jos și scriind secvențial cifre binare corespunzătoare arcilor, se pot obține codurile literelor alfabetului de intrare.
De exemplu, luați în considerare construirea arborelui de codificare Huffman pentru alfabetul celor opt litere enumerate în tabelul 1.
Începem să construim un copac din lista frunzelor (vezi Figura 1) și urmați pașii.
Fig. 1. Lista nodurilor frunze libere.
În prima etapă, două dintre frunzele copacului sunt alese cu cele mai mici greutăți z7 și z8. Ele se alătură nodului părinte, a cărui greutate este setată la 0,04 +0,02 = 0,06. Apoi, nodurile z7 și z8 sunt eliminate din lista liberă. Nodul z7 corespunde cu ramura 0 a părintelui, nodul z8 cu ramura 1. Arborele de codare după prima etapă este prezentat în Fig. 2.
Fig. 2. Arborele de codificare Huffman după primul pas.
În a doua etapă, perechea "cea mai ușoară" este foaia z6 și nodul liber (z7 + z8). Pentru ei, este creat un părinte cu o greutate de 0,16. Nod z6 0 corespunde nodului părinte ramură (z7 + z8) - ramură 1. În această etapă, arborele de codificare după cum urmează (a se vedea figura 3 ..).
Fig. 3. Arborele de codificare Huffman după al doilea pas.
În a treia etapă, cele mai mici probabilități sunt z5. z4. z3 și un nod liber (z6 + z7 + z8). Astfel, la acest pas, puteți crea un părinte pentru z5 și (z6 + z7 + z8) cu o greutate de 0,26. obținerea arborelui de codare prezentat în Fig. 4. Rețineți că în această situație sunt posibile mai multe variante ale nodurilor de legătură cu cele mai mici greutăți. În acest caz, toate aceste variante vor fi corecte, deși pot conduce la seturi diferite de coduri, care, totuși, vor avea aceeași eficiență pentru o anumită distribuție de probabilități.
Fig. 4. Arborele de codificare Huffman după al treilea pas.
În al patrulea pas, perechea "cea mai ușoară" sunt frunzele z3 și z4. Arborele de codificare Huffman este prezentat în Fig. 5.
Fig. 5. Arborele de codificare Huffman după al patrulea pas.
În al cincilea pas, selectăm nodurile cu cele mai mici ponderări 0,22 și 0,20. Arborele de codificare Huffman după al cincilea pas este prezentat în Fig. 6.
Fig. 6. Arborele de codificare Huffman după al cincilea pas.
La a șasea etapă, există trei noduri libere cu scale 0.42. 0,32 și 0,26. Alegeți cele mai mici greutăți 0,32 și 0,26. Arborele de codificare Huffman după al șaselea pas este prezentat în Fig. 7.
Fig. 7. Arborele de codificare Huffman după al șaselea pas.
În a șaptea etapă, rămâne să combinăm cele două vârfuri libere rămase, după care obținem arborele de codificare Huffman final, prezentat în Fig. 8.
Fig. 8. Arborele de codificare Huffman final.
Pe baza arborelui construit, literele sunt reprezentate de coduri care reflectă calea de la nodul rădăcină la foaia corespunzătoare literei dorite. În exemplul considerat, literele alfabetului de intrare sunt codificate așa cum se arată în Tabelul 2.
Tabelul 3 arată că codurile s-au dovedit a fi prefixe, iar cele mai probabile litere corespund codurilor mai scurte.
Implementarea practică a algoritmului
Pentru a spori eficiența compresiei, este necesar ca atunci când se construiește un arbore de cod, să se folosească date despre probabilitățile apariției literelor din acest fișier și să nu fie medii pe un număr mare de texte. În urma acestui fapt, sunt necesare statistici privind apariția literelor dosarului comprimat, care pot fi obținute printr-o trecere preliminară prin dosar.
Pentru a accelera munca, este obișnuit să nu determinăm probabilitatea apariției literelor pi. și frecvența apariției (numărul de apariții) a literei din fișierul ni. Acest lucru face posibilă simplificarea și accelerarea semnificativă a algoritmului (nu sunt necesare operațiuni în virgulă mobilă lentă și operațiuni de divizare). Cu această abordare, algoritmul de operare nu se modifică, deoarece frecvențele sunt direct proporționale cu probabilitățile. Merită menționat faptul că greutatea nodului rădăcină al copacului de codare va fi în acest caz egală cu numărul total de litere din fișierul care este procesat.
Instruire interactivă
După ce vă cunoașteți partea teoretică a lucrării, vă sugerăm să practicați practicarea construirii arborilor de cod Huffman folosind un sistem de formare interactivă. Pentru a face acest lucru, du-te la acest link.
Articole similare
Trimiteți-le prietenilor: