Keď sa snažíš odoslať veľký súbor e-mailom alebo ušetriť miesto na disku, použiješ kompresiu. Bezstratová kompresia zmenší súbor tak, že pri rozbalení dostaneš presne pôvodný obsah — každý bit zostane zachovaný.
Prečo komprimovať?
Nekomprimované súbory môžu byť zbytočne veľké, pretože obsahujú opakujúce sa vzory. Kompresia tieto vzory identifikuje a nahradí ich kompaktnejšou reprezentáciou.
Príklad: Text „AAAAAAAA" obsahuje 8 písmen A, ale možno ho zapísať skratkou „8A" — 2 znaky namiesto 8.
Kódovanie dĺžkou behu (Run-Length Encoding)
Najjednoduchší spôsob bezstratovej kompresie. Namiesto opakovania rovnakých hodnôt zapíšeme počet opakovaní a hodnotu.
Pôvodné dáta: BBBBBWWWBBBB
Skomprimované: 5B3W4B
def rle_compress(data):
if not data:
return []
compressed = []
count = 1
for i in range(1, len(data)):
if data[i] == data[i - 1]:
count += 1
else:
compressed.append((count, data[i - 1]))
count = 1
compressed.append((count, data[-1]))
return compressed
text = "BBBBBWWWBBBB"
vysledok = rle_compress(text)
print(vysledok) # [(5, 'B'), (3, 'W'), (4, 'B')]
RLE funguje výborne pre obrázky s veľkými plochami rovnakej farby (napr. logá, ikonky), ale nie pre fotografie, kde sa farba každého pixela líši.
Huffmanova kompresia
Pokročilejší algoritmus, ktorý častejším znakom priraďuje kratšie kódy a zriedkavejším dlhšie.
Príklad pre text „ABRACADABRA":
- A sa vyskytuje 5-krát → kód:
0(1 bit) - B sa vyskytuje 2-krát → kód:
10(2 bity) - R sa vyskytuje 2-krát → kód:
110(3 bity) - C sa vyskytuje 1-krát → kód:
1110(4 bity) - D sa vyskytuje 1-krát → kód:
1111(4 bity)
Bežné písmená zaberajú menej miesta, čím sa celkový súbor zmenší.
Huffmanova kompresia sa používa v mnohých formátoch — je súčasťou ZIP archívov, PNG obrázkov aj PDF dokumentov.
Formáty používajúce bezstratovú kompresiu
| Formát | Typ dát | Algoritmus |
|---|---|---|
| ZIP, 7z, RAR | Akékoľvek súbory | Deflate (LZ77 + Huffman) |
| PNG | Obrázky | Deflate |
| FLAC | Audio | Lineárna predikcia |
| GIF | Animácie | LZW |
Prečo „bezstratová" kompresia?
Slovo bezstratová znamená, že pri dekompresii dostaneš bit po bite identický originál. Toto je nevyhnutné pre:
- Textové súbory a kód — jediná zmenená číslica môže program pokaziť
- Medicínske snímky — žiadna informácia nesmie byť stratená
- Archívne zálohy — súbor musí byť presne obnoviteľný
Bezstratová kompresia nedosiahne tak malé súbory ako stratová. ZIP zmenší textový súbor o 60–80 %, ale fotografiu len o 10–20 %. Pre fotografie je efektívnejší JPEG (stratová kompresia).
Cvičné príklady
Použi kódovanie dĺžkou behu (RLE) na kompresiu reťazca 'WWWWWBBBWW'. Koľko znakov má pôvodný a skomprimovaný reťazec?
Zobraziť odpoveď
Prečo je bezstratová kompresia nevyhnutná pre zdrojový kód programov, ale pre fotografie môžeme použiť stratovú?