Uživatelské nástroje
informatika:maturita:huffmann
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] rydlo vytvořeno |
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 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> | - **Zjistíme četnost** jednotlivých znaků:<WRAP> | ||
| ^ Znak | T | E | SPC | N | J | O | X | S | | ^ 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. | - 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> | - Nejnižší četnost mají znaky X,S, proto vznikne dvojznak (X,S) s četností 2:<WRAP> | ||
| ^ Znak | T | E | SPC | N | J | (X,S) | O | | ^ Znak | T | E | SPC | N | J | (X,S) | O | | ||
| Řádek 23: | Řádek 23: | ||
| </WRAP> | </WRAP> | ||
| - Další dvojice v pořad je O a dvojznak (X,S):<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> | </WRAP> | ||
| - Nyní mají nejnižší četnost znaky N a J, vzniká z nich dvojznak:<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> | </WRAP> | ||
| - V dalším kroku budeme slučovat trojznak XSO a dvojznak NJ, který bude mít hodnotu 7:<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> | </WRAP> | ||
| - Dále slučujeme mezeru a E:<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> | </WRAP> | ||
| - V předposledním kroku bude složený znak NJXSO spojen s T:<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> | </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> | - 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> | </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 | | ||
informatika/maturita/huffmann.1601153862.txt.gz · Poslední úprava: 26. 09. 2020, 22.57 autor: rydlo
Nástroje pro stránku
