Metody komprese a kódování dat

Mendelova zemědělská a lesnická univerzita Provozně ekonomická fakulta

Metody komprese a kódování dat Bakalářská práce

Vedoucí práce: Mgr. Tomáš Foltýnek, Ph.D.

Petr Chladil

Brno, 2008

2

Rád bych zde poděkoval Mgr. Tomáši Foltýnkovi, Ph.D. za mnoho cenných odborných rad, trpělivost a především ochotu poradit s jakýmkoli problémem.

3

4

Prohlašuji, že jsem tuto práci vypracoval samostatně s použitím literatury, kterou uvádím v přehledu. V Brně dne 26. května 2008

…………………………………

5

6

Abstrakt Chladil, P. Metody komprese a kódování dat. Bakalářská práce. Brno, 2008. Práce se zabývá popisem jednotlivých metod komprese a kódování dat a charakteristikou nejběžnějších formátů dat, kde jsou tyto metody použity. Pro lepší pochopení jsou součástí dva demonstrační programy na přiloženém CD.

Abstract Chladil, P. Data compresion and encryption methods. Bachelor thesis. Brno, 2008. The thesis describes particular methods of data compresion and encryption and defines the most common data formats, in which the methods are used. For better understanding there are two demo programs enclosed on CD.

7

8

Obsah 1. Úvod a cíl práce........................................................................ 11 1.1.. Úvod .......................................................................................................11 1.2. Cíl práce..................................................................................................12 2. Teoretická východiska práce .................................................... 13 2.1. Základní pojmy ......................................................................................13 2.2. Dělení kompresních metod....................................................................13 2.3. Objektově orientované programování (OOP) .......................................14 2.3.1. Dědičnost ........................................................................................14 2.3.2. Zapouzdření ....................................................................................14 2.3.3. Polymorfismus ................................................................................14 2.4. Programovací jazyk Java........................................................................14 2.4.1. Vznik................................................................................................15 2.4.2. JDK..................................................................................................15 2.4.3. Dva typy programů v Javě ..............................................................15 2.4.4. Metody, třídy, balíky .......................................................................15 2.4.5. Prostředí Netbeans .........................................................................16 3. Metodika práce ........................................................................ 16 3.1. Analýza problému ..................................................................................16 3.2. Postup řešení..........................................................................................16 4.Vlastní práce............................................................................ 17 4.1. Bezztrátová komprese............................................................................17 4.1.1. Slovníkové metody..........................................................................17 4.1.2. Statistické metody...........................................................................21 4.1.3. Ostatní metody................................................................................25 4.2. Využití metod bezztrátové komprese.....................................................25 4.2.1. ZIP ...................................................................................................26 4.2.2. RAR .................................................................................................26 4.2.3. PDF..................................................................................................26 4.2.4. GIF...................................................................................................27 4.2.5. PNG .................................................................................................27 4.2.6. TIFF.................................................................................................27 4.2.7. PCX..................................................................................................28 4.3. Ztrátová komprese .................................................................................28 4.3.1. Grafika.............................................................................................28 4.3.2. Video ...............................................................................................29 4.3.3. Zvuk.................................................................................................32 4.4. Demonstrační aplety vybraných metod.................................................33 4.4.1. Huffmanovo kódování ....................................................................33 4.4.2. Aritmetické kódování......................................................................35 5. Závěr ....................................................................................... 38 6.Literatura ................................................................................ 40

9

10

1. Úvod a cíl práce 1.1.

Úvod

Snad každý, kdo se alespoň jednou rozhodl strávit dovolenou v přírodě, řešil problém, který se zdá být možná trochu nestandardní, pracný a mnohdy poměrně komplikovaný. Jedná se o sbalení spacího pytle, umístění ho zpět do obalu. Pokud je rozbalen, je rozhodně větší než když se umě sbalí. Je to velmi výhodné při jeho převozu, což jistě ocení jak pěší, tak cyklisté či motoristé. Přitom existuje nespočet metod, jakým způsobem lze spací pytel do obalu nasoukat. Potřeba zmenšení objemu při skladování a přenosu je velmi vhodná nejenom při odjezdu na letní dovolenou, ale je výhodou i při práci s daty. Daty je myšlen text, grafika a v neposlední řadě i hudba a video. I zde platí ono již zmíněné šetření místa. Možnost redukovat velikost dat je velmi výhodná především finančně. Pokud se nám podaří jistou metodou zmenšit velikost souboru, provedli jsme kompresi či komprimaci dat (tato slova jsou synonyma). Podle toho, jakou metodu jsme použili, je možné rozdělit kompresi na ztrátovou a bezztrátovou (též bezeztrátovou). V případě, že se nám podaří opačným postupem dosáhnout původních dat (rozbalit spací pytel), byla použita komprese bezztrátová, v opačném případě se jedná o metodu ztrátovou. Pojmy často spojované právě s kompresí jsou kódování a šifrování. Mezi veřejností je například velmi známá Caesarova šifra, která pracovala na jednoduchém principu, a přesto nebyla dlouho prolomena. Dalo by se říci, že mnoho válečných konfliktů bylo v minulosti ovlivněno kódováním či šifrováním – asi nejvíce 2. světová válka, se kterou je pojem kódovacího stroje Enigma neodmyslitelně spjat. Šifrování a kódování se staletími měnilo, protože starší šifry byly prolomeny a již neplnily svůj účel. Postupem času docházelo ke vzniku daleko složitějších algoritmů, které bylo a je obtížné nebo téměř nemožné překonat. V současnosti je například velmi používané asymetrické šifrování. V dnešní době by kreslení nebo psaní na vyholenou hlavu či jiné praktiky používané dříve působily spíše jako žert. Nyní je ke kódování používána prakticky jen výpočetní technika především z důvodu časového a rychlostního. Pojmy komprese a kódování nabývají velmi často podobného významu, jelikož při kompresi vzniká jistý kód, který nahrazuje buď zcela nebo částečně původní data. Avšak většinou nejde účelně o utajení obsahu, ale spíše o zmenšení objemu dat (dekodér je veřejně k dispozici).

11

Je nutné dodat, že i nyní existují metody kódování, u nichž je důležité utajit podobu přenášené informace. Dekodér není v tomto případě pochopitelně dostupný pro každého, ale pouze pro toho, kdo má zprávu rozluštit. Určité množství lidí pojmy týkající se komprimace, kódování dat a formátů buď vůbec nezná, nebo zná pouze okrajově. Navíc literatura vyskytující se na internetu není často zcela přesná, ba co více, bývá i zavádějící. Následující text by měl přinést přijatelnou formou vysvětlení základních zákonitostí týkajících se tématu, které hrálo, hraje a ještě bude hrát velkou roli nejen ve vývoji výpočetní techniky.

1.2.

Cíl práce

Tato práce má mít především charakter výukového materiálu pro studenty předmětu Komprimace a šifrování, který je od zimního semestru akademického roku 2007/2008 vyučován jako volitelný na Mendelově zemědělské a lesnické univerzitě v Brně. Kódování a komprese dat jsou pouze částí sylabu tohoto předmětu, avšak částí velmi důležitou. Cílem je vytvořit takový podklad, který pomůže studentům vytvořit si představu o základních komprimačních metodách a o formátech, se kterými přicházejí denně do styku při práci s výpočetní technikou. Soustředěnost by měla být kladena především na jádro problému, tj. pochopení jednotlivých algoritmů a seznámení s nejběžnějšími formáty. Pro lepší porozumění bude doplněn výukový materiál o ukázky vybraných algoritmů pomocí demonstračních programů. Zde by mělo hrát významnou roli grafické rozhraní s velkým důrazem na názornost. Textová a softwarová část by měly tvořit jeden celek navenek působící jednotně a zejména by se měly navzájem doplňovat.

12

2. Teoretická východiska práce 2.1.

Základní pojmy

