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
abbamá znakafrekvenciu 2 a znakbtiež 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á
0a 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:
- Spočítajte, koľkokrát sa v reťazci vyskytuje každý znak.
- Vložte uzly znakov do prioritnej fronty podľa ich frekvencií.
- 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.
- 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.