Codarea Huffman

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

1. Ordonare: Se ordonează simbolurile sursei în ordine descrescătoare a probabilităților: P(a₁) ≥ P(a₂) ≥ ... ≥ P(aₙ)

2. 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

3. Reordonare: Sursa redusă se reordonează descrescător după probabilitate

4. Repetare: Se repetă pașii 2-3 până se ajunge la o sursă redusă formată din doar 2 simboluri

5. Atribuire coduri: Sursei finale de 2 elemente i se atribuie codurile 0 și 1

6. 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:

Pasul 1: Prima reducere

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

Sursă redusă (reordonată):

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ă):

Pasul 3: A treia reducere

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

Sursă redusă (reordonată):

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

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