Search
RLE (run-length encoding) je bezeztrátová komprese, která kóduje vstupní data tak, že kóduje posloupnosti stejných hodnot do dvojic (délka posloupnosti, hodnota). Účinnost komprese je silně závislá na charakteru vstupních dat, která musí obsahovat delší sekvence stejných znaků, jinak výrazně účinnost komprese klesá.
Příklad vstupních dat kodéru RLE:
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
Výsledek kódování RLE (není výstupem programu řešícího HW04, pouze demonstrační):
W12B1W12B3W24B1W14
Nejčastější implementace je komprese bytového proudu. Implementuje se pomocí dvojic bytů, jeden byte udává hodnotu kódovaného bytu (symbol), druhý byte určuje počet opakování. Nevýhoda je, že pro jeden neopakující se symbol v proudu bytů se kóduje tato hodnota pomocí dvojice bytů, proto pro nevhodná vstupní data může být komprese neúčinná a velikost proudu z výstupu kóderu RLE až dvojnásobná oproti vstupu. Proto pro naší implementaci zvolíme následující pravidla:
a) kódování neopakujícího se symbolu
A ⇒ A
b) kódování symbolů s jedním opakováním
AA ⇒ AA
c) kódování sekvence 3 - 255 stejných symbolů
AAA ⇒ A3
d) pro sekvence delší než 255 stejných symbolů proběhne kódování 'nadvakrát'. Následující příklad je zkáceným zápisem zakódování 257 znaků 'A'
A..A ⇒ A255AA
A
B
$ cat file.in AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA $ ./hw04 < file.in > file.out $ cat file.out AB $ hexdump -C file.out 00000000 41 42 0a |AB.| 00000003
V rámci tohoto domácího úkolu budeme místo binárního vyjádření počtu opakování používat dekadické číslice v ASCII kódování; bude jednodušší vizuální i automatická kontrola. Při výpočtu kompresního poměru pak ale bude třeba počítat s tím, že čísla větší než 9 jsou reprezentovány dvěma a více byty v ASCII kódování.
Error: Neplatny symbol!\n
100
0x0A
$ hexdump -v -e '1/1 "%02X "' pub01.out
BWWBBBWWWWWWWBBBBBBBWWWBBBWWWWBBBWWWWWWBBBBBBBBBWWWWWWBBBBBB
BWWB3W7B7W3B3W4B3W6B9W6B6
Pocet vstupnich symbolu: 60 Pocet zakodovanych symbolu: 25 Kompresni pomer: 0.42
ABC
Pocet vstupnich symbolu: 3 Pocet zakodovanych symbolu: 3 Kompresni pomer: 1.00
AABTTT
AABT3
Pocet vstupnich symbolu: 6 Pocet zakodovanych symbolu: 5 Kompresni pomer: 0.83
ABBbdfbYYYY
ABB
Error: Neplatny symbol!
Veřejné příklady + Makefile: hw04_-_rle.zip