Huffmanov kód

Kód D (tabuľka 2.4) má najmenšie spomedzi všetkých uvedených. Na druhej strane, malá zmena v kóde C (tabuľka 2.3) spôsobí, že jeho entropia klesne ešte pod túto hranicu. Keď vymeníme kódové slová pre symboly a , entropia pre kód C klesne o , teda . Tento nový kód je tiež jednoznačne dekódovateľný.

Týmto postupom môžeme entropiu postupne znižovať a tým daný kód stále zlepšovať. D.A. Huffman zostrojil algoritmus (Huffman, 1952) na tvorbu optimálneho kódu s minimálnym . Algoritmus a kód, ktorý sa vytvára, boli nazvané podľa ich autora.

Vytváranie optimálneho kódu

Majme teda zdrojovú abecedu:

• . Táto rovnica a 3.2 hovoria, že keď sú zdrojové symboly usporiadané zostupne podľa ich početnosti, potom dĺžky ich kódových slov by mali byť v neklesajúcom poradí. Inak povedané, dĺžky kódových slov častejšie sa vyskytujúcich zdrojových symbolov nesmú byť dlhšie ako menej vyskytujúcich sa symbolov. Kódové slová priradené posledným dvom zdrojovým symbolom (s najmenšou početnosťou) majú rovnakú dĺžku.
• Zdrojové symboly s najmenšou početnosťou majú im prislúchajúce kódové slová líšiace sa len v poslednom bite.
• Každá možná sekvencia dĺžky musí byť buď kódové slovo, alebo jeden z jej prefixov musí byť kódové slovo.

To, ako zabezpečiť tieto podmienky, je napísane v samotnej učebnici. Samotným algoritmom sa budeme zaoberať v nasledujúcej časti.

Algoritmus

Na základe týchto troch pravidiel vieme, že najmenej vyskytujúce sa zdrojové znaky majú rovnakú dĺžku kódových slov, ktoré im boli priradené. Tieto kódové slová sa líšia iba v poslednom bite (teda v 0 a 1). Preto tieto dva zdrojové symboly môžu byť spojené do nového symbolu, ktorého početnosť bude . Novovzniknutá abeceda má o jeden symbol menej ako pôvodná abeceda. Túto abecedu preusporiadame, aby sme znova splnili podmienku nerastúcich početností. Podobný postup môžeme aplikovať na túto abecedu a posledným dvom symbolom priradiť hodnoty $0$ a $1$ ktoré, spojíme do nového symbolu. Algoritmus sa zastaví v momente, keď spojíme posledné dva symboly a vznikne nám abeceda s jedným symbolom. Tomuto symbolu (pokiaľ sa nikde nevyskytla chyba) sme priradili početnosť .

Na ukážku si zoberme kód, ktorý je uvedený v tabuľke 3.1. Obrázky 3.1 až 3.6 ilustrujú postupné vytváranie Huffmanovho stromu. Sú na nich zobrazené len modifikované zdrojové abecedy, kde už sú jednotlivé symboly usporiadané podľa ich početnosti. Celý postup sa dá zhrnúť do nasledujúcich krokov.

• zostupne zoraď symboly zdrojovej abecedy podľa ich početnosti
• spoj posledné dva symboly
  • vytvor z nich nový symbol, ktorého početnosť bude ich súčtom.
  • priraď im binárne 0 a 1.
• tento postup opakuj, pokiaľ nevznikne abeceda s jedným symbolom
• traverzovaním vzniknutého stromu priraď jednotlivým symbolom ich kódové slová.

Tabuľka 3.1:Príklad na Huffmanov kód

Zdroj. symbol	Početnosť	Kódové slovo	Dĺžka
			2
			3
			2
			4
			4
			2

Obrázok 3.1: Krok Huffmanovho algoritmu 1

Obrázok 3.2: Krok Huffmanovho algoritmu 2

Obrázok 3.3: Krok Huffmanovho algoritmu 3

Obrázok 3.4: Krok Huffmanovho algoritmu 4

Obrázok 3.5: Krok Huffmanovho algoritmu 5

Obrázok 3.6: Krok Huffmanovho algoritmu 6

Modifikácie

Pokiaľ máme zdroj, ktorý má iba binárnu abecedu (prvá časť tabuľky 3.2), vytvorením Huffmanovho kódu nič neušetríme. Na druhej strane nám entropia hovorí o možnosti kompresie, pretože jej hodnota je . Tu sa ponúka možnosť kódovať dibity. Huffmanov kód pre dibity je v druhej časti tabuľky 3.2 a výsledná bitová náročnosť je potom bitu na znak.

Tabuľka 3.2: Modifikácia Huffmanovho kódu

Zdroj. symbol
Početnosť
Huffman. kód	0

Ďalšími významnými modifikáciami sú Huffmanové kódy pre vopred neznáme postupnosti, kedy sa Huffmanova tabuľka mení adaptívne podľa kódovaných dát. Tieto kódy sú najdôležitejšie pri prenose dát v reálnom čase bez degradácie.

Záverečný komentár

Vytváranie Huffmanovho kódu nie je jednoznačné. Nejednoznačnosť nastáva v prípadoch, keď dva symboly počas výpočtu majú rovnakú početnosť. Tu môže ľahko nastať zámena týchto dvoch symbolov pri vytváraní Huffmanovho stromu. Tento problém sa rieši vzájomnou dohodou (na triedenie sa použije stabilný algoritmus).