Entropie
Jedním z nejdůležitějších pojmů z oblasti komprese dat je entropie, což je veličina udávající průměrné množství informace obsažené v jednom symbolu dat. Jednotkou této veličiny je bit. Entropii lze definovat také jako míru překvapení dekódující strany, jako informační obsah symbolu (datové zprávy) nebo jako průměrný minimální počet bitů nutný k zakódování jednoho symbolu dat. Značí se H a formálně ji lze definovat jako
kde p(a) značí pravděpodobnost výskytu symbolu a z abecedy A.
Kódování je proces vzájemně jednoznačného (bijektivního) přiřazení symbolů jedné abecedy (vstupní data) symbolům abecedy druhé (kódy, kódová slova). Kódy mohou být přiřazeny jednotlivým symbolům nebo blokům vstupního toku. Například aritmetické kódování přiřazuje kód celému vstupnímu souboru dat (bitové kódy jednotlivých symbolů nelze odlišit).
Takové kódování, které snižuje redundanci dat, lze nazývat kompresí. V tomto textu se pod pojmem kód rozumí jednak vlastní kódové slovo pro určitý symbol nebo soubor těchto slov (např. Huffmanův kód).
Proměnná délka
Dalším důležitým pojmem je kódování s proměnnou délkou (VLC, variable-length coding), což je takové kódování, kde se symbolům přiřazují kódy různé délky (různého počtu bitů). V případě, že se často vyskytujícím se symbolům přiřadí krátké kódy a méně často vyskytujícím se symbolům kódy delší, jedná se o entropické kódování. Entropické kodéry mohou komprimovat data téměř optimálně vzhledem k jejich entropii. Příkladem takového kódování je Huffmanovo.
Souvisejícím pojmem je prefixový kód, což je kód s vlastností, že žádné kódové slovo není prefixem jiného kódového slova. Důsledkem této vlastnosti je to, že kód je při dekódování jednoznačný i bez oddělovačů.
Entropické kódování má za úkol nahradit často se vyskytující symboly krátkými bitovými kódy. Délka těchto kódů je závislá na četnosti výskytu daného symbolu ve vstupním toku dat. Může nastat situace, kdy je symbolu přidělen kód delší, než je velikost původního symbolu. Tento případ nastává, jsou-li kratší kódy již přiděleny častěji se vyskytujícím symbolům. I přesto je komprese možná, protože k větší úspoře místa dojde právě vyjádřením častých symbolů krátkými kódy. Příkladem entropických kodérů jsou např. Golombovo-Riceovo kódování, Eliasovo gama kódování, Fibonacciho kódování, Huffmanovo kódování nebo aritmetické kódování.
Unární kódování
Nejjednodušší entropický kodér je unární kodér, který mapuje nezáporná celá čísla N na bitové sekvence N bitů 1 a ukončující bit 0. Bity 0 a 1 lze samozřejmě zaměnit. Takový převod je užitečný jen, pokud jsou data seřazena vzestupně podle pravděpodobnosti jejich výskytu ve vstupním toku. Jako důsledek toho jsou častěji se vyskytujícím symbolům přiřazeny kratší bitové kódy než symbolům méně frekventovaným.
Takový kód je optimální jen pro geometrické rozložení pravděpodobnosti vstupních symbolů p(N) = 2−N. Protože přímo takové rozložení pravděpodobnosti výskytu symbolů bude velmi vzácné a protože délka kódu velmi rychle roste, je toto kódování užitečné spíše jako součást jiných entropických kodérů než přímo pro použití na kódované symboly. V tabulce níže vidíme unárního kód čísel 0–3.
| N | Kód |
|---|---|
| 0 | 0 |
| 1 | 10 |
| 2 | 110 |
| 3 | 1110 |
| 4 | 11110 |
| … | … |
Golombovo-Riceovo kódování
Golombovo-Riceovo (nebo jen Riceovo) kódování je speciální případ Golombova kódování. Na rozdíl od obecného Golombova kódování jej však lze na počítačích rychle a jednoduše realizovat. Stejně jako unární kódování mapuje i Golombův-Riceův kodér nezáporná celá čísla N na bitové kódy s proměnnou délkou. Kód je však na rozdíl od pevně daného unárního kódu parametrizovatelný parametrem M = 2C (M je mocninou 2). Metodu je tedy možné lépe adaptovat na data.
V případě M = 1 je kód shodný s unárním kódem. Parametr M nemusí být po celou dobu kódování konstantní. Pro získání kódu čísla N se nejprve určí hodnoty Q = ⌊ N / M ⌋, R = N – Q a C = ⌈ log2 M ⌉. Hodnota Q se pak kóduje unárně a hodnota R klasicky binárně na C bitech. V následující tabulce vidíme Riceův kód čísel 0–12 pro parametr M = 4.
| N | Q | R | Kód |
|---|---|---|---|
| 0 | 0 | 0 | 1 00 |
| 1 | 0 | 1 | 1 01 |
| 2 | 0 | 2 | 1 10 |
| 3 | 0 | 3 | 1 11 |
| 4 | 1 | 0 | 01 00 |
| 5 | 1 | 1 | 01 01 |
| 6 | 1 | 2 | 01 10 |
| 7 | 1 | 3 | 01 11 |
| 8 | 2 | 0 | 001 00 |
| 9 | 2 | 1 | 001 01 |
| 10 | 2 | 2 | 001 10 |
| 11 | 2 | 3 | 001 11 |
| 12 | 3 | 0 | 0001 00 |
| … | … | … | … |
Shannonovo-Fanovo kódování
Shannonovo-Fanovo kódování odvozuje kódová slova přímo od pravděpodobností výskytu kódovaných symbolů (adaptuje se na data). Nejlepších výsledků dosahuje, když jsou pravděpodobnosti výskytu kódovaných symbolů záporné mocniny 2. Huffmanovo kódování však v praxi generuje o něco lepší kód. K vytvoření kódu symbolů je použit binární strom. Symboly jsou listy stromu, jehož hrany reprezentují kód symbolu (např. levá hrana znamená bit 0, pravá bit 1). Konstrukce stromu vypadá následovně.
- Seřadit symboly sestupně podle jejich pravděpodobností.
- Rozdělit tuto množinu (rodičovský uzel) na dvě podmnožiny (synovské uzly) tak, že obě budou mít nejlépe stejný součet pravděpodobností.
- Rekurzivně aplikovat krok 2. na obě podmnožiny až do rozkladu na jednotlivé symboly.
Huffmanovo kódování
Huffmanovo kódování je velmi populární metoda použitá např. v metodách bzip2, Deflate, JPEG nebo MP3. Opět se adaptuje na kódovaná data a nejlepších výsledků dosahuje pro pravděpodobnosti, které jsou rovny záporné mocnině 2. Pro vytvoření kódů využívá také binárního stromu. Symboly jsou opět listy stromu s hranami, které udávají jejich kód. Konstrukce stromu se však poněkud liší.
- Seřadit symboly dle jejich pravděpodobností.
- Vybrat 2 symboly s nejnižší pravděpodobností, spojit je do nového uzlu.
- Dokud je co spojovat, pokračuje se opět krokem 2.
Vytvořený strom se nazývá Huffmanův strom. Při této konstrukci má kodér jistou volnost ve výběru symbolů, které bude dále spojovat. Kanonický Huffmanův kód je Huffmanův kód sestavený podle daných deterministických pravidel. Je vhodný pro přenos k dekompresoru (stačí přenést délky kódových slov). U adaptivní varianty (změna pravděpodobností výskytu symbolů v průběhu komprese) je nutné při kompresi i dekompresi opravovat strom, aby stále vyhovoval výše uvedené konstrukci. K tomu se používají hlavně dva algoritmy označované podle počátečních písmen jmen jejich tvůrců – algoritmus FGK (Faller, Gallager, Knuth) a algoritmus V (Vitter).
Jednoduchý příklad Huffmanova stromu sestaveného pro pět symbolů s pravděpodobnostmi 0,1, 0,1, 0,2, 0,2 a 0,4 je uveden na obrázku výše (symboly nejsou pro jednoduchost uvedeny, pouze jejich pravděpodobnosti). Symbol s nejvyšší četností (a odtud pravděpodobností) výskytu obdržel kód o délce 1 bit. Dva symboly s nejnižší četností výskytu obdržely naopak kódy o délce 4 bity. Vytvořený kód ale není pro toto rozložení pravděpodobností optimální, protože pravděpodobnosti nejsou mocninami dvou (jako např. 0,5 nebo 0,25). Pro optimální kód (délka kódu odpovídá entropii symbolu) je třeba použít aritmetické kódování.
Aritmetické kódování
Na rozdíl od předchozích kódů vytváří aritmetické kódování optimální kódy pro libovolné pravděpodobnosti výskytu kódovaných symbolů. Metoda přidělí jeden kód celému kódovanému souboru dat, nikoli jednotlivým symbolům. Klíčovou myšlenkou metody je zužování intervalu úměrně pravděpodobnosti výskytu právě kódovaného symbolu. Zužování intervalu vyžaduje další bity, takže délka kódu postupně roste.
Začíná se s intervalem, který se podle pravděpodobností kódovaných symbolů neustále zužuje, a výsledkem kódování je libovolné číslo z výsledného intervalu. Ke kompresi dochází, protože symbol s vyšší pravděpodobností zúží interval méně (přidá méně bitů) než symbol s pravděpodobností nižší. Princip se běžně vysvětluje na reálném intervalu 〈0; 1), praktické implementace však musejí pracovat s celými čísly (např. 32bitový int). Implementace adaptivní varianty je značně jednodušší než v případě Huffmanova kódování (oprava Huffmanova stromu). Postačí pouhá aktualizace modelu dat, což může znamenat jen inkrementace četnosti symbolu v poli a případně inkrementaci kumulovaných četností všech následujících symbolů.
Na obrázku níže vidíme aritmetické kódování řetězce acab. Začíná se s intervalem 〈0; 1), výsledek je libovolné číslo z intervalu 〈0,6875; 0,703125).
(Autorem obrázků je David Bařina.)
