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ž:

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í: 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.