usaa25/sk1

Zadanie -Naprogramovať nástroj na kompresiu a dekompresiu binárnych súborov pomocou kompresného algoritmu (nie RLE). Program má podporovať súbory do 10 MB, dosiahnuť minimálne 10% kompresiu a po dekompresii má byť súbor identický s pôvodným.

Stručný opis funkčnosti -Program komprimuje a dekomprimuje súbory pomocou Huffmanovho kódovania. Pri kompresii analyzuje frekvenciu výskytu jednotlivých bajtov a vytvorí pre ne optimálne binárne kódy - častejšie bajty dostanú kratšie kódy. Pri dekompresii použije uloženú frekvenčnú tabuľku na rekonštrukciu pôvodných dát.

STRUČNY OPIS RIEŠENIA

Program používa Huffmanovo kódovanie:

Kompresia: Načíta súbor do pamäte Spočíta frekvenciu každého bajtu (0-255) Vytvorí zoznam uzlov pre bajty s nenulovou frekvenciou Zoradí uzly podľa frekvencie (bubble sort) Postupne spája dva uzly s najnižšou frekvenciou do stromu Vygeneruje binárne kódy prechádzaním stromu Zakóduje dáta pomocou týchto kódov bit po bite Uloží veľkosť, frekvenčnú tabuľku a komprimované dáta

Dekompresia: Načíta veľkosť a frekvenčnú tabuľku Zrekonštruuje Huffmanov strom rovnakým spôsobom Číta komprimované dáta bit po bite Pre každý bit prechádza stromom (0=vľavo, 1=vpravo) Keď dosiahne list, zapíše zodpovedajúci bajt Pokračuje kým nedekóduje celý súbor

PODMIENKY FUNGOVANIA

Program funguje správne za týchto podmienok:

Vstupný súbor existuje a je čitateľný Veľkosť súboru je maximálne 10 MB Dostatočná voľná pamäť (aspoň 2× veľkosť súboru) Súbor nie je prázdny Pri dekompresii sa používa súbor vytvorený týmto programom

Kompresia:

Textové súbory: 40-60% kompresia Zdrojové kódy: 30-50% kompresia Binárne súbory: 5-30% kompresia (závisí od obsahu) Už komprimované súbory (zip, jpg): minimálna alebo žiadna kompresia Veľmi malé súbory (<1 KB): môžu byť väčšie kvôli hlavičke (1032 B)

ZOZNAM POUŽITYCH ZDROJOV

Youtube: https://www.youtube.com/watch?v=JsTptu56GM8 Youtube: https://www.youtube.com/watch?v=iiGZ947Tcck Youtube: https://www.youtube.com/watch?v=goOa3DGezUA Internet: https://en.wikipedia.org/wiki/LZ77_and_LZ78 Internet: ChatGBT Prompt: Príklady kompresie dát