Informační společnost

Lidská společnost se přehoupla do věku, který klade stále větší důraz na informace. Na různých datových nosičích máme svá osobní data, kterých si nesmírně ceníme, dokonce někdy mnohem více než hmotného majetku. V případě hmotných statků totiž není takovým problémem si pořizovat stále nové věci, nemluvě o tom, že člověk je k takovému životnímu stylu na počátku 21. století přímo vybízen. Zato ztráta fotografií, rodinného videa nebo třeba zdrojových kódů vyvíjeného softwaru může být mnohem kritičtější. Se vzrůstajícím množstvím vlastněných datových souborů roste i potřeba jejich vhodného ukládání, zálohování a v neposlední řadě i komprese. Kdo z nás by si chtěl například všechny videosoubory ukládat v plné kvalitě tak, jak je získal z videokamery? S tím by byl problém i při současné kapacitě záznamových nosičů.

Definice pojmu

Komprese je definována jako proces zakódování vstupní informace skrze určité kódovací schéma tak, aby výstupní informace zabírala méně bitů (nebo jiných jednotek, které udávají množství informace). Opačný proces ke kompresi nazýváme dekompresí.

Základní přístupy

1. Bezeztrátová komprese zachovává veškerou informaci. Pokud tedy provedeme kompresi následovanou dekompresí, získáme opět původní posloupnost bitů. Tento přístup je nutný například u textu, kdy si nemůžeme dovolit zprávu pozměnit. Lze však také uvažovat algoritmy, které například nenávratně sníží počet bílých znaků v textu, což už spadá do kategorie komprese ztrátové.
2. Ztrátová komprese vnáší do kódovaných dat šum, přitom je však zachována určitá míra podobnosti s originálními daty. Opakovaná komprese může vést k výraznému porušení až k úplnému zničení dat. Této metody je využito při kompresi obrazu a zvuku, kde naše smysly často nejsou schopny ani rozlišit originál od jeho mírně pozměněné kopie, kterou lze díky určité struktuře a vhodnému kódování uložit na menším počtu bitů.

Digitální informace

Použití digitálního (nespojitého) signálu nastartovalo hlubší uvažování o kompresi dat, bylo totiž nutné řešit otázky kódování. Důležitým motorem pro rozvoj komprese byl také rozvoj telekomunikací. Vznikla potřeba přenést po linkách s malou šířkou pásma velké kvantum informací. V některých případech bylo dokonce nutné přenášet data v reálném čase, tedy například provádět „přímý přenos“ zvuku nebo obrazu. V těchto případech bylo (a stále je) nasazení vhodných kompresních algoritmů nezbytnou nutností.

Morseův kód

Jedním z prvních způsobů kódování zpráv byla Morseova abeceda, kterou vynalezl Morse roku 1838. Její primární použití bylo v telegrafii. Na struktuře Morseovy abecedy si můžeme povšimnout určitých kompresních prvků. Je obecně známo, že písmena „e“ a „t“ jsou v angličtině nejpoužívanějšími. A právě z tohoto důvodu jsou v Morseově kódu reprezentována nejkratšími řetězci.

Pokrok v teoretické informatice

Pozdní 40. léta 20. století jsou spojena se jmény Claude Shannon a Robert Fano, kteří navrhli, aby se jednotlivá kódová slova systematicky přiřazovala znakům (blokům) podle statistické pravděpodobnosti jejich výskytu v dané zprávě.

Huffmanovo kódování

Zmíněných poznatků využil David Huffman v roce 1951, kdy definoval přesnou matematickou metodu, jež vytvářela minimální prefixový kód. Prefixový kód umožňuje jednoznačné dekódování informace, aniž by v textu musely být nějaké meziznakové oddělovače. Celý trik spočívá v tom, že žádný konkrétní kód znaku nezačíná kódem znaku jiného. V okamžiku dočtení posledního bitu znaku je tento znak ihned rozpoznán a začínají se číst další bity zprávy.

Pro srovnání: Morseova abeceda, která není prefixová, musela používat kromě krátké značky („tečka“) a dlouhé značky („čárka“) čtyři typy oddělovacích mezer (mezi jednotlivými tečkami a čárkami, mezi písmeny, mezi slovy a mezi větami). Každá z nich měla přesně stanovenou délku. Přísně technicky vzato se tedy nejedná o binární kód, protože bylo použito 6 kódovacích prvků.

Dekódování u Huffmanova kódu probíhá pomocí binárního vyhledávací stromu. Vždy při přečtení nuly nebo jedničky se rozhodneme pro jednu z větví. V okamžiku, kdy dosáhneme listu, můžeme dát na výstup patřičný znak a začít znovu od kořene. Tento přístup však s sebou nese i jeden problém – obě větve stromu mají stejnou pravděpodobnost a každá z nich poloviční pravděpodobnost svého rodičovského uzlu. Takový scénář však téměř nikdy nekoresponduje s původním rozložením pravděpodobnosti znaků ve zprávě.

Adaptivní Huffmanovo kódování

V 70. letech vzrůstá potřeba digitálního ukládání textů. Ve většině případů se používá tzv. adaptivní Huffmanovo kódování. To vychází ze stejného principu jako původní Huffmanovo kódování až na to, že používá pouze jeden průchod zprávou. Po přečtení nového znaku jsou aktualizovány statistické informace a vytvořen nový strom. Tento přístup je však poměrně výpočetně náročný.

Využití ukazatelů

Píše se rok 1977, Abraham Lempel přišel s novým způsobem koprese dat pomocí ukazatelů. O rok později jeho práci zdokonalil Jacob Ziv. Tyto algoritmy jsou označovány jako LZ77 a LZ78. V roce 1984 pak byly provedeny ještě další úpravy skrze Terry Welshe. Zmíněné algoritmy se staly populární a byly využity jak v programu PKZIP, tak v modernějších RAR, ARJ, GZIP či ACE. Dokonce byly hardwarově implementovány do modemů.

Algoritmus LZ77

Ve zprávě jsou vyhledávány stejné řetězce znaků. Místo opětovného vypsání nalezené stejné sekvence znaků, je uložen ukazatel na místo, kde již byla objevena totožná sekvence. Kromě ukazatele je ještě nezbytné uložit délku této sekvence. Algoritmus LZ78 je vylepšením, které pracuje na základě vytvoření vlastního slovníku použitých řetězců.

80. léta

Příchod 80. let s sebou přinesl první větší využití digitálních obrázků. Vzniká potřeba nalézt vhodné formáty pro jejich uložení a objevují se odpovídající standardy. Formát GIF používá již zmíněnou LZW metodu (Lempel-Zip-Welsch).

90. léta

Dochází k masivnímu rozšíření multimédií, digitalizaci obrazu, zvuku i videa. Obrovský prostor získávají kompresní metody, které jsou ztrátové. Známý formát pro uložení obrázků zvaný JPG využívá ztrátové diskrétní kosinové transformace, která je následována Huffmanovým nebo aritmetickým kódováním.

Aritmetické kódování

Cílem aritmetického kódování je vytvořit z původního souboru jediné číslo. Tato metoda se začala používat až začátkem 90. let, protože vyžadovala přítomnost matematického koprocesoru. Lze ji považovat za nástupce Huffmanova kódování, protože řeší jeho hlavní slabinu, která spočívá v zaokrouhlování statistických pravděpodobností při sestavování dekódovacího stromu.

Komprese zvuku a MP3

Německý Fraunhofer Institut Integrierte Schaltungen ve spolupráci s University of Erlangen vyvinul na konci 80. let kompresní algoritmus, který byl určen pro digitální telekomunikaci a rozhlasové služby. Byla vytvořena 3 schémata: layer I, layer II a layer III, které bylo nejvýkonnější a je určeno pro nízké bitové proudy. Právě MPEG 1 Layer III, obecně známý jako MP3, spatřil světlo světa v roce 1992, byl standardizován organizací ISO a dosáhl na přelomu tisíciletí masového použití.