Komprese[1] neboli zabalení archivu je převod do archivní podoby, v níž se podstatně zmenší jeho velikost. V této podobě nelze se souborem běžně pracovat, ale lze jej kdykoliv rozbalit (dekomprimovat) do původní podoby. Dekomprese[1] neboli rozbalení souboru je postup, při němž se z archivního (komprimovaného) souboru znovu vytvoří původní soubor, který je možné dále zpracovávat. Kompresní poměr[1] je porovnání velikosti původního souboru s jeho komprimovanou podobou. Udává se většinou v procentech. Jedná se o poměr nové velikosti komprimovaného souboru k jeho původní velikosti. Komprimační program[1] je takový, jehož hlavním úkolem je vytvoření komprimovaného (zmenšeného) souboru, který je možno snadno archivovat a přenášet. Zpravidla umožňuje vložit do jednoho archivního souboru velké množství jiných souborů nebo celých složek. V podstatě existují dva zcela rozdílné principy komprese dat. První z nich je bezztrátová komprese. Používá se, jak již název napovídá, tam, kde si nelze dovolit jakoukoliv ztrátu dat – u binárních a textových souborů. Existují však takové soubory, ve kterých ztráta některých dat vůbec nevadí. Jedná se o tzv. redundantní (s nadbytečným množstvím informace) soubory, jejichž komprese může být i ztrátová.[2]

2.2.

Dělení kompresních metod

Rozdělit metody lze na statické a adaptivní metody. Neadaptivní algoritmy jsou určeny výhradně pro komprimace specifického druhu dat. Většinou obsahují předdefinované slovníky nebo řetězce znaků, o kterých je známo, že jejich pravděpodobnost výskytu v souborech dat je vysoká. Adaptivní algoritmus je naproti tomu schopen dosáhnout určité nezávislosti na komprimovaných datech. Takové algoritmy neobsahují žádné statické slovníky řetězců. Budují si slovníky pro každý komprimovaný soubor dat znovu dynamicky v průběhu kódování.[2] Rozdělení na symetrické a nesymetrické komprimační algoritmy je založeno na porovnání množství práce, která se podle algoritmu vykoná při kompresi dat a dekompresi dat. Pokud je doba potřebná pro kompresi i dekompresi dat přibližně stejná, jedná se o symetrickou kompresi. Některé algoritmy jsou však záměrně konstruovány jako asymetrické. Většina komprimačních algoritmů provede větší množství operaci při kompresi. Tento

13

přístup je výhodný tam, kde soubor dat ukládáme na disk sice v komprimované podobě, ale často s ním pracujeme (data musí být při práci dekomprimována). Existují i asymetrické algoritmy, jejichž práce je delší při dekomprimaci, nejsou tolik rozšířené, ale i ty mají své opodstatnění. Při vytváření záložních kopií dat lze předpokládat, že zatímco zálohování bude probíhat v pravidelných intervalech, většina zálohovaných dat již nebude nikdy použita.[2]

2.3.

Objektově orientované programování (OOP)

Základním pojmem je (již podle názvu) objekt. Pamatuje si svůj stav a nabízí operace, pomocí nichž s nimi můžeme pracovat – metody. Formou objektu ve struktuře programu, která podchycuje obecně objekty podobného typu se nazývá třída.

2.3.1. Dědičnost Každý objekt reálného světa má jiné vlastnosti. To platí i u objektů. Jak vytvořit jednotlivé objekty a přitom jejich shodné metody nedeklarovat opakovaně, pomáhá vytvářet dědění. V případě třídy mající základní vlastnosti lze pomocí dědění vytvořit instanci třídy, která bude mít jednak vlastnosti původní „mateřské“ třídy, jednak je možnost přidat další metody. Potom je možno nazvat tu novou potomkem.[3]

2.3.2. Zapouzdření V objektově orientovaných programovacích jazycích je zcela běžné, že objekty spolu komunikují, a to pomocí zpráv. Příkladem může být potřeba využití metody jedné třídy třídou druhou. V tom případě si mezi sebou vymění zprávy. Odeslán bude požadavek na využití metody, odpovědí bude například hodnota. Tento způsob předávání zpráv mezi objekty bez možnosti znát implementaci při zpracování požadavku je nazýván zapouzdřením.[3]

2.3.3. Polymorfismus Za předpokladu, že existují alespoň dva objekty, z nichž je jeden potomkem toho druhého a mají nejméně jednu stejně pojmenovanou metodu, můžeme tyto objekty označit jako polymorfní. Jedná se o možnost ovládat sadu objektů jedním.[3]

2.4.

Programovací jazyk Java

Dnes je již pojem programovací jazyk běžně známý napříč širokou veřejností. Avšak Java, jeden z objektově orientovaných jazyků, se od ostatních liší především

14

nezávislostí na operačním systému. Informace uvedené v následujících podkapitolách týkající se programovacího jazyka Java jsou převzaty z Herout, P. Učebnice jazyka Java.[4]

2.4.1. Vznik V roce 1991 začal vývoj jazyka na principu C++ s původním názvem Oak. Pod označením Java byl poprvé představen v roce 1995 firmou Sun na konferenci. Již zde zaujala mnohé zúčastněné, kteří si uvědomovali, že se tento jazyk může zařadit mezi významné co se týče programování webových aplikací i tvorby „běžných“ programů. Java vzbudila velký průmyslový zájem hlavně kvůli tehdejšímu prudkému rozvoji internetu.

2.4.2. JDK Java Development Kit je sada nástrojů pro vývoj aplikací a plnohodnotnou práci s jazykem Java. Obsahuje JRE (viz. dále), překladač, nástroj pro vytváření dokumentace či JAR archivů. Pokud chceme pracovat s Javou, musí být JDK nainstalován. Java Runtime Enviroment je častěji nazýván jako Java platforma. Skládá se ze dvou částí, které jsou nezbytné pro spouštění samostatných programů. Jsou jimi Java Virtual Machine (JVM) a Java Core API. Druhá jmenovaná část obsahuje základní knihovny a musí být součástí každého prostředí, kde se Java používá.

2.4.3. Dva typy programů v Javě Podle účelu by se daly programy v Javě rozdělit na dva základní typy. Prvním jsou aplikace, což jsou samostatné programy známé z jiných programovacích jazyků, druhým jsou aplety, jež se používají na webových stránkách (často jako demonstrační programy). Pro spuštění apletu je nezbytný webový prohlížeč, který ho zavede do paměti počítače.

2.4.4. Metody, třídy, balíky Základní členění v metod v Javě je na metody třídy (statické) a metody instance (objekt odvozený od nějaké třídy). Program v Javě obsahuje jednu nebo více metod (podprogramů). Začíná voláním metody main() a končí jejím opuštěním. Toto platí pouze pro samostatné programy, aplet volá nejdříve metodu init() a jeho činnost končím zavoláním metody destroy(). Jsou zde ještě přesně definované další tři: start(), stop() a paint(Graphics g). Avšak všechny nemusí být využity.

15

Třídou bývá většinou seskupení několika metod, jež jsou poté přístupné pomocí tečkové notace. Název třídy musí v Javě začínat velkým písmenem. Hlavními vlastnostmi tříd jsou polymorfismus a dědění. Balíky jsou takovými knihovnami tříd, sdružují třídy do globálnějších skupin. K dispozici jsou předdefinované logicky uspořádané balíky, třídy a metody, které je možné použít. Příkladem může být třída Math obsahující metody pro matematické výpočty.

2.4.5. Prostředí Netbeans „Vývojové prostředí NetBeans IDE je nástroj, pomocí kterého programátoři mohou psát, překládat, ladit a šířit programy. Vývojové prostředí je vytvářeno v jazyce Java - ale může podporovat jakýkoliv programovací jazyk (např. C++). Kromě toho také existuje velké množství modulů, které toto vývojové prostředí rozšiřují. Vývojové prostředí NetBeans je bezplatně šířený produkt, který je možné používat bez jakýchkoliv omezení. Je použitelný na operačních systémech Windows, Linux, Mac OS X a Solaris.“ [5] Aktuální uvolněná verze 6.0 je z prosince 2007.

3. Metodika práce 3.1.

Analýza problému

