Huffmanovo kódovanie

10th Nov 2026

Ú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:

Odovzdanie:

  • Súbor u9/huffman_tree.py odovzdajte 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: pri table = [None, 6, 11, None, None] volanie hash_insert(table, 16) vráti 3 a uloží 16 na index 3.
  • 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 prvom None alebo 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áti True, ak strom obsahuje danú hodnotu, inak False. Pri každom porovnaní pokračujte iba do príslušného podstromu. Pre prázdny strom vráťte False. Príklad: ak tree je koreň s hodnotou 5, ľavým dieťaťom s hodnotou 2 a pravým dieťaťom s hodnotou 8, potom bst_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ženie 3 do koreňa s hodnotou 5 vráti strom, ktorého koreň má hodnotu 5, ľavé dieťa hodnotu 3 a pravé dieťa je None.

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 listy A a B a pravým potomkom, ktorým je list C. Spoločný rodič listov A a B má hodnotu symbol = None.
  • B – Dĺžka zakódovanej správy: Napíšte funkciu huffman_size(tree, freq), ktorá vypočíta súčet početnosť × dĺžka kódu pre všetky znaky. Dĺžka kódu je hĺbka listu. Ak strom obsahuje jediný znak, jeho kód má dĺžku 1. 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ýsledok 18.

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 objektmi HuffmanNode z 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, vyvolajte ValueError. Príklad: pre strom s koreňom, ľavým listom A a pravým vnútorným uzlom, ktorého deti sú listy B a C, 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ĺžky 1. 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 sumu 0 vráťte 0. 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áťte 0. Príklady: max_non_adjacent([4, 1, 1, 9, 1, 5]) == 18; max_non_adjacent([2, 7, 9, 3, 1]) == 12.

Previous Post Next Post

Huffmanovo kódovanie