Run-length kódování

Komprese RLE neboli Run-length encoding je velmi jednoduchá forma komprese dat, ve které jsou po sobě jdoucí sekvence dat se stejnou hodnotou uloženy jako jedna hodnota plus její počet. To je nejužitečnější u dat, která obsahují mnoho takových "sekvencí"; například jednoduchá grafika s plochými barevnými plochami, jako jsou ikony a loga .

Představte si například obrazovku, která obsahuje černý text na bílém pozadí. Takových sekvencí by bylo mnoho s bílými pixely na prázdných okrajích a dalšími sekvencemi černých pixelů v oblasti textu. Předpokládejme jeden řádek (nebo skenovací řádek ), kde N představuje černé oblasti a B bílé:

BBBBBBBBBBBBNBBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBBNBBBBBBBBBBBBBBB

Pokud na tento řádek použijeme kódování délky běhu , dostaneme následující:

12B1N12B3N24B1N14B

Interpretováno jako 12 písmen B, 1 N písmeno, 12 B písmen, 3 N písmen atd. Kód délky běhu vykreslí původních 67 znaků za pouhých 18. To znamená, že původní řádek má 67 bajtů a kódovaný řetězec má pouze 18 bajtů. Toto kódování přeložené do binárního , jehož princip je stejný, se používá pro ukládání obrázků. Pomocí této metody lze komprimovat i binární datové soubory. První bajt obsahuje číslo, které představuje, kolikrát se znak opakuje. Druhý bajt obsahuje samotný znak. V ostatních případech jsou zakódovány do jednoho bajtu: 1 bit (0 nebo 1) a 7 bitů pro určení počtu po sobě jdoucích znaků.

Modernější kompresní systémy však často používají deflační algoritmus nebo jiné algoritmy založené na LZ77 , které mají výhodu v použití řetězcových sekvencí .

Některé formáty, které používají toto kódování, zahrnují Packbits , PCX a ILBM .

Run-length encoding provádí bezeztrátovou kompresi dat a je široce používáno na indexovaných 8bitových obrázcích (původně se používalo pro černobílé obrázky). Nefunguje to tak dobře na obrázcích s neustále se měnící barvou pixelů jako na fotografiích, ačkoli JPEG jej efektivně využívá na koeficienty, které zbyly po transformaci a kvantování bloků obrázků. Následně vytvořila základ dalších kompresních systémů, jako je CCITT skupina 3 – 1D