Huffmanov strom

9th Nov 2026

Slovenským vedcom z Technickej univerzity v Košiciach sa podaril prielom vo vesmírnom výskume. Z miniatúrnej odpaľovacej rampy, ktorá sa nachádza niekde medzi superpočítačom Perún a jedálňou Združené poschodia, sa chystajú vypustiť raketu Tukáčik. Na obežnú dráhu Zeme má vyniesť prvú družicu TUKE s názvom TU UDRU ZEM – TUKE Umelá družica Zeme.

Vašou úlohou je navrhnúť komunikačný protokol, ktorý bude vyhovovať obmedzeným možnostiam antény a vysielacieho výkonu družice. Protokol má prenášať písmená slovenskej abecedy čo najúspornejšie. Môže používať iba dva symboly – krátky a dlhý, podobne ako Morseova abeceda.

Cieľ

Precvičiť si tvorbu Huffmanovho stromu a:

  • prácu s prioritnou frontou,
  • reprezentáciu binárneho prefixového stromu,
  • počítanie frekvencií znakov,
  • rekurzívne prechádzanie stromu,
  • kódovanie a dekódovanie reťazca.

Základné pojmy

  • Frekvencia je počet výskytov znaku vo vstupných dátach. Napríklad v reťazci abba má znak a frekvenciu 2 a znak b tiež frekvenciu 2.
  • List je uzol bez potomkov. V tomto cvičení uchováva jeden znak.
  • Vnútorný uzol spája dve vetvy a uchováva súčet ich frekvencií. Znak uchovávať nemusí.
  • Kód znaku je postupnosť odbočení od koreňa po príslušný list: ľavá vetva znamená 0 a pravá 1.
  • Koreň je najvyšší uzol stromu. Jeho frekvencia sa rovná súčtu frekvencií všetkých listov.

Huffmanov kód je prefixový: kód jedného znaku nie je začiatkom kódu iného znaku. Bitový reťazec preto možno čítať postupne, bez oddeľovačov. Častejšie znaky zvyčajne dostanú kratšie kódy.

Príklad stromu:

(("a", "b"), "c")

Tento strom môže znamenať kódy:

{
    "a": "00",
    "b": "01",
    "c": "1",
}

Vetve doľava priraďte bit "0" a vetve doprava bit "1".

Návrh binárneho stromu

Najprv určite, ako bude vyzerať uzol binárneho stromu: aké údaje bude uchovávať a ako sa budú ukladať odkazy na jeho potomkov.

Potom vytvorte triedu Huffmanovho stromu. V jej konštruktore zostavte strom zo zadaného reťazca:

  1. Spočítajte, koľkokrát sa v reťazci vyskytuje každý znak.
  2. Vložte uzly znakov do prioritnej fronty podľa ich frekvencií.
  3. Opakovane vyberte dva uzly s najnižšími frekvenciami a spojte ich do nového vnútorného uzla. Jeho frekvencia je súčtom frekvencií potomkov.
  4. Pokračujte, kým vo fronte nezostane jediný uzol – koreň stromu.

Pri rovnakej frekvencii patrí prvý vybraný uzol doľava. Na efektívne vyberanie uzlov a udržiavanie prioritnej fronty použite modul heapq.

Príklad: Pre reťazec abbc sú frekvencie a: 1, b: 2 a c: 1. Najprv sa spoja uzly a a c (pri zhode rozhoduje poradie výberu), potom sa ich spoločný uzol s frekvenciou 2 spojí s uzlom b.

Zostavenie kódovacej tabuľky

Kódovacia tabuľka je slovník, ktorý každému znaku priraďuje jeho kódové slovo – postupnosť núl a jednotiek.

Prejdite strom od koreňa k listom a počas prechodu si zaznamenávajte bity jednotlivých vetiev. Ošetrite aj osobitné prípady: prázdny strom a strom s jediným uzlom.

Ak použijete rekurziu, odovzdajte čiastkový kód rekurzívnej funkcii, aby sa bity z cesty ku koreňu nestratili.

Keď je kódovacia tabuľka hotová, zakódujte reťazec tak, že kód každého znaku spojíte v pôvodnom poradí.

Príklad: Ak tabuľka obsahuje a → 0, b → 10 a c → 11, reťazec abca sa zakóduje ako 010110.

Dekódovanie

Pri dekódovaní využite prefixovú vlastnosť Huffmanovho stromu. Začnite na jeho koreni a čítajte vstupné bity postupne: pri 0 pokračujte doľava, pri 1 doprava. Keď dôjdete do listu, zapíšte znak a vráťte sa ku koreňu, aby ste mohli dekódovať ďalší znak.

Príklad: Pri tabuľke z predchádzajúcej časti sa reťazec 010110 dekóduje ako abca: 0 → a, 10 → b, 11 → c, 0 → a.

Previous Post Next Post

Huffmanov strom