Kodowanie Długości Serii

Prostota kodowania RLE

Kodowanie długości serii należy do klasycznych i intuicyjnych form bezstratnej kompresji danych. kodowanie długości serii (RLE). Algorytm zastępuje każdą serię powtarzających się wartości parą zawierającą wartość i długość serii. Wariant może zapisywać także serie jednoelementowe, zależnie od przyjętego formatu.

RLE wykorzystuje ciągłe bloki identycznych danych. Analiza globalnej częstości symboli i słownik fraz należą do innych klas metod. Prostota i szybkość RLE decydowały o jego użyciu w faksach oraz formatach obrazów. Dekoder odtwarza serię przez powtórzenie wartości wskazaną liczbę razy, więc nie musi przechowywać złożonego modelu danych. Zasada ta ułatwia zrozumienie metod, które łączą kodowanie serii z innymi etapami kompresji.

Zasada działania kodowania długości serii

Mechanizm RLE można pokazać na sekwencji kolorowych płytek:

CZERWONY, CZERWONY, CZERWONY, CZERWONY, CZERWONY, ZIELONY, ZIELONY, ZIELONY, NIEBIESKI, NIEBIESKI

Zwięzły opis tej sekwencji ma postać:

5 CZERWONYCH, 3 ZIELONE, 2 NIEBIESKIE

RLE skanuje strumień danych i dla każdej maksymalnej serii kolejnych, identycznych wartości zapisuje dwie informacje. Seria kończy się przed zmianą symbolu albo na końcu strumienia, więc dwie sąsiednie serie nie mogą mieć tej samej wartości:

• Licznik: Liczba wystąpień wartości w serii.
• Wartość: Symbol powtarzany w serii.

Przykład RLE: prosta mapa bitowa

RLE pasuje do prostych obrazów bitmapowych z ograniczoną paletą, takich jak ikony, logotypy i rysunki techniczne. Poniżej pokazano kompresję monochromatycznej strzałki o wymiarach 10x8 pikseli. W tym przykładzie kodowanie wykonujemy osobno dla każdego wiersza, aby zachować granice obrazu. Konkretny format może też przechowywać wiersze jako osobne jednostki. Po połączeniu wierszy w jeden strumień graniczne serie mogłyby się połączyć, więc wynik miałby inną liczbę par.

Krok 1: dane nieskompresowane

Obraz można zapisać jako sekwencję wartości pikseli. W przykładzie 'B' oznacza biały piksel, a 'C' czarny piksel. Odczyt od lewej do prawej i z góry na dół tworzy liniowy strumień danych. Spacje między grupami oddzielają wiersze i nie należą do danych:

BBBBBBBBBB BBBBCBBBBB BBBBCBBBBB BBBBCBBBBB CCCCCBBCCC BBBBCBBBBB BBBBCBBBBB BBBBCBBBBB

W formie nieskompresowanej obraz wymaga przechowania 80 wartości pikseli (10 pikseli w wierszu * 8 wierszy). Przy jednym bajcie na piksel daje to 80 bajtów, pomijając nagłówki i ewentualne wyrównanie wierszy.

Krok 2: proces kodowania RLE

Koder RLE skanuje strumień i identyfikuje maksymalne serie identycznych wartości. W każdym kroku zapisuje serię przed przejściem do kolejnego symbolu:

1. Pierwsza seria to 10 białych pikseli. Koder zapisuje parę (10, B).
2. Następna seria to 4 białe piksele. Zapisuje (4, B).
3. Następnie seria 1 czarnego piksela. Zapisuje (1, C). Wariant podstawowy zapisuje również serie o długości 1.
4. Następnie seria 5 białych pikseli. Zapisuje (5, B).
5. Proces jest kontynuowany wiersz po wierszu aż do końca strumienia danych. Zmiana z białego na czarny albo z czarnego na biały rozpoczyna nową serię.

Krok 3: wynik i analiza

Ostateczna, zakodowana reprezentacja naszego obrazu RLE to następująca sekwencja par (licznik, wartość):

(10, B), (4, B), (1, C), (5, B), (4, B), (1, C), (5, B), (4, B), (1, C), (5, B), (5, C), (2, B), (3, C), (4, B), (1, C), (5, B), (4, B), (1, C), (5, B), (4, B), (1, C), (5, B)

Oryginalne dane miały 80 wartości, a wyjście zawiera 22 pary, czyli 44 zapisane wartości. Dla pierwszego wiersza 10 białych pikseli (BBBBBBBBBB) tworzy parę (10, B), więc 10 symboli zastępują 2 pola. Pary z kolejnych wierszy pozostają osobne, ponieważ ten przykład koduje każdy wiersz niezależnie. Dla całego obrazu daje to współczynnik kompresji:

