Komprese

Obsah [skrýt] 1 Definice 2 Pojmy 3 Rozdělení kompresních metod 3.1 Ztrátové × bezeztrátové 3.2 Statistické × slovníkové metody 3.3 Statické × dynamické metody 4 Příklady metod

Definice

• Kompresní metody: Postupy, vedoucí ke snížení objemu dat při zachování podstatné informace.

Pojmy

• Kompresní poměr
  • Poměr velikosti původních dat a velikosti zkomprimovaných dat.
  • Závisí na konkrétních datech, která komprimujeme.

• Entropie
  • Množství podstatné informace obsažené v datech.
  • Velikost dat při použití ideálního kompresního algoritmu bezeztrátové komprese.

Rozdělení kompresních metod

Ztrátové × bezeztrátové

• Ztrátové typicky u videa, audia, obrázků a dalších dat, která jsou již sama zatížena chybou.
• Ztrátové mohou docílit výrazně vyššího kompresního poměru za cenu dílčího poškození (zhoršení kvality) komprimovaných dat.

Statistické × slovníkové metody

Statistické metody

• Nahrazují jednotlivé hodnoty symbolů posloupností bitů.
• Můžeme si představit třeba tabulku: E => 01, A => 100, T => 101,...
• Vychází z toho, že pravděpodobnost výskytu znaků se dá spočítat a není stejná.
• Pro běžná počítačová data malý kompresní poměr, jsou spíše součástí jiných metod.

Slovníkové metody

• Nahrazují celé posloupnosti symbolů (slova) za posloupnosti bitů.
• Převodní tabulka je větší, ale můžeme docílit lepšího kompresního poměru.
• Do této skupiny patří většina běžně používaných metod.

Statické × dynamické metody

Statické metody

• Po celou dobu komprese datového souboru se převodní tabulka nemění.
• Většinou se převodní tabulka musí přiložit k souboru.
• Často je třeba nejprve předzpracovat statistiku výskytu znaků.

Dynamické metody

• Upravují převodní tabulku v průběhu komprese.

Příklady metod

LZ 77

• Používá kompresní program ZIP a odvozené.
• Bezeztrátová slovníková metoda
• Autoři Lempel a Ziv, Izrael, 1977.

LZ 78

• Tvoří základ algoritmů programů RAR a GZIP
• Autoři Lempel a Ziv, Izrael, 1978.