Domů » Informatika » Kódování » Komprese dat

Komprese dat

Lidé mají odvěkou touhu získávat a shromažďovat informace. To není v informační době problém. Co je omezené, je kapacita médií a úložišť. Proto vznikaly a stále vznikají různé metody, jak na nich ušetřit místo a mít tak prostor pro další data. Také kapacitou přenosových kanálů se musí nakládat ekonomicky a každá možnost, jak jimi protlačit více informací za časovou jednotku, přijde telekomunikačním společnostem vhod. Právě komprese umožnila vznik a rychlý rozvoj technologií pro vzdálený přenos obrazu či videa.

Komprese je speciální druh kódování dat za účelem zmenšení jejich objemu odstraněním nadbytečné informace (redundance). Kompresní algoritmus definuje přesný postup, jak toho docílit. Musí obsahovat i odpovídající opačný postup pro dekompresi, který původní informaci zpětně zrekonstruuje. Kompresní algoritmus převádí zdrojové jednotky (symboly a posloupnosti symbolů – tzv. slova a posloupnosti slov) na posloupnosti bitů. Zdrojové jednotky se mohou označovat jako vzory (originály) a výsledné posloupnosti jako obrazy.

Princip komprese

Komprese je založená na odstraňování nadbytečnosti (redundance), která je způsobena především:

  • opakováním symbolů
  • opakováním slov či frází z těchto symbolů složených
  • kontextovou závislostí (např. v angličtině následuje za Q většinou U)
  • neefektivní přímou reprezentací
  • nejednotným rozložením symbolů v textu

Obecným principem komprese je přiřazení krátkých kódů častým symbolům a delších kódů symbolům vzácnějším.

Druhy komprese

Ztrátová komprese

Ztrátová komprese využívá nedokonalosti lidských smyslů. Je pouhou aproximací originálu – z informace odstraňuje detaily do té míry, dokud ji ještě lze uspokojivě rekonstruovat. Tento způsob komprese se nejčastěji používá pro hudbu, video a obrázky. Příklady: JPEG, H.264, MPEG.

Bezeztrátová komprese

Bezeztrátová komprese, jak již název napovídá, zachovává vždy kompletní informaci. Dekomprimovaná data jsou identická originálu. Příklady: LZ77, LZ78, LZW, Huffmanovo kódování.

Další vlastnosti komprese

  • symetrická – asymptotická složitost komprese i dekomprese je podobná
  • asymetrická – asymptotická složitost komprese a dekomprese se od sebe významně liší (např. komprese trvá mnohem delší dobu)
  • kaskádová – komprese je založená na postupném skládání funkcí, dekomprese probíhá v opačném pořadí s opačnými funkcemi
  • proudová – na vstup kompresního algoritmu přichází jednotlivé symboly, výstup je vytvářen po symbolech
  • bloková – na vstup kompresního algorimu přichází celý blok dat, výstup je vytvářen po blocích
  • statická – model kompresního algoritmu se v čase nemění, je přesně dán v okamžiku implementace aplikace
  • semiadaptivní – komprese má dva průchody: při prvním se projdou celá vstupní data a upraví se model kompresního algoritmu, při druhém průchodu se komprimuje
  • adaptivní – kódy se připraví až na základě dat a proto se musí pokaždé přenést tabulka znaků
  • lokálně adaptivní – např. metoda „move to front“

Kompresní algoritmy

Statistické metody

Statistické metody komprese jsou založené na pravděpodobnosti výskytu jednotlivých symbolů.

Slovníkové metody

Slovníkové metody jako svůj model používají slovník – speciální dynamickou datovou strukturu, které se postupně vytváří během čtení vstupu.

  • Algoritmus LZ77
    • varianta LZH (offset zakódovaný Huffmanovým kódováním)
    • varianta LZSS (další vylepšení)
    • varianta Deflate (dva nezávislé Huffmanovy stromy)
  • Algoritmus LZ78
  • Algoritmus LZW
    • varianta LZMW (pomalejší, efektivnější rozšiřování slovníku, LRU mazání)
    • varianta LZAP (pomalejší, efektivnější rozšiřování slovníku)
    • varianta LZY
Slovně orientované metody

Rodina statistických bajtově-orientovaných slovníkových kompresních metod je primárně určená pro kompresi textů v přirozeném jazyce a zdrojových kódů.

  • Algoritmus End-Tagged Dense Code
    • základní varianta
    • dynamická varianta
    • odlehčená dynamická varianta
  • Algoritmus (S,C)-Dense Code
    • základní varianta
    • dynamická varianta
    • odlehčená dynamická varianta
Kontextové metody
  • Algoritmus PPM (Prediction with Partial Matching)
  • Algoritmus DCA (Data Compression using Antidictionaries)
  • Algoritmus ACB (Associate Code of Buyanovsky)
  • Burrows-Wheelerova komprese

Měření účinnosti

Aby bylo možné jednotlivé metody komprese objektivně porovnávat, vzniklo několik standardních benchmarků a metrik. Mezi nejznámější benchmarky patří již starší, ale stále používané množiny souborů: Calgary Corpus a Canterbury Corpus. Další korpusy jsou již ve vývoji, mimo jiné i na ČVUT.

Calgary Corpus (1987)
  • 18 souborů (text, obrázky, binární soubory)
  • dnes již zastaralý
Canterbury Corpus (1997)

Reference