Zde si ukážeme jak nalézt kód minimální délky pomocí binárního stromu.

Zadání:
Zakódujme 4 znaky Huffmanovým kódem, známe-li pravděpodobnosti jejich výskytu, a spočítejme průměrnou délku kódového slova.

Znak	Pravděpodobnost
A	0,4
B	0,3
C	0,2
D	0,1

Řešení:

Jednotlivé znaky umístíme jako samostatné vrcholy a budeme z nich postupně generovat binární strom.

 

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

 

 

Vezmeme z množiny X dva prvky s nejmenší pravděpodobností (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 pravděpodobností jeho synů. Právě použité prvky z množiny X vyjmeme a namísto nich do X přidáme jejich otce.

 

 

Tento postup 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ímy 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 2 - 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:

 

A	0
B	10
C	110
D	111

 

Huffmanova konstrukce minimálního kódu je vždy optimální, ale není jednoznačná. Při přiřazování kódových slov 0 a 1 jednotlivým hranám uzlů není definováno, zda má být 1 vlevo nebo vpravo, můžeme si u každého uzlu vybrat. Kódová slova pro jednotlivé znaky zdrojového kódu se pak mohou lišit, ale vždy budou mít sestrojené Huffmanovy kódy zdrojového textu stejné hodnoty pro průměrnou délku kódového slova, kompresní poměr a faktor komprese.

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

d* = 1x0,4 + 2x0,3 + 3x0,2 + 3x0,1 = 1,9