Zde je praktická ukázka zakódování textového řetězce pomocí binárního stromu.

Zadání:
Najděte minimální kód pomocí Huffmanova algoritmu pro textový řetězec "VESELE SELE V LESE.". Spočítejte průměrnou délku kódového slova, kompresní poměr a faktor komprese.

Řešení:

U jednotlivých znaků spočítáme jejich četnost, umístíme je jako samostatné vrcholy a budeme z nich postupně generovat binární strom.

Krok 1 - spočítáme četnosti jednotlivých znaků a pravděpodobnost jejich výskytu v zdrojovém textu:

 

Znak	Četnost	Pravděpodobnost
E	7	0,368
S	3	0,158
L	3	0,158
" " (mezera)	3	0,158
V	2	0,105
.	1	0,053
∑	19	1

 

Krok 2 - Množinu, kterou tvoří vrcholy, označíme X.

 

 

Vezmeme z množiny X dva prvky s nejmenší četností (zvýrazněny modře) a spojíme je tak, že z nich uděláme bratry, přičemž jejich otec bude mít ohodnocení rovnající se součtu četností jeho synů. Právě použité prvky z množiny X vyjmeme a namísto nich do X přidáme jejich otce. (Pozn.: Při vytváření binárního stromu můžeme použít jak četnost, tak pravděpodobnost výskytu znaků, výsledek je stejný.)

 

 

Tento postup rekruzivně opakujeme tak dlouho, až je množina X jednoprvková. Spojované prvky jsou vždy zvýrazněny modře.

 

 

 

 

 

 

Tento jediný prvek v množině X je kořenem binárního stromu, zatímco obdélníky s původními znaky zdrojového textu jsou listy tohoto stromu. Jednotlivým hranám každého uzlu přiřadíme kódová slova 0 a 1.

 

 

Krok 3 - přiřazení kódových slov jednotlivým zdrojovým znakům:

Postupujeme tak, že pro každý znak zdrojového kódu hledáme cestu od kořene k příslušnému listu a zaznamenáváme postupně kódová slova jednotlivých hran:

 

E	0
S	100
L	101
" "	110
V	1110
.	1111

 

 

Textový řetězec "VESELE SELE V LESE." má tento minimální kód pomocí Huffmanova algoritmu:

1110010001010110100010101101110110101010001111

Průměrná délka kódového slova je:

d* = 1x0,368 + 3x0,158 + 3x0,158 + 3x0,158 + 4x0,105 + 4x0,053 = 2,422

Kompresní poměr je podíl rozměru vstupního proudu a rozměru výstupního proudu.
Rozměr vstupního proudu: Předpokládejme, že zdrojové znaky pocházejí z osmibitového (rozšířeného) ASCII kódu, tj. každý znak zabírá 8 bitů. Zdrojový text má 19 znaků, rozměr vstupního proudu je 19 * 8 = 152 bitů.
Rozměr výstupního proudu: Spočítáme počet jedniček a nul ve výsledném kódu. Rozměr výstupního proudu je 46 bitů.

Kompresní poměr je 152 / 46 = 3,3

Faktor komprese je podíl rozměru výstupního proudu a rozměru vstupního proudu.

Faktor komprese je 46 / 152 = 0,302

Data po kompresi tedy zabírají 30,2% původního prostoru.