RLE
Z Wikipedii
Run-Length Encoding (RLE, kodowanie długości serii) - prosta metoda bezstratnej kompresji danych, której działanie polega na opisywaniu ciągów tych samych liter (bitów, bajtów, symboli, itp.) za pomocą licznik powtórzeń (długości ciągu), a dokładniej przez pary: licznik powtórzeń litery, litera.
Na przykład w ciągu
wwwwwiiiikkkkkkkiiippppppeeeeeddddiia
litera 'w' powtarza się 5 razy, co jest zapisywane jako 5w (ciąg pięciu liter w), dalej 'i' występuje 4 razy - 4i, itd. - ostatecznie uzyskuje się ciąg:
5w4i7k3i6p5e4d2i1a
składający się z 18 znaków, podczas gdy kodowany ciąg składał się z 37 znaków.
Dane, które charakteryzują się takim rozkładem liter to głównie obrazy bitmapowe, np. pomiędzy wierszami tekstu występują długie ciągi pikseli w kolorze tła, dokumenty fax, w których dominuje białe tło. Dlatego kompresja RLE jest stosowana m.in. w faksach, w różnych formatach zapisu obrazu, takich jak PCX, BMP, TGA, również jako jeden z filtrów w dokumentach PostScript i PDF.
Kodowanie RLE jest także stosowane jako jeden z końcowych etapów kompresji, który poprzedzają transformaty mające na celu utworzenie ciągów znaków dobrze kompresowanych przez RLE; takie transformaty, to np. Burrowsa-Wheelera i MTF lub w przypadku kompresji dźwięku jakiś sposób predykcji.
W niektórych praktycznych implementacjach (np. w filtrach Postscript i PDF) zapobiega się kodowaniu serii 1-elementowych, a więc powstawianiu ciągów postaci 1a1b1c1a. W takich przypadkach koder wysyła specjalny kod, który informuje dekoder, że następne n symboli należy wprost skopiować, a nie powielać - dla przykładowych danych będzie to ciąg (4)abca (a więc 5 symboli, zamiast 8).
