Bezeztrátová komprese

[zapotocnylubos]

RLE (Run-Length Encoding)

Nejjednodušší kompresní metoda – kódování sekvencí opakujících se hodnot.

• Komprese obrázků s velkými jednobarevnými plochami
• Fax standard (CCITT)
• Základ pro pochopení principu redundance

Entropie a informace

Matematický základ komprese – kolik informace data skutečně nesou.

• Shannonova entropie
• Optimální délka kódu
• Proč nelze komprimovat donekonečna

Huffmanovo kódování

Optimální prefix kódy na základě frekvence symbolů.

• Komprese textu
• Součást JPEG, MP3, ZIP
• Stavba Huffmanova stromu

Aritmetické kódování

Kódování celé zprávy jako jediného čísla na základě pravděpodobností.

• Lepší kompresní poměr než Huffman
• Základ moderních kompresních algoritmů
• JPEG 2000, HEIF

LZ77 / LZ78

Slovníkové metody – nahrazování opakujících se sekvencí referencemi.

• LZ77: základ GZip, ZIP, PNG
• LZ78: základ LZW (GIF, TIFF)
• Komprese souborů obecně

LZW (Lempel-Ziv-Welch)

Rozšíření LZ78 s dynamicky budovaným slovníkem.

• GIF, TIFF formáty
• Historicky důležitý (patentové spory)

Burrows-Wheeler Transform (BWT)

Předzpracování dat pro lepší kompresovatelnost.

• Základ bzip2
• Využití v bioinformatice (komprese DNA sekvencí)