HW5: Huffmanovo Kódovanie

V kontexte kompresie v informačnej teórii uvažujme o konečnej, neprázdnej množine $\Sigma$ (alebo inač povedané, abecede) a pravdepodobnostnom rozdelení $P: \Sigma \rightarrow [0,1]$. Vašou úlohou je skonštruovať prefixové kódovanie $C: \Sigma \rightarrow \{0,1\}^*$. Kódovanie musí byť také, aby očakávaná dĺžka kódu $L(C) = \sum_{s \in \Sigma} P(s) \cdot\bigl|C(s)\bigr|$ bola asymptoticky minimalizovaná v súlade so Shannonovou entropiou $H(P) = −\sum_{s\in\Sigma} P(s) \log_2 P(s)$, pričom je rešpektovaná štandardizovaná forma kladená kanonickou verziou Huffmanového algoritmu.

Skvelé, nie? A teraz menej formálne. Vašou úlohou je implementovať Huffmanovo kódovanie, teda algoritmus pre bezstrátovú kompresiu dát, ktorý prevedie znaky vstupného súboru (odteraz "symboly") na postupnosti bitov (odteraz "kódové slová") také, že vo výsledku minimalizujete veľkosť výstupného súboru. Intuitívne – symbolom, ktoré sa vo vstupnom súbore vyskytujú najčastejšie, priradíte kratšie kódové slová, zatiaľ čo najviac zriedkavým symbolom priradíte tie najdlhšie.

Huffmanov kód má v praxi široké využitie ako súčasť moderných kompresných algoritmov. Konkrétne je kódovanie súčasťou komplexnejších algoritmov (DEFLATE) a má využitie v bežne používaných formátoch ako ZIP, gzip, a JPEG.

Vašou úlohou bude implementovať dve funkcie:

Parameter input_path obsahuje cestu ku vstupnému binárnemu súboru. V prípade, že je cesta nullptr, alebo operačný systém nedokáže otvoriť súbor z ľubovoľného dôvodu, vypíšte na štandardný chybový výstup vhodnú hlášku a program ukončite.

Podobné pravidlá platia pre cestu ku výstupnému súboru output_path s jednou výnimkou. V prípade, že je output_path nullptr, vypíšte výstup na stdout.

Obe funkcie vrátia 0 v prípade úspechu a ľubovoľné iné číslo v prípade chyby. Program tak isto skončí s chybou v prípade, že je vstupný súbor prázdny.