🧠 Kompresné algoritmy v Pythone

Prečo komprimujeme?

Kompresia zmenší množstvo dát potrebných na uloženie alebo prenos.

AAAAAAAAAABBBBBBCCCCCCCC

Obsahuje veľa opakovaní, preto sa dá dobre komprimovať.

Q7mK2pL9xR4aT8zW

Náhodné dáta sa komprimujú oveľa horšie.

Viac: Kompresia dát

Bezstratová a stratová kompresia

Typ Príklady Po dekompresii
Bezstratová ZIP, PNG, FLAC dáta sú úplne rovnaké
Stratová JPEG, MP3, MPEG dáta sú mierne zmenené

Bezstratovú kompresiu použijeme napríklad pri zdrojovom kóde, dokumentoch alebo databázach.

Viac: Bezstratová kompresia, Stratová kompresia

Pomer kompresie

pomer = komprimovaná veľkosť / pôvodná veľkosť
úspora = 1 - pomer

Príklad:

pôvodný súbor:       1000 B
komprimovaný súbor:   600 B
úspora:                40 %

Keď kompresia nepomôže

Kompresia nemusí byť vždy úspešná. Pri krátkych alebo náhodných dátach môže výsledok narásť:

ABCD → 1A1B1C1D

Kompresor musí uložiť aj informáciu o opakovaní, takže pri malom vstupe môže réžia prevážiť úsporu.

Viac: Kompresia dát

📦 RLE – Run Length Encoding

RLE nahrádza súvislé opakovanie dvojicou (počet, znak).

AAAABBBAAC
 4A   3B  2A 1C

Výsledok:

4A3B2A1C

Viac: Run-length encoding

Kedy sa hodí RLE?

RLE funguje dobre pri obrázkoch s veľkými jednofarebnými plochami alebo pri podobných opakujúcich sa dátach.

Pri dátach bez dlhých behov opakujúcich sa znakov môže byť výsledok väčší než originál.

Príklady použitia sa nachádzajú v jednoduchých obrazových a bitmapových formátoch.

Viac: Run-length encoding

RLE v Pythone: kódovanie

def rle_encode(data: str) -> list[tuple[int, str]]:
    if not data:
        return []

    result = []
    count = 1

    for current, previous in zip(data[1:], data):
        if current == previous:
            count += 1
        else:
            result.append((count, previous))
            count = 1

    result.append((count, data[-1]))
    return result

RLE v Pythone: výsledok

print(rle_encode("AAAABBBAAC"))
# [(4, 'A'), (3, 'B'), (2, 'A'), (1, 'C')]

Formát (počet, znak) je jednoznačnejší než textový zápis 4A3B2A1C, najmä ak sa v dátach nachádzajú číslice.

📚 LZ77 – posuvné okno

LZ77 hľadá opakovanie v nedávno spracovanej časti textu.

ABC | ABCABC
    └─ zhoda sa nachádza 3 znaky dozadu

Opakovanie môže zapísať ako token:

(vzdialenosť, dĺžka, ďalší znak)
(3, 6, "")

Viac: LZ77

LZ77 – ako čítať token

Token (3, 6, "") znamená:

  • vráť sa o 3 znaky,
  • skopíruj 6 znakov,
  • potom nepridaj žiadny nový znak.

Takto sa opakujúca sekvencia uloží kratšie než jej opätovným zapísaním.

LZ77 – jednoduchý príklad

text = "ABABABA"

# Jeden z možných výstupov:
tokens = [(0, 0, "A"),
          (0, 0, "B"),
          (2, 5, "")]

Dekóder postupne kopíruje znaky z už vytvoreného výsledku.

LZ77 a DEFLATE

LZ77 je základom algoritmu DEFLATE, ktorý používajú napríklad ZIP a GZIP.

DEFLATE kombinuje vyhľadávanie opakovaní s Huffmanovým kódovaním.

Viac: DEFLATE

📖 LZ78 – slovník fráz

LZ78 buduje slovník už nájdených fráz a zapisuje dvojicu:

(index slovníka, nový znak)

Opakované frázy sa nahrádzajú indexmi.

Viac: LZ78

LZ78 – príklad slovníka

Pre text ABAABABAABAB môže slovník vyzerať napríklad takto:

Index Fráza
1 A
2 B
3 AA
4 ABA
5 AB

LZW – slovník a číselné kódy

