Termín odevzdání | 7.11.2020 23:59 CET |
---|---|
Bodový zisk | 4b |
Počet uploadů | |
Typ zadání | povinné |
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
(pro připomenutí, znak B
má číselnou podobu v ASCII tabulce 66):
$ 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
” a program ukončete s návratovou hodnotou 100
. Viz Příklad 4. Běh programu je v tomto případě okamžitě ukončen a výstupní soubor není ukončen znakem 0x0A
.
0x0A
, který se při výpočtu kompresního poměru nezapočítává.
$ hexdump -v -e '1/1 "%02X "' pub01.out
Vstupní hodnoty (stdin) | Výstup (stdout) | Chybový výstup (stderr) | Návratová hodnota |
---|---|---|---|
BWWBBBWWWWWWWBBBBBBBWWWBBBWWWWBBBWWWWWWBBBBBBBBBWWWWWWBBBBBB | BWWB3W7B7W3B3W4B3W6B9W6B6 | Pocet vstupnich symbolu: 60 Pocet zakodovanych symbolu: 25 Kompresni pomer: 0.42 | 0 |
Vstupní hodnoty (stdin) | Výstup (stdout) | Chybový výstup (stderr) | Návratová hodnota |
---|---|---|---|
ABC | ABC | Pocet vstupnich symbolu: 3 Pocet zakodovanych symbolu: 3 Kompresni pomer: 1.00 | 0 |
Vstupní hodnoty (stdin) | Výstup (stdout hex) | Chybový výstup (stderr) | Návratová hodnota |
---|---|---|---|
AABTTT | AABT3 | Pocet vstupnich symbolu: 6 Pocet zakodovanych symbolu: 5 Kompresni pomer: 0.83 | 0 |
Vstupní hodnoty (stdin) | Výstup (stdout) | Chybový výstup (stderr) | Návratová hodnota |
---|---|---|---|
ABBbdfbYYYY | ABB | Error: Neplatny symbol! | 100 |
Veřejné příklady + Makefile: hw04_-_rle.zip
Povinné zadání | |
---|---|
Název v BRUTE | HW04 |
Odevzdávané soubory | main.c |
Argumenty při spuštění | žádné |
Kompilace pomocí | clang -pedantic -Wall -Werror -std=c99 -O2 |
Procvičované oblasti | cykly a podmínky |