Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- informatika:maturita:huffmann [26. 09. 2020, 22.57] – vytvořeno rydlo
+++ informatika:maturita:huffmann [26. 09. 2020, 23.18] (aktuální) – rydlo
@@ Řádek 7: / Řádek 7: @@
 V klasickém kódování ASCII zabere 22 B neboli 176 b.
-V Huffmanově kódování pouze 46 b tedy necelých 6 B.
+V Huffmanově kódování pouze 60 b tedy necelých 8 B.
-Postup:
+==== Postup ====
   - **Zjistíme četnost** jednotlivých znaků:<WRAP>
 ^ Znak     |  T  |  E  |  SPC  |  N  |  J  |  O  |  X  |  S  |
@@ Řádek 17: / Řádek 17: @@
   - 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:
+==== 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  |
@@ Řádek 23: / Řádek 23: @@
 </WRAP>
   - Další dvojice v pořad je O a dvojznak (X,S):<WRAP>
-^ Znak     |  T  |  E  |  SPC  |  ((X,S),O)  |  N  |  J  |
+^ Znak     |  T  |  E  |  SPC  |   ( (X,S),O)  |  N  |  J  |
-^ Četnost  |  6  |  5  |   4   |      3      |  2  |  2  |
+^ Č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)  |
+^ Znak     |  T  |  E  |  SPC  |  (N,J)  |  ( (X,S),O)  |
-^ Četnost  |  6  |  5  |   4   |    4    |      3      |
+^ Č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  |
+^ Znak     |  ( (N,J),( (X,S),O) )  |  T  |  E  |  SPC  |
-^ Četnost  |         7           |  6  |  5  |   4   |
+^ Četnost  |           7            |  6  |  5  |   4   |
 </WRAP>
   - Dále slučujeme mezeru a E:<WRAP>
-^ Znak     |  (E,SPC)  |  ((N,J),((X,S),O))  |  T  |
+^ Znak     |  (E,SPC)  |  ( (N,J),( (X,S),O) )  |  T  |
-^ Četnost  |     9     |         7           |  6  |
+^ Č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)  |
+^ Znak     |  ( ( (N,J),( (X,S),O) ),T)  |  (E,SPC)  |
-^ Četnost  |           13            |     9     |
+^ Č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))  |
+^ Znak     |  ( ( ( (N,J),( (X,S),O) ),T),(E,SPC))  |
-^ Četnost  |                22                 |
+^ Četnost  |                  22                    |
 </WRAP>
-Výše uvedený řetězec lze zapsat také formou stromu:
+==== Výše uvedený řetězec lze zapsat také formou stromu ====
-{{ :informatika:maturita:huffmanstrom.png?nolink&200 |Strom Huffmanova kódování pro větu "TENTO TEXT JE JEN TEST"}}
+{{ :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  |