LZW začína slovníkom jednotlivých znakov a postupne pridáva dlhšie frázy.

počiatočný slovník: A, B, C, ...
nové položky:       AB, BA, ABA, ...
výstup:             65, 66, 256, ...

Viac: LZW

LZW v Pythone: kódovanie

def lzw_encode(data: str) -> list[int]:
    dictionary = {chr(i): i for i in range(256)}
    phrase = ""
    result = []
    next_code = 256

    for char in data:
        candidate = phrase + char
        if candidate in dictionary:
            phrase = candidate
        else:
            result.append(dictionary[phrase])
            dictionary[candidate] = next_code
            next_code += 1
            phrase = char

LZW v Pythone: dokončenie funkcie

    if phrase:
        result.append(dictionary[phrase])
    return result

Používal sa napríklad vo formáte GIF a v starších implementáciách PDF.

Viac: LZW, GIF

Porovnanie algoritmov

Algoritmus Hlavná myšlienka Kedy sa hodí
RLE počty opakovaných znakov jednoduché, opakujúce sa dáta
LZ77 posuvné okno opakujúce sa texty a súbory
LZ78 slovník fráz slovníková kompresia
LZW slovník a číselné kódy GIF, historické formáty

Všetky uvedené algoritmy sú bezstratové.

Kde sa s nimi stretneme?

  • ZIP, GZIP – LZ77/DEFLATE a ďalšie techniky,
  • PNG – bezstratová kompresia obrazu,
  • GIF – LZW,
  • JPEG – stratová kompresia obrazu,
  • FLAC – bezstratová kompresia zvuku,
  • Brotli a Zstandard – moderná kompresia dát a webu.

Viac: ZIP, PNG, JPEG, FLAC, Brotli, Zstandard

Formát nie je iba jeden algoritmus

Samotný algoritmus často nie je celý formát.

Reálne formáty kombinujú viac techník, napríklad:

  • hľadanie opakovaní,
  • slovníkové kódovanie,
  • Huffmanovo kódovanie,
  • hlavičku a kontrolné súčty.

Praktická ukážka: GZIP v Pythone

import gzip

text = "Python je programovací jazyk. " * 1000
data = text.encode("utf-8")
compressed = gzip.compress(data)
restored = gzip.decompress(compressed)

Viac: Gzip

Praktická ukážka: vyhodnotenie

print("Pôvodná veľkosť:", len(data), "B")
print("Komprimovaná veľkosť:", len(compressed), "B")
print("Úspora:", round(100 * (1 - len(compressed) / len(data)), 1), "%")
print("Obnovené dáta sú rovnaké:", restored == data)

Výsledok ukáže veľkosť pred kompresiou, po kompresii, percentuálnu úsporu a overenie bezstratovosti.

Praktická úloha: porovnanie vstupov

Porovnaj tri typy vstupu:

samples = {
    "opakovaný text": "ABC" * 1000,
    "bežný text": "Python je programovací jazyk. " * 200,
    "krátky text": "Q7mK2pL9xR4aT8zW",
}

Pre každý vstup zmeraj pôvodnú veľkosť, veľkosť po gzip, percentuálnu úsporu a over, či sa dáta po dekompresii rovnajú pôvodným dátam.

Praktická úloha: otázka

Ktorý vstup sa komprimoval najlepšie a prečo?

Pri odpovedi porovnaj najmä množstvo opakovaní, dĺžku vstupu a réžiu kompresného formátu.

Viac: Gzip, Bezstratová kompresia

Na čo si dať pozor pri implementácii?

  • RLE textový zápis môže byť nejednoznačný pri čísliciach.
  • Pri reálnych súboroch meriame bajty, nie počet znakov.
  • LZW verzia so slovníkom 0–255 predpokladá bajtové dáta.
  • Treba ošetriť prázdny vstup.
  • Komprimácia môže pri krátkych alebo náhodných dátach zväčšiť výsledok.

🧾 Zhrnutie

  • Kompresia využíva opakovanie a pravidelnosti v dátach.
  • Bezstratová kompresia umožňuje presnú obnovu pôvodných dát.
  • RLE je jednoduché, LZ77 používa posuvné okno a LZ78/LZW slovník.
  • Reálne formáty zvyčajne kombinujú viac algoritmov.
  • Najlepšia metóda závisí od typu vstupných dát.

Zdroje

Reload?