Cíle

Huffmanovo kódování

Algoritmus byl navržen Davidem Huffmanem (1925 - 1999) v roce 1952.

Podle úvodního třídění se jedná o statistickou a bezeztrátovou metodu.

Princip

Naším cílem bude nalézt "efektivní" zakódování určité množiny znaků, kde pro každý znak je předem dána jeho četnost v nějakém textu. Efektivností zakódování rozumíme to, že kódy jsou co nejkratší a znak s větší četností nemá nikdy delší kód než symbol s menší četností.

Budeme navíc požadovat, aby kódování bylo prefixové, tj. aby celý kód jednoho symbolu nebyl počátečním úsekem - prefixem - jiného symbolu. Jinak by nebylo možné text jednoznačně dekódovat.

Vstupem Huffmanova algoritmu je množina znaků spolu s přiřazením četností, výstupem je binární strom, pomocí kterého odvodíme hledané kódování.

Algoritmus komprese

1. Vytvoření binárního stromu pro Huffmannův kód
2. Uložení stromu
3. Nahrazení znaků jednotlivými kódy

Algoritmus vytvoření stromu

1. zjistíme četnosti znaků v zadaném textu
2. každý znak bude nyní triviálním stromem o jediném vrcholu s četností rovnou četnosti znaku
3. posloupnost stromů seřadíme vzestupně zleva doprava podle četnosti
4. stromy, které mají stejnou četnost, seřadíme tak, aby vyšší strom byl vlevo od nižšího (tj. triviální strom o jediném vrcholu musí být vpravo od stromu se stejnou četností a s více listy)
5. pokud mají některé stromy stejnou četnost i stejnou výšku, použijeme kritérium pořadí v abecedě
6. spojíme dva stromy nejvíce vlevo, vzniklému stromu přiřadíme četnost jako součet četností stromů, ze kterých byl tento strom vytvořen
7. opakujeme body 3 - 6
8. algoritmus končí, když nám v posloupnosti zůstane jediný strom - hledaný strom pro Huffmanův kód

Odvození Huffmanova kódu

Kódem znaku je posloupnost nul a jedniček vytvořená takto:

• najdu ve stromu cestu z kořene k hledanému znaku
• je-li vrchol číslo n+1 v této cestě levým synem n-tého vrcholu, potom na n-tém místě v kódu znaku bude nula, jinak jednička (neboli krok vlevo - nula, krok vpravo - jednička)

Pseudokód

• jednotlivé znaky označíme za vrcholy grafu (listy stromu) a dáme je do seznamu S

while (S.length>1) {

     v S nalezneme dva vrcholy m, n s nejmenšími četností výskytu

     p = new Vrchol;

     p.left = m;

     p.right = n;

     p.count = m.count + n.count; // count je četnost výskytu

     S.remove(m, n);

     S.add(p);

}

• nyní S obsahuje pouze kořen stromu
• najdeme kódy jednotlivých znaků (při průchodu z kořene do listu kódujeme 0 při kroku vlevo a 1 vpravo)

Algoritmus dekomprese

1. Načtení stromu
2. Nahrazení kódů původními znaky

Pseudokód

v = vrchol stromu;

while (!eof(input)) do {

     b = read bit;

     if (b==0) v = v.left;

     else v = v.right;

     if (v je list) {

          write v.value; // znak reprezentovaný tímto listem

          v = vrchol stromu;

     }

}

Příklad

Mějme text ABRAKADABRA.

četnosti jednotlivých znaků:

A - 5

B - 2

R - 2

K - 1

D - 1

Vytváření Huffmanova stromu viz obrázek .

Kódy jednotlivých znaků tedy budou:

A - 0

B - 111

R - 10

K - 1101

D - 1100

A zakódované slovo bude: 01111001101011000111100

Poznámka

Efektivnost Huffmanova kódování závisí na rozložení četností jednotlivých znaků v zadaném textu - při rovnoměrném rozložení četností algoritmus nebude mít žádný význam.