I když paměťová média mají stále
větší kapacitu a neustále klesá cena uložení jednotky informace, potřeba
úsporného ukládání dat je stále aktuální. Jde zejména o hospodárnější
distribuci programů a dat a o lepší využití telekomunikačních kanálů.
Navíc moderní techniky ztrátové komprese umožňují vznik zcela nových
aplikací jako je digitální záznam videa či přenos telefonních a jiných
zvukových zpráv.
Algoritmy na redukci objemu dat
se dají rozdělit na dvě velké skupiny:
Bezztrátová komprese, kdy
komprimovaná data po dekomprimaci jsou naprosto totožná s daty před
komprimací, nedochází tedy ke ztrátě informací.
Ztrátová komprese se uplatňuje
u obrazových a zvukových dat. Výsledek po dekomprimaci komprimovaných
dat se sice nerovná původním datům, je jim však velice podobný a s
ohledem na nedokonalost lidských smyslů je rozdíl nevýznamný. Cílem je
ukládat data úsporně a dosáhnout toho, aby rozdíl mezi uloženými a
původními daty byl téměř nepostřehnutelný.
Bezztrátová komprese
Bezztrátová komprese je použitelná
pro všechny druhy dat (texty, obrázky, zvuky apod.) bez rozdílu.
Cenou univerzální použitelnosti je však omezená účinnost, která se
vyjadřuje poměrem velikosti originální a redukované verze dat, jež v
průměru dosahuje zhruba 2 : 1 (výsledek pochopitelně závisí na konkrétních
datech).
Bezztrátová komprese nachází
uplatnění v řadě oblastí. V dalším textu jsou tyto oblasti popsány.
Zálohování a archivace
Zálohování a archivace se provádí na
pásku či disk pomocí zálohovacích a archivačních programů, které
mají díky kompresi šetřit prostor na médiu a čas potřebný pro uložení dat,
neboť zálohovací média jsou obvykle pomalá. Komprese se provádí pomocí
programů užívajících univerzální kompresní algoritmy a též hardwarově na
řadiči příslušného zařízení (streamru). Smyslem zálohování a archivace je
především vytvářet záložní média a záložní data pro případ obnovy omylem
smazaných dat či havárie.
Pro zálohování se používá
rozšířených utilit (WinZip, Arj, Rar a dalších). Jejich užití je
jednoduché, jsou dostupné (řada z nich jsou sharewary) a některé jsou pro
nekomerční účely použitelné i zdarma.
Komprese disků za provozu (on-line)
byla před několika lety oblíbená, dnes při dostupnosti disků o velké
kapacitě prakticky zmizela. Jde o kompresi, která se provádí v
procesu ukládání dat souborovým podsystémem operačního systému. Její
algoritmus musí být dostatečně rychlý, čehož se dociluje za cenu
účinnosti.
Velice oblíbeným produktem byl
Stacker firmy Stac Electronics. Firma Microsoft pro DOS 6.0 vyvinula
systém DoubleSpace, který později (po právních sporech o patentová práva)
předělala a přejmenovala na DriveSpace (ten je součástí i Windows 95). Ve
všech uvedených programech se provádí komprimace disku najednou.
Komprimované disky jsou citlivější na poruchy a havárie a data na
komprimovaných discích jsou pro jiné operační systémy (např. Windows NT)
nedostupná.
Komprese dat je obvykle přímo
vestavěná do používaných komunikačních prostředků. Vzhledem ke stále
omezeným kapacitám telekomunikačních linek je komprese při přenosu dat
velmi důležitá. Komprese je prováděna jednak technickými prostředky a
jednak programovou nadstavbou. Modemy mají kompresní metodu přímo
zahrnutou v protokolech. Pokud se však přenášejí data komprimovaná
jinou metodou, k žádné další kompresi již nedojde.
Obrazová data jsou přímo vzorová pro
kompresi, právě proto se zde datová redukce užívá nejčastěji. Bitmapové
obrázky zejména většího rozměru mají nároky na velikost souboru téměř
neúnosné a přitom datová redukce je zde obvykle velice účinná.
Užívá se různých metod, které
vycházejí z různých nároků obrazů. Zcela odlišnou charakteristiku mají
např. černobílý fax, ruční kresba nebo digitalizovaná fotografie. Užívají
se jak metody bezztrátové, tak i ztrátové.
Pro barevné fotografie ve vysokém
rozlišení se často užívají ztrátové metody. Pro obrázky černobílé či s
malou paletou barev (do 256) se hodí metody bezztrátové. Pro obrázky typu
ruční černobílá kresba nebo fax se hodí jednoduché komprimační metody,
protože tyto obrázky obsahují velké bílé plochy.
V komprimaci barevných obrázků vede
algoritmus LZW, který je využíván v řadě grafických formátů (zejm.
TIFF a GIF), jeho nevýhodou je však jeho patentová ochrana. Zejména z
těchto důvodů byl vyvinut nový grafických formát PNG (Portable Network
Graphics).
Ztrátová komprese se užívá pro
záznam fotografií ve vysokém rozlišení, přenos zvuku či videa.
Vzhledem k vysokému rozlišení by byl výsledný objem informací tak
rozsáhlý, že by bylo prakticky nemožné tyto informace ukládat a
zpracovávat. Vyvíjejí se proto techniky ztrátové komprese, které
respektují vlastnosti přenášených dat a způsoby jejich vnímání lidskými
smysly.
Nejjednodušší typy ztrátové komprese
se užívají u fotografií. Využívá se zde nedokonalostí lidského oka podobně
jako u řešení barevné televize. Metoda fraktálové komprese „hledá” v
obrázku útvary podobné fraktálovým obrazcům, které lze popsat několika
málo parametry. Využívá toho, že řada objektů reálného světa vykazuje
soběpodobnost - má „fraktálových charakter”.
Významnou vlastností ztrátové
komprese je možnost široce parametrizovat redukci a získávat tak různě
kvalitní výsledky. Lze tedy si předem stanovit procento ztráty informace,
výsledek redukce si prohlédnout, posoudit a vybrat si pak redukci, která
přináší nejlepší výsledky z hlediska kompresního poměru a stupně zkreslení
obrázku. Těchto způsobů užívá např. obrazový
formát pro ukládání fotografií JPEG.
JPEG v první řadě není
přímo algoritmus, ale je to standard, který vyvinula Joint Photographic
Expert Group – standard, a popisuje mechanizmus jak za pomocí konkrétní
transformace (DCT) lze převést data z bitmapy t.j rastrového formátu do
tzv. frekvenčního formátu, který lze popsat matematickým vzorcem, jenž je
docela snadno přenosný.
klasická
bitmapa bmp
zkomprimovaný obraz
Pix1: R=250
| G=15 | B=0
R = 250 –
50*x
Pix2: R=200
| G=30 | B=0
G = 15 +
15*x
Pix3: R=150
| G=45 | B=0
B = 0 + 0*x
Pix4: R=100
| G=60 | B=0
Pix5: R=50
| G=75 | B=0
Všechny osoby a charaktery v této tabulce jsou zcela
vymyšleny a neodpovídají skutečnosti... Je ale doufám zřejmé, co je
podstatou ukládání dat za pomoci různých algoritmů, tj. že při bitmapových
datech(vlevo) musíme na cílový počítač přenášet informace o hodnotě třeba
kanálu R pro každý(!) bod v řádku, pomocí funkce(vpravo) přenášíme jen pár
koeficientů této funkce(x je pozice konkrétního bodu)
Pečlivému pozorovateli neunikne hned první nevýhoda JPEG formátu a to že
obrázek jako takový se nedá rovnou zobrazit ale je nutné jej vypočítat! To
jest přijatá data jsou víceméně pouze sada vzorečků, z nichž je nutno
získat pozici a zastoupení RGB složek pro každý pixel, aby to pak
zobrazovací systém, pracující více méně jen s hodnotami RGB, dovedl
zobrazit.
Jak to tedy vlastně funguje:
Protože JPEG standard je chráněn ISO a ITU Copyrightem není možné
uveřejnit přesný popis. Ale pro pochopení si ukážema
schéma, které kdysi popsal Tom Lane:
Krok 1 : Transformace obrázku do vhodného systému
barev:
RGB --> HSL
smyslem této procedury je fakt, že lidské oko je schopno
rozlišit velice přesně změny na ose L (lightness na obrázku vpravo) -
v odstínu barvy, ale velice špatně vnímá změny na osách S a H(saturation a
hue), které definují barvu jako takovou. Důsledkem takovéto transformace
je skutečnost, že pak si můžeme dovolit velice silnou kompresi a ztráty
dat na osách S a H aniž by si toho pozorovatel obrázku všiml.
U zvukových dat se při
redukci vychází z frekvenční analýzy a vhodným způsobem se vybírají jen ty
frekvence, které jsou pro lidské ucho nejdůležitější. Vždy je důležitý cíl
- je to buď maximální redukce záznamu bez nároků na vyšší kvalitu, anebo
zachování co nejvyšší kvality při stanovené maximální horní hranice
kapacity přenosového kanálu.
Nejnáročnější je komprese
pohyblivého obrazu se zvukovým doprovodem (video sekvence). Vychází se zde
z toho, že sousední obrázky v rámci jednoho záběru se liší jen na omezené
ploše, vybere se proto „zajímavá oblast” obrázku a aplikuje se ztrátová
komprese. Tuto technologii pochopitelně nelze aplikovat na hranici dvou
záběrů nebo při prudké změně scény. Protože však lidské oko je méně
citlivé než ucho, krátké pozdržení předchozího obrazu neruší tak jako
výpadek zvuku. To ovšem klade vysoké nároky na udržování plynulého
zvukového doprovodu při přehrávání digitálního videa.
Některé metody ztrátové komprese se
uplatňují pro kompresi i dekompresi v reálném čase, jiné potřebují delší
dobu komprese, která se musí provádět odděleně. Platí to především pro
kompresi videa, která je výpočetně velice náročná. Příkladem takové
komprese je MPEG.
MP3
Formát MP3 je pouze jedním z řady Mpeg formátů. Původně
byl formát MPEG používán pro vysokou kompresi videa a už málo kdo ví, že
byl a je používán také k vysoké a velmi kvalitní kompresi zvuku. Formát MP3
byl zaveden jako standard, ale formát MP3 nachází postupně své konkurenty
jako např. VQ, A2b aj. Principem souborů MP3 je komprese Mpeg Audio Layer
3 (layer=vrstva). Mezi hlavní rys MP3 souboru je standard : komprese
stereo WAV souboru do MP3 souboru - 44 kHz ,stereo, 16 bit., 128kB/s.
Tento soubor MP3 má kvalitu blížící se k AUDIO CD. Soubory WAV ve stejné
kvalitě jako CD se dají získat grabováním z CD (což je bezztrátové) nebo
pomocí nahrávání LINE IN (zde už dochází k dosti velkému zkreslení) Mezi
největší výhody MP3 patří : velikost souboru - komprese při CD
kvalitě 12:1. Skladba, která trvá 4 minuty zabere na pevném disku
přibližně 40 MB (ve formátu WAV - 44 Khz, 16bit., stereo), po kompresi asi
4 MB (ve formátu MP3 - 44Khz, 16bit.,stereo, 128 Kb/s). Na jeden
CD-ROM (700) lze tedy uložit přibližně 700 minut záznamu zvuku v CD
kvalitě (to je 14 alb po 50 minutách).
Princip MP3 formátu se dá popsat takto
: datový tok MPEG je 1.5 Mb/s - z toho je 1.2 Mb/s pro video data
a 0.3 Mb/s pro audio data. Pro docela důležité srovnání, datový tok u CD
(stereo,16bit a 44,1 kHz) je 1.4 Mb/s. MPEG podporuje kompresní
poměry od 1:2.7 až po 1:24. S kompresním poměrem 1:6 (256 Kb/s.) i ten
nejlepší sluchový analytik má problém rozeznat výsledný komprimovaný
soubor od původního originálu. Jde zde vlastně o podobný princip jako u
např. komprimaci JPEG grafického formátu (I když principy jsou zde
rozdílné)
Další důležítý pojem v MPEG formátu je
psychoakustický model. V podstatě jde o stejný klam, jako např. u
grafického formátu JPEG - prostě se vynechají detaily, kterých si stejně
nikdo nevšimne. Průměrné lidské ucho je schopno zachytit zvuk v těchto
mezích: frekvenční rozsah 20Hz - 20kHz, dynamický rozsah (ticho - hluk)
asi 98 dB.
Metoda FREQUENCE MASKING je založena na
tom, že lidské ucho není schopné rozlišit signál slabší, který tak
zanikne. Druhá metoda zvaná TEMPORAL MASKING je
založena na vjemu zvuku. třeba, když se bude přehrávat frekvenční
signál 1 kHz o hlasitosti 60dB a k němu ještě tón 1.1 kHz o hlasitosti 40
dB, bude tón překryt a bude neslyšitelný.
Je metoda založená na zjišťování
opakujících se znaků. Je to algoritmus jednoduchý, rychlý, avšak s
nikterak výraznými výsledky. Je vhodné pro černobílé obrázky s velkými
bílými plochami a obecně pro soubory s rozsáhlejšími bloky opakujících se
hodnot. Kromě starších grafických formátů se užívá jako prvotní postup
před uplatněním jiného, efektivnějšího algoritmu. Značně zjednodušená
demonstrace: opakující se znaky v posloupnosti se nahradí příznakem
opakování, počtem výskytů v opakování a opakujícím se znakem. Např. AAAABCDEEEF se zakóduje jako *4ABCD*3EF, kde hvězdička představuje příznak
opakování. Výhodou proudového kódování je velmi jednoduché dekódování.
Kódování opakovaných retězců
Pricipem je, že se vyhledávají řetězce
(posloupnosti znaků) v předchozích datech, pokud byl již řetězec užit,
místo jeho opakování se uvedené pouze kód tohoto řetězce. Příkladem jsou
metody zvané Lempel-Ziv algoritmy (označované LZ...) nazvané podle svých
tvůrců (Lempela a Ziva). Např. LZ77 si lze představit tak, že se postupně
prochází vstupní text a narazí-li se na opakující se řetězec, pak se místo
jeho opakování vloží příznak opakovaného řetězce, pozice a délka řetězce,
který se opakuje. Pro představu: řetězec ABCBCACB se kóduje jako
ABC*22A*32. Hvězdička je opět příznak opakování, první číslice pozice a
druhá délka opakujícího se řetězce.
Huffmanovo kódování
Tato metoda využívá různé četnosti
znaků ve zdrojovém textu. Zatímco běžné kódování znaků v počítači
přiřazuje každému znaků stejný počet bitů (zpravidla 8), zde se
nejčetnější znaky uloží s minimálním počtem bitů a méně četné pak se stále
větším. Celkově se tak průměrná délka daná počtem bitů zobrazujících jeden
znak minimalizuje. Např. v posloupnosti ABCBADBEAB je nejčetnější B (4
výskyty), dále A se třemi výskyty a konečně C, D, E po jednom výskytu. V
tomto případě by pro B stačil jeden bit, pro A dva a pro C tři a pro D, E
po čtyřech. Pro celkovou délku by pak stačilo 21 bitů a nikoli 10 znaků *
8 bitů, tj. 80 bitů v kódu ASCII.
Podstatou kódování je, že text se
poprvé podrobí statistickému zjišťování počtu znaků a vytvoří se
posloupnost znaků (dlouhá např. 256 bajtů pro 256 znaků) uspořádaných
podle výskytu znaků v kódovaném souboru. Tato posloupnost se pak pro účely
dekódování připojí k výslednému zakódovanému souboru. Při druhém průchodu
souborem se pak provádí kódování. Z uvedeného je zřejmé, že velmi krátké
soubory se nekódují, protože výsledný soubor by byl delší než původní.
Huffmanovo kódování se obvykle užívá v
kombinaci s jinými metodami a to jak pro bezztrátovou kompresi, ale i pro
kompresi ztrátovou. Např. WinZip i Arj užívají kombinaci opakujících se
řetězců (LZ77) a Huffmanova kódování.