GMLWiki

Tato stránka je pouze pro čtení. Můžete si pouze prohlédnout zdrojový kód, ale ne ho měnit. Zeptejte se správce, pokud si myslíte, že něco není v pořádku.
====== 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ů:<WRAP>
^ Znak     |  T  |  E  |  SPC  |  N  |  J  |  O  |  X  |  S  |
^ Četnost  |  6  |  5  |   4   |  2  |  2  |  1  |  1  |  1  |
</WRAP>
  - **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:<WRAP>
^ Znak     |  T  |  E  |  SPC  |  N  |  J  |  (X,S)  |  O  |
^ Četnost  |  6  |  5  |   4   |  2  |  2  |    2    |  1  |
</WRAP>
  - Další dvojice v pořad je O a dvojznak (X,S):<WRAP>
^ Znak     |  T  |  E  |  SPC  |   ( (X,S),O)  |  N  |  J  |
^ Četnost  |  6  |  5  |   4   |        3      |  2  |  2  |
</WRAP>
  - Nyní mají nejnižší četnost znaky N a J, vzniká z nich dvojznak:<WRAP>
^ Znak     |  T  |  E  |  SPC  |  (N,J)  |  ( (X,S),O)  |
^ Četnost  |  6  |  5  |   4   |    4    |       3      |
</WRAP>
  - V dalším kroku budeme slučovat trojznak XSO a dvojznak NJ, který bude mít hodnotu 7:<WRAP>
^ Znak     |  ( (N,J),( (X,S),O) )  |  T  |  E  |  SPC  |
^ Četnost  |           7            |  6  |  5  |   4   |
</WRAP>
  - Dále slučujeme mezeru a E:<WRAP>
^ Znak     |  (E,SPC)  |  ( (N,J),( (X,S),O) )  |  T  |
^ Četnost  |     9     |           7            |  6  |
</WRAP>
  - V předposledním kroku bude složený znak NJXSO spojen s T:<WRAP>
^ Znak     |  ( ( (N,J),( (X,S),O) ),T)  |  (E,SPC)  |
^ Četnost  |             13              |     9     |
</WRAP>
  - 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:<WRAP>
^ Znak     |  ( ( ( (N,J),( (X,S),O) ),T),(E,SPC))  |
^ Četnost  |                  22                    |
</WRAP>

==== 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  |
GMLWiki

Uživatelské nástroje

Nástroje pro tento web

Nástroje pro stránku
