Huffmanovo kódování

je příkladem bezeztrátového kompresního algoritmu. Nejčetnějším znakům přiřazuje kratší kódovací sekvenci, čímž šetří místo. Je detailně popsané např. na anglické wiki, existuje online applet, který provede rozbor na strom libovolné zadané věty.

Příklad komprese textu

Mějme větu: TENTO TEXT JE JEN TEST

V klasickém kódování ASCII zabere 22 B neboli 176 b.

V Huffmanově kódování pouze 60 b tedy necelých 8 B.

Postup

Zjistíme četnost jednotlivých znaků:

Znak	T	E	SPC	N	J	O	X	S
Četnost	6	5	4	2	2	1	1	1

Vytvoříme strom četností: Vezmeme dva znaky s nejnižší četností, vytvoříme z nich nový „složený znak (dvojznak)“, jehož četnost odpovídá součtu četností znaků ve dvojici. To opakujeme tak dlouho, dokud nezbude jen jediný „složený znak“ ze všech znaků obsažených ve zprávě.

Zpětně procházíme vzniklý strom a na každé úrovni přidělujeme vždy symboly 1 a 0 tak, že větev/znak s vyšší četností dostane 1 a větev/znak s nižší četností 0.

Na příkladu

Nejnižší četnost mají znaky X,S, proto vznikne dvojznak (X,S) s četností 2:

Znak	T	E	SPC	N	J	(X,S)	O
Četnost	6	5	4	2	2	2	1

Další dvojice v pořad je O a dvojznak (X,S):

Znak	T	E	SPC	( (X,S),O)	N	J
Četnost	6	5	4	3	2	2

Nyní mají nejnižší četnost znaky N a J, vzniká z nich dvojznak:

Znak	T	E	SPC	(N,J)	( (X,S),O)
Četnost	6	5	4	4	3

V dalším kroku budeme slučovat trojznak XSO a dvojznak NJ, který bude mít hodnotu 7:

Znak	( (N,J),( (X,S),O) )	T	E	SPC
Četnost	7	6	5	4

Dále slučujeme mezeru a E:

Znak	(E,SPC)	( (N,J),( (X,S),O) )	T
Četnost	9	7	6

V předposledním kroku bude složený znak NJXSO spojen s T:

Znak	( ( (N,J),( (X,S),O) ),T)	(E,SPC)
Četnost	13	9

Při posledním složení už vznikne jediný složený znak, tedy kompletní strom: - V předposledním kroku bude složený znak NJXSO spojen s T:

Znak	( ( ( (N,J),( (X,S),O) ),T),(E,SPC))
Četnost	22

Výše uvedený řetězec lze zapsat také formou stromu

Strom Huffmanova kódování pro větu "TENTO TEXT JE JEN TEST"

Při zpětném sestavení přidělujeme 1 a 0

krok:	1	2	3	4	5	Celkem
T	1	0	10
E	0	1	01
SPC	0	0	00
N	1	1	1	1	1111
J	1	1	1	0	1110
O	1	1	0	0	1100
X	1	1	0	1	0	11010
S	1	1	0	1	1	11011

online zpracování stromu

Zakódovaný text

100111111011000010011101010001110010011100111110010011101110

Dekódování probíhá sekvenčně náhradou za znak z tabulky, vždy jakmile to nalezená sekvence umožňuje:

10	01	1111	10	1100	00	10	01	11010	10	00	1110	01	00	1110	01	1111	00	10	01	11011	10
T	E	N	T	O	T	E	X	T	J	E	J	E	N	T	E	S	T