Algorytmy » Kompresja

Run Lenght Encoding (RLE)

Kodowanie RLE jest stosowane do kompresji danych, w których pod rząd występuje wiele takich samych znaków (np. jednolite powierzchnie w plikach graficznych bmp).

Przyjrzyjmy się takiemu ciągowi znaków:
AAABBAAAACCAAAAAAABBBBBCCCCC

W skrócie można to zapisać tak:
3A2B4A2C7A5B5C
(czyli 3 litery A, potem 2 razy B, następnie 4 A…)

Z 28 znaków udało nam się zmniejszyć ilość potrzebnego miejsca do 14. Całkiem nieźle. Jedynie połowa pierwotnego rozmiaru.

Ale to jest bardzo optymistyczna wersja. Zwykle nie mamy tyle szczęścia i często występują pojedyncze znaki po sobie np. tak:
AAABAABCABACCCABBAAAACCCAACC

Jeżeli mielibyśmy to zapisać w taki sam sposób jak ostatnio to wyglądałoby to tak:
3A1B2A1B1C1A1B1A3C1A2B4A3C2A2C
30 znaków zamiast 28. Coś słabo z tą naszą kompresją. Więc może kodować tylko te ciągi, które mają więcej niż 2 takie same znaki? Spróbujmy:
3ABAABCABA3CABB4A3CAACC

Teraz mamy 23 znaki zamiast 28. Już lepiej. Ale jest problem: skąd będziemy wiedzieli, kiedy mamy do czynienia z liczbą znaków do wstawienia, a kiedy z pojedynczym symbolem? W tym momencie przychodzi nam z pomocą tzw. escape sequence (np. zapisując w C printf(„Ala ma kota\\n”) to \\n nazywa się escape sequence. Mówi nam, że to n to nie litera tylko koniec linii). Musimy wybrać sobie jakiś znacznik, który będzie nam mówił, że w tym miejscu znajduje się liczba znaków, a za nią kod znaku, który trzeba powtórzyć.

Weźmy sobie np. znak Q jako ten znacznik:
Q3ABAABCABAQ3CABBQ4AQ3CAACC

Mamy, więc 28 znaków zakodowanych 27 znakach. Nie jest to rewelacja, ale np. dla plików graficznych z dużymi obszarami powtarzających się ciągów będzie lepiej.

Pojawia się jednak problem. Co zrobić, jeżeli wystąpi np. Q gdzieś w pliku. Ano trzeba go zakodować tak, jakby był ciągiem. Np.
AAABBQQCCCQABBBCCCCCCCBBBBABBAAAAQQQCCC

Należałoby zakodować tak:
Q3ABBQ2QQ3CQ1QAQ3BQ7CQ4BABBQ4AQ3QQ3C

Tutaj akurat Q występuje dosyć często. Zwykle wybiera się taki symbol, który występuj najrzadziej w tekście.

Oczywiście przedstawiony tutaj sposób można użyć dla dowolnych danych. Przede wszystkim do danych binarnych się on nadaje. Teoretycznie można kodować nawet poszczególne bity: ciągi 0 i 1 (choć to już lekka przesada).

Algorytm kodowania:
1. Znajdź najrzadziej występujący znak i zapisz go (ew. z góry można założyć jakiś kod).
2. Odczytuj po kolei ciągi takich samych znaków.
  a) Jeżeli znakiem jest nasz znacznik, to zapisz ciąg: znacznik, liczba wystąpień, znak
  b) Jeżeli długość ciągu jest krótsza niż 3 znaki to zapisz cały ciąg.
  c) Jeżeli długość ciągu jest dłuższa niż 2 znaki to zapisz w postaci: znacznik, liczba wystąpień, znak
3. Powtarzaj punkt 2, aż dojdziesz do końca pliku

Algorytm dekodowania:
1. Odczytaj znacznik (ew., jeżeli ustalony to może być na stałe w programie zakodowany).
2. Odczytaj znak.
  a) Jeżeli jest to znacznik, to odczytaj następną liczbę (n) oraz kolejny znak (c) i zapisz n razy znak c.
  b) Jeżeli jest to zwykły znak, to zapisz go.
