algorytm.org

Algorytm ByteRun

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 ByteRun
Ocena użytkowników:***** / 9
SłabyŚwietny 
Wpisany przez Bartosz Wikiera, 08 lutego 2012 15:44

By omówić zasady działania algorytmów ByteRun i RLE (Run Length Encoding) należy najpierw powiedzieć czym jest kompresja. Idąc za słownikiem języka polskiego jest to proces, którego celem jest nadanie czemuś mniejszej wielkości lub objętości. Oczywiście w informatyce tym "czymś" są dane - czy to w postaci tekstów, obrazów lub muzyki. Algorytm którego zasadę działania postaram się omówić jest prostym algorytmem kompresji bezstratnej. Znaczy to mniej więcej tyle iż dane po kompresji możemy przywrócić do ich pierwotnej formy nie tracąc przy tym żadnych informacji. Czasami zdarza się, że zależy nam nie tyle na dokładności co maksymalnym zmniejszeniu rozmiaru – wtedy stosuje się różnorakie algorytmy kompresji stratnej (jednym z popularnych formatów wykorzystującym taką właśnie kompresje jest JPEG).
Algorytmy ByteRun i RLE nie tworzą żadnego słownika pomocniczego wykorzystywanego do kompresji. Ich jedynym zadaniem jest zmniejszenie redundancji danych. Algorytmy te wykorzystywane do kompresji małych obrazów, dziś praktycznie nieużywane jeszcze w latach 80-tych były stosowane np. na ówczesnych amigach.

Algorytm ByteRun analizuje ciąg znaków bajt po bajcie i potrafi wykonywać dwie czynności:

Pojedynczy bajt ze znakiem może zawierać wartości od -128 do 127 włącznie. Pozostałą, nieprzydzieloną wartość -128, traktujemy jako kod pusty (wartość taka jest ignorowana podczas dekompresji).
Dzięki sekwencji powtarzania pozbywamy się nadmiarowych danych. Warto jednak zauważyć, że algorytm ten może w szczególnych przypadkach zwiększyć rozmiar pliku (np. sekwencja dwóch różnych znaków występujących naprzemiennie)

Przykład:

Ciąg bajtów: 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 7, 7, 8, 8, 8, 8, 8, 8, 2, 1, 3
Napotykamy na 5 zer, zatem do skompresowanego ciągu wstawiamy sekwencje powtarzania: -4, 0
Następnie 6 różnych znaków, więc do skompresowanego ciągu wstawiamy sekwencje kopiowania 6 bajtów: 5, 1, 2, 3, 4, 5, 6
Potem trzy siódemki i sześć ósemek, do skompresowanego ciągu wstawiamy dwie sekwencje powtarzania: -2, 7 oraz -5, 8
Na końcu trzy różne znaki, wstawiamy sekwencje kopiowania 3 bajtów: 2, 2, 1, 3
Wynik: -4, 0, 5, 1, 2, 3, 4, 5, 6, -2, 7, -5, 8, 2, 2, 1, 3
Spróbujmy teraz rozpakować tak skompresowane dane.
Czytamy n, wynosi ono -4, zatem mamy tutaj powtarzanie sekwencji danych z kolejnego bajtu. Powtarzamy zatem 0, –n+1 = -(-4)+1 = 4+1 = 5 razy.
Następne odczytane n, wynosi 5, zatem mamy tutaj kopiowanie sekwencji danych. Długość tej sekwencji wynosi n+1 = 5+1 = 6 bajtów: 1, 2, 3, 4, 5, 6.
Kolejne odczytane n, wynosi -2 mamy tutaj powtarzanie sekwencji danych z kolejnego bajtu. Powtarzamy zatem 7, –n+1 = -(-2)+1 = 2+1 = 3 razy.
Następne odczytane n, wynosi -5 mamy tutaj powtarzanie sekwencji danych z kolejnego bajtu. Powtarzamy zatem 8, –n+1 = -(-5)+1 = 5+1 = 6 razy.
Kolejne odczytane n, wynosi 2, zatem mamy tutaj kopiowanie sekwencji danych. Długość tej sekwencji wynosi n+1 = 2+1 = 3 bajtów: 2, 1, 3.
Wynik: 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 7, 7, 8, 8, 8, 8, 8, 8, 2, 1, 3
Czyli dane, które zostały uprzednio spakowane.

Uwaga: Czasami zdarza się, że w bardziej opłaca się skopiować więcej znaków po kolei, niż przepisać a następnie powtórzyć np. dwa znaki.
Bliźniaczym algorytmem jest RLE.
Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++pakuje sekwencje powtarzających się conajmniej 2 bajtów
.cpp
.cpp
***** / 0
Tomasz LubińskiC/C++pakuje sekwencje powtarzających się conajmniej 3 bajtów
.cpp
.cpp
***** / 0
 
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:58
Dodaj komentarz