2. feladat: Huffman kódolás

Eredeti feladat

A következő megadott betűk és az előfordulásaik száma alapján a Huffman kód felhasználásával töltse ki a szürke részeket! Gyakoriságok: A:4, B:5, C:3, D:2, E:5.

Huffman-fa

graph TD Root((19)) ---|0| Node9((9)) Root ---|1| Node10((10)) Node9 ---|0| A[A: 4] Node9 ---|1| B[B: 5] Node10 ---|0| E[E: 5] Node10 ---|1| Node5((5)) Node5 ---|0| D[D: 2] Node5 ---|1| C[C: 3]

Megoldás menete (Logika)

  1. Sorba rendezés: Rakd növekvő sorrendbe a gyakoriságokat: D(2), C(3), A(4), B(5), E(5).
  2. Fa építése: Vedd a két legkisebbet (D és C), vond össze őket egy ággá (2+3=5). Most a listád: 5(DC), 4(A), 5(B), 5(E).
  3. Ismétlés: Mindig a két legkisebbet vond össze, amíg csak egyetlen gyökér marad.
  4. Kódolás: A kész fán az élekre írj 0-t (balra) és 1-et (jobbra). Egy betű kódja az út a gyökértől a betűig.
  5. Bitek száma:
    • Huffman-nal: Σ (gyakoriság * kódhossz).
    • Nélküle (fix hossz): gyakoriságok összege * ⌈log2(betűk száma)⌉. Itt 5 betűhöz 3 bit kell (2^3=8 > 5).

Felkészülés más számokra

Ha a betűk száma vagy a gyakoriságuk változik: