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;