====== 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 [[https://en.wikipedia.org/wiki/Huffman_coding|anglické wiki]], existuje [[http://huffman.ooz.ie/?text=TENTO%20TEXT%20JE%20JEN%20TEST|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 ====
{{ :informatika:maturita:huffmanstrom.png?nolink&300 |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** |
[[http://huffman.ooz.ie/?text=TENTO TEXT JE JEN TEST|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 |