Run Length Encoding


       W poprzednich artykułach omówiłem kompresję słownikową i probabilistyczną.

(Sięgamy do wcześniejszych wydań magazynu SERIOUS - Zenon)

       Metody te pomimo wielu zalet nie zawsze jednak umożliwiają optymalną kompresję. Jeżeli w danych, które chcemy skompresować jest ciąg identycznych bajtów, powyższe metody nie sprawdzają się najlepiej. W przypadku metody słownikowej taki sam ciąg powinien wystąpić wcześniej, żeby mógł być skrócony (chociaż da się to ominąć).

       Często metoda słownikowa operuje na krótkich frazach, co może powodować, że jeden ciąg będzie podzielony na kilka części, pomimo, że można by to zrobić optymalniej. Także metoda probabilistyczna jest mało użyteczna w przypadku takich danych. Na przykład ciąg 64 identycznych bajtów można za jej pomocą spakować maksymalnie do 8 bajtów (co i tak jest mało realne), natomiast sama struktura tych danych sugeruje, że można by tutaj zastosować metodę, która skróci te dane do dwóch, może trzech bajtów.

       Metoda, która najlepiej nadaje się do kompresji powtarzających się danych, zwana metodą powtarzających się elementów lub RLE (Run Length Encoding), stosuje licznik informujący ile razy powtarza się dany bajt, po czym następuje bajt, który należy powielić. Tutaj jednak pojawia się problem odróżnienia licznika od pozostałych danych. I tu można zastosować dwa podejścia.

       Pierwszym sposobem jest wybranie najrzadziej występującego bajtu i traktowanie go jak znacznik dla sekwencji. Dane nie stanowiące sekwencji będą przepisywane bez zmian.

       Przykład.

Ciąg wejściowy:

0000011112000087654...000000

Każdy z bajtów zawiera się w powyższym przykładzie na jednej pozycji. "..." - oznacza, że jest tu dużo różnych dziwnych danych, które akurat, w tym przykładzie, mało nas interesują ;-)

Interesuje nas jedynie to, że najrzadziej występującym symbolem okazał się bajt "2". Możemy zakodować nasz ciąg wejściowy jako:

2 250 241 212 240 87654 ... 260

       Spacje zostały użyte tylko w celu ułatwienia oglądania (nie tworzą danych wynikowych) ;-) Ciąg wejściowy miał długość 25+? bajtów, wyjściowy natomiast ma 21+?.

Przeanalizujmy:
Pierwszy bajt informuje, co jest znacznikiem ("2").

"250": "2" - znacznik czyli mamy do czynienia z sekwencją, kolejne dwa bajty określają szczegóły.
"5" - kolejny bajt powielamy pięciokrotnie.
"0" - bajt, który należy powielić.

Czyli dostajemy "00000".

"241": "2" - sekwencja, "41" --> "1111"

Dekodujemy pozostałe grupy. Po zdekodowaniu grupy "240" natrafiamy na "8".

Ponieważ nie jest to znacznik sekwencji, więc przepisujemy bez zmian. Tak samo z pozostałymi bajtami, aż do kolejnej "2".

Podczas kompresji może wystąpić dość specyficzna sytuacja o której należy tu wspomnieć. Jeśli bajtem do kompresji okaże się bajt, który wyznaczony został na znacznik sekwencji, to nie może on być w prosty sposób przepisany jak inne bajty, które nie tworzą sekwencji (np. "87654"). W naszym przykładzie takim bajtem jest ten z pozycji dziesiątej ("2"). Przepisanie go bez zmian spowodowałoby że przy dekompresji bajt ten zostałby potraktowany jak znacznik, niszcząc całą strukturę danych. W celu ominięcia takiej sytuacji stosuje się zabieg tworzenia sekwencji o długości 1.

W naszym przykładzie "2" zostało zakodowane jako

