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)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) 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.