3. Powtarzaj punkt 2, aż dojdziesz do końca pliku.

Proste, nieprawdaż?

A to jest przykładowa implementacja:
  procedure KodujRLE(PlikZ, PlikDo: TFileStream; Znacznik: Byte);
  var
    Znak1, Znak2, Licznik: Byte;
  begin
    PlikZ.ReadBuffer(Znak1, 1);
    Licznik := 1;
    while PlikZ.Position < PlikZ.Size do
    begin
      repeat
        Inc(Licznik);
        if PlikZ.Read(Znak2, 1) = 0 then
          Break;
      until (Znak2 <> Znak1) or (Licznik>=255);
      if (Licznik > 2) or (Znak1 = Znacznik) then
      begin
        PlikDo.WriteBuffer(Znacznik, 1);
        PlikDo.WriteBuffer(Licznik, 1);
        PlikDo.WriteBuffer(Znak1, 1);
      end
      else
        PlikDo.WriteBuffer(Znak1, 1);
      Znak1 := Znak2;
      Licznik := 1;
    end;
  end;
 
  procedure DekodujRLE(PlikZ, PlikDo: TFileStream; Znacznik: Byte);
  var
    Znak, Licznik, i: Byte;
  begin
    while PlikZ.Position < PlikZ.Size do
    begin
      PlikZ.ReadBuffer(Znak, 1);
      if Znak = Znacznik then
      begin
        PlikZ.ReadBuffer(Licznik, 1);
        PlikZ.ReadBuffer(Znak, 1);
        for i := 1 to Licznik-1 do
          PlikDo.WriteBuffer(Znak, 1);
      end
      else
        PlikDo.WriteBuffer(Znak, 1);
    end;
  end;

3 komentarze

kamil9499 2014-08-08 19:19

mógłby ktoś wytłumaczyć mi krok po kroku jak kodować metodą REL ? Mam "wczytywać" każdą literkę osobno czy jak ? co potem robić ?  Wiem jak działa kompresja i dekompresja RLE ale nie mam pomysłu jak zaimplementować w Pascalu właśnie to wczytywanie. Proszę o pomoc. Nie szukam kodu tylko chce żeby mnie ktoś naprowadził na to jak to zrobic. Z góry dzieki za pomoc.  

pkotowski 2004-11-29 10:00

Metoda ze znacznikami jest calkiem niezla, lecz wydaje mi sie, ze ta zastosowana w np. formacie PCX jest wydajniejsza. Tzn. biezemy sobie jakas liczbe odpowiednio wysoka np. 192 i jesli podczas kodowania chcemy zapisać, że znak powtórzył się 15 razy to dodajemy te dwie wartości uzyskując 207 po czym liczbę tą zapisujemy a poniej znak ktory kodujemy. Podczas odczytu danych sprawdzamy:
<pseudo kod>
jesli odczytany bajt > 192 to
  ilosc powtorzen := odczytany bajt - 192
  znak = kolejny bajt
w przeciwnym wypadku
  ilosc powtorzen := 1
  znak = odczytany bajt
</pseudo kod>

Jeśli natomiast chcemy zapisac bajt o wartosci wiekszej niz 192 to ilosc powtorzen wynosci 193 a nastepnym bajtem jest znak, ktory kodujemy.

Wada algorytmu jest to, ze mozemy zakodowac w tym przypadku 255 - 192 powtorzen. Oczywiscie wartosc ta mozna sobie dobierac zaleznie od danych, ktore chcemy kodowac, ale to raczej temat na inny watek ;)
Zaleta natomiast pobycie sie znacznika, ktory za kazdym razem zajmowalby jeden bajt wiecej przy kazdym powtarzajacym sie znaku.

Oczywiscie mozna algorytm rozwinac jeszcze o zapisywanie powtarzajacyh sie ciagach znakow, ale to juz inna bajka.

TKW 2004-08-26 17:45

"\\n" to \n, a nie Line Feed (LF).