RLE
![]() | RLE – oznaczenie literowe powiatu leżajskiego na tablicach rejestracyjnych pojazdów w Polsce |
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, pikseli itp.) za pomocą licznika powtórzeń (długości serii), 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. aż 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, jak w dokumentach faksowych, 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 – jeden ze sposóbów predykcji.
W niektórych praktycznych implementacjach (np. w filtrach PostScript i PDF, w formacie TGA) zapobiega się kodowaniu serii 1-elementowych, a więc powstawaniu 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
, czyli 5 symboli, zamiast 8.
RLE 2D
W kompresji obrazów bitmapowych można stosować również rozszerzenie metody, w której sprawdza się, czy w bieżącym wierszu obrazu powtarzają się piksele z wiersza wcześniejszego, wykorzystując w ten sposób ewentualne przestrzenne zależności.
Może sprawdzać, czy zachodzi równość ciągu pikseli i dla pewnego zakresu jak również na skos, tj. porównywać z ciągami pikseli z poprzedniego wiersza przesuniętymi o jedną pozycję w lewo lub prawo ( lub ). Jeśli zostanie znaleziony taki ciąg, wówczas zapisywana jest jego długość oraz kierunek porównania (tj. powyżej, powyżej na skos w lewo lub powyżej na skos prawo). Rzecz jasna prócz tego stosowana jest zwykła metoda RLE.
Przykład
Fragment obrazu:
y-1: a b c d a a a b c ← przetworzony wiersz obrazu y : b c d a a c c b c ← przetwarzany wiersz
Wiersz może zostać zakodowany 6 symbolami: (powyżej na skos w prawo)5
, 2c
, (powyżej)2
. Udało się znaleźć w przetwarzanym wierszu dwa ciągi występujące w poprzednim wierszu, oprócz tego powtarza się litera c
.
Dla porównania po zastosowaniu wyłącznie kodowania długości serii: 1b1c1d2a2c1b1c
(14 symboli), zaś po eliminacji ciągów 1-elementowych: (3)bcd2a2c(2)bc
(11 symboli).
Bibliografia
- Artur Przelaskowski: Kompresja danych: podstawy, metody bezstratne, kodery obrazów. Warszawa: BTC, 2005. ISBN 83-60233-05-5.
- Khalid Sayood: Kompresja danych. Wprowadzenie. Warszawa: RM, 2002. ISBN 83-7243-094-2.
- Britannica: topic/run-length-encoding