Při tvorbě opor je velmi důležité, ale byly informace podány takovým způsobem, který by umožňoval snadné a rychlé pochopení řešeného problému avšak ne na úkor zjednodušení. Správné rozdělení do skupin a struktura nadpisů by měla přispívat k možnosti zařadit zkoumanou problematiku do celku. Způsob vyjadřování by měl působit jasně a nepříliš komplikované slovní obraty zlepšit čtivost textu.

3.2.

Postup řešení

Prvním krokem by mělo bezpochyby být pečlivé prostudování všech zdrojů (knihy, internet), které by poskytovaly informace o problematice kódování, komprimace a formátů. Nabyté znalosti by měly být zpracovány tak, aby bylo možné výsledný materiál použít jako studijní materiál. Údaje o jednotlivých metodách nesmí postrádat jistou strukturu. Každá z nich bude systematicky popsána. Chybět by neměly obecné informace o konkrétní metodě, případně zajímavosti z její historie, které by mohly obsahovat i údaje o autorech. Princip kódování a dekódování by však měl být tělem, tím nejdůležitějším. V případě, že se bude jednat o metodu složitější, může být

16

doplněna o obrázek či obrazovou ukázku demonstračního programu, na které bude názorněji vidět řešený problém. V poslední části popisu by zcela jistě neměla chybět informace o tom, v jakých formátech či konkrétně programech se daného algoritmu využívá. Další částí práce budou základní údaje o formátech, především o těch nejběžnějších. Zmínění o tom, jakých kompresních metod využívají, by mělo pomoci uvědomit si způsob vytvoření formátu pomocí znalostí nabytých v předchozí části. Tímto způsobem by si měl každý, kdo bude studovat tuto práci, zafixovat jisté spojitosti nezbytné pro pochopení celé problematiky komprese a kódování dat. Poslední částí, která by měla dotvářet celkový komplex, budou demonstrační programy. Jelikož se jedná o studijní matriál umístěný na internetu, tak je i předpoklad, že programy by mělo být možno spustit pomocí webového prohlížeče. Za tohoto předpokladu přicházely do úvahy jako programovací jazyky Java a Flash. Zvolena je Java, jež se svými aplety umožňuje stejně jako Flash dobré grafické rozhraní, ale navíc je multiplatformní. Jak již bylo uvedeno v úvodní kapitole, velký důraz bude kladen hlavně na názornost ukázek.

4. Vlastní práce 4.1.

Bezztrátová komprese

Bezztrátovou kompresí se rozumí taková, při níž je možno komprimovaná data (text, hudba, grafika) zpětně rekonstruovat tak, že nedojde k žádným změnám vhledem k datům původním. Algoritmy realizující bezeztrátovou kompresi je možné z hlediska počtu průchodů rozdělit na adaptivní a neadaptivní. Adaptivní nebo též dynamické metody prochází zadaná data pouze jednou a již v prvním průchodu je kódují. Naproti tomu metody neadaptivní je prochází poprvé a zjistí četnost výskytu jednotlivých znaků (statické Huffmanovo kódování). Druhým průchodem se data zakódují daným algoritmem.

4.1.1. Slovníkové metody Jedná se o adaptivní metody, které si při průchodu vytváří slovník, jež je poté buď distribuován s kódem, nebo si jej dekompresní algoritmus vytvoří sám, aby bylo možné data převést do původní podoby. Do této skupiny se řadí různé modifikace algoritmu LZ (Lempel-Ziv), které jsou poměrně často využívány v současných formátech.

17

LZ77 LZ77, v některé literatuře označovaný jako LZ1, představila v roce 1977 dvojice Abraham Lempel a Jacob Ziv. Tito nyní izraelští vědci přišli s metodu, která je dodnes modifikována a kombinována s jinými metodami. Podle principu je nazývána metodou posuvného okna. Pro lepší vysvětlení předpokládejme, že budou data reprezentována řetězcem. Posuvné okno (sliding window) je rozděleno na část, kde už jsou zakódovaná data, a na část, kde jsou ta nezakódovaná. Hranice mezi těmito částmi bude nazývána rozmezím. Kódování začíná nastavením sliding window na řetězec, který má být zakódován, tak, že část pro již zakódovaná data je prázdná a druhá část je naplněna řetězcem (netřeba celým). Hledá se shoda co nejdelšího řetězce (počínajíce rozmezím) z nezakódované části s řetězcem v zakódované části. V případě shody je nový podřetězec zakódován uspořádanou trojicí (i,j,a), kde i je pozice prvního znaku v zakódované části, j je délka podřetězce a a nezakódovaný znak, za který se posune rozmezí sliding window. První znak je zakódován jako (0,0,a). kde a je první znak kódovaného řetězce. Výsledným kódem je množina uspořádaných trojic (i,j,a), u kterých je nutné zachování pořadí. Způsob, jakým se kóduje metodou LZ77, ukazuje obrázek 1, kde je posuvné okno nastaveno na náhodně zvoleném řetězci. Zeleně je označena již zakódovaná část, červeně ta nezakódovaná. V tomto případě by dalším krokem bylo zapsání trojice (3,3,x) a poté posunutí rozmezí za znak x (v tomto případě je to čtvrtý znak v nezakódované části).

obrázek 1: Ilustrační ukázka kódování metodou LZ77

Při dekódování je potřeba mít k dispozici uspořádané trojice a stejně velké sliding window jako při kódování. První dvě čísla v trojici udávají index a délku řetězce, který byl již použit. Ten se dohledá a zapíše na výstup. Třetí údaj je znak, jež se přidá na výstup. V našem příkladě by první trojice (0,0,x) byla na výstupu dekódována jako znak x. Jak vyplývá z předchozího, algoritmus je málo účinný tam, kde je výskyt opakování řetězců (dat) nepříliš častý, případně žádný, naopak dosahuje dobrých kompresních poměrů v datech, která se skládají ze shodných podřetězců. Je zřejmé, že čím větší je sliding window, tím větší šance, že se v něm najde shoda.

18

I když je tato metoda relativně stará, stále je používána a to především jako hlavní kompresní algoritmus v programech GZip, Zip, PKZip, jako vedlejší v mnoha dalších (WinRAR nebo 7-Zip).[6] LZ78 Druhá verze algoritmu dvojice Lempel a Ziv (proto někdy nazývána LZ2), jež byla představena o rok později než ta první. Metoda si za běhu vytváří slovník frází. Tento slovník je reprezentován n-árním stromem. I zde se bude pracovat s pojmem rozmezí, za něž je považována hranice mezi zakódovanou a nezakódovanou částí. Prvním krokem je vytvoření kořene stromu, jež bude mít pořadové číslo nula. Poté se začne kódovat zadaný řetězec. Přečte se první znak. Vytvoří se nový uzel s nejnižším dalším pořadovým číslem, v tomto případě jedna, který je spojen s uzlem nula ohodnocenou hranou. Ta má hodnotu znaku, který byl přečten jako první. Tím je zakódován první znak, metoda vytvoří odkaz do slovníku ve tvaru (0,a), kde a je první znak. Dále se přečte druhý znak. Pokud je stejný jako první (tzn. už je ve slovníku jednou kódován), není nutné ho kódovat a tak se k němu přečte další znak. Nyní se hledá, zda je ve slovníku tato dvojice znaků. Pokud by byla, přečetl by se další znak. Tak by se postupovalo, dokud by se nenašla fráze, jež ve slovníku není obsažena. Jinými slovy jde o to najít frázi, která je již ve slovníku, kromě posledního znaku. Tímto posledním znakem se ohodnotí nová hrana, která povede do nového uzlu. Metoda vytvoří odkaz (c,a), kde c je číslo uzlu, ze kterého nová hrana vychází, a a je poslední znak. Poté se posune rozmezí za poslední znak a celý postup se opakuje.

obrázek 2: Příklad vytvoření stromu metodou LZ78

Příklad n-árního stromu naznačuje obrázek 2. V tomto případě je n rovno třem, protože vstupní řetězec (na obrázku vlevo) obsahuje právě tři různé znaky. Čtvrtý krok je zobrazen červeně. Zjistí se, zda vede z kořene stromu hrana s hodnotou y. Je vidět, že ano, proto se algoritmus dostane do uzlu 1. Přidá se další

