Příklad
|
Přibližný čas, který strávíte studiem této kapitoly, je 20 - 30 minut.
Zadání:
Najděte minimální kód pomocí Huffmanova algoritmu pro textový řetězec "MATES MATE TETU.". Spočítejte průměrnou délku kódového slova, kompresní poměr a faktor komprese.
Řešení:
Krok 1 - spočítáme četnosti jednotlivých znaků a pravděpodobnost jejich výskytu v zdrojovém textu:
| Znak | Výskyt | Pravděpodobnost |
| T | 4 | 0,25 |
| E | 3 | 0,1875 |
| M | 2 | 0,125 |
| A | 2 |
0,125 |
| "" (mezera) | 2 |
0,125 |
| S |
1 |
0,0625 |
| U |
1 |
0,0625 |
| . |
1 |
0,0625 |
| ∑ | 16 | 1 |
Krok 2 - budeme postupně vytvářet tabulku.
-
V prvním sloupci jsou zdrojové znaky uspořádané podle pravděpodobnostního výskytu.
-
Sečteme poslední dvě pravděpodobnosti (provedeme redukci) a výsledek zařadíme podle velikosti mezi ostatní pravděpodobnosti - třetí sloupec - redukce je odlišena modrou barvou.
-
Znovu sečteme poslední dvě pravděpodobnosti a výsledek opět zařadíme podle velikosti - pátý sloupec.
-
Sčítání pravděpodobností provádíme tak dlouho, až zůstanou pouze dva řádky.
-
Spodním dvěma znakům v každém sloupci přiřadíme kódové znaky 1 a 0.
| T(0,25) |
|
T(0,25) | |
T(0,25) | |
T(0,25) | |
| E(0,1875) |
|
E(0,1875) | |
E(0,1875) | |
A""(0,25) | |
| M(0,125) | |
M(0,125) | |
U.S(0,1875) | |
E(0,1875) | |
| A(0,125) |
|
A(0,125) | |
M(0,125) | |
U.S(0,1875) | 1 |
| ""(0,125) |
|
""(0,125) | |
A(0,125) | 1 |
M(0,125) | 0 |
| S(0,0625) |
|
U.(0,125) | 1 |
""(0,125) | 0 |
|
|
| U(0,0625) |
1 |
S(0,0625) | 0 |
|
|
|
|
| .(0,0625) |
0 |
|
|
|
|
|
|
Pokračování tabulky
| U.SM(0,3125) | A""E(0,4375) | U.SMT(0,5625) | 1 |
||
| T(0,25) | U.SM(0,3125) | 1 |
A""E(0,4375) | 0 |
|
| A""(0,25) | 1 |
T(0,25) | 0 |
||
| E(0,1875) | 0 |
Krok 3 - přiřazení kódových slov jednotlivým zdrojovým znakům.
-
Uděláme si novou tabulku, v prvním sloupci jsou všechny zdrojové znaky.
-
Dále budeme vycházet z předchozí tabulky a budem postupovat od zadu. Znaky U.SMT mají 1 - ve druhém sloupci nově vytvářené tabulky budou mít hodnou 1 a znaky A""E mají 0 - ve druhém sloupci nově vytvářené tabulky budou mít hodnou 0. Tím máme vyplněný druhý sloupec nové tabulky.
-
V předchozí tabulce se posuneme dopředu. Znaky U.SM mají 1 - ve třetím sloupci nově vytvářené tabulky budou mít hodnou 1 a znak T má 0 ve třetím sloupci nově vytvářené tabulky bude mít hodnou 0. Tím máme vyplněný třetí sloupec nové tabulky.
-
Takto pokračujeme až na začátek předchozí tabulky.
-
V posledním sloupci nové tabulky jsou kódová slova pro jednotlivé zdrojové znaky.
| T | 1 |
0 |
|
|
|
|
|
10 |
| E |
0 |
0 |
|
|
|
|
00 |
|
| M |
1 |
1 | |
0 |
|
|
|
110 |
| A |
0 |
1 |
|
1 |
|
|
011 |
|
| "" |
0 |
1 |
|
0 |
|
|
010 |
|
| S |
1 |
1 |
|
1 |
|
0 |
|
1110 |
| U |
1 |
1 |
|
1 |
|
1 |
1 |
11111 |
| . |
1 |
1 |
|
1 |
|
1 |
0 |
11110 |
Textový řetězec "MATES MATE TETU." má tento minimální kód pomocí Huffmanova algoritmu:
1100111000111001011001110000101000101111111110
Průměrná délka kódového slova je:
d* = 2x0,25 + 2x0,1875 + 3x0,125 + 3x0,125 + 3x0,125 + 4x0,0625 + 5x0,0625 + 5x0,0625 = 2,875
Kompresní poměr je podíl rozměru vstupního proudu a rozměru výstupního proudu.
Rozměr vstupního proudu: Předpokládejme, že zdrojové znaky pocházejí z osmibitového (rozšířeného) ASCII kódu, tj. každý znak zabírá 8 bitů. Zdrojový text má 16 znaků, rozměr vstupního proudu je 16 * 8 = 128 bitů.
Rozměr výstupního proudu: Spočítáme počet jedniček a nul ve výsledném kódu. Rozměr výstupního proudu je 46 bitů.
Kompresní poměr je 128 / 46 = 2,78
Faktor komprese je podíl rozměru výstupního proudu a rozměru vstupního proudu.
Faktor komprese je 46 / 128 = 0,36
Data po kompresi tedy zabírají 36% původního prostoru.