====== Huffmanovo kódování ======

**Huffmanovo kódování** je algoritmus, který využívá metodu kódování s proměnnou délkou slova. Hlavní myšlenka je prostá: znaky (nebo symboly), které se v datech vyskytují nejčastěji, jsou kódovány kratší sekvencí bitů, zatímco méně časté znaky mají kódy delší.

Tímto způsobem se celková velikost dat zmenší, aniž by došlo k jakékoli ztrátě informací při zpětném dekódování.

----

====== Jak algoritmus funguje (Tvorba stromu) ======

Proces vytvoření Huffmanova kódu probíhá v několika krocích:

  1. **Analýza četnosti:** Spočítáme, kolikrát se každý znak v textu vyskytuje.
  2. **Vytvoření prioritní fronty:** Každý znak se stane samostatným uzlem (listem) stromu s váhou odpovídající jeho četnosti.
  3. **Stavba binárního stromu:**
    * Vybereme dva uzly s nejmenší četností.
    * Spojíme je do nového uzlu, jehož váha je součtem obou.
    * Tento proces opakujeme, dokud nezůstane pouze jeden kořenový uzel.
  4. **Přiřazení kódů:** Cestě doleva k potomkovi přiřadíme hodnotu **0** a cestě doprava hodnotu **1**.



----

====== Příklad v praxi ======

Mějme slovo: ''BANANA''
  * Četnosti: A (3x), N (2x), B (1x).
  * Znak 'A' je nejčastější, dostane tedy nejkratší kód (např. ''0'').
  * Znak 'B' je nejméně častý, dostane nejdelší kód (např. ''110'').

Bez komprese (v ASCII) by každý znak zabral 8 bitů (celkem 48 bitů). Po Huffmanově kódování může celé slovo zabrat například jen 10-12 bitů.



----

====== Prefixová vlastnost ======

Klíčovou vlastností Huffmanova kódování je, že **žádný kód není prefixem (začátkem) jiného kódu**.
Díky tomu při čtení bitového proudu (např. ''01101...'') dekodér přesně ví, kde jeden znak končí a druhý začíná, aniž by potřeboval oddělovače. Jakmile narazí na sekvenci, která odpovídá nějakému znaku v Huffmanově stromu, okamžitě jej zapíše a začne číst další znak od nuly.

----

====== Výhody a omezení ======

^ Vlastnost ^ Popis ^
| **Bezztrátovost** | Po dekompresi získáme identická data, bit po bitu. |
| **Optimalita** | Je to nejefektivnější metoda kódování jednotlivých symbolů. |
| **Statická vs. Dynamická** | Vyžaduje buď uložení tabulky kódů spolu se souborem (statická), nebo složitější výpočet za běhu (adaptivní). |
| **Závislost na četnosti** | Pokud mají všechny znaky stejnou četnost, komprese nebude fungovat (soubor se nezmenší). |

----

====== Kde se Huffmanovo kódování používá? ======

Huffmanův algoritmus se málokdy používá samostatně, většinou je součástí složitějších kompresních řetězců:
  * **Deflate:** Algoritmus v ZIPu a PNG, který kombinuje Huffmanovo kódování s metodou LZ77.
  * **Multimedia:** Poslední fáze komprese u formátů JPEG a MP3.
  * **Síťová komunikace:** Součást protokolu HTTP/2 pro kompresi hlaviček.

----
//Související pojmy: Binární strom, Algoritmus, Komprese dat, ZIP, JPEG, Bitová hloubka, Entropie.//