2.1. Metoda RLE

Jednou z nejstarších metod komprese je metoda proudového kódování RLE (Run Length Encoding), která se snaží v datovém toku objevit a redukovat posloupnosti opakujících se znaků. Místo této posloupnosti je uložen pouze speciální znak představující indikátor, opakovaný znak a počet opakování. Například posloupnost xyzzzzyyyyyxwwww můžeme uložit jako xy#z4#y5x#w4, kde znak '#' představuje indikátor komprese. V tomto případě jsme tedy řetězec délky 16 znaků nahradili komprimovaným řetězcem délky 12 znaků.

Úspěšnost komprese můžeme popsat parametrem faktor komprese jako 12/16=0,75, jenž udává, jakou část původního prostoru zabírají údaje po kompresi. V tomto případě je faktor komprese 75 %. Jinou možností je jeho převrácená hodnota - kompresní poměr, který v tomto případě činí 16/12=1,33. Čím větší je kompresní poměr, tím úspěšnější je komprese.


Úkol k zamyšleníÚkol k zamyšlení
Co znamená velikost kompresního poměru menší než 1? Kdy k této situaci může při použití metody RLE dojít a jakým způsobem tomu můžeme zamezit?

Je třeba si uvědomit, že každou posloupnost opakujících se znaků zakódujeme do tří znaků (indikátor, opakující se znak a počet opakování). Je-li tedy tato posloupnost kratší než tří znaky, spotřebujeme na její zakódování více prostoru, než kolik zabrala původně. Při právě třech znacích ke zkrácení ani prodloužení nedojde, ovšem ztratíme čas, nutný k dekompresi textu. Proto se tato komprese používá až od jisté minimální délky posloupnosti, v tomto případě například až od délky čtyři.

Dalším problém nastává v situaci, kdy délka posloupnosti opakujících se znaků je větší než číslo, kterým jsme schopni tuto délku reprezentovat. Například pokud ukládáme délku posloupnosti do jedné slabiky, můžeme uložit pouze hodnoty 0 až 255. Vzhledem k tomu, že komprimujeme pouze posloupnosti délky alespoň čtyři znaky, jsme schopni ukládat hodnotu délky v kódu s posunutou nulou (číslo 0 znamená délku 4, číslo 255 délku 259 znaků). Je-li posloupnost delší než 259 znaků, můžeme ji však rozdělit na kratší úseky a ty pak kódovat samostatně za cenu jisté ztráty kompresního poměru. Případně můžeme jiným indikátorem specifikovat, že délka posloupnosti bude uložena např. na dvou slabikách.


Úkol k zamyšleníÚkol k zamyšlení
Co když bude posloupnost komprimovaných znaků v předchozím příkladu obsahovat znak '#'? Jakým způsobem zajistíme rozlišení indikátoru od běžného znaku?

Pokud víme, že komprimujeme pouze textové soubory obsahující tiskutelné znaky, mezery, tabulátory a konce řádků, stačí zvolit jako indikátor znak, jenž se v textu nemůže vyskytnout. Připustíme-li však možnost výskytu znaků s libovolným kódem, je třeba zavést další speciální znak, jenž ruší speciální význam následujícího znaku. Příklady tohoto řešení najdete ve většině programovacích jazyků u speciálních znaků v řetězcových konstantách. V jazyce C je zpětné lomítko v řetězcové konstantě považováno právě za takový únikový znak (escape character), definující nebo měnící speciální význam následujícího znaku nebo posloupnosti znaků. Při použití zpětného lomítka jako únikového znaku bychom tedy poslounost a#cccc\d zakódovali jako a\##c4\\d. Je zřejmé, že výskyt speciálních znaků v komprimovaném textu opět vede ke zhoršení efektivity komprese.

Jinou variantou je do výstupu vždy po výskytu tří stejných znaků vložit počet dalších opakování. Potom nemusíme rezervovat žádné speciální znaky, neboť začátek komprimovaného úseku je indikován výskytem tří stejných znaků po sobě. Například řetězec aabbbccccdddddse zakóduje jako aabbb0ccc1ddd2. Tato varianta metody RLE se používá v kombinaci s dalšími v protokolech určených pro modemy.

Úkol k textu
Implementujte v některém programovacím jazyce funkci, která provede kompresi zadaného řetězce metodou RLE. Jako únikový znak použijte zpětné lomítko, jako indikátor komprese znak '#'. Počet opakování reprezentujte jedinou číslicí.

Metoda RLE je bezeztrátová, symetrická a velmi rychlá, ovšem často za cenu nižšího kompresního poměru. Vzhledem k tomu, že v běžných textových souborech se posloupnosti opakujících se znaků příliš nevyskytují (snad s výjimkou mezer), je tato metoda efektivní spíše pro kompresi grafických a zvukových souborů, kde nedochází k velkým změnám, například pro kompresi obrázků s malou hloubkou barev nebo u zvukových souborů zachycujících řeč. Konkrétně se tato metoda používá například v grafických formátech PCX nebo BMP.