Kompresní kódy

Když reprezentujeme informace, třeba obrázek, digitálně, musíme ji rozdělit do malých kousků. To nám umožní poslat obrázek jako posloupnost symbolů barev. A tyto barvy můžeme reprezentovat pomocí čísel, použitím nějakého kódu. Podívejme se na následující problém: Alice a Bob umí vysílat a přijímat zprávy v dvojkové soustavě. [pípání Morseovky] Účtují svým zákazníkům 1 penci za každý bit, pokud chtějí používat jejich systém. Přijde pravidelný zákazník a chce poslat zprávu. A jeho zpráva má 1000 symbolů. Význam té zprávy je zcela neznámý. Normálně bychom tuto zprávu poslali standardním dvoubitovým kódováním. Což vede k účtování za 2000 bitů. Alice a Bob ale předtím zanalyzovali tohoto zákazníka. A zjistili, že pravděpodobnost použití jednotlivých symbolů je různá. Můžou využít znalost těchto pravděpodobností ke zmenšení objemu přenosu a zvýšení jejich zisku? Jaká je optimální strategie kódování? David Huffman vymyslel optimální strategii a publikoval ji v roce 1952. Je založená na budování binárního stromu zespoda nahoru. Začneme tak, že si vypíšeme všechny symboly dolů a budeme jim říkat uzly. A pak najdeme 2 uzly s nejmenšími pravděpodobnostmi, v našem případě B a C. A spojíme je do jednoho. A sečteme jejich pravděpodobnosti. A tohle opakujeme s dalšími 2 nejméně pravděpodobnými uzly. A pokračujeme ve spojování, dokud nám nezbude jediný uzel nahoře. Nakonec označíme hrany v tomto stromě 0 a 1, v libovolném pořadí. Kódem pro každé písmeno je prostě cesta z vršku stromu k danému písmenu. Třeba pro A je to jediná hrana s 1. Říká se tomu Huffmanovo kódování a v takovýchto případech ho nemůžete porazit. Schválně to zkuste. Například, když zkrátíte kód pro D na pouhou 0. Pak zpráva 011 by mohla znamenat DAA nebo možná taky jenom B. Takže kdybyste chtěli, aby to fungovalo, museli byste zavést mezeru mezi znaky, a to by vyrušilo všechny úspory během přenosu. Jak moc tohle zmenší zprávu, v porovnání s původními 2000 bity? Musíme prostě spočítat, kolik bitů připadne průměrně na jedno písmeno. Vynásobíme tedy délku každého kódu s pravděpodobností výskytu a sečteme je dohromady. Zjistíme, že průměrná délka je 1.75 bitů na jeden symbol. To znamená, že při použití Huffmanova kódování očekáváme zmenšení zprávy z 2000 bitů na 1750 bitů. Claude E. Shannon byl první, kdo tvrdil, že limit komprese bude vždy entropie zdrojové zprávy. Když se entropie neboli nejistota našeho zdroje snižuje, díky známé statistické struktuře, schopnost komprimace se zvyšuje. [pípání Morseovky] Naopak, když se entropie zvyšuje, kvůli nepředvídatelnosti, naše schopnost komprimovat se snižuje. [pípání Morseovky] Pokud bychom chtěli komprimovat za hranici entropie, nutně bychom museli zahodit část informace z naší zprávy.