Algorytm RLE (Run Length Encoding) jest jednym z najprostszych algorytmów bezstratnej kompresji danych. Jego idea polega na zamianie ciągów powtarzających się symboli oznaczeniem, że wystąpił ciąg danego symbolu i określeniu jego długości. Istnieje kilka sposobów takiej kompresji:

• wykorzystanie specjalnego znaku do oznaczenia ciągu
• użycie podwójnego symbolu do oznaczenia sekwencji powtarzających się znaków

Rozpatrzmy różnice pomiędzy tym kodowaniem na przykładzie pliku zawierającym następujące dane:
ABBBBBBBBBCCDEFB

W pierwszym sposobie musimy mieć jakiś symbol, który nie istnieje w kompresowanym pliku, do oznaczenia sekwencji powtarzających się symboli. W naszym przypadku może to być znak średnika. Zatem nasz przykładowy plik po skompresowaniu wyglądałby następująco: AB;9;C;2;DEFB
Należy zauważyć, że znak średnika wykorzystujemy tylko do oznaczenia powtórzeń, dzięki temu nie tracimy miejsca w przypadku pojedynczych symboli.

Ciekawszym i bardziej uniwersalnym jednak sposobem jest oznaczenie sekwencji poprzez dwa powtarzające się symbole i podanie za nim długości sekwencji pomniejszonej o dwa. Zmniejszonej gdyż dwa symbole już wypisaliśmy, a więc podamy w ten sposób ile brakuje do naszej oryginalnej sekwencji. Tak więc przy zastosowaniu tego sposóbu otrzymamy następujący wynik:
ABB7CC0DEFB
A więc podczas dekompresji odczytujemy kolejne znaki, jeżeli odczytany znak jest różny od poprzedniego to poprostu wypisujemy go na wyjście. Jeżeli natomiast jest taki sam jak poprzednio odczytany to wypisujemy go na wyjście a następnie odczytujemy z kolejnej komórki ile razy jeszcze powinniśmy go wypisać.
Należy tutaj zauważyć, że poruszając się po pojedynczych bajtach jesteśmy w stanie w takiej pojedynczej komórce zapisać maksymalną długość ciągu rowną 255. Dlatego też ta opcja bywa nazywana algoytmem RLE z progiem. W pierwszym opisanym sposobie nie było z tym problemu gdyż liczbę wystąpień symboli w ciągu braliśmy w znak średnika, dlatego pomiędzy dwoma średnikami mogliśmy wpisać dowolnie dużą liczbę. W tym sposobie musimy zatem zabezpieczyć nasz program kompresujący przed przypadkiem gdy wejściowa sekwencja do kompresji będzie dłuższa niż 257 znaków (257 znaków A zapiszemy po skompresowaniu jako AA255). Co gdy sekwencja jest dłuższa? Wypisujemy do kompresowanego pliku sekwencje dla 257 powtarzających się znaków i zaczynamy kompresję od nowa. Zatem dla 260 powtarzających się znaków A otrzymamy w skompresowanym pliku zapis AA255AA1.
Algorytm ten świetnie sprawdza się dla plików zawierających dużo powtarzających się danych. Mogą to być pliki tekstowe z dużą ilością spacji, albo obrazy z dużymi powierzchniami w kolorach bieli lub czerni.
Gdyby obraz poniżej zapisać jako bitmapę o 256 kolorach wówczas można spakować go tym algorytmem z około 6 kB do 1.5 kB. Wynik jest imponujący jak na tak prosty algorytm ale wynika z tego, że w bitmapie tej występują duże obszary o tym samym kolorze. W dodatku każdy kolor w bitmapie o 256 kolorach zapisywany jest dokładnie na jednym bajcie. Sprawia to, że obok siebie występuje wiele takich samych wartości.
Algorytm RLE wykorzystywany jest między innymi do kompresji czołówek logo windows 3.1, 95 i 98, a także w jednym z podformatów TIFF.

Komentarze