Úkol odevzdejte mailem (adresu najdete na webu katedry), s předmětem ZP2 - domácí úkol 1, jako přílohu soubor se zdrojovým kódem (a nic dalšího). Odevzdávejte nejpozději 4. 5. ve 23:59.
Za úkol lze získat 15 bodů.
Run Length Encoding (RLE) je velmi jednoduchý bezeztrátový kompresní princip. Vysvětlíme jej na posloupnostech symbolů a později si řekneme, jak jej uplatníme v jednoduchém kompresním programu.
Vstupem RLE je posloupnost symbolů (symbol je zde abstraktní pojem, který nijak nevztahujeme k jazyku C, znakům v textu atd.). Tu převedeme do komprimované podoby s pomocí následujícího principu:
Pokud se v posloupnosti za sebou nachází n-krát symbol
x, převedeme ji na dvojici (x, n).
Předchozí bod aplikujeme na maximálně dlouhé (= nejdou prodloužit) podposloupnosti vstupní posloupnosti v pořadí, ve kterém se ve vstupní posloupnosti vyskytují.
Například posloupnost aaabaabcccccbccccd zakódujeme
na
(a,3)(b,1)(a,2)(b,1)(c,5)(b,1)(c,3)(d,1)Za základě RLE implementujte jednoduchý kompresní program. Soubor pro
kompresi budeme otevírat v binárním módu. Pro RLE budeme za jeden symbol
považovat jeden bajt souboru. Dvojici (x, n), kde
x je symbol a n je počet jeho výskytů budeme
do výsledného souboru ukládat pomocí dvou bajtů: do prvního uložíme
x, do druhého uložíme n-1. Takto jsme schopni
uložit pouze dvojice, kde je n <= 256. Dvojice, kde je
n>256, si představíme jako posloupnost
n/256 dvojic (x, 256), případně následovanou
dvojicí (x, r), kde r = n % 256. Tyto dvojice
poté uložíme stejným způsobem, jako dvojice s
n<=256.
Kompresní program implementujte jako funkce
void RLE_encode(char* in_path, char *out_path);
void RLE_decode(char* in_path, char *out_path);Argument in_path je ceska k načítanému souboru, argument
out_path je cesta k souboru, do kterého program ukládá.
Program lze otestovat tak, ze zkomprimujete a dekomprimujete soubor a výsledek porovnate s původním souborem.