Bezeztrátová komprese

Algoritmy bezeztrátové komprese dat nemohou zaručit kompresi pro všechny vstupní soubory dat. Jinými slovy, pro každý algoritmus bezeztrátové komprese dat bude existovat vstupní soubor dat, který se při zpracování algoritmem nezmenší, a pro každý algoritmus bezeztrátové komprese dat, který zmenší alespoň jeden soubor, bude existovat alespoň jeden soubor, který zvětší. To lze snadno dokázat pomocí elementární matematiky s použitím počítacího argumentu takto:

• Předpokládejme, že každý soubor je reprezentován jako řetězec bitů libovolné délky.
• Předpokládejme, že existuje kompresní algoritmus, který každý soubor převede na výstupní soubor, který není delší než původní soubor, a že alespoň jeden soubor bude zkomprimován na výstupní soubor, který je kratší než původní soubor.
• Nechť M je nejmenší číslo takové, že existuje soubor F o délce M bitů, který se zkomprimuje na něco kratšího. Nechť N je délka (v bitech) komprimované verze F.
• Protože N<M, každý soubor délky N si při kompresi zachová svou velikost. Takových souborů je možné vytvořit 2N. Spolu s F tak vznikne 2N+1 souborů, které se všechny zkomprimují do jednoho z 2N souborů délky N.
• Ale 2N je menší než 2N+1, takže podle principu holubice musí existovat nějaký soubor délky N, který je současně výstupem kompresní funkce na dvou různých vstupech. Tento soubor nelze spolehlivě dekomprimovat (který ze dvou originálů by to mělo dát?), což je v rozporu s předpokladem, že algoritmus byl bezeztrátový.
• Musíme tedy dojít k závěru, že naše původní hypotéza (že kompresní funkce žádný soubor neprodlouží) je nutně nepravdivá.

Každý bezeztrátový kompresní algoritmus, který některé soubory zkrátí, musí nutně některé soubory prodloužit, ale není nutné, aby se tyto soubory velmi prodloužily. Většina praktických kompresních algoritmů poskytuje možnost „úniku“, která může vypnout normální kódování u souborů, které by se zakódováním staly delšími. Teoreticky je zapotřebí pouze jeden dodatečný bit, který dekodéru sdělí, že normální kódování bylo vypnuto pro celý vstup; většina kódovacích algoritmů však pro tento účel používá nejméně jeden celý bajt (a obvykle více než jeden). Například komprimované soubory deflate se nikdy nemusí zvětšit o více než 5 bajtů na 65 535 bajtů vstupu.

Ve skutečnosti, pokud uvažujeme soubory o délce N, pokud by všechny soubory byly stejně pravděpodobné, pak pro jakoukoli bezeztrátovou kompresi, která zmenšuje velikost nějakého souboru, musí být očekávaná délka komprimovaného souboru (zprůměrovaná přes všechny možné soubory o délce N) nutně větší než N. Pokud tedy nevíme nic o vlastnostech komprimovaných dat, můžeme je rovnou nekomprimovat vůbec. Bezeztrátový kompresní algoritmus je užitečný pouze v případě, že máme větší pravděpodobnost komprese určitých typů souborů než jiných; pak by algoritmus mohl být navržen tak, aby tyto typy dat komprimoval lépe.

Hlavní poučení z tohoto argumentu tedy není, že hrozí velké ztráty, ale pouze to, že nelze vždy vyhrát. Zvolit algoritmus vždy implicitně znamená vybrat podmnožinu všech souborů, které se stanou užitečně kratšími. To je teoretický důvod, proč potřebujeme mít různé kompresní algoritmy pro různé druhy souborů: nemůže existovat žádný algoritmus, který by byl dobrý pro všechny druhy dat.

„Trik“, který umožňuje bezeztrátovým kompresním algoritmům, použitým na typ dat, pro který byly navrženy, důsledně komprimovat takové soubory do kratší podoby, spočívá v tom, že všechny soubory, na které jsou algoritmy navrženy, mají nějakou formu snadno modelovatelné redundance, kterou má algoritmus odstranit, a patří tedy do podmnožiny souborů, které tento algoritmus může zkrátit, zatímco ostatní soubory by se nezkomprimovaly nebo dokonce zvětšily. Algoritmy jsou obecně zcela specificky uzpůsobeny pro určitý typ souboru: například programy pro bezeztrátovou kompresi zvuku nefungují dobře na textové soubory a naopak.

Zejména soubory s náhodnými daty nelze důsledně komprimovat žádným myslitelným algoritmem pro bezeztrátovou kompresi dat: tento výsledek se ostatně používá k definici pojmu náhodnosti v teorii složitosti algoritmů.

