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