Huffmanův algoritmus je jednoduchý grafový algoritmus pro kompresi dat. Vstupem algoritmu je množina znaků spolu s četnostmi jejich výskytu ve zprá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 však 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 jiného. To zaručuje jednoznačnost kódování i dekódování.

Pseudokód

  • Vytvoř graf, který se skládá z €n€ kořenových stromů. Každý strom €T_i€ se skládá z jednoho kořenového uzlu reprezentujícího jeden symbol €S_i€. Váha stromu €w(T_i)€ je rovna četnosti použití daného symbolu €S_i€ ve zprávě.
  • Dokud není graf souvislý, opakuj:
  • Najdi dva různé stromy €T_1€ a €T_2€ s minimální váhou.
  • Vytvoř nový kořenový strom €T_3€ s novým kořenem, jehož levý potomek je €T_1€ a pravý potomek €T_2€. Váha tohoto nového stromu je rovna součtu vah stromů €T_1€ a €T_2€, tedy €w(T_3)=w(T_1)+w(T_2)€.
  • Odeber oba dva stromy €T_1€, €T_2€ 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ČetnostTriviální kód
mezera40000
,20001
?10010
A60011
D10100
E20101
H10110
J20111
K21000
M21001
O11010
R11011
S21100

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.

diagram

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:

diagram

Výsledná kódovací tabulka:

ZnakČetnostTriviální kód (pro srovnání)Huffmanův kód
mezera40000000
,200011100
?1001000100
A6001110
D1010000101
E201010011
H1011001010
J201110100
K210000110
M210010111
O1101001011
R110111101
S21100111

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