19

znak a vytvoří se uzel 4, do něhož vede hrana y. Na výstup je zapsána uspořádaná dvojice (1,y), jak je uvedeno níže. Pro zpětnou rekonstrukci je nutné distribuovat jak zakódovaná data, tak i slovník. Podle uspořádané dvojice (c,a) se rozhoduje jak se pohybovat ve stromu – od kořene se prochází strom tak, aby se dosáhlo uzlu c. Podřetězec jedné uspořádané dvojice je složen z hodnot hran, kterými se prochází, a jako poslední znak řetězce je a. Takto se dekóduje každá dvojice (c,a) a z ní se zpět složí celkový řetězec. Tento algoritmus je základem pro LZW, které je využito například v dříve velmi využívaném formátu GIF.[7] LZW Metoda vyvinutá v roce 1984 trojicí Abraham Lempel, Jacob Ziv a Terry Welch (někdy též označovaná jako LZW84). Jedná se o vylepšení algoritmu LZ78. Nebyl příliš využívaný, protože byl na dvacet let patentovaný (patent vypršel v roce 2003).[8] Princip kódování je založen na opakování frází, které jsou již uloženy ve slovníku. Jednotlivé znaky jsou ve slovníku uloženy pod nejmenšími čísly (při kódování ASCII jsou znaky pod čísly 0-255) a další víceznaková spojení jsou pod čísly 256 a výše. To znamená, že každá fráze obsažená ve slovníku je nahrazena přirozeným číslem, nová se tam přidá pod nejmenší volné číslo. Konkrétněji se začíná s proměnou c, která obsahuje první znak řetězce. Další proměnou je řetězec w, která je zatím prázdná. Poté se zjišťuje, zda je spojení w+c ve slovníku. Pokud ano, znak c se přidá k řetězci w a do c se načte další znak v pořadí, na výstup se nic nezapisuje. Pokud ne, zapíše se fráze w+c do slovníku jako nová a na výstup se zapíše číslo řetězce w. Výstupem je tedy řada přirozených čísel. Pro lepší představivost by mohl sloužit obrázek 3, kde je vidět naznačení práce algoritmu LZW. Zelenou barvou jsou označeny jednotlivé znaky umístěné ve slovníku, červeně právě komprimované znaky. Jedná se o druhý krok, kdy je zjištěno, že hodnota xy (w+c) není ve slovníku, proto se tam přidá pod pořadové číslo 4. Na výstup by se v tomto případě zapsala pořadí řetězce uložená v proměnné w, tedy 1.

20

obrázek 3: Ukázka práce algoritmu LZW

Distribuuje se pouze výstupní kód a musí být známy jednoznakové fráze ve slovníku. Dekodér si dokáže vytvořit zbytek slovníku ze zadaných dat sám. Přečte se první index a zjistí se, jaký znak mu odpovídá. Poté se přečte druhý index, který odpovídá opět jednomu znaku. I přes již zmíněné patentování byl používán ve starších programech ZIP, dokumentech PDF a především v grafice jako algoritmus formátů GIF a TIFF.[8]

4.1.2. Statistické metody Do této skupiny patří metody, jejichž princip je založen na pravděpodobnosti výskytu znaků v řetězci (opět se bude pro jednoduchost pracovat s řetězcem). Původně byly neadaptivní (statické), časem vznikly jejich adaptivní modifikace, které umožňují pouze jeden průchod dat k zakódování. Ovšem všechny následující principy budou vysvětleny na původních vybraných statických metodách. Shannon-Fanovo kódování Metoda publikovaná roku 1949 Shannonem a Weawerem a současně nezávisle na nich Fanem. Fano byl učitel Huffmana, který za několik let poté vymyslel metodu, jež vychází z Shannon-Fanova kódování. Jedná o statistickou metodu, proto se bude pracovat s četnostmi výskytů jednotlivých znaků, které se seřadí sestupně (zleva doprava). Z nich se bude vytvářet binární strom, a to od kořene. Ten bude ohodnocen součtem četností všech znaků. Dále se bude dělit na dva listy. Cílem je rozdělit četnosti do obou listů co nejvyváženěji. Poté se levé hraně přiřadí hodnota nula, pravé hodnota jedna. Tento rozklad a ohodnocování bude probíhat do té doby, až budou všechny listy obsahovat četnosti jednotlivých znaků. Kód znaku určíme tak, že budeme procházet vzniklý binární strom od kořene až k danému listu a z nul a jedniček, které se „míjí“, vznikne kód daného znaku.

21

obrázek 4: Ukázka práce Shannon-Fanova kódování

Vytvoření binárního stromu ze zadaného řetězce (zeleně) zobrazuje obrázek 4. Kořen stromu udává počet znaků řetězce, dále se dělí na dvě poloviny, by byl strom vyvážený. Dekódování probíhá opět pomocí binárního stromu sestaveného při kompresi. Pomocí kódu jednotlivých znaků se prochází strom. Kód se čte po číslicích, jednička znamená vpravo, nula vlevo. Pomocí tohoto pravidla je možné najít ke každému kódu odpovídající znak. Metoda dnes není dnes příliš využívána jako hlavní algoritmus, maximálně jako sekundární algoritmus komprese například v programu WinZip.[9] Huffmanovo kódování Tuto metodu představil v roce 1952 David A. Huffman. Vytvořil ji jako domácí úkol místo zkoušky při svých studiích. Základním principem je přiřazování nejkratšího kódu nejčastěji se vyskytujícím znakům. Stejným způsobem uvažoval již o 152 let dříve Samuel Morse, který na stejné zákonitosti postavil způsob kódování anglické abecedy –vznik telegrafní Morseovy abecedy.[10] Při kódování je nejdříve nutné zjistit četnosti jednotlivých znaků a seřadit je vzestupně. Cílem je vytvořit binární strom těchto četností. Jednotlivé četnosti jsou vlastně hodnoty listů stromu. Spojují se vždy dva listy s nejmenšími četnostmi. Jejich spojením vznikne nový list, jehož četnost bude součtem četností listů, z nichž vznikl. Pokud je listů se stejnými četnostmi více než dva, spojí se první dva. Pokud je strom sestaven (zbude jediný uzel), jednotlivé hrany se ohodnotí jedničkami (hrany vpravo) a nulami (hrany vlevo). Kód jednotlivého písmene je hodnota, která je rovna posloupnosti jedniček a nul při průchodu od kořene k listu daného znaku. Kód celého řetězce je složen z kódů písmen, jež je distribuován s Huffmanovým stromem, aby bylo možné provést zpětně dekódování. Ukázkou je práce demonstračního programu (obrázek 5), který pro vstupní řetězec „komprese“ vytvořil binární strom. Jak je vidět, pomocí něj je možné sestavit výstupní kód. Například pro první písmeno řetězce k je 000 – pokaždé je

22

při procházení stromu od kořene zvolena cesta vlevo. Výsledný kód má jednu výraznou výhodu oproti kódům Morseovy abecedy – není třeba oddělovat jednotlivé znaky, protože jejich hodnoty jsou jednoznačně určeny. Takový kód se nazývá bezprefixový.

obrázek 5: Ukázka vytvoření binárního stromu pomocí Huffmanova kódování (Java aplet)

Dekódování probíhá v podstatě opačně. Nejdříve se zjistí, co reprezentují jednotlivé kódy pomocí Huffmanova stromu. Kódy se nahradí znaky, které je reprezentují, a pomocí nich se zrekonstruuje původní řetězec. Metoda je využívána v nejznámějších kompresních programech WinZip a WinRar, ale také v ARJ a JAR.[9] Její využití je i ve ztrátové kompresi, kde se používá například v koncové fázi komprese JPEG.[11] Jedná se o velmi populární algoritmus, a to také proto, že nebyl narozdíl od jiných nikdy patentován. Aritmetické kódování Jde o metodu, která vychází z Huffmanova kódování. I zde hraje nejdůležitější roli při kódování četnost jednotlivých znaků. Je nejmladší metodou ze statistických, které zde byly zmíněny. Komprese probíhá tak, že se nejprve zjistí četnosti výskytu jednotlivých znaků ve vstupním řetězci. Seřadí se podle abecedy. Poté se interval <0,1) rozdělí na jednotlivé podintervaly (všechny polozavřené zleva) v poměru pravděpodobností, tj. četnosti výskytu jednotlivých znaků. První znak v řetězci zúží interval podle jeho pravděpodobnosti. Druhý znak zúží již zmenšený interval naprosto stejným způsobem. Je zřejmé, že čím je znak pravděpodobnější, tím méně ho zúží. Výsledkem je interval, ze kterého se vybere jakýkoliv zlomek a ten je

23

uveden jako číslo v binární soustavě. Distribuuje se dvojkové číslo, délka řetězce a pravděpodobnosti výskytu jednotlivých znaků.

obrázek 6: Ukázka práce aritmetického kódování

Jak ukazuje obrázek 6, první fází je rozdělení intervalu podle četností jednotlivých znaků. Poté se čte první znak vstupního řetězce, který je zařazen do podintervalu (červená čára). Ten se posléze, jak je vidět na obrázku, rozdělí opět dle četností – dojde k přepočítání. Takto se postupuje tolikrát, kolik znaků má vstupní řetězec. Výsledné číslo je pro jednoduchost určeno jako střed konečného intervalu. Dekomprese probíhá tak, že se vybere podinterval tak, aby do něj náležel binární kód. Na výstup se zapíše takový znak, který do tohoto podintervalu podle pravděpodobnosti patří. Takto se pokračuje až se dostaneme k původnímu intervalu <0,1). Aritmetické kódování se samo o sobě téměř nepoužívá, jedině v kombinaci s nějakou jinou, často slovníkovou metodou nebo jako jedna z částí ztrátové komprese JPEG. Navíc je kvůli svým výpočtům poměrně dost náročné na výkon počítače.[2]

24

4.1.3. Ostatní metody Do této podskupiny metod patří ty, které pracují na zcela jiném principu, než jaký byl doposud zmíněn. Statistické metody počítaly četnosti znaků, slovníkové si vytvářely slovník. Avšak žádná zatím nepočítala s opakováním jednoho znaku za sebou. RLE Run Length Encoding neboli proudové kódování je jednou z nejjednodušších a zároveň nejstarších metod, které jsou používány. Existuje více variant kódování touto metodou. Ta základní pracuje tak, že se zakóduje proud jednotlivých znaků, tzn. prochází se řetězec a opakovaný znak je nahradí trojicí Ian, kde I je indikátor komprese (znak nevyskytující se v textu), a je opakující se znak a n počet opakování. Kdyby byl řetězec například wwww, kód by byl Iw4. Z toho je jasné, že se efekt komprese dostaví, až pokud se nějaký znak vyskytuje více než třikrát za sebou, proto se kratší proudy nekódují. Drobným vylepšením umožňujícím kompresi proudů délky až 258 znaků (v předchozím případě pouze 255) je RLE s posunutou stupnicí. Princip je stejný, pouze zápis kódu je trojící Ia(n-3). V předešlém příkladu by bylo výstupem Iw1. V případě, že není možnost využít indikátoru komprese, je možné místo něj použít tři po sobě jdoucí znaky kódovaného proudu a za něj opět zapsat počet opakování zmenšený o tři. Při použití výše zmíněného příkladu by bylo výsledkem www1. Dekódování je velmi intuitivní a záleží na použité variantě. Pokud je nalezen indikátor komprese, zapíše se znak s příslušným počtem opakování na výstup. Jestli je ovšem nalezen pouze znak bez indikátoru, tak se beze změny opíše. Nejčastější využití této metody je v počítačové grafice a to hlavně u obrázků s malou barevnou hloubkou nebo tam, kde jsou velké plochy stejné barvy. Jako hlavní metoda je použita ve formátu PCX, jako vedlejší může být v JPEG nebo TIFF.

4.2.

Využití metod bezztrátové komprese

Metody bezztrátové komprese dat využívají výše zmíněné algoritmy ke kompresi dat, u kterých je požadavek na zpětnou rekonstrukci do původní podoby. Formáty, které jsou dále zmíněny, využívají povětšinou nejeden kompresní algoritmus. Častým jevem vyskytujícím se v praxi je využívání hlavní a vedlejší metody, čímž se mnohdy výrazně zvyšuje kompresní poměr.

25

4.2.1. ZIP Autorem tohoto velmi populárního formátu uřčeného ke kompresi a k archivování dat je Phil Katz, který jej vytvořil pro svůj program PKZIP v roce 1989. I když dnes už k těm nejlepším co se týče kompresního poměru nepatří, stále se řadí k těm nejpopulárnějším. Jedním z kompresních algoritmů, který Katz použil ve svých verzích, je deflate. To je kombinace metody LZ77 a Huffmanova kódování, jež byly detailněji popsány v předchozí kapitole. Pro vytváření a práci s archivy ZIP existuje poměrně dost programů pro různé platformy. Pro Windows je asi nejběžnější WinZip či WinRar (pouze dekomprese), pro Linux je to program Zip. Tento formát podporuje i spousta dalších programů. Většinou lze poznat soubor ve formátu ZIP podle přípony .ZIP, avšak existují i výjimky. Jmenujme například Java archivy s příponou .JAR nebo balíčky pro aplikace Mozilla s příponou .XPI.

4.2.2. RAR Autorem tohoto dnes patentovaného formátu je Eugene Roshal (Roshal ARchive). Dostupný je dekompresní algoritmus v podobě zdrojového kódu, čímž je umožněna aplikace dekodéru do různých programů a mmohaplatformní podpora. Nejznámější program WinRar používá ke kompresi kromě dalších metod také LZ77 a Huffmanovo kódování. Na rozdíl od WinZipu, jehož je největším konkurentem, dokáže opravovat poškozené komprimované soubory. Již zmíněný sharewarový program pro Windows má i v Linuxu svou podobu, která se jmenuje jednoduše Rar. Pomocí takových programů jsou vytvářeny archivy snadno rozpoznatelné podle přípony .RAR, .R00 či nejnověji .RAR3.

4.2.3. PDF Jedná se o formát vyvinutý firmou Adobe (1993) k ukládání dokumentů s koncovkou .PDF (Portable Document File). Hlavním cílem jeho vytvoření byla potřeba, aby se text (včetně obrázků) mohl zobrazovat stejně na různých zařízeních bez ohledu na hardware či programové vybavení. Veškerý text, který se do dokumentu tohoto typu uloží, se zakóduje pomocí slovníkové metody LZW84. Do dokumentu lze uložit jak obrázky, grafy, tabulky tak i další objekty. Programů, jež umožňují práci se soubory ve formátu PDF, existuje mnoho. Avšak přímo společnost Adobe nabízí freewarový nástroj Abobe Reader, který je volně ke stažení. Je pravidelně aktualizován a nejnovější verze přináší i možnost přeformátování dokumentu.

26

4.2.4. GIF Formát vyvinutý v roce 1987 pro rastrovou grafiku (Graphics Interface Format), jehož barevná hloubka je 8 bitů na pixel. Umožňuje umístění několika vrstev na sebe, čehož se dá využít k tvorbě animací. Obrázek ve formátu GIF je, stejně jako dokument PDF, komprimován bezeztrátovou metodou LZW84. Je podporován všemi platformami a dokáže s ním pracovat snad každý prohlížeč obrázků či webový prohlížeč. Byl často využíván pro tvorbu grafiky (především animací) na webu. Díky své velké barevné nevýhodě je dnes nahrazován formátem PNG a dalšími.

