Strona główna » Algorytmy » Artykuły » Kodowanie RLE
 

Kodowanie RLE

https://mattomatti.com/a0164

Kodowanie

Kodowanie RLE (ang. Run-length Encoding) to metoda bezstratnej kompresji informacji. Sprawdza się ona bardzo dobrze, gdy dane mają bardzo dużo takich samych wartości obok siebie. W przeciwnym razie kompresja nie jest zbyt skuteczna. Technika kompresji polega na zamianie wielu identycznych znaków tj. AAAA..A na parę znak i ilość wystąpień pomiędzy np. znakami średnika. Jeśli znak nie występuje obok siebie wiele razy to nie dopisuje się ile razy występuje.

Przykład

Przykładowo jest do zakodowania tekst "AAAAAAA1111123". Używając kompresji RLE otrzymany wynik to będzie "A;7;1;5;23". Teraz, żeby rozkodować dane należałoby przeglądać wszystkie znaki po kolei i jeśli po znaku występuje średnik to znaleźć następny, odczytać liczbę pomiędzy nimi i tyle razy powielić znak.

Wady i zalety

Niewątpliwą zaletą jest fakt, że dla ciągu złożonego z co najmniej czterech znaków kompresja jest tym skuteczniejsza im więcej znaków. Niestety kodując fragmenty danych złożone z dwóch lub czterech bajtów wydłużają dane wynikowe odpowiednio o 100% i 50%. Z tego powodu tego typu kompresja nie znajduje zbyt szerokiego zastosowania, ale kiedyś była powszechnie stosowana do zmniejszania rozmiarów obrazków złożonych z 16 kolorów.

Przykładowo poniższe dane nie zostaną skompresowane, a znacząco powiększą ich rozmiar: "AABBCC" to "A;2;B;2;C;2;". Tekst wynikowy jest dwa razy dłuższy, ale oczywiście po dekompresji otrzymany by został tekst wejściowy.

Implementacja

Kodowanie

Funkcja kodujRLE() przyjmuje jeden argument dane - czyli wartości przeznaczone do kompresji. Jako wynik otrzymuje się dane zapisane jako tekst.

  1. string kodujRLE(string dane) {
  2.   string wynik = "";
  3.   int licznik = 0;
  4.   char c = dane[0];
  5.   for (int i = 0; i < dane.size(); i++) {
  6.     if (dane[i] == c) {
  7.       licznik++;
  8.     } else {
  9.       dopisz(wynik, c, licznik);
  10.       c = dane[i];
  11.       licznik = 1;
  12.     }
  13.   }
  14.   dopisz(wynik, c, licznik);
  15.   return wynik;
  16. }

Działanie algorytmu polega na przejrzeniu wszystkich znaków po kolei. Początkowo licznik jest ustawiony na 0, a ostatnio wybrany znak przyjmujemy, że był taki jak pierwszy w danych. W pętli sprawdzamy czy i-ty znak jest taki sam jak poprzedni jest tak to zwiększamy licznik. Jednak jeśli nie to dopisujemy odpowiednie dane do wyniku, a następnie zmieniamy ostatni znak i resetujemy licznik. Po zakończeniu pętli należy dopisać odczytane, ale nie dopisane dane.

Dopisywanie danych odbywa się poprzez przekazanie aktualnego wyniku, ostatniego znaku oraz licznika do metody dopisz():

  1. void dopisz(string &str, char c, int licznik) {
  2.   if (licznik > 0) {
  3.     str += c;
  4.     if (licznik > 1) {
  5.       str += ";" + to_string(licznik) + ";";
  6.     }
  7.   }
  8. }

Funkcja ta rozróżnia dwa przypadki zapisu: pojedynczego znaku oraz, gdy znak występuje więcej niż jeden raz.

Dekodowanie

Funkcja dekodujRLE() dla pewnych wartości przekazanych w dane zwraca skompresowane dane.

  1. string dekodujRLE(string dane) {
  2.   string wynik = "";
  3.   for (int i = 0; i < dane.size(); i++) {
  4.     if (dane[i] == ';') {
  5.       i++;
  6.       int a = 0;
  7.       while (dane[i] != ';') {
  8.         a = a*10 + dane[i] - '0';
  9.         i++;
  10.       }
  11.       while (a-- > 1) {
  12.         wynik += wynik[wynik.length() - 1];
  13.       }
  14.     } else {
  15.       wynik += dane[i];
  16.     }
  17.   }
  18.   return wynik;
  19. }

W pętli, dopóki nie zostanie napotkany średnik wszystkie znaki są dopisywane do wyniku. Jeśli w tekście zostanie odnaleziony średnik to odczytywana jest wartość pomiędzy nim, a następnym. Po odczytaniu wartości ostatni znak jest powielany a - 1 razy, ponieważ raz już został dopisany.

Testowanie funkcji

Do przetestowania kodu można skorzystać z poniższego fragmentu kodu, który wczyta dane, a następnie dokona ich kompresji:

  1. int main () {
  2.   string dane;
  3.   cout << "Podaj dane do kompresji:\n";
  4.   getline(cin, dane);
  5.   string zakodowane = kodujRLE(dane);
  6.   cout << "Po kompresji:\n" << zakodowane;
  7.   string dekodowane = dekodujRLE(zakodowane);
  8.   cout << "\nPo dekodowaniu:\n" << dekodowane;
  9.   system("pause");
  10.   return 0;
  11. }

Zadania

Zadanie 1

Napisz kod, który dokona kompresji danych według następujących warunków: każdy ciąg takich samych znaków jest zamieniany na parę (znak, liczba wystąpień). Przyjmujemy, że liczba wystąpień to zawsze wartość z przedziału od 1 do 9. Ciągi o długości dłuższej niż 9 są dzielone na mniejsze. Przykładowo "AAAAAAAAAAAAAB" należałoby zapisać jako "A9A4B1". Napisz również dekoder dla skompresowanych danych i przetestuj działanie programu.