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.