Kompressor – domáca časť skúšky

Zadanie

Cieľom zadania je naprogramovať nástroj na kompresiu a dekompresiu súborov. Program musí fungovať pre ľubovoľné binárne súbory do veľkosti 10 MB. Po dekompresii musí byť výsledný súbor rovnaký ako pôvodný.

Nie je povolené použiť RLE (Run Length Encoding). Je povolené použiť napríklad Huffmanovo kódovanie alebo iný algoritmus.

Popis programu

Program umožňuje:

skomprimovať súbor
dekomprimovať súbor
vypísať pomoc pri spustení

Program sa spúšťa z príkazového riadka a pracuje so súbormi zadanými ako argumenty.

Použitý algoritmus

Použil som Huffmanovo kódovanie.

Najprv sa spočítajú frekvencie jednotlivých bajtov vo vstupnom súbore. Podľa frekvencií sa vytvorí Huffmanov strom. Každému bajtu sa priradí bitový kód.

Do výsledného súboru sa uloží:

veľkosť pôvodného súboru
tabuľka frekvencií
skomprimovaný bitový tok

Pri dekompresii sa z tabuľky frekvencií znovu vytvorí strom a pomocou neho sa dáta dekódujú späť.

Použitie programu

./compressor -c vstupny_subor vystupny_subor Skomprimuje vstupný súbor do výstupného. ./compressor -d skomprimovany_subor vystupny_subor Dekompresia späť na pôvodné dáta. ./compressor -h Vypíše pomoc.

Technické detaily

program je napísaný v jazyku C (štandard C11)
používa iba štandardnú knižnicu C
práca so súbormi je realizovaná pomocou fopen, fread a fwrite
program je rozdelený na viac súborov:
- main.c – spracovanie argumentov a spustenie programu
- compressor.c – implementácia kompresie a dekompresie
- compressor.h – hlavičkový súbor
preklad prebieha pomocou Makefile

Obmedzenia

maximálna veľkosť vstupného súboru je 10 MB
kompresia nemusí byť efektívna pre všetky typy súborov
program nevyužíva žiadne externé knižnice

Testovanie

Program bol testovaný na súboroch z Canterbury corpus. Po dekompresii bol výsledný súbor vždy zhodný s pôvodným.

Použité zdroje

študijné materiály k predmetu
základný popis Huffmanovho kódovania
generatívny model ChatGPT (OpenAI)

Použitý prompt: "Implement Huffman compression in C without external libraries"

2.3 KiB Raw Permalink Blame History Unescape Escape