Úloha 9: Huffmanovo kódovanie
Implementujte jednoduchý Huffmanov kompresor pre text. Riešenie má obsahovať:
- tabuľku početností znakov,
- zostavenie Huffmanovho stromu pomocou
heapq, - generovanie prefixových kódov,
- kódovanie a dekódovanie textu,
- výpočet kompresného pomeru.
Strom reprezentujte objektmi triedy HuffmanNode, nie n-ticami. List obsahuje
znak a nemá potomkov; vnútorný uzol nemá znak a má ľavého aj pravého potomka.
Prázdny strom reprezentuje None. Ľavá vetva má kód 0, pravá vetva 1.
Podrobný opis: Huffmanov strom.
Na prečítanie:
- Huffmanovo kódovanie – University of Michigan: tvorba stromu a vlastnosť prefixových kódov.
- Huffmanovo kódovanie – NIST Dictionary of Algorithms and Data Structures: stručná definícia a ďalšie odkazy.
- Modul
heapq– dokumentácia Pythonu: prioritná fronta na zostavenie stromu.
Odovzdanie:
- Súbor
u9/huffman_tree.pyodovzdajte do 16. 11. 2026 v systéme Traktor: U9: TU UDRU ZEM.
Príprava na písomku 2
Písomka bude obsahovať úlohy podobné niektorým z nasledujúcich príkladov.
1. Hašovacie tabuľky
V oboch úlohách je tabuľka neprázdny zoznam nezáporných celých čísel a hodnôt
None, ktoré označujú voľné miesta. Použite h(key) = key % len(table) a
lineárne skúšanie s návratom na začiatok. Nepoužívajte dict ani set.
- A – Vloženie kľúča: Napíšte funkciu
hash_insert(table, key), ktorá vloží kľúč na prvé voľné miesto v poradí skúšania a vráti jeho index. Ak kľúč už existuje, vráťte jeho index a tabuľku nemeňte. Ak je tabuľka plná a kľúč v nej nie je, vráťte-1. Príklad: pritable = [None, 6, 11, None, None]volaniehash_insert(table, 16)vráti3a uloží16na index3. - B – Vyhľadanie kľúča: Napíšte funkciu
hash_find(table, key), ktorá vráti index kľúča alebo-1, ak sa v tabuľke nenachádza. Hľadanie ukončite pri prvomNonealebo po skontrolovaní celej tabuľky. Predpokladajte, že kľúče boli vložené lineárnym skúšaním a z tabuľky sa nič nemazalo. Príklad:hash_find([None, 6, 11, 16, None], 11) == 2.
2. Binárny vyhľadávací strom
Strom reprezentujte objektmi triedy BSTNode, ktorá má atribúty value,
left a right. Prázdny podstrom je None. Hodnoty sú celé čísla bez
duplicít.
- A – Vyhľadávanie: Napíšte funkciu
bst_contains(tree, value), ktorá vrátiTrue, ak strom obsahuje danú hodnotu, inakFalse. Pri každom porovnaní pokračujte iba do príslušného podstromu. Pre prázdny strom vráťteFalse. Príklad: aktreeje koreň s hodnotou5, ľavým dieťaťom s hodnotou2a pravým dieťaťom s hodnotou8, potombst_contains(tree, 8) == True. - B – Vloženie: Napíšte funkciu
bst_insert(tree, value), ktorá vráti strom po vložení hodnoty podľa pravidiel binárneho vyhľadávacieho stromu. Existujúcu hodnotu nevkladajte opakovane. Príklad: vloženie3do koreňa s hodnotou5vráti strom, ktorého koreň má hodnotu5, ľavé dieťa hodnotu3a pravé dieťa jeNone.
3. Huffmanov strom
Strom reprezentujte objektmi triedy HuffmanNode. Uzol má
atribúty symbol, left a right. List obsahuje znak v symbol a má oboch
potomkov None. Vnútorný uzol má symbol = None a odkazy na ľavý aj pravý
podstrom. Prázdny strom je None.
- A – Zostavenie stromu: Napíšte funkciu
build_huffman(freq). Vstupom je neprázdny slovník znakov a ich kladných celočíselných početností. Opakovane spojte dva stromy s najmenšou váhou; prvý vybraný strom bude ľavým potomkom. Pri rovnakej váhe vyberte strom, ktorého listy obsahujú abecedne najmenší znak. Výsledkom je koreň Huffmanovho stromu. Na jediný znak vráťte list pre tento znak. Príklad: pre{"A": 2, "B": 3, "C": 8}vráti funkcia koreň s ľavým podstromom obsahujúcim listyAaBa pravým potomkom, ktorým je listC. Spoločný rodič listovAaBmá hodnotusymbol = None. - B – Dĺžka zakódovanej správy: Napíšte funkciu
huffman_size(tree, freq), ktorá vypočíta súčetpočetnosť × dĺžka kódupre všetky znaky. Dĺžka kódu je hĺbka listu. Ak strom obsahuje jediný znak, jeho kód má dĺžku1. Slovník obsahuje presne znaky zo stromu. Príklad: pre strom z úlohy A a početnosti{"A": 2, "B": 3, "C": 8}je výsledok18.
4. Huffmanovo dekódovanie
- A – Dekódovanie podľa tabuľky: Napíšte funkciu
huffman_decode(bits, codes), ktorá dekóduje bitový reťazec pomocou slovníka znak → kód. Kódy sú neprázdne a prefixové; vstup predstavuje úplnú platnú správu. Pre prázdny vstup vráťte"". Príklad:huffman_decode("010110", {"A": "0", "B": "10", "C": "11"}) == "ABCA". - B – Dekódovanie prechodom stromu: Napíšte funkciu
huffman_decode_tree(bits, tree), ktorá dekóduje správu priamym prechodom objektmiHuffmanNodez témy 4. Po dosiahnutí listu pridajte jeho znak do výsledku a pokračujte od koreňa. Strom má aspoň dva listy. Ak vstup skončí uprostred kódového slova, vyvolajteValueError. Príklad: pre strom s koreňom, ľavým listomAa pravým vnútorným uzlom, ktorého deti sú listyBaC, platíhuffman_decode_tree("01011", tree) == "ABC". Vstup"1"pre rovnaký strom vyvoláValueError.
5. Kódovanie dĺžky behov (RLE)
- A – Kódovanie: Napíšte funkciu
rle_encode(text), ktorá každú maximálnu skupinu rovnakých susedných znakov nahradí dvojicou(znak, počet). Vráťte zoznam dvojíc; pre prázdny text vráťte[]. Príklad:rle_encode("AAABBAC") == [("A", 3), ("B", 2), ("A", 1), ("C", 1)]. - B – Dekódovanie: Napíšte funkciu
rle_decode(data), ktorá zo zoznamu dvojíc(znak, kladný počet)obnoví pôvodný reťazec. Každý znak je reťazec dĺžky1. Pre prázdny zoznam vráťte"". Príklad:rle_decode([("A", 3), ("B", 2), ("A", 1)]) == "AAABBA".
6. Dynamické programovanie
V oboch úlohách použite dynamické programovanie a postupne vypĺňajte tabuľku.
- A – Minimálny počet mincí: Napíšte funkciu
min_coins(coins, amount), ktorá vráti najmenší počet mincí potrebný na vytvorenie zadanej sumy. Každú mincu možno použiť neobmedzene veľakrát. Hodnoty mincí sú kladné celé čísla a suma je nezáporná. Ak sumu nemožno vytvoriť, vráťte-1; pre sumu0vráťte0. Príklady:min_coins([1, 3, 4], 6) == 2;min_coins([2, 4], 7) == -1. - B – Súčet nesusediacich prvkov: Napíšte funkciu
max_non_adjacent(numbers), ktorá vráti najväčší súčet vybraných prvkov zoznamu nezáporných celých čísel. Nesmiete vybrať prvky zo susedných pozícií. Pre prázdny zoznam vráťte0. Príklady:max_non_adjacent([4, 1, 1, 9, 1, 5]) == 18;max_non_adjacent([2, 7, 9, 3, 1]) == 12.