Codarea Shannon-Fano

Prezentare generală

Codarea Shannon-Fano este o metodă de codare a surselor discrete care produce coduri instantanee (cu proprietate de prefix), folosind o abordare top-down (de sus în jos). Metoda a fost dezvoltată independent de Claude Shannon și Robert Fano.

Spre deosebire de algoritmul Huffman (care este bottom-up), Shannon-Fano împarte recursiv mulțimea simbolurilor în două submulțimi cu probabilități cât mai egale.

Procedura de codare Shannon-Fano

Pași

1. Ordonare: Se ordonează simbolurile sursei S = {s₁, s₂, ..., sₙ} în ordinea descrescătoare a probabilităților

2. Partiționare: Se împarte mulțimea de simboluri în două submulțimi astfel încât suma probabilităților din fiecare submulțime să fie cât mai apropiată una de cealaltă

3. Atribuire: Se atribuie simbolul 0 primei submulțimi și simbolul 1 celeilalte (sau invers)

4. Recursivitate: Se aplică recursiv pașii 2-3 pe fiecare submulțime, adăugând câte un bit la cuvintele de cod, până când fiecare submulțime conține un singur simbol

Condiția ideală

Metoda funcționează absolut optimal (produce un cod absolut optimal) atunci când probabilitățile simbolurilor sunt puteri întregi ale lui 1/2:

P(sₖ) = (1/2)^nₖ,  unde nₖ este un număr întreg pozitiv

În acest caz, partiționările se pot face exact în două submulțimi cu probabilități egale, iar inegalitatea Kraft devine egalitate:

Σ 2^(-nᵢ) = 1

Exemplu pas cu pas

Sursa

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

Pasul 1: Prima partiționare

Se caută partiția cu probabilități cât mai egale:

• Varianta A: {s₁, s₂} (0.55) vs. {s₃, s₄, s₅, s₆} (0.45) → diferență 0.10
• Varianta B: {s₁, s₂, s₃} (0.75) vs. {s₄, s₅, s₆} (0.25) → diferență 0.50

Se alege Varianta A (diferență minimă):

• {s₁, s₂} → primul bit = 0
• {s₃, s₄, s₅, s₆} → primul bit = 1

Pasul 2: Partiționarea submulțimii {s₁, s₂}

• {s₁} (0.30) vs. {s₂} (0.25) → diferență 0.05

Rezultat:

• s₁ → 00
• s₂ → 01

Pasul 3: Partiționarea submulțimii {s₃, s₄, s₅, s₆}

• {s₃} (0.20) vs. {s₄, s₅, s₆} (0.25) → diferență 0.05
• {s₃, s₄} (0.32) vs. {s₅, s₆} (0.13) → diferență 0.19

Se alege prima variantă:

• {s₃} → 10 (gata — un singur simbol)
• {s₄, s₅, s₆} → 11

Pasul 4: Partiționarea submulțimii {s₄, s₅, s₆}

• {s₄} (0.12) vs. {s₅, s₆} (0.13) → diferență 0.01

Rezultat:

• s₄ → 110
• {s₅, s₆} → 111

Pasul 5: Partiționarea submulțimii {s₅, s₆}

• s₅ → 1110
• s₆ → 1111

Rezultatul final

Calcul lungime medie și eficiență

L = 0.30×2 + 0.25×2 + 0.20×2 + 0.12×3 + 0.08×4 + 0.05×4
  = 0.60 + 0.50 + 0.40 + 0.36 + 0.32 + 0.20
  = 2.38 biți/simbol

Entropia sursei:

H(X) = -(0.30·log₂0.30 + 0.25·log₂0.25 + 0.20·log₂0.20
       + 0.12·log₂0.12 + 0.08·log₂0.08 + 0.05·log₂0.05)
     ≈ 2.361 biți/simbol

Eficiență: η = H(X) / L = 2.361 / 2.38 ≈ 0.992 (99.2%)

Comparație Shannon-Fano vs. Huffman

Concluzie importantă: Algoritmul Huffman este întotdeauna cel puțin la fel de bun ca Shannon-Fano. În cazurile în care probabilitățile nu sunt puteri ale lui 1/2, Huffman poate produce coduri cu lungime medie strict mai mică.

