Kódování délky běhu (eng. r unlength e ncoding , RLE ) neboli opakovací kódování je algoritmus komprese dat , který nahrazuje opakované znaky (série) jedním znakem a počtem jeho opakování. Série je sekvence skládající se z několika stejných znaků. Při kódování (balení, komprimaci) je řetězec identických znaků, které tvoří řadu, nahrazen řetězcem obsahujícím samotný opakující se znak a počet jeho opakování.
Představte si obrázek obsahující černý text na plném bílém pozadí. Při čtení pixelů takového obrázku řádek po řádku bude existovat řada bílých (pozadí) a černých (písmena) pixelů . Písmeno Boznačuje černý pixel a písmeno W bílý pixel. Zvažte nějaký libovolný obrázkový řetězec o délce 51 znaků:
WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWSpočítejme si počet znaků:
Celkem nalezeno 5 epizod. Nahraďte sérii počtem opakování a samotnou opakující se postavu:
9W3B24W1B14WVýsledkem byla sekvence 12 znaků. Původní sekvence sestávala z 51 znaků. Data byla komprimována 51/12≈4,25krát.
Vezměme si řetězec skládající se z velkého počtu neopakujících se znaků:
ABCABCABCDDDFFFFFFPo kompresi metodou RLE bude takový řádek vypadat takto:
1A1B1C1A1B1C1A1B1C3D6FPůvodní řetězec se skládá z 18 znaků a komprimovaný řetězec z 22. Velikost dat se zvýšila 22/18≈1,22krát.
Aby se po kompresi velikost dat nezvětšila, je abeceda, ve které se zaznamenávají délky běhů, rozdělena na dvě části (obvykle stejné). Například abecedu celých čísel lze rozdělit na dvě části: kladná a záporná čísla. Kladná čísla se používají k zaznamenání počtu opakování jednoho znaku a záporná čísla k zaznamenání počtu nestejných znaků za sebou.
Počítejme znaky s ohledem na výše uvedené:
Komprimovaný řetězec bude zapsán jako:
-9ABCABCABC3D6FPůvodní řetězec se skládá z 18 znaků a komprimovaný řetězec z 15. Velikost dat se zmenšila 18/15=1,2 krát.
Předpokládejme, že implementace metody RLE pro záznam délek řad (pro počítání počtu znaků) používá proměnnou typu integer se znaménkem „ “. Do takové proměnné můžete psát čísla od -128 do 127 včetně. Co když je délka série 128 znaků nebo více? V tomto případě je série rozdělena na díly tak, aby délka dílu nepřesáhla 127 znaků. Například řada 256 znaků „A“ bude zakódována následujícím řetězcem (256=127+127+2): signed char
127A127A2APsaní algoritmu RLE v nějakém programovacím jazyce s ohledem na tato omezení není triviální.
Kódování používané k ukládání obrázků samozřejmě funguje na binárních datech a ne na znacích ASCII , jako v diskutovaných příkladech, ale princip zůstává stejný.
Je zřejmé, že takové kódování je účinné pro data obsahující velký počet sérií, například pro jednoduché grafické obrázky, jako jsou ikony a grafika. Toto kódování však není vhodné pro obrázky s hladkými tóny, jako jsou fotografie.
Mezi běžné formáty pro sbalení dat pomocí RLE patří PackBits , PCX a ILBM .
Libovolné binární datové soubory lze komprimovat kódováním délky běhu , protože specifikace formátu souboru často zahrnují opakované bajty v oblasti zarovnání dat. Moderní kompresní systémy (jako je Deflate ) však častěji používají algoritmy založené na LZ77 , které jsou zobecněním metody run-length kódování a pracují se znakovými sekvencemi ve tvaru „BWWBWWBWWBWW“.
Zvuková data, která mají dlouhé po sobě jdoucí bajty (jako jsou zvukové vzorky nízké kvality ), mohou být komprimována pomocí RLE poté , co na ně bylo aplikováno Delta kódování .
| Kompresní metody | |||||||
|---|---|---|---|---|---|---|---|
| Teorie |
| ||||||
| Bezztrátový |
| ||||||
| Zvuk |
| ||||||
| snímky |
| ||||||
| Video |
| ||||||