Uvažme ukládání řetězců do souboru v binárním formátu.
Naprogramujte funkci
void append(char* string, char* filename), která na konec
souboru přidá nový řetězec.
Naprogramujte funkci
long search(char* string, char* filename), která prohledá
soubor a pokud obsahuje záznam o daném řetězci, vrátí jeho offset od
začátku souboru. Jinak vrátí -1.
V souboru odpovídá řetězci jeden záznam, záznamy jsou v souboru za sebou. Jeden záznam vypadá následovně.
offset velikost vyznam
--------------------------------------------------------------------------
0 2 velikost retezce v bajtech
2 ? ulozeny retezec, chapan jako posloupnost unsigned char
bez 0 na konci
--------------------------------------------------------------------------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)Naprogramujte základ jednoduchého kompresního programu.
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);