Kódovanie dĺžkou behu

Kódovanie dĺžkou behu (po anglicky Run-Length Encoding, skratka RLE) je jeden z najjednoduchších a najstarších kompresných algoritmov. Je elegantný vo svojej jednoduchosti a skvelý na pochopenie toho, ako kompresia vôbec funguje.

Základný princíp

RLE funguje na veľmi jednoduchom nápade: ak sa rovnaká hodnota opakuje viackrát za sebou, namiesto toho, aby sme ju zapísali viackrát, zapíšeme počet opakovaní a potom samotnú hodnotu.

Príklad:

Pôvodné dáta: AAAAABBBCCDDDDDD

Skomprimované RLE: 5A3B2C6D

Algoritmus v Pythone

def rle_komprimuj(data):
    """Skomprimuje reťazec pomocou RLE."""
    if not data:
        return ""
    
    vysledok = ""
    pocet = 1
    
    for i in range(1, len(data)):
        if data[i] == data[i - 1]:
            pocet += 1
        else:
            vysledok += str(pocet) + data[i - 1]
            pocet = 1
    
    vysledok += str(pocet) + data[-1]
    return vysledok


def rle_dekomprimuj(data):
    """Dekomprimuje RLE reťazec späť na originál."""
    vysledok = ""
    i = 0
    while i < len(data) - 1:
        pocet = int(data[i])
        znak = data[i + 1]
        vysledok += znak * pocet
        i += 2
    return vysledok


# Test
original = "AAAAABBBCCDDDDDD"
komprimovane = rle_komprimuj(original)
dekomprimovane = rle_dekomprimuj(komprimovane)

print(f"Originál:       {original} ({len(original)} znakov)")
print(f"Skomprimované:  {komprimovane} ({len(komprimovane)} znakov)")
print(f"Dekomprimované: {dekomprimovane}")
print(f"Zhoda: {original == dekomprimovane}")

Kedy RLE funguje dobre?

RLE je efektívny, keď sa dáta skladajú z dlhých opakujúcich sa sekvencií:

• Čiernobiele obrázky (dlhé behy bielych alebo čiernych pixelov)
• Jednoduché grafické ikony a logá
• Faxové dokumenty (biely papier s čiernym textom)

RLE je neefektívny (môže dokonca zväčšiť súbor), keď sa každý prvok líši:

• Fotografie s rôznofarebným pozadím
• Náhodné dáta
• Zašifrované súbory

RLE v praxi — formát BMP

Formát BMP (bitmapové obrázky Windows) voliteľne podporuje RLE kompresiu. Pre 8-bitové obrázky s veľkými plochami rovnakej farby to môže znížiť veľkosť súboru o desiatky percent.

Príklad z reálneho sveta: fax

Faxové zariadenia historicky používali RLE kompresiu. Typická stránka dokumentu obsahuje najmä biely papier s čiernymi znakmi — dlhé behy bielych pixelov sa komprimujú veľmi efektívne.