4.2.5. PNG Zkratka pochází z anglického Portable Network Graphics (vyslovuje se „ping“). Jedná se o formát, jež má být jakousi náhradou za GIF, který díky své barevné hloubce a patentu na LZW84 (do roku 2004) nebyl optimální. PNG nemá ovšem oproti předchozímu možnost tvorby jednoduchých animací, což v praxi neumožňuje úplné nahrazení GIFu (existují nové formáty, které umožňují i animování, ale ještě se globálně neprosadily). Výhodou PNG je však možnost transparentnosti obrázků. Využívá kompresního algoritmu deflate, což je, jak již bylo zmíněno, kombinace LZ77 a Huffmanova kódování. Je nutné dodat, že se používají ještě různé filtry, které zvyšují kompresní poměr nebo mají další význam. Dnes je podporován téměř všemi nově vydanými grafickými programy, a to jak komerčními (Corel Photo-Paint, Adobe Photoshop), tak volně šířenými. Některé ho používají i jako implicitní formát pro ukládání.

4.2.6. TIFF Další z formátů určených pro ukládání rastrové grafiky - Tagged Image File Format. Vyvinut byl firmou Aldus v roce 1986. Dnes je velice vhodný pro ukládání obrázků bez ztráty informace. Umožňuje to je jeho bezztrátová komprese – většinou se používá LZW84, RLE a další algoritmy, ale nemusí být komprimován vůbec. Tím pochopitelně vzniká i problém s případnou kompatibilitou, což může způsobit problémy při otevírání souborů v různých programech. Je podporován všemi platformami, většina prohlížečů obrázků jej podporuje. Oproti ostatním má jednu obrovskou výhodu, a to takovou, že umožňuje uložení několika bitmapových obrázků do jednoho souboru.

27

4.2.7. PCX Firma Soft vytvořila tento formát pro svou aplikaci PC Paintbrush. Dnes na něj licenci vlastní Microsoft. Formát je proto určen především pro operační systémy Windows. Kompresní algoritmus buď není vůbec použit, nebo je soubor komprimován proudovým kódováním – RLE, jež dosahuje při kompresi jednoduchých bitových map dobrých výsledků co se týče kompresního poměru.

4.3.

Ztrátová komprese

Metody ztrátové komprese jsou charakteristické především tím, že neprobíhá zpětné dekódování, protože by nebylo dosaženo původní podoby dat. Často se komprese dosáhne tím, že se vypustí informace, která je nadbytečná z hlediska vnímatelnosti lidských smyslů. Proto jsou tyto metody používány v oblasti počítačové grafiky, hudby a videa.

4.3.1. Grafika S obrázky (grafickou informací) se setkává běžný uživatel počítače denně. Jelikož jejich objem bývá mnohdy velký, je nutná komprese, která zmenší velikost souborů na přijatelnější hodnotu. K tomu slouží velmi často následující metody. Diskrétní kosinová transformace Často se vyskytuje, jak v literatuře, tak na internetu, zkratka DCT z anglického názvu této metody. Jedná se o ztrátovou metodu, která má však i svou bezeztrátovou verzi. Ta zde ovšem nebude řešena. Princip kódování je založen na potlačování rozdílů v blízkých barvách. Z obrazu je vyňata ta část, která je pro lidské oko nepostřehnutelná, čímž je možné dosáhnout komprese až 75 procent. Již podle názvu je zřejmé, že se obraz transformuje. Pokud má několik sousedních pixelů podobnou barvu, tak se nahradí jednou společnou, jež je průměrem barev původních (přepočet). Snad nejběžnějším použitím této metody je ve formátu JPEG, který je dnes velmi často používán v oblasti rastrové grafiky.[2] JPEG Jeden z nejpopulárnějších grafických formátů je Joint Photographic Experts Group (zkratka JPEG). Jedná se v podstatě i o způsob uložení obrazové informace čili o kompresní algoritmus.

28

Jak již bylo řečeno, ztrátová komprese využívá nedokonalosti lidského oka, které je citlivé na změny jasu a intenzity barev, ale hůře postřehne drobnou změnu barvy. Toho právě JPEG využívá. Komprese by se dala shrnout do čtyř částí.[2] První z nich je transformace barev z RGB do YUV. Právě zde totiž dochází k oddělení barevných složek (U a V) a složky jasu (Y). Jas se nemění, protože by to člověk postřehnul, tudíž složka Y zůstává beze změny. Pracuje se tedy již pouze s barvami, které se v dalším kroku tzv. podvzorkují. Jedná se o redukci barev přepočtem v horizontálním a ve vertikálním směru v poměrech 2:1 (svisle se někdy barvy nemění). Po tomto postupu se obraz rozdělí na čtverce o straně 8 bodů a aplikuje se na něj diskrétní kosinová transformace, jejíž princip je uveden výše. Výsledkem je opět čtverec stejné velikosti, ale transformovaný tak, že důležité barevné informace jsou v levém horním rohu čtverce, se stoupající vzdáleností důležitost barevných informací klesá. Již nevratnou fází ztrátové komprese je kvantifikování. Jedná se o vydělení frekvencí jednotlivých čtverců kvantifikačními koeficienty (součást kvantifikační matice) a následné zaokrouhlení na celé číslo. Vzniknou matice, které se převedou jistým způsobem na posloupnost čísel a ta se zakóduje buď Huffmanovým, nebo aritmetickým kódováním. Soubor se distribuuje s informacemi o kódování a s kvantifikační tabulkou v hlavičce. Vysvětlením principu fungování kompresního algoritmu JPEG se dostáváme k JPEG jako k formátu. Jeho kompresní poměr je velmi dobrý, uvádí se komprese 20:1.[2] Jistě každý uživatel ocení, že si ve většině programů může nastavit, jak moc chce obrázek komprimovat. Zde se dostáváme k pojmu Q faktor. Pokud je nastaven na 1, tak se jedná o velmi nízký stupeň komprese, pokud na 100, jde o maximální možnou kompresi. Tímto nastavením Q faktoru se zvolí stupeň kvantifikování (kvantifikační matice). Komprese metodou JPEG je vhodná pro obrázky s velkou barevnou hloubkou (24 bitů na pixel). Je tedy velice vhodná pro barevné fotografie, kde se používá asi nejčastěji. Avšak velice nevhodným použitím by bylo na obrázek, který má mnoho velkých jednobarevných ploch či ostrých přechodů. Jedná se v současnosti o velice populární formát, proto je podporován téměř všemi aplikacemi, ať už běží pod jakýmkoli operačním systémem.

4.3.2. Video V dnešní době, kdy jsou různé přenosné přehrávače v kursu, je komprese videa nezbytná, protože není potřeba tak velký úložný prostor pro data, a tím se

29

snižují náklady na výrobu, což dělá přehrávače dostupnější. Do této kapitoly jsou zahrnuty i multimediální kontejnery, které kromě videa obsahují i jiná data. MPEG[2] Jedná se o zkratku Moving Picture Expert Group, která označuje skupinu zabývající se standardy komprese obrazové informace a také zvukové stopy. V současnosti jsou používány tři standardy, se kterými může uživatel přijít do styku – MPEG-1, MPEG-2, MPEG-4. Prvním z nich je MPEG-1, který je vytvořen pro datové přenosy od 0,9 do 1,5 Mb/s (CD). MPEG-2 je navržený pro DVD video, dálkový a satelitní přenos s rychlostí až 15 Mb/s. MPEG-4 je standardizován pro nízkou rychlost přenosu (modem), rozšiřuje MPEG-1 o 3D obsah a další vylepšení. Vysvětlení komprese proběhne na prvním standardu. Komprese obrazu MPEG-1 probíhá obdobně jako u JPEGu. Snímky jsou převedeny do barevného formátu YUV, kde se opět mění pouze barevné složky, přičemž jas zůstává nezměněn (psychoakustický model). Dále se obrazová informace rozdělí na čtverce o straně 8 pixelů, na něž se aplikuje diskrétní kosinová transformace. Následným krokem je kvantifikování. Takto probíhá komprese statického obrazu, ovšem je zřejmé, že v případě videa by tento způsob nedosahoval příliš dobrých výsledků. Částí navíc oproti kompresi JPEG jsou pohybové vektory. Vznikají na základě rozdílu snímku aktuálního oproti snímku předchozímu. Spolu s kvantifikovanými koeficienty jsou v poslední fázi komprimovány Huffmanovým kódem. MPEG-1 používá tři druhy snímků. Prvním z nich je snímek typu I – intraframe. Jedná se o běžný statický snímek, který nemá žádnou informaci o snímku předchozím (příkladem může být první snímek videa). Dalším je typ P – predicted, který v sobě obsahuje odkaz na předchozí snímek (typu I nebo P) a také pohybové vektory – údaj o tom, jak se části snímku změnily. Posledním třetím typem je B – bidirectional, což je snímek obousměrný. Ten potřebuje znát informaci o nejbližším snímku předchozím a následném, z jejichž pohybových vektorů vytvoří průměrováním nejlepší přechod. Snímky, se kterými typ B pracuje, musí být typu I nebo P. Nejhoršího kompresního poměru je logicky dosaženo u typu I, jelikož se jedná v podstatě o obrázek. Typ P dosahuje lepších výsledků – je zde obsažena informace o předchozím snímku a pohybový vektor, nejlépe je na tom s kompresním poměrem typ B, který obsahuje dva pohybové vektory. Je tudíž žádoucí používat co nejvíce snímků B, aby byl celkový kompresní poměr co nejnižší. Většinou vypadá struktura posloupnosti snímků tak, jak to zobrazuje obrázek 7.

