Kompresja RLE: kodowanie długości serii

Kompresja bezstratna zmniejsza dane tak, żeby dało się je odtworzyć co do znaku. Najprostsza metoda to RLE (kodowanie długości serii): serię jednakowych znaków zastępuje liczba powtórzeń i znak, więc AAAABBBCC staje się 4A3B2C. Dekodowanie odwraca ten zapis.

Każdy przykład przejdziesz krok po kroku w kursie Algorytmy: zakres rozszerzony: w przeglądarce, bez instalowania niczego i bez konta.

Przejdź kodowanie RLE krok po kroku

Kodowanie RLE

Licznik count mówi, ile razy powtórzył się bieżący znak. Gdy następny znak jest inny (albo napis się skończył), seria trafia do wyniku:

def rle_encode(text):
    result = ""
    count = 1
    for i in range(1, len(text) + 1):
        if i < len(text) and text[i] == text[i - 1]:
            count += 1
        else:
            result += str(count) + text[i - 1]
            count = 1
    return result


for text in ["AAAABBBCC", "WWWWWWWWWWWWB", "ABC"]:
    code = rle_encode(text)
    print(text, code, round(len(code) / len(text), 2))

AAAABBBCC 4A3B2C 0.67
WWWWWWWWWWWWB 12W1B 0.38
ABC 1A1B1C 2.0

Ostatnia kolumna to stopień kompresji: dla ABC zakodowany napis jest dwa razy dłuższy. RLE opłaca się tylko przy długich seriach.

Dekodowanie RLE

Liczba powtórzeń może mieć kilka cyfr (12W), więc cyfry trzeba składać w liczbę, aż pojawi się znak:

def rle_decode(code):
    result = ""
    count = 0
    for c in code:
        if c.isdigit():
            count = count * 10 + int(c)
        else:
            result += c * count
            count = 0
    return result


print(rle_decode("4A3B2C"))
print(rle_decode("12W1B"))
print(rle_decode("24B1A"))

AAAABBBCC
WWWWWWWWWWWWB
BBBBBBBBBBBBBBBBBBBBBBBBA

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Kodowanie RLE

Specyfikacja. Dane: niepusty napis s z liter (bez cyfr). Wynik: napis zakodowany RLE: przed każdą serią jednakowych znaków jej długość.

Lista kroków:

1. Wczytaj napis s. Ustaw wynik w jako pusty napis i długość bieżącej serii k = 1.
2. Dla i = 2, 3, …, długość(s) + 1 wykonaj krok 3.
3. Jeśli znak s[i] istnieje i jest taki sam jak s[i - 1], seria trwa: zwiększ k o 1. W przeciwnym razie seria się skończyła: dopisz do w liczbę k i znak s[i - 1], ustaw k = 1.
4. Wypisz w.

Pseudokod:

wczytaj s
w ← ""
k ← 1
dla i = 2, 3, ..., długość(s) + 1 wykonuj
  jeżeli i ≤ długość(s) i s[i] = s[i - 1] to
    k ← k + 1
  w przeciwnym razie
    w ← w + napis(k) + s[i - 1]
    k ← 1
wypisz w

Schemat blokowy:

Dekodowanie RLE

Specyfikacja. Dane: napis zakodowany RLE (liczba, potem znak). Wynik: napis odkodowany.

Lista kroków:

1. Wczytaj napis s. Ustaw wynik w jako pusty napis i liczbę powtórzeń k = 0.
2. Dla kolejnych znaków c napisu s wykonaj krok 3.
3. Jeśli c jest cyfrą, dopisz ją do liczby k: k = 10 · k + cyfra (liczby mogą mieć kilka cyfr). W przeciwnym razie dopisz do w znak c powtórzony k razy i ustaw k = 0.
4. Wypisz w.

Pseudokod:

wczytaj s
w ← ""
k ← 0
dla i = 1, 2, ..., długość(s) wykonuj
  c ← s[i]
  jeżeli c ≥ "0" i c ≤ "9" to
    k ← k * 10 + kod(c) - kod("0")
  w przeciwnym razie
    w ← w + powtórz(c, k)
    k ← 0
wypisz w

Schemat blokowy:

Najczęstsze błędy

• Zgubiona ostatnia seria. Seria trafia do wyniku dopiero przy zmianie znaku, a po ostatnim znaku zmiany nie ma. Pętla musi obsłużyć koniec napisu.
• Jedna cyfra liczby powtórzeń. Dekodowanie int(code[i]) psuje serie dłuższe niż 9 znaków. Składaj liczbę z kolejnych cyfr.
• Cyfry w danych. Napis 11122 zakodowany jako 312 jest niejednoznaczny. RLE w tej postaci działa tylko dla danych bez cyfr.
• Licznik nie wyzerowany. Po zakończeniu serii licznik wraca do 1 przy kodowaniu i do 0 przy dekodowaniu.

Ćwicz w przeglądarce

W temacie o kompresji kursu Algorytmy: zakres rozszerzony:

• dekodowanie RLE,
• kiedy RLE się nie opłaca,
• kompresja wiersza obrazka,
• stopień kompresji.

Przycisk Algorytm przy tych lekcjach pokazuje listę kroków, pseudokod i schemat blokowy. Pełna lista: algorytmy.

Dla nauczycieli

RLE łączy programowanie z tematem reprezentacji danych: uczniowie kodują wiersze prostego obrazka i liczą, ile miejsca oszczędzają. W BitWizards przydzielasz kurs klasie i widzisz przebieg pisania kodu każdego ucznia. Platforma jest darmowa dla szkół - jak zacząć.