Codarea Huffman - ProgMaster

Prezentare generală

Codarea Huffman (1952, David Huffman) este o metodă de codificare care furnizează întotdeauna un cod optimal — adică un cod unic decodabil, cu proprietate de prefix și cu lungimea medie minimă posibilă. Codul Huffman este un cod compact (cvasioptimal), realizând cea mai mică lungime medie a cuvintelor de cod dintre toate codurile prefix posibile.

Algoritmul Huffman — pași

Ordonare: Se ordonează simbolurile sursei în ordine descrescătoare a probabilităților: P(a₁) ≥ P(a₂) ≥ ... ≥ P(aₙ)
Reducere: Se construiește o sursă redusă prin reunirea ultimelor două simboluri (cele cu cele mai mici probabilități) într-un singur simbol nou, a cărui probabilitate este suma probabilităților celor două simboluri reunite
Reordonare: Sursa redusă se reordonează descrescător după probabilitate
Repetare: Se repetă pașii 2-3 până se ajunge la o sursă redusă formată din doar 2 simboluri
Atribuire coduri: Sursei finale de 2 elemente i se atribuie codurile 0 și 1
Parcurgere inversă: Se parcurge în sens invers arborele de reduceri, la fiecare bifurcație adăugând un simbol suplimentar (0 sau 1) pentru a distinge cele două ramuri

Proprietățile codului Huffman

Este întotdeauna un cod prefix (instantaneu decodabil)
Este optimal: niciun alt cod prefix nu poate avea o lungime medie mai mică
Lungimea medie satisface: H(X) ≤ L < H(X) + 1 (pentru coduri binare)
Eficiența este maximă dintre toate codurile prefix

Exemplu complet pas cu pas

Sursa inițială

Fie sursa S = {s₁, s₂, s₃, s₄, s₅} cu probabilitățile:

Simbol	s₁	s₂	s₃	s₄	s₅
P	0.35	0.25	0.20	0.12	0.08

Pasul 1: Prima reducere

Se reunesc s₄ (0.12) și s₅ (0.08) → simbol nou {s₄,s₅} cu P = 0.20

Sursă redusă (reordonată):

Simbol	s₁	s₂	s₃	{s₄,s₅}
P	0.35	0.25	0.20	0.20

Pasul 2: A doua reducere

Se reunesc s₃ (0.20) și {s₄,s₅} (0.20) → {s₃,s₄,s₅} cu P = 0.40

Sursă redusă (reordonată):

Simbol	{s₃,s₄,s₅}	s₁	s₂
P	0.40	0.35	0.25

Pasul 3: A treia reducere

Se reunesc s₁ (0.35) și s₂ (0.25) → {s₁,s₂} cu P = 0.60

Sursă redusă (reordonată):

Simbol	{s₁,s₂}	{s₃,s₄,s₅}
P	0.60	0.40

Pasul 4: Atribuire coduri (de la final spre început)

Sursa finală de 2 elemente:

{s₁,s₂} → 0
{s₃,s₄,s₅} → 1

Parcurgere inversă — pasul 3:

s₁ → 00
s₂ → 01

Parcurgere inversă — pasul 2:

s₃ → 10
{s₄,s₅} → 11

Parcurgere inversă — pasul 1:

s₄ → 110
s₅ → 111

Rezultat final

Simbol	P	Cuvânt de cod	Lungime
s₁	0.35	`00`	2
s₂	0.25	`01`	2
s₃	0.20	`10`	2
s₄	0.12	`110`	3
s₅	0.08	`111`	3

Calcul lungime medie

L = Σ pᵢ · lᵢ
  = 0.35 × 2 + 0.25 × 2 + 0.20 × 2 + 0.12 × 3 + 0.08 × 3
  = 0.70 + 0.50 + 0.40 + 0.36 + 0.24
  = 2.20 biți/simbol

Calcul entropie și eficiență

H(X) = -(0.35·log₂0.35 + 0.25·log₂0.25 + 0.20·log₂0.20 + 0.12·log₂0.12 + 0.08·log₂0.08)
     = -(0.35·(-1.515) + 0.25·(-2.0) + 0.20·(-2.322) + 0.12·(-3.059) + 0.08·(-3.644))
     = 0.530 + 0.500 + 0.464 + 0.367 + 0.292
     = 2.153 biți/simbol

Eficiența: η = H(X) / L = 2.153 / 2.20 = 0.9786 (97.86%)
Redundanța: R = 1 - η = 0.0214 (2.14%)

Verificarea primei teoreme a lui Shannon

H(X) ≤ L < H(X) + 1
2.153 ≤ 2.20 < 3.153  ✓

Coduri Huffman de dispersie minimă

Când la reordonarea sursei reduse, simbolul compus se plasează pe poziția cea mai de sus posibil (cât mai aproape de capul listei), se obține un cod Huffman de dispersie minimă. Aceasta conduce la diferențe minime între lungimile cuvintelor de cod, ceea ce este preferabil din motive practice de transmisie (dimensiunea bufferului necesară este mai mică).

Puncte cheie pentru examen

Algoritmul Huffman: ordonare → reunire ultimele 2 → reordonare → repetare → atribuire coduri invers
Codul Huffman este optimal (lungime medie minimă) și are proprietate de prefix
Lungimea medie: L = Σ pᵢ · lᵢ
Eficiența: η = H(X) / L; redundanța: R = 1 - η
Satisface prima teoremă a lui Shannon: H(X) ≤ L < H(X) + 1
Plasarea simbolului compus sus → cod Huffman de dispersie minimă
La examen: trebuie să știi să aplici algoritmul pas cu pas și să calculezi L, η, R