30

obrázek 7: Posloupnost snímků MPEG-1[2]

Zde je vidět, že pro zobrazení snímku I není potřeba informace o jiném snímku (nevede do něj žádná šipka). Pro zobrazení snímku P je potřeba znát předchozí snímek I nebo P (zelené šipky). Ke snímkům typu B jsou zapotřebí snímky předchozí (červené šipky) a následující (modré šipky). Dekomprese souborů, jež používají normu MPEG-1, probíhá při vlastně při přehrávání. Je podstatně rychlejší než komprese, což znamená, že se jedná o asymetrickou kompresi dat. Jakmile se začne přehrávat video soubor, načte se první snímek (I), následuje snímek B, který potřebuje znát následující snímek P, tudíž se načte i P. Informace o snímku I se udržují do té doby, dokud s ním pracuje nějaký další snímek, poté se vypustí. Tímto způsobem dojde k přehrání celého videa. MPEG-2 je určený především pro přehrávání filmů v DVD kvalitě. Je používán pro digitální televizní vysílání v některých státech. Ovšem dříve či později bude pravděpodobně nahrazen MPEG-4. Tento standard je zatím používán pro přehrávání videa především na internetu či v kapesních přehrávačích, ale především svou vyšší kvalitou a menší velikostí souborů má předpoklady nahradit MPEG-1 i MPEG-2. Hodně se o něm mluví v souvislosti s digitálním vysíláním v ČR. MP4 V dnešní době jde o velmi známý a skloňovaný výraz, k jehož popularitě hodně přispěly přenosné přehrávače pracující s tímto formátem. Jde o tzv. multimediální kontejner, který je součástí nejnovějšího standardu MPEG-4. Může obsahovat menu, titulky (i více), 3D objekty, audio a video soubory. Videosignál může být ale uložen v jakémkoliv standardu MPEG, zvuk buď ve formátu MP3 nebo AAC. Existuje oficiální modifikace, která je určená pro přenos hovorů v mobilních telefonech, ta používá ke kompresi zvuku formát AMR.

31

WMV Windows Media Video je souborový videoformát, který byl standardizován v roce 2006. Byl vytvořen firmou Microsoft a je chráněn zákonem. Soubory tohoto typu lze přehrávat pomocí mnoha přehrávačů, z nichž nejznámější jsou Windows Media Player a PowerDVD.

4.3.3. Zvuk Není již třeba opakovat nutnost komprese zvukových souborů. Existuje řada formátů, které se svou účinností liší podle druhu zvukových dat. Používá se psychoakustický model, který počítá s nedokonalostí lidského sluchu. Rozlišují se formáty, které jsou vhodnější pro hudbu či pro mluvené slovo. AMR Jedná se o formát a zároveň o komprimační algoritmus, který je velmi vhodný pro kompresi mluveného slova. Často se s ním setkáváme v mobilních telefonech, kde jsou do souborů typů AMR ukládány hlasové záznamy – diktafon, zvuk v MMS zprávách. MP3 Jedná se o velmi populární formát, který je standardem MPEG-1 pro kompresi zvukové části videozáznamu. Za svou oblíbenost vděčí především schopnosti uchovat záznam v poměrně vysoké kvalitě při nízké velikosti souboru (zmenšení zhruba desetkrát). Základním předpokladem jsou možnosti slyšitelnosti lidského ucha. To je možné vnímat frekvence asi 20Hz až 20kHz[12] a dynamický rozsah 96dB. Proto se mohou například vyšší frekvence než 20kHz vypustit. Dále se při kódování využívá frekvenčního a časového maskování. Pokud jsou zároveň přehrávány dva zvukové signály, ten slabší se může jednoduše vypustit, protože nebude slyšet (frekvenční maskování). Časové maskování je založeno na setrvačnosti vjemu zvuku. V případě, že jsou přehrávány dva signály a následně se ten silnější vypne, ucho ho slyší ještě nějakou dobu po vypnutí. Komprese je poté podpořena dalšími prostředky. Datový tok se u souboru MP3 pohybuje v rozmezí 32kb/s až 320kb/s. Je nutností uvést i další hudební formáty, jež jsou součástí MPEG-1. Jsou jimi MP1 a MP2. Druhý uvedený se používá především pro kompresi zvuku u Video CD. Tvoří základ pro formát MP3.

32

AAC O tomto formátu se mluví jako o budoucím nástupci MP3, protože kvalita komprese hudebních souborů je o dost lepší, navíc jejich výsledná velikost je až o 30 procent menší. AAC je standardizován v MPEG-2 a MPEG-4, avšak není zpětně kompatibilní s MPEG-1. Distribuovat soubory s koncovkou .AAC není problémové, avšak jakékoliv kodéry či přehrávače umožňující přehrávat tento formát musí počítat s patentem, kterým je postižen. V současnosti je využíván jako komprese audio souborů v produktech firmy Apple (například iPod), v kontejnerech MP4 v telefonech Sony Ericsson nebo v Sony Playstation 3. WMA Jedná se formát vyvinutý firmou Microsoft, který měl nahradit formát MP3 v systémech Windows (z důvodů placení poplatků). Kvalita hudebních souborů je velmi dobrá, jedná se o velmi schopného konkurenta AAC.

4.4.

Demonstrační aplety vybraných metod 4.4.1. Huffmanovo kódování

Prvním z dvojice demonstračních apletů je ukázka principu Huffmanova kódování. Program pracuje podle myšlenky popsané v charakteristice této metody. Nejprve ale k popisu struktury. Cílem byla tvorba apletu, proto byla vytvořena třída Huffman, která je potomkem již předdefinované třídy Applet. Tak je možnost využívat metody typické pro aplety. První z nich je init(). Zde se definují příkazy, jež se mají provést při spuštění apletu. V tomto případě se vykreslí úvodní formulář se všemi tlačítky, nadpisy a textové pole, do kterého je možné zadat vstupní řetězec (viz obrázek 8).

obrázek 8: Úvodní stránka apletu Huffmanova kódování

Klíčovou metodou je paint(Graphics g), pomocí níž vykreslujeme veškeré útvary včetně textu. Jelikož aplet by měl být názorný, vhodné bylo použít

33

krokování – použití tlačítek Další krok a Krok zpět. Krokování je programově řešeno přes logické proměnné, pomocí nichž je řečeno vykreslovací metodě, co má provést. Zadáním vstupního řetězce do textového pole a následným stiskem tlačítka Start je přiřazena hodnota true proměnné startKrokovani, která umožní vypsání jednotlivých znaků včetně jejich absolutních četností – listů binárního stromu, jak to zobrazuje obrázek 9.

obrázek 9: Vypsání znaků a jejich četností

Nyní je už možné provádět hlavní činnost, a tou je vytvoření binárního stromu. Začne spojování připravených listů a to ty s nejmenší četností. Pokud je jich víc (náš případ), spojí se dva první. Postupuje se tak do té doby, až zbude jen jeden list. Při vytváření stromu se navíc ohodnocují hrany - levé nulou, pravé jedničkou. Vytvořený strom včetně ohodnocených hran ukazuje obrázek 10.

