Run-length encoding (RLE)

Čo sa v cvičení naučíte

Po vyriešení cvičenia budete vedieť:

• vysvetliť princíp bezstratovej kompresie pomocou dĺžok opakujúcich sa údajov,
• rozdeliť vstup na skupiny po sebe idúcich rovnakých bajtov,
• implementovať kódovanie aj dekódovanie vlastného binárneho formátu,
• pracovať s objektmi bytes a bytearray,
• rozlíšiť hodnotu bajtu od jednoprvkového objektu bytes,
• spracovať aj nulové bajty, číslice, dvojbodky, medzery a ľubovoľné ďalšie binárne údaje,
• overiť, že dekódovanie zakódovaných údajov vráti pôvodný vstup,
• používať testy ako presnú špecifikáciu požadovaného správania.

Čo si musíte preštudovať

Pred riešením si zopakujte najmä tieto témy:

• definovanie funkcií, parametre a návratová hodnota,
• cykly while a podmienky if,
• indexovanie a rezanie sekvencií,
• funkcie len() a metódu .find(),
• prevod desiatkového čísla na text pomocou str() a prevod textu na číslo pomocou int(),
• kódovanie textu na bajty pomocou .encode("ascii"),
• rozdiel medzi str, bytes a bytearray,
• násobenie sekvencií, napríklad b"A" * 3,
• výnimku ValueError a základné spracovanie neplatného formátu,
• vlastnosti bezstratovej kompresie a situácie, v ktorých môže byť RLE väčšie než pôvodné údaje.

Užitočné kapitoly v oficiálnom Python manuáli:

• Python Tutorial – úvod do jazyka,
• definovanie funkcií,
• príkaz while,
• príkaz if,
• vstavané funkcie len(), int() a str(),
• typ bytes,
• typ bytearray,
• operácie spoločné pre sekvencie,
• metódy bytes, vrátane .find(),
• metóda str.encode(),
• výnimky a try/except,
• vstavaná výnimka ValueError.

Porozumejte zadaniu

V súbore run_length_encoding.py máte doplniť funkcie:

def encode(data):
    ...

def decode(data):
    ...

Obe funkcie prijímajú aj vracajú objekt bytes. Nepracujte preto s textovým reťazcom str a nepredpokladajte, že vstup obsahuje iba písmená. Vstup môže obsahovať všetkých 256 možných hodnôt bajtu.

Každá skupina rovnakých po sebe idúcich bajtov sa zapíše v tvare:

počet:bajt

Počet je desiatkové číslo, za ním nasleduje dvojbodka a presne jeden pôvodný bajt. Zakódujte aj skupiny s dĺžkou 1.

Napríklad:

b"AABCCCDEEEE" -> b"2:A1:B3:C1:D4:E"

Dekódovanie musí tento zápis prejsť opačným smerom:

b"2:A1:B3:C1:D4:E" -> b"AABCCCDEEEE"

Dvojbodka oddeľuje počet od bajtu, ale dvojbodka v pôvodných údajoch nie je problém. Napríklad pôvodné b":::" sa zakóduje ako b"3::". Rovnako sa nesmie zamieňať znak b"1" s počtom 1 v zakódovanom formáte.

Ako implementovať encode

Prechádzajte vstup zľava doprava. Na začiatku skupiny si zapamätajte jej pozíciu. Potom posúvajte koniec skupiny dovtedy, kým sa nasledujúci bajt rovná prvému bajtu skupiny alebo kým nedosiahnete koniec vstupu.

Pre skupinu od indexu start po index end:

1. počet opakovaní je end - start,
2. počet preveďte na ASCII bajty,
3. pridajte dvojbodku,
4. pridajte prvý bajt skupiny,
5. pokračujte od indexu end.

Na skladanie výsledku je vhodný bytearray, pretože doň môžete postupne pridávať časti pomocou .extend(). Na konci ho preveďte na bytes.

Pri práci s bytes si všimnite dôležitý rozdiel:

data[0]       # celé číslo, napríklad 65
data[0:1]     # bytes, napríklad b"A"

Pri porovnávaní bajtov môže byť užitočné indexovanie. Pri pridávaní jedného bajtu do výsledku je praktické použiť rez data[start:start + 1].

Prázdny vstup nemá žiadne skupiny, preto výsledkom kódovania musí byť b"".

Ako implementovať decode

Dekodér číta zakódované údaje po jednotlivých skupinách. Od aktuálnej pozície:

1. nájdite najbližšiu dvojbodku,
2. časť pred dvojbodkou preveďte na celé číslo,
3. prečítajte presne jeden bajt za dvojbodkou,
4. tento bajt pridajte do výsledku toľkokrát, koľko určuje počet,
5. posuňte pozíciu za práve spracovaný bajt.

Pri platnom vstupe musí byť počet kladný a za každou dvojbodkou musí byť jeden bajt. Ak sa rozhodnete kontrolovať neplatný vstup, môžete pri jeho zistení vyvolať ValueError. Dôležité je, aby ste pri dekódovaní nepoužívali samotnú dvojbodku ako súčasť pôvodných dát — slúži iba ako oddeľovač.

Odporúčaný postup

1. Prečítajte si celé zadanie v .docs/instructions.md aj pripravené testy.
2. Najprv vyriešte encode pre prázdny vstup, jednu skupinu a viac skupín.
3. Potom implementujte decode pre rovnaké príklady.
4. Overte vlastnosť decode(encode(data)) == data.
5. Otestujte vstupy s číslicami, dvojbodkami, medzerami, b"\x00" a hodnotou 255 (b"\xff").
6. Spustite automatické testy a skontrolujte, že funkcie nič nevypisujú, ale výsledok vracajú pomocou return.

RLE je bezstratové: pri správnej implementácii sa pôvodné údaje dajú úplne obnoviť. Nie každý vstup však zmenší. Ak sa rovnaké bajty často nestriedajú, počet a dvojbodka môžu vytvorený zápis dokonca predĺžiť.

Kontrolné príklady

encode(b"")
# b""

encode(b"XYZ")
# b"1:X1:Y1:Z"

encode(b"AABBBCCCC")
# b"2:A3:B4:C"

decode(b"2:A3:B4:C")
# b"AABBBCCCC"

data = bytes(range(256)) + b"\x00\x00\xff\xff"
decode(encode(data)) == data
# True

Ďalšie úlohy na precvičenie

• Run-Length Encoding na Exercisme,
• Atbash Cipher,
• Rail Fence Cipher.

Previous Post Next Post