Teorema Kraft-Fano

Inegalitatea Kraft (numită și Kraft-Fano) stabilește echivalența:

Un cod prefix cu lungimile cuvintelor l₁, l₂, ..., lₘ și alfabet de D simboluri există dacă și numai dacă: Σ D^(-lᵢ) ≤ 1

Când inegalitatea devine egalitate (Σ D^(-lᵢ) = 1), arborele de cod este complet — nu există noduri frunză nefolosite.

Puncte cheie pentru examen

• Shannon-Fano: abordare top-down — împărțire recursivă în submulțimi cu probabilități cât mai egale
• Atribuire 0/1 la fiecare partiționare, recursiv, până la un singur simbol per submulțime
• Produce cod prefix (instantaneu), dar nu întotdeauna optimal
• Este absolut optimal doar când P(sₖ) = (1/2)^nₖ
• Huffman este superior: produce întotdeauna lungimea medie minimă
• Inegalitatea Kraft-Fano: Σ D^(-lᵢ) ≤ 1 — condiție necesară și suficientă pentru cod prefix
• La examen: trebuie să știi să aplici procedeul pas cu pas și să compari cu Huffman

Exemplu practic complet: Shannon-Fano vs Huffman

Sursa

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

Algoritmul Shannon-Fano pas cu pas

Pasul 1: Simbolurile sunt deja ordonate descrescător.

Pasul 2: Prima diviziune — se împarte în 2 grupuri cu probabilități cât mai egale:

Grup A: {s₁, s₂, s₃}  → P = 0.30 + 0.25 + 0.20 = 0.75
Grup B: {s₄, s₅, s₆}  → P = 0.12 + 0.08 + 0.05 = 0.25

Alternativă:
Grup A: {s₁, s₂}      → P = 0.55
Grup B: {s₃, s₄, s₅, s₆} → P = 0.45    ← mai echilibrată!

Alegem varianta mai echilibrată: {s₁, s₂} primesc 0, {s₃, s₄, s₅, s₆} primesc 1.

Pasul 3: Subdiviziunea grupului A: {s₁, s₂}:

s₁ (0.30) → 0
s₂ (0.25) → 1

Coduri parțiale: s₁ → 00, s₂ → 01

Pasul 4: Subdiviziunea grupului B: {s₃, s₄, s₅, s₆}:

{s₃}           → P = 0.20  → 0
{s₄, s₅, s₆}  → P = 0.25  → 1

Cod parțial: s₃ → 10

Pasul 5: Subdiviziunea {s₄, s₅, s₆}:

{s₄}      → P = 0.12  → 0
{s₅, s₆}  → P = 0.13  → 1

Cod parțial: s₄ → 110

Pasul 6: Subdiviziunea {s₅, s₆}:

s₅ → 0    cod final: 1110
s₆ → 1    cod final: 1111

Rezultat Shannon-Fano

Calcul lungime medie și eficiență

L_SF = 0.30×2 + 0.25×2 + 0.20×2 + 0.12×3 + 0.08×4 + 0.05×4
     = 0.60 + 0.50 + 0.40 + 0.36 + 0.32 + 0.20
     = 2.38 biți/simbol

H(X) = -(0.30·log₂0.30 + 0.25·log₂0.25 + 0.20·log₂0.20
       + 0.12·log₂0.12 + 0.08·log₂0.08 + 0.05·log₂0.05)
     = 0.5211 + 0.5000 + 0.4644 + 0.3671 + 0.2915 + 0.2161
     = 2.3602 biți/simbol

η_SF = H(X) / L_SF = 2.3602 / 2.38 = 0.9917 = 99.17%

Comparație cu codul Huffman pentru aceeași sursă

Aplicând algoritmul Huffman se obține L_Huffman = 2.38 biți/simbol (în acest caz coincide!). Diferența apare la surse cu distribuții mai dezechilibrate.

Observație: Shannon-Fano este suboptimal în cazul general, dar pentru multe distribuții practice produce rezultate identice sau foarte apropiate de Huffman.