Komprese dat je algoritmická (obvykle reverzibilní) transformace dat prováděná za účelem snížení objemu, který zabírají. Používá se pro racionálnější využití zařízení pro ukládání a přenos dat. Synonyma - balení dat , komprese , kompresní kódování , zdrojové kódování . Opačný postup se nazývá obnova dat (dekomprese, dekomprese).
Komprese je založena na odstranění redundance obsažené v původních datech. Nejjednodušším příkladem redundance je opakování fragmentů v textu (například slova přirozeného nebo strojového jazyka). Taková redundance je obvykle eliminována nahrazením opakující se sekvence odkazem na již kódovaný fragment s uvedením jeho délky. Další druh redundance je způsoben tím, že některé hodnoty v komprimovaných datech se vyskytují častěji než jiné. Snížení množství dat je dosaženo nahrazením často se vyskytujících dat krátkými kódovými slovy a vzácných dat dlouhými ( entropické kódování ). Komprese dat, která nemají vlastnost redundance (například náhodný signál nebo bílý šum , šifrované zprávy), je v zásadě nemožná bez ztráty.
Bezeztrátová komprese umožňuje zcela obnovit původní zprávu, protože nesnižuje množství informací v ní i přes zkrácení délky. Taková možnost nastává pouze v případě, že rozložení pravděpodobností na množině zpráv není jednotné, například některé zprávy teoreticky možné v předchozím kódování se v praxi nevyskytují.
Základem každé kompresní metody je model zdroje dat, přesněji řečeno model redundance . Jinými slovy, komprese dat využívá určité apriorní znalosti o tom, jaký druh dat je komprimován. Bez takových informací o zdroji nelze učinit žádné předpoklady o transformaci, které by zmenšily velikost zprávy. Model redundance může být statický, nezměněný pro celou komprimovanou zprávu, nebo může být vytvořen či parametrizován ve fázi komprese (a obnovy). Metody, které umožňují měnit model informační redundance na základě vstupních dat, se nazývají adaptivní. Neadaptivní jsou obvykle vysoce specializované algoritmy používané pro práci s daty, která mají dobře definované a neměnné charakteristiky. Naprostá většina dostatečně univerzálních algoritmů je do určité míry adaptivní.
Všechny metody komprese dat jsou rozděleny do dvou hlavních tříd:
Při použití bezztrátové komprese je možné zcela obnovit původní data, ztrátová komprese pak umožňuje obnovit data s deformacemi, které jsou z hlediska dalšího využití obnovených dat obvykle nevýznamné. Bezeztrátová komprese se obvykle používá k přenosu a ukládání textových dat, počítačových programů, méně často - ke snížení objemu audio a video dat , digitálních fotografií atd., v případech, kdy je zkreslení nepřijatelné nebo nežádoucí. Ztrátová komprese, která je mnohem účinnější než bezeztrátová komprese, se obvykle používá ke snížení množství zvuku, videa a digitálních fotografií v případech, kdy je taková redukce prioritou a není vyžadována úplná shoda původních a obnovených dat.
Kompresní poměr je hlavní charakteristikou kompresního algoritmu. Je definován jako poměr objemu původních nekomprimovaných dat k objemu komprimovaných dat, to znamená: , kde k je kompresní poměr, S o je objem původních dat a Sc je objem komprimovaná data. Čím vyšší je kompresní poměr, tím efektivnější je algoritmus. Je třeba poznamenat:
Situace s k < 1 je při kompresi docela možná. Je v zásadě nemožné získat bezeztrátový kompresní algoritmus, který by za předpokladu jakýchkoli dat produkoval na výstupu data menší nebo stejné délky. Důvodem pro tuto skutečnost je, že protože počet různých zpráv o délce n bitů je přesně 2 n , bude počet různých zpráv s délkou menší nebo rovnou n (pokud existuje alespoň jedna zpráva menší délky) rovný nejvíce 2 n . To znamená, že není možné jednoznačně mapovat všechny původní zprávy na komprimovanou: buď některé původní zprávy nebudou mít komprimovanou reprezentaci, nebo několik originálních zpráv bude mít stejnou komprimovanou reprezentaci, což znamená, že je nelze rozlišit. I když však kompresní algoritmus zvětší velikost původních dat, je snadné zajistit, aby se jejich velikost zaručeně nezvýšila o více než 1 bit. Pak i v nejhorším případě dojde k nerovnosti:
To se provádí následovně: pokud je množství komprimovaných dat menší než množství původních, vrátíme komprimovaná data tak, že k nim přidáme „1“, jinak vrátíme původní data přidáním „0“ k nim).
Kompresní poměr může být buď konstantní (některé algoritmy pro kompresi zvuku, obrázků atd., jako je A-law , μ-law , ADPCM , kódování zkrácených bloků ) a proměnný. Ve druhém případě může být stanovena buď pro každou konkrétní zprávu, nebo vyhodnocena podle některých kritérií:
nebo jakékoliv jiné. V tomto případě ztrátový kompresní poměr silně závisí na dovolené kompresní chybě nebo kvalitě , která obvykle funguje jako parametr algoritmu. V obecném případě mohou konstantní kompresní poměr zajistit pouze metody ztrátové komprese dat.
Hlavním kritériem pro rozlišení mezi kompresními algoritmy je přítomnost nebo nepřítomnost výše popsaných ztrát. V obecném případě jsou algoritmy bezztrátové komprese univerzální v tom smyslu, že jejich použití je jistě možné pro data jakéhokoli typu, přičemž možnost použití ztrátové komprese musí být odůvodněna. U některých datových typů nejsou deformace v zásadě povoleny. Mezi nimi
Různé algoritmy mohou vyžadovat různé množství zdrojů výpočetního systému, na kterém jsou implementovány:
Obecně platí, že tyto požadavky závisí na složitosti a „inteligenci“ algoritmu. Obecný trend je následující: čím efektivnější a všestrannější je algoritmus, tím větší jsou požadavky na výpočetní zdroje, které klade. Ve specifických případech však mohou jednoduché a kompaktní algoritmy fungovat stejně dobře jako složité a univerzální. Systémové požadavky určují jejich spotřebitelské kvality: čím méně náročný algoritmus, tím jednodušší, a tedy kompaktnější, spolehlivější a levnější systém jej lze implementovat.
Protože algoritmy komprese a obnovy pracují ve dvojicích, záleží na poměru systémových požadavků k nim. Zkomplikováním jednoho algoritmu je často možné výrazně zjednodušit jiný. Jsou tedy možné tři možnosti:
Kompresní algoritmus vyžaduje více výpočetních zdrojů než algoritmus obnovy. Toto je nejběžnější poměr, typický pro případy, kdy jednou zkomprimovaná data budou použita opakovaně. Příkladem jsou digitální audio a video přehrávače. Algoritmy komprese a obnovy vyžadují přibližně stejné výpočetní zdroje. Nejpřijatelnější varianta pro komunikační linky, kdy ke kompresi a obnově dochází jednou na jejích dvou koncích (například v digitální telefonii). Algoritmus komprese je výrazně méně náročný než algoritmus obnovy. Tato situace je typická pro případy, kdy je kompresní procedura implementována jednoduchým, často přenosným zařízením, pro které je množství dostupných zdrojů velmi kritické, například kosmická loď nebo velká distribuovaná síť senzorů. Může se také jednat o data, která je třeba dekomprimovat ve velmi malém procentu případů, jako jsou například záběry CCTV.Existují dva hlavní přístupy ke kompresi dat neznámého formátu:
Kompresní metody | |||||||
---|---|---|---|---|---|---|---|
Teorie |
| ||||||
Bezztrátový |
| ||||||
Zvuk |
| ||||||
snímky |
| ||||||
Video |
|