Apple a formát AAC

Firma Apple vydala přepracovaný a vylepšený formát, který používá kódovací strategii vycházející z MP3. Jeho hlavním problémem je však podpora. V současné době jeho přehrávání umožňují aplikace QuickTime, iTunes a přehrávače iPod.

Ogg Vorbis

Ogg Vorbis je další z případných nástupců MP3, který je srovnatelný se současnými moderními formáty. Jeho největší výhodou je to, že je vyvíjen jako svobodný software. Na druhou stranu tento fakt může zabránit jeho většímu rozšíření.

Microsoft Windows Media

WMA (Windows Media Audio) je typickým proprietárním (uzavřeným) formátem, který vyvinula firma Microsoft. Má poměrně kvalitní kompresní poměr a je podporován širokou škálou aplikací stejně tak jako kapesních i stolních přehrávačů. Pro potřeby videa Microsoft uvedl formát WMV (neboli Windows Media Video).

Komprese videa

V oblasti kódování videa se nejvíce prosadila skupina Moving Picture Experts Group (MPEG), která pracuje pod vedením organizace ISO. Vznikly následující standardy:

• MPEG 1 kóduje video i audio, je určen pro digitální nosiče, využívá datový tok do 1,5 Mbit/s.
• MPEG 2 zajišťuje kódování při nižších datových tocích za poloviční vzorkovací frekvence.
• MPEG 3 byl původně plánován pro HDTV, později byl sloučen s MPEG 2.
• MPEG 4 je kompresní standard z roku 1998 určený pro web (a vysílání v přímém přenosu), videotelefonii, internetovou televizi a distribuci videa na CD nosičích.

DivX

DivX ;-) 3.11 Alpha (v původní názvu se skutečně nacházela emotikona) vznikl na základě reverzního inženýrství z kodeku Micorosft MPEG-4 Version 3. Následovaly práce na jeho vylepšení. Od verze 6 (rok 2005) se autoři snaží o vytvoření speciálního formátu, který může obsahovat kromě videa třeba i titulky v několika jazycích a další metadata.

Xvid

Při problémech, které provázaly vývoj kodeku DivX (zejména verze 4) se část vývojářů začala věnovat jeho open source variantě. Takto vznikl DivX, který je šířen pod GPL.

Závěr

Na základě současných kompresních technik jsme schopni u textu a textových diagramů dosáhnout poměru 3:1, u fotografií při bezeztrátové kompresi poměru 2:1, při ztrátové 20:1. Stále zlepšující se výpočetní schopnosti počítačů nám umožňují použít složitější matematické metody a dosáhnout ještě zajímavějších výsledků. Ukázkou tohoto jevu je nedávný nástup formátu MPEG-4 a z něj odvozených kodeků. Pro získání dalších informací ohledně studované problematiky doporučuji projít některé z následujících odkazů.

Reference a prameny

1. Kompresní algoritmy
   http://gimli.mysteria.cz/komprese/algoritmy.html
2. Živě.cz – Definice pojmu komprese
   http://www.zive.cz/slovnik/Default.asp?EXPSDIC=komprimace
3. Wikipedia – Datová komprese
   http://en.wikipedia.org/wiki/Data_compression
4. Wolfram Science – Historie datové komprese
   http://www.wolframscience.com/reference/notes/1069b
5. Wikipedia – Morseův kód
   http://en.wikipedia.org/wiki/Morse_code
6. Wolfram Science – Historie ztrátové komprese
   http://www.wolframscience.com/reference/notes/1072d
7. MujMac.cz – Komprese a formáty
   http://www.mujmac.cz/art/multimedia/hudba_komp1.html
8. Michal Toman – O MP3
   http://home.zcu.cz/~mtoman/mp3_cut.htm
9. Wikipedia – MPEG-4
   http://en.wikipedia.org/wiki/MPEG-4
10. Wikipedia – DivX
    http://en.wikipedia.org/wiki/DivX
11. Wikipedia – Xvid
    http://en.wikipedia.org/wiki/Xvid