Informac
podle ČSN 369001 význam, který člověk přikládá datům; zpráva.
Entropie informace
Míra neurčitosti před přijetím zprávy; množství informace.
Komprese dat
Snaha o zmenšení velikosti datových souborů - snižuje se entropie;
postup, který se pro takové zmenšení velikosti datových souborů používá.
Ztrátová komprese dat
Postup komprese dat, který záměrně odstraní část informace,
kterou pokládá za nedůležitou, přesné obnovení původní informace není možné.
Tento způsob je hojně využíván při kompresi obrazu a zvuku.
Bezeztrátová komprese dat
Postup komprese dat, který umožňuje opětovné získání přesné vstupní informace.
Limitem bezeztrátové komprese je entropie informace.
Kódování
Proces, při kterém jsou transformována zdrojová data na data komprimovaná.
Opačný proces se nazývá dekódování. Při transformaci se používá kód -
zobrazení, které přiřazuje každé zdrojové jednotce jedno kódové slovo (kód)
a zároveň nepřiřazuje dvěma jednotkám stejná slova. Na kód máme i další požadavek:
aby byl jednoznačně dekódovatelný. To splňují blokové kódy - kódy kde všechna
kódová slova mají pevnou délku. Prefixové kódy, jsou kódy kde platí,
že žádný kód není prefixem jiného a tak je zaručena jednoznačnost při čtení
zleva doprava. Tyto kódy jsou také jednoznačně dekódovatelné, ale nemusí
být blokové.
Redundance kódu
Rozdíl délky zprávy a entropie informace v ní obsažené.
Optimální kód
Kód s minimální redundancí.
Asymptoticky optimální kód
Kód, kde se délka kódového slova blíží entropii příslušné jednotky s rostoucí
entropií zprávy.
Statistický model zdroje dat
Vstupní informace je tvořena množinou hodnot, vlastnosti této množiny můžeme
popsat statistickým modelem. Pro zjednodušení je dále uvažována textová
informace a množinou hodnot jsou znaky.
Statistický model nultého stupně
Každý znak textu je statisticky nezávislý na jiném znaku a pravděpodobnost
výskytu každého znaku je stejná.
Statistický model prvního stupně
Výskyt znaku je sice nezávislý na výskytu jiného znaku, ale pravděpodobnosti
výskytu jednotlivých znaků jsou různé.
Statistický model druhého stupně
Tento model zohledňuje různé pravděpodobnosti výskytu dvojice znaků v textu.
Všem dvojicím je tedy přiřazena určitá pravděpodobnost.
Statistický model n-tého stupně
Sleduje se pravděpodobnost výskytu n-tice znaků v textu. Entropie informace
klesá s rostoucím stupněm statistického modelu, například pro anglickou
abecedu s mezerou je pro model nultého stupně entropie 4,75 bitů na znak a
pro model 3. stupně 2,77 bitů na symbol.
Kódování celých čísel
V řadě kompresních algoritmů je třeba zakódovat celé číslo jednoznačně
dekódovatelným kódem. Kromě blokového kódu můžeme použít i některý z prefixových
kódů, například Fibonacciho kód.
Fibonacciho kódy
Kódy založené na Fibonacciho číslech řádu m≥2. Fibonacciho čísla jsou
definována rekurzivním vztahem:
F0=F-1=...=F-m+1=1
Fn=Fn-m + Fn-m+1 + ... + Fn-1 n≥1
Každé nezáporné číslo N má pak binární reprezentaci. Vlastností této reprezentace je,
že neobsahuje nikdy dvě jedničky za sebou.
Fibonacciho kód řádu 2 je pak pro N vytvoříme reverzací reprezentace a doplnění o jedničku:
F(N)=d0 d1 d 2 ... dk 1
Výsledná binární slova tak tvoří prefixový kód, protože končí dvěma jedničkami,
které se nikde jinde ve slově nevyskytují.
Podobně se dají vytvořit i Fibonacciho kódy vyšších řádů, které komprimují ještě lépe.
Přesto však žádný z těchto kódů není asymptoticky optimální.
Protože jsou tyto kódy optimální do vysokého N,
jsou použity i v demonstračních implementacích.
Kompresní poměr
Poměr velikosti zakódovaných dat a původních dat.
Sourozenecká vlastnost
Binární strom má sourozeneckou vlastnost když:
- každý uzel kromě kořene má sourozence
- uzly mohou být seřazeny v pořadí neklesající pravděpodobnosti tak, že
každý uzel sousedící v seznamu s nějakým uzlem je jeho sourozenec (leví synové
budou na sudých místech v seznamu a praví synové na lichých místech).
Slovník
Dvojice D = (M,C), kde M je konečná množina slov, C je zobrazení,
které zobrazuje M na množinu kódových slov. L(m) bude označovat délku kódového
slova C(m) v bitech.
Statické kódování
Model pro kodér i dekodér je pevně určený bez ohledu
na aktuálně kódovaná data. Tato metoda je vhodná pouze v případě, že kódujeme data,
která mají podobné modely, například texty.
Semiadaptivní kódování
Nad kódovanými daty je nejprve vytvořen příslušný
model, podle kterého jsou data zakódována. Tento model pak musí být odeslán spolu
se zakódovanými daty. Výhodou je, že statistický model přesně odpovídá datům,
nevýhodou je naopak to, že data se musí projít 2x - jednou pro vytvoření modelu
a podruhé při kódování. Další nevýhodou je nutnost uložení statistického modelu
do výstupu.
Adaptivní kódování
Model se vytváří během kódování ze vstupních dat a
dekodér ho odvozuje z komprimovaných dat. Kódování i dekódování probíhá jedním
průchodem, model dobře odpovídá komprimovaným datům.
Statické slovníkové metody
Používají ke kódování statický slovník, který je předem připraven. Pro přípravu
tohoto slovníku se používají:
- Řetězce pevné délky - n-gramy - například v angličtině se
často opakují digramy th, in, er, re, an
- Řetězce proměnlivé délky - tento způsob vytváří slovník pro
nejfrekventovanější slova - v angličtině je 50% textu tvořeno asi 150 slovy.
Statické slovníkové metody nereagují na přesný výskyt slov v textu, proto dosažený
kompresní poměr nemusí být dobrý.
Semiadaptivní slovníkové metody
Podobně jako u semiadaptivních statistických metod se i zde vytváří slovník ze
zdrojových dat, ale poté musí být ke kódovaným datům přidán.
Adaptivní slovníkové metody
Tyto metody vycházejí z metod které popsali Lempel a Ziv ve dvou článcích v letech
1977 a 1978. Metoda LZ 77 používá posuvné okno, LZ 78 rostoucí slovník.