Je prokazatelně nemožné vytvořit algoritmus, který by dokázal bezeztrátově komprimovat jakákoli data. Přestože se v průběhu let objevilo mnoho tvrzení společností o dosažení „dokonalé komprese“, kdy lze libovolný počet N náhodných bitů vždy zkomprimovat na N – 1 bitů, lze tento druh tvrzení bezpečně odmítnout, aniž bychom se zabývali dalšími podrobnostmi týkajícími se údajného kompresního schématu. Takový algoritmus odporuje základním zákonům matematiky, protože pokud by existoval, bylo by možné jej opakovaně použít k bezeztrátovému zmenšení libovolného souboru na délku 0. Údajně „dokonalé“ kompresní algoritmy jsou z tohoto důvodu často posměšně označovány jako „magické“ kompresní algoritmy.

Na druhou stranu bylo také prokázáno, že neexistuje algoritmus, který by určil, zda je soubor nekomprimovatelný ve smyslu Kolmogorovovy složitosti. Proto je možné, že jakýkoli konkrétní soubor, i když se jeví jako náhodný, může být výrazně komprimovaný, a to i včetně velikosti dekompresoru. Příkladem jsou číslice matematické konstanty pí, které se zdají být náhodné, ale lze je vygenerovat velmi malým programem. Nicméně i když nelze určit, zda je konkrétní soubor nekomprimovatelný, jednoduchá věta o nekomprimovatelných řetězcích ukazuje, že více než 99 % souborů libovolné délky nelze zkomprimovat o více než jeden bajt (včetně velikosti dekompresoru).

Matematické pozadíEdit

Abstraktně lze na kompresní algoritmus pohlížet jako na funkci na posloupnostech (obvykle oktetů). Komprese je úspěšná, pokud je výsledná sekvence kratší než původní sekvence (a instrukce pro dekompresní mapu). Aby byl kompresní algoritmus bezeztrátový, musí kompresní mapa tvořit injekci z „obyčejných“ na „komprimované“ bitové posloupnosti.

Princip holubí díry zakazuje bijekci mezi kolekcí posloupností délky N a libovolnou podmnožinou kolekce posloupností délky N-1.

Princip holubí díry zakazuje bijekci mezi kolekcí posloupností délky N a libovolnou podmnožinou kolekce posloupností délky N-1. Proto není možné vytvořit bezeztrátový algoritmus, který by zmenšil velikost každé možné vstupní posloupnosti.

Body použití v teorii reálné kompreseUpravit

Konstruktéři reálných kompresních algoritmů připouštějí, že toky s vysokou informační entropií nelze komprimovat, a proto zahrnují zařízení pro detekci a zpracování této podmínky. Zřejmým způsobem detekce je použití surového kompresního algoritmu a testování, zda je jeho výstup menší než vstup. Někdy se detekce provádí pomocí heuristiky; například kompresní aplikace může považovat soubory, jejichž názvy končí na „.zip“, „.arj“ nebo „.lha“, za nekomprimovatelné, aniž by byla provedena sofistikovanější detekce. Běžným způsobem řešení této situace je citování vstupu nebo nekomprimovatelných částí vstupu ve výstupu, čímž se minimalizuje režie komprese. Například datový formát zip určuje pro vstupní soubory, které byly do archivu doslovně zkopírovány, „metodu komprese“ „Uloženo“.

The Million Random Digit ChallengeEdit

Mark Nelson v reakci na tvrzení o zázračných kompresních algoritmech, která se objevují v komp.compression, zkonstruoval binární soubor o velikosti 415 241 bajtů s vysoce entropickým obsahem a vypsal veřejnou výzvu v hodnotě 100 dolarů pro kohokoli, kdo napíše program, který by byl spolu se svými vstupními daty menší než jím poskytnutá binární data a přitom je dokázal bezchybně rekonstruovat.

V sekci FAQ diskusní skupiny comp.compression je uvedena výzva Mika Goldmana, který nabízí 5 000 dolarů za program, který dokáže komprimovat náhodná data. Patrick Craig výzvu přijal, ale místo aby data zkomprimoval, rozdělil je do samostatných souborů, z nichž všechny končily číslem 5, které nebylo uloženo jako součást souboru. Vynechání tohoto znaku umožnilo, že výsledné soubory (plus, v souladu s pravidly, velikost programu, který je znovu složil) byly menší než původní soubor. Ke skutečné kompresi však nedošlo a informace uložené v názvech souborů byly nezbytné pro jejich opětovné sestavení ve správném pořadí v původním souboru a tyto informace nebyly při porovnávání velikosti souborů brány v úvahu. Samotné soubory tedy k rekonstrukci původního souboru nestačí, nutné jsou také názvy souborů. Patrick Craig souhlasil s tím, že nedošlo k žádné smysluplné kompresi, ale tvrdil, že znění výzvy to ve skutečnosti nevyžaduje. Úplnou historii události, včetně diskuse o tom, zda výzva byla či nebyla technicky splněna, najdete na webu Patricka Craiga.