obrázek 10: Vytvoření Huffmanova binárního stromu

Výsledný uzel je ohodnocen součtem četností všech znaků, což je vlastně počet písmen řetězce. Jak je vidět, listy stromu mají dvě barvy – buď žlutou (aktivní)

34

nebo černou (neaktivní). Posledním krokem je vypsání binárního kódu. Jelikož je pro každý nově vytvořený uzel evidován v poli tříd ListStromu, je možné zpětně sestavit posloupnost jedniček a nul. Tato posloupnost se vytvoří pro každý znak a posléze pro celý řetězec.

4.4.2. Aritmetické kódování Druhým z dvojice ukázkových programů je aplet naznačující kompresi aritmetickým kódováním. Základní metody jsou popsány u příkladu výše a není již třeba zmiňovat jejich význam. Aritmetické kódování funguje na principu zužování intervalu <0,1). K tomu, aby bylo možné jej zmenšit, je nutností ho rozdělit v poměru četností jednotlivých znaků. Důležitými informacemi, které jsou tedy pro začátek potřeba je zjištění četnosti znaků, seřazení dle abecedy a poté určení relativních kumulativních četností. To názorně ukazuje obrázek 11, kde jsou četnosti při vypisování zaokrouhlovány na 3 desetinná místa.

obrázek 11: Zjištění základních údajů při aritmetickém kódování

Takto vzniknuvší přehled je navíc doplněn o svislou osu, která je rozdělena na jednotlivé podintervaly. Všechno toto se objeví po zadání vstupního řetězce a stisknutí tlačítka Start. Pokračovat je možné stiskem tlačítka Další krok. Ten zapříčiní přečtení prvního znaku vstupního řetězce, vybrání podintervalu, do kterého příslušný znak náleží, a následné zmenšení (obrázek 12).

35

obrázek 12: Ukázka zúžení intervalu aritmetického kódování

Takto probíhá kódování dokud se neprojde po znacích celý vstupní řetězec. Výsledkem je jakékoliv číslo ležící v posledním intervalu. V našem případě se určí výsledný interval a poté se prostým výpočtem určí střed intervalu, tj. výsledné číslo. Všechny tyto informace jsou zobrazeny v tabulce vpravo, jak ukazuje obrázek 13.

36

obrázek 13: Výsledek apletu aritmetického kódování

Aplet má ve webovém prohlížeči rozměry 2000 na 750 pixelů, což umožňuje viditelně zobrazit až 30 druhů jednotlivých znaků. Ovšem při stále rostoucím odstupu os, které jsou níže vykreslovány, by tento rozsah nebylo možné zobrazit. Z tohoto důvodu není možné pomocí demonstračního programu zakódovat přehledně delší řetězce.

37

5. Závěr V úvodní části je vysvětlena problematika bezztrátové komprese, jejíž principy jsou na rozdíl od ztrátové lépe představitelné. Především způsob komprese a následné dekomprese, ale i doplňující informace o autorech, případně další zajímavé údaje dotváří ucelený pohled na jednotlivé metody. Velmi užitečná je navazující podkapitola, kde je možné si získané znalosti uložit do širších souvislostí. Čtenář se tak dozví, které formáty ukládají data bezztrátově a jakou metodu, případně metody k tomu používají. Tato kapitola je poměrně podrobně řešena, principy algoritmů jsou jasně vysvětleny. Existuje jich však více než je uvedeno, jedná se o jejich kombinace či vylepšení, avšak všechny zde neuvedené jsou mimo rámec obsahu předmětu Komprimace a šifrování, pro který je tento výukový materiál určen. Ztrátová komprese je rozebírána v druhé části práce. Zde se většinou pojmy algoritmy a formáty slučují, protože většina algoritmů vede k vytvoření formátu stejného názvu. Zevrubněji jsou zde řešeny pouze ty významné, co se týče grafické, hudební a video komprimace. Pouze informativně je zde řešena většina algoritmů, jelikož jejich přesné principy by způsobily zabíhání do přílišných detailů. Zde je důležité naznačení principů a u každého typu dat (grafika, hudba, video) podrobněji popsat způsob komprese, aby si čtenář uvědomil, jakým přístupem dochází ke komprimaci konkrétního typu dat. Demonstrační programy nesou názornou ukázku práce Huffmanova a aritmetického kódování. Základní nastínění způsobu, jakým byly aplety vytvořeny, práce jednotlivých metod a řešení drobných problémů ukazuje rozdíl mezi slovní a programovou interpretací. Pro lepší názornost jsou vloženy obrázky, které zobrazují grafické řešení. Samozřejmostí je popis postupu, jakým se dojde k výslednému kódu. Že tato práce není vyčerpávající, již řečeno bylo. V budoucnu by bylo tuto práci velmi vhodné rozšířit o informace týkající se novějších verzí metod, kombinací algoritmů a také metod nově vzniklých. Údaje o formátech ztrátové komprese a způsobu jejich vzniku by mohly být rozšířeny o detailnější popis komprese a následné dekomprese. Co se týče praktické části, bylo by minimálně vhodné vybrat si několik metod, které jsou často používány, a experimentálním způsobem porovnat jejich kvality co se týče kompresního poměru a rychlosti komprese a dekomprese. Výsledky by se daly zpracovat a použít jako statistický materiál. Jistě dalším dobrým krokem by byla implementace některých dalších algoritmů. Vhodnými kandidáty byly slovníkové metody či metoda RLE.

38

Výsledkem studia odborné literatury a konzultací je materiál, který svým pojetím dokáže obeznámit čtenáře poutavou formou se základy kódování a komprese dat. Prostudováním této práce si člověk, který se s metodami dříve nikdy neseznámil, udělá ucelenou představu, jež bude odrazový můstek pro hlubší studium dané problematiky. Student předmětu Komprimace a šifrování jistě ocení studijní oporu, která mu pomůže při studiu odstranit nejasnosti, případně ověří výsledek kódování pomocí apletu.

39

6. Literatura [1] [2] [3]

[4] [5] [6]

[7] [8] [9] [10]

[11]

[12]

40

PECINOVSKÝ, J. Archivace a komprimace dat. 1. vyd. Praha: Grada Publishing, 2003. 116 s. Snadno a rychle. ISBN 80-247-0659-8. MORKES, D. Komprimační a archivační programy. 1. vyd. Praha: Computer Press, 1998. 179 s. ISBN 80-7226-089-8. Objektově orientované programování. Dokument dostupný na internetu: http://cs.wikipedia.org/wiki/Objektov%C4%9B_orientovan%C3%A9_pr ogramov%C3%A1n%C3%AD. HEROUT, P. Učebnice jazyka Java. 2. vyd. České Budějovice: KOPP, 2000. 349 s. ISBN 80-7232-115-3. Netbeans. Dokument ve formátu HTML dostupný na internetu: http://cs.wikipedia.org/wiki/Netbeans. BALÍK, M. a kol. LZ-77. Dokument ve formátu HTML dostupný na internetu: http://www.stringology.org/DataCompression/lz77/index_cs.html. Lempel-Ziv-78 (LZ78). Dokument ve formátu HTML dostupný na internetu: http://www.binaryessence.com/dct/en000140.htm. LZW84. Dokument dostupný na internetu: http://cs.wikipedia.org/wiki/LZW84. Compression Programs. Dokument ve formátu HTML dostupný na internetu: http://www.maximumcompression.com/programs.php. BENEŠ, M. Huffmanovo kódování. Dokument ve formátu HTML dostupný na internetu: http://www.cs.vsb.cz/benes/vyuka/pte/texty/komprese/ch02s02.html. Huffmanovo kódování. Dokument ve formátu HTML dostupný na internetu: http://cs.wikipedia.org/wiki/Huffmanovo_k%C3%B3dov%C3%A1n%C3 %AD. ČEŠKOVÁ, M. Hudba na počítači v rekordním čase. 1. vyd. Praha: Grada Publishing, 2003. 84 s. ISBN 80-247-0811-6.