Run-length encoding je jednoduchá metoda bezztrátové komprese. V článku vysvětlím, v čem spočívá, jak se s ní pracuje a ukážu příklad na obrázku BMP.
Motivace
Mějme řetězec 20-ti znaků
AAABBCCCCCCCAAAAAAAA
Dokážeme zmenšit počet znaků v řetězci, aniž bychom ztratili byť jen jedinou hodnotu, kterou obsahuje?
Mějme obrázek
Je nutné uložit jej pixelu po pixelu, aby pak mohl být ve stejné formě zobrazen?
Algoritmus RLE
Řetězec výše můžeme přečíst jako "á á á bé bé cé cé cé...", nebo možná přirozeněji "tři á, dvě bé, sedm cé a osm á". Stejně tak můžeme obrázek přečíst jako "tři černé, čtyři bílé, čtyři černé, pět bílých a čtyři černé". A to je ono -
jednoduše nahradíme podřetězce stejných znaků jejich délkou a samotným znakem. Řetězec výše tedy bude po zakódování vypadat
3A2B7C8A
Vidíme, že z původních 20-ti znaků dostáváme 8, aniž bychom přišli o originál. Jsme totiž schopni z našich 8-mi znaků přesně rekonstruovat vstupní řetězec o délce 20-ti.
Algoritmus existuje ve více variantách a úpravách, které z části řeší nevhodná vstupní data. Používají se speciální symboly, které například detekují opakování celých skupin, mění směr průchodu, nebo značí nezakódovanou sekvenci. Poslední případ můžeme demonstrovat na řetězci
AAABCDEFGHIII
který by po zakódování neoptimalizovaným způsobem vypadal
3A1B1C1D1E1F1G1H3I
Docílili jsme záporné komprese, kdy z původních 13-ti znaků dostáváme 18. Zkusme zavést speciální symbol "#", který použijeme spolu s číslem reprezentující počet nezakódovaných znaků. Dostaneme
3A7#BCDEFGH3I
tedy 13 znaků po zakódování.
Implementace
opakovani = 1;
vystup = "";
for(pro vsechny znaky - 1) {
if (znak == nasledujici znak) {
opakovani += 1;
} else {
vystup += opakovani + znak;
}
}
if (predposledni znak != posledni znak) {
vystup += "1" + posledni znak;
}
Cyklus projde vstupní řetězec znak po znaku a ve chvíli kdy se následující znak nerovná zpracovávanému přidá k výstupnímu řetězci informaci o počtu jeho opakování. Na konci máme v proměnné
vystup řetězec s výsledným tvarem vstupu po kompresi.
Příklad s BMP
Obrázek použitý nahoře jako příklad jsem v
Gimpu uložil jako BMP a poté otevřel v HEX módu v
PSPadu. Jak vidíme, zapsal se nekomprimovaně. Byty 00 jsou pixely černé barvy a FF barvy bílé.
Pokud v Gimpu zaškrtneme při ukládání možnost "Run-Length Encoded" a podíváme se do souboru, uvidíme zkomprimovanou verzi.
Literatura a odkazy
http://www.fileformat.info/format/bmp/egff.htm
http://www.root.cz/clanky/pcx-prakticky-implementace-komprimace-rle
Žádné komentáře:
Okomentovat