$80 / 44 \approx 1.82:1$. Jest to współczynnik dla uproszczonego modelu pól. Większe jednolite obszary zwiększają ten współczynnik, a wynik zależy także od liczby pól sterujących i sposobu zapisu licznika.

Dekompresja RLE

Dekompresor otrzymuje sekwencję par (licznik, wartość). Dla każdej pary zapisuje wartość na wyjściu tyle razy, ile wskazuje licznik. Po przejściu po wszystkich parach powinien otrzymać 80 pikseli, czyli dokładnie długość obrazu z przykładu.

1. Odczytaj pierwszą parę: (10, B). Wyjście: "BBBBBBBBBB".
2. Odczytaj drugą parę: (4, B). Wyjście: "BBBB".
3. Odczytaj trzecią parę: (1, C). Wyjście: "C".
4. ... i tak dalej, aż do osiągnięcia końca skompresowanych danych.

Dekompresja wymaga przejścia po parach i powtórzenia wartości wskazaną liczbę razy. Ten koszt obliczeniowy pasuje do zastosowań, w których liczy się szybkie dekodowanie. Weryfikacja sumy liczników może wykryć niepełny albo uszkodzony strumień.

Najgorszy przypadek RLE

RLE jest metodą wyspecjalizowaną. Długie serie zmniejszają liczbę zapisów, natomiast dane bez powtórzeń wymagają dodatkowego licznika przy każdym symbolu. Wtedy wynik może być większy od danych wejściowych, szczególnie gdy licznik zajmuje osobne pole o stałym rozmiarze.

Przykład: ciąg znaków bez powtórzeń

Rozważmy ciąg "W Szczebrzeszynie chrząszcz brzmi w trzcinie". Podstawowy koder RLE skanuje go znak po znaku:

• Widzi 'W'. Seria 'W' ma długość 1. Musi to zakodować jako (1, W).
• Widzi ' '. Seria spacji ma długość 1. Musi to zakodować jako (1, spacja).
• Widzi 'S'. Seria 'S' ma długość 1. Koduje to jako (1, S).
• ...i tak dalej dla każdego znaku.

W tym ciągu nie ma serii identycznych znaków dłuższych niż 1. Wynik składa się więc z par (1, znak), przez co zawiera dwa pola na każdy znak i jest dłuższy od ciągu wejściowego.

Przykład pokazuje, że RLE wymaga danych z odpowiednią liczbą powtórzeń albo wariantu, który przełącza się na zapis surowych fragmentów.

Implementacje i warianty RLE

Praktyczne implementacje RLE rozszerzają podstawowy model o sposób zapisu fragmentów, dla których para licznik + wartość nie daje oszczędności. Progi przełączania zależą od rozmiaru licznika, wartości oraz narzutu nagłówka.

Flagi sterujące

Jednym z wariantów jest specjalny bajt kontrolny albo flaga. Koder wybiera zapis dla każdego segmentu danych:

• Dla serii opłacalnej w zapisie, na przykład od 3 identycznych znaków, zapisuje flagę "następna jest seria", licznik i wartość.
• Dla fragmentu bez powtórzeń zapisuje flagę "następują dane surowe", licznik bajtów i same bajty.

Ten wariant może ograniczyć rozrost danych, ponieważ serie i fragmenty surowe mają osobne reprezentacje. Przykładowo PackBits w TIFF używa sterowania dla serii i danych literalnych, a BMP definiuje warianty RLE8 i RLE4. Warianty RLE występują także w PCX.

Zastosowania

RLE występuje jako samodzielna metoda oraz jako etap większych formatów i algorytmów. W każdym zastosowaniu znaczenie licznika, wartość symbolu i sposób oznaczania końca danych określa konkretny format.

• Faksy: Zalecenia ITU-T T.4 i T.6 kodują obrazy czarno-białe za pomocą kodów długości serii, w tym jednowymiarowego kodowania Modified Huffman oraz kodowania dwuwymiarowego.
• Formaty plików obrazów: RLE i jego warianty występują między innymi w BMP (Windows Bitmap), PCX i TIFF (Tagged Image File Format).
• Etap większego algorytmu: Transformata Burrowsa-Wheelera, używana w bzip2, przestawia dane bez zmiany ich zawartości. Implementacja bzip2 wykonuje własny etap RLE przed transformacją, a po niej stosuje między innymi kodowanie move-to-front i Huffmana.

RLE jako podstawowa metoda kompresji

Kodowanie długości serii opisuje przewidywalne powtórzenia za pomocą licznika i wartości. Długie serie dają mały zapis, a dane bez powtórzeń wymagają wariantu z fragmentami surowymi. RLE pozostaje użyteczne w obrazach, faksach i jako element potoków, które łączą je z transformacjami oraz kodowaniem entropijnym.