algorytm.org

Algorytm RLE (Run Length Encoding)

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm RLE (Run Length Encoding)
Ocena użytkowników:***** / 17
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 16 czerwca 2007 12:34

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
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.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 5
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 3
Tomasz LubińskiJava
.java
.java
***** / 3
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 30 lipca 2012 17:57
Komentarze
photo
0 # adn 2011-04-11 08:31
jaki jest sens zamiast "CC" wpisywać "C;2;", albo "CC0"?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Sloniu 2012-10-18 12:46
weźmy sytuacje ze mamy coś takiego do zakodowania 'AABCC5555' jeżeli nie zapiszemy tego z zerem to się sypnie. bez zera: AABCC552 i on teraz zacznie się mieszać przy dekodowaniu bo jak rozróżnić czy to 5 to następny znak czy liczba ilosci po cc? dlatego własnie piszemy 0. AA0BCC0552 i teraz wiemy czego jest ile.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Romek 2011-08-09 11:58
Tak naprawdę ten rodzaj algorytmu jest używany w formacie PCX. Tyle, że tam licznikiem powtórzeń jest fragment bajtu. RLE jest używany w Windows także przy obrazach dwukolorowych oraz 16-kolorowych.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # mariusz_temporary 2012-02-27 12:28
"jaki jest sens zamiast "CC" wpisywać "C;2;", albo "CC0"?
"

moim zdaniem taki, że algorytm to mechanizm, który dotyczy wszystkich możliwych przypadków wystąpienia różnych wartości i jeśli nawet dla przypadku CC zamieniamy na CC0, to pozostawiamy uniwersalność algorytmu. W przeciwnym razie musimy budować dodatkowe warunki na sytuacje wyjątkowe...
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Romek 2014-11-17 02:38
Ostatnie zdanie artykułu wprowadza zamieszanie gdyż w czołówkach Windows używany jest sposób kodowania rle, ale różni się od tego podanego w artykule.

Podczas dekodowania
wczytywane są dwa kolejne bajty b0 i b1.
jeżeli b0<>0, to powtórz b0 razy bajt (pixel) b1
w przeciwnym przypadku:
jeżeli b1=0 to jest koniec linii;
jeżeli b1=1 to koniec pliku;
jeżeli b1=2 to przeskok na obrazie o x=b2 pikseli i y=b3 wierszy;
w pozostałych przypadkach b1=3..255 skopiuj kolejnych b1 bajtów (pikseli).

Dokładniej było to opisane w PCKurierze 24/92
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz