Domů » Informatika » Kódování » Huffmanovo kódování

Huffmanovo kódování

Huffmanův algoritmus je jednoduchý algoritmus pro kompresi dat. Lze jej zařadit mezi grafové algoritmy, protože pracuje s grafy. Vstupem algoritmu je množina znaků spolu s četnostmi jejich výskytu ve správě. Výstupem je Huffmanův strom, pomocí kterého lze jednotlivé znaky zakódovat do binárního kódu i dekódovat zpět. Během přenosu zprávy se musí kromě zakódovaného binárního řetězce přenést i použitý Huffmanův strom (není-li dohodnutý předem).

Komprese spočívá v tom, že se častěji používané znaky zakódují menším počtem bitů než znaky méně časté. Výsledný kód se nazývá prefixový, protože žádné kódové slovo není prefixem nějakého dalšího. To zaručuje jednoznačnost kódování i dekódování.

Kroky algoritmu

  • Vytvoř graf, který se skládá z n kořenových stromů. Každý strom Ti se skládá z jednoho kořenového uzlu reprezentujícího jeden symbol Si. Váha stromu w(Ti) je rovna četnosti použití daného symbolu Si ve zprávě.
  • Dokud není graf souvislý, opakuj:
    • Najdi dva různé stromy T1 a T2 s minimální váhou.
    • Vytvoř nový kořenový strom T3 s novým kořenem, jehož levý potomek je T1 a pravý potomek T2. Váha tohoto nového stromu je rovna součtu vah stromů T1 a T2, tedy w(T3) = w(T1) + w(T2).
    • Odeber oba dva stromy T1, T2 z grafu.
  • Výsledný binární kořenový strom se nazývá Huffmanův strom. Každou jeho levou hranu označ nulou a pravou hranu jedničkou. Kód pro každý znak je dán cestou z kořene do odpovídajícího listu tak, že se postupně zapisují binární čísla u navštívených hran.

Stejné znaky se stejnými četnostmi mohou díky rozdílné implementaci vytvořit i několik rozdílných Huffmanových stromů – délka kódových slov pro stejné symboly je však shodná.

Příklad

Chceme zakódovat a zkomprimovat zprávu „AHOJ, JAK SE MAS, KAMARADE?“. Tato zpráva je dlouhá 27 znaků a obsahuje 13 různých symbolů.

Triviální kód

Následující tabulka udává jednotlivé znaky, jejich četnost a triviální kódování:

Znak Četnost Triviální kód
mezera 4 0000
, 2 0001
? 1 0010
A 6 0011
D 1 0100
E 2 0101
H 1 0110
J 2 0111
K 2 1000
M 2 1001
O 1 1010
R 1 1011
S 2 1100

Zpráva by se pomocí triviálního kódování zakódovala do následujícího řetězce:

0011 0110 1010 0111 0001 0000 0111 0011
1000 0000 1100 0101 0000 1001 0011 1100
0001 0000 1000 0011 1001 0011 1011 0011
0100 0101 0010          

Výpočtem zjistíme, že výsledná zpráva má velikost 108 bitů.

Huffmannův kód

Prvním krokem kódování je sestavení Huffmanova stromu. V prvním kroku máme stromy představující symboly a váhy jsou rovny jejich četnosti.

první krok Huffmanova algoritmu

Následující kroky mohou vypadat například takto:

  • ?(1) + D(1) s výslednou vahou 2
  • H(1) + O(1) s výslednou vahou 2
  • R(1) + ,(2) s výslednou vahou 3
  • ?D(2) + E(2) s výslednou vahou 4
  • HO(2) + J(2) s výslednou vahou 4
  • K(2) + M(2) s výslednou vahou 4
  • R,(3) + S(2) s výslednou vahou 5
  • _(4) + ?DE(4) s výslednou vahou 8
  • HOJ(4) + KM(4) s výslednou vahou 8
  • A(6) + R,S(5) s výslednou vahou 11
  • _?DE(8) + HOJKM(8) s výslednou vahou 16
  • _?DEHOJKM(16) + AR,S(11) s výslednou vahou 27
  • strom je dokončen

Výsledný Huffmanův strom:

výsledný Huffmanův strom

Výsledná kódovací tabulka:

Znak Četnost Triviální kód Huffmanův kód
mezera 4 0000 000
, 2 0001 1100
? 1 0010 00100
A 6 0011 10
D 1 0100 00101
E 2 0101 0011
H 1 0110 01010
J 2 0111 0100
K 2 1000 0110
M 2 1001 0111
O 1 1010 01011
R 1 1011 1101
S 2 1100 111

Pomocí Huffmanova kódu se zpráva zakóduje takto:

10 01010 01011 0100 000 1100 0100 10
0110 1100 111 0011 1100 0111 10 111
000 1100 0110 10 0111 10 1101 10
00101 0011 00100          

Výpočtem zjistíme, že výsledná zpráva má velikost 96 bitů. Spolu se zprávou je však nutné přenést i odpovídající Huffmanův strom (není-li dohodnutý předem) a tak se výhoda Huffmanova kódování projeví až u zpráv určité délky.

Reference

  • Dr. Jeanne Stynes, Computer Science