"212", czyli:
 2 - znacznik wystąpienia sekwencji
  1 - ile razy powielić.
   2 - bajt, który należy powielić.

       Powoduje to wydłużenie danych wynikowych, ale ten sposób kompresji nadaje się tylko do specyficznych danych, a w takich danych często się zdarza, że jakiś bajt nie występuje ani razu.

       Przy niewielkiej liczbie wystąpień bajtu-znacznika kompresja też może okazać się opłacalna. Jak zawsze sens stosowania metody zależy od struktury kompresowanych danych. Jednak może się tak zdarzyć, że sporo bajtów ułożonych jest w grupy, a pomimo to kompresja okazuje się nieopłacalna. Powodem tego jest zbliżona częstotliwość wy stępowania poszczególnych bajtów. Nie sposób wówczas wybrać bajt, który służyłby za znacznik, gdyż każde jego wystąpienie w danych wejściowych wydłuża dane wyjściowe, często do tego stopnia, że kompresja traci sens.

       W takiej sytuacji można zastosować drugą metodę. Charakteryzuje się ona tym, że występują tutaj dwa znaczniki. Jeden dla sekwencji i drugi dla pozostałych danych. Już z jednym znacznikiem był problem, a z dwoma ma być prościej? Tak, ponieważ nie jest on teraz bajtem ale bitem. W związku z tym bajt można podzielić na dwie części:

ZXXXXXXX.
"Z" - oznacza znacznik.

Przyjmijmy że:1 - sekwencja
0 - dowolne dane

"XXXXXXX" - jest licznikiem.

W przypadku sekwencji licznik informuje ile razy skopiować bajt, który pojawi się jako następny. Ponieważ nie ma sensu kodować sekwencji jedno i dwuelementowych, więc wartość zero licznika może oznaczać trójelementowe sekwencje. I tak analogicznie maksymalna wartość licznika (127) oznacza sekwencje 130-elementowe. Sekwencje jedno i dwuelementowe można traktować jak dane nie stanowiące sekwencji.

W przypadku gdy Z=0, licznik informuje ile kolejnych danych należy przepisać bez jakichkolwiek zmian. Ponieważ zero jest wartością mało sensowną, więc ilość danych do przepisania będzie wartością licznika zwiększoną o jeden. Z danych w naszym przykładzie mamy:

$82$00 $81$01 $00$02 $81$00 $04$08$07$06$05$04 ... $83$00

       Czyli otrzymaliśmy 16+? bajtów. (HEX)

Dla rozwiania wątpliwości zdekodujmy:

$82=%10000010 czyli:
znacznik=1 i licznik=2, a więc sekwencja, czyli ilość elementów wynosi (licznik+3). Dla sekwencji pobieramy kolejny bajt ($00). Po zdekodowaniu otrzymujemy 00000.

$81=%10000001: Z=1, L=1, więc sekwencja, pobieramy kolejny bajt ($01) i przepisujemy go (L+3) razy: 1111

$00=%10000000: Z=0, L=0, dane niepowtarzalne. Ich ilość wynosi (L+1), więc przepisujemy (L+1) kolejnych bajtów (czyli w naszym przypadku 1). Na wyjście trafi więc bajt 2.

Kolejna grupa $81$00 -> 0000

Następny bajt $04. Z=0, L=4. Dane niepowtarzalne o ilości (L+1), czyli przepisujemy 5 sztuk: 87654.

       Trudno jest określić, która z powyższych metod jest lepsza. Jak zawsze wszystko zależy od danych wejściowych. Ważne jest to, iż metoda ta zakłada występowanie dość specyficznego układu danych i tylko wówczas jest sens jej stosowania. Jednak jeśli ten specyficzny układ danych wystąpi, a metoda ta nie zostanie zastosowana, wyniki kompresji będą znacząco gorsze, nawet przy stosowaniu dość złożonych algorytmów jakimi są metody słownikowe i probabilistyczne.

Glonisz/Quasimodos