39 lines
2.2 KiB
Markdown
39 lines
2.2 KiB
Markdown
Zadanie
|
|
|
|
A. Kompressor
|
|
|
|
Naprogramuj nástroj na kompresiu a dekompresiu. Na kompresiu použite aspoň dva kompresné algoritmy, napr. : Huffmanovo kódovanie, LZ77, LZ78, Run Length kódovanie alebo iný.
|
|
|
|
Meno vstupného a výstupného súboru načítajte ako argument príkazového riadka. V zadaní by mali byť implementované tieto dve funkcie:
|
|
|
|
/**
|
|
* Skomprimuje súbor in a zapíše do súboru out.
|
|
* @arg in smerník na otvorený vstupný súbor (na čítanie)
|
|
* @arg out smerník na otvorený výstupný súbor (na zápis)
|
|
* @return počet bajtov skomprimovaného súboru
|
|
*/
|
|
int compress(FILE* in, FILE* out);
|
|
/**
|
|
* Dekomprimuje súbor in a zapíše do súboru out.
|
|
* @arg in smerník na otvorený vstupný súbor (na čítanie)
|
|
* @arg out smerník na otvorený výstupný súbor (na zápis)
|
|
* @return počet bajtov dekomprimovaného súboru
|
|
*/
|
|
void decompress(FILE* in, FILE* out);
|
|
|
|
Kompresor a dekompresor by mal byť schopný pracovať s ľubovoľným binárnym súborom do 10 MB. Súbor by mal byť po skomprimovaní menší minimálne o 10 percent a po dekomprimovaní by mal byť zhodný s pôvodným súborom. Pri práci s binárnymi súbormi môžete využiť funkcie fopen(), fread() a fwrite().
|
|
|
|
Na otestovanie kompresora a dekompresora použite súbory z Cantebury corpus
|
|
|
|
Riešenie
|
|
|
|
Implementácia mojho riešenia zahŕňa algoritmus Run Length Encoding pracujúci na úrovni jednotlivých bajtov. Pri enkódovani sa hľadajú počty po sebe idúcich rovnakých bajtov a zapisuje sa počet namiesto samotných bajtov. Príklad:
|
|
|
|
in.txt: out.txt
|
|
AAAAAABB A6B2
|
|
|
|
V najlepšom prípade kompresia dokáže enkódovať bajty v pomere 1:127,5, v najhoršom prípade ide "negatívnu" kompresiu s pomerom 2:1.
|
|
|
|
Moje riešenie ukladá počet bajtov do jedného bajtu, t.j. maximálne 255. V prípade, že by vstupný súbor obsahoval príkladovo 500 rovnakých znakov A po sebe, uložili by sa ako A255 A245.
|
|
|
|
Pri dekódovaní sa v cykle čítajú 2 bajty, prvým je bajt ktorý sa opakuje a druhý je počet opakovaní. Tie sa následne vygenerujú v logickej pamäti programu a následne uložia pomocou jedného volania. |