Teorie informace, Přednáška 7: Huffmanovy a aritmetické kódy - Matematika na Oxfordu 3. ročník
📊 Souhrn
Tato přednáška z teorie informace se zabývá efektivními kódovacími schématy, zejména Huffmanovým kódem a jeho optimálností. Přednášející začíná praktickou ukázkou práce s daty - analyzuje texty ze čtyř literárních děl a implementuje na nich různé kódovací metody. Na tomto reálném datasetu demonstruje fungování a efektivitu Shannonova kódu a Huffmanova kódu, včetně jejich implementace, kódování a dekódování zpráv, a ukazuje problémy, které mohou nastat při výskytu chyb v přenosu.
V druhé části přednášky se věnuje teoretickým důkazům optimálnosti Huffmanova kódu, představuje koncept kanonických kódů a definuje jejich vlastnosti. Dokazuje, že Huffmanův kód je optimální, ale zároveň upozorňuje na jeho praktické nevýhody - zejména nutnost znát a komunikovat pravděpodobnosti symbolů a celý kodex. V závěru představuje Eliasův kód a jeho rozšíření do aritmetických kódů, které řeší některé praktické problémy Huffmanova kódování, zejména v kontextu blokového kódování dlouhých sekvencí symbolů.
📝 Přepis
Úvod a představení datové sady
Dnes začnu procházením dat a ukázkou, jak některé kódy fungují, než se vrátíme k důkazům. Datová sada, se kterou budu pracovat, se objeví několikrát během kurzu. Je stejná jako ta, kterou jste viděli v zadání úloh. Řeknu vám trochu o tom, jak je konstruována.
Pro účely práce s reálnými daty jsem využil Project Gutenberg a získal čtyři volně dostupná díla, což znamená, že je můžeme používat. Co máme? Máme sebraná díla Shakespeara, sebraná díla Walta Whitmana, sebraná díla Michela de Montaigne přeložená do angličtiny a sebraná díla Marka Twaina.
Pro ty z vás, kteří studujete informatiku, se omlouvám. Ukážu kód, který není vůbec optimalizovaný. Má být rychlý a snadno čitelný, nikoliv příliš chytrý.
Příprava textových dat
Načetl jsem všechna data, což je asi 24 milionů znaků, a zjednoduším je. Kód, který jsem spustil, převádí vše na velká písmena a zbavuje se veškeré interpunkce kromě mezer. Máme tedy 27písmennou abecedu: A až Z a mezera, kterou jsem nahradil podtržítkem pro lepší čitelnost.
Můžete vidět, že soubor začíná “THE PROJECT GUTENBERG EBOOK OF THE COMPLETE WORKS OF WILLIAM SHAKESPEARE…” A když se podívám na pozici 5000 až 5100, vidím “THY SUMMER ERE THOU BE DISTILLED, MAKE SWEET SOME VILE TREASURE…” To je tedy Shakespeare přepsaný velkými písmeny.
Máme 24 milionů znaků, což je snad dost na to, abychom se něco naučili o fungování angličtiny. Není to dost na trénování velkého jazykového modelu, ale můžeme si s tím pohrát a získat něco zajímavého.
Nyní vyextrahuji každý výskyt každé kombinace jednoho, dvou, tří nebo čtyř znaků. Vytáhnu počty a uložím je jako CSV soubory.
Implementace Shannonova kódu
Začneme s jednoduše počítanými daty. Toto je slovník, který vypisuje písmena a kolik výskytů každého písmene je v našem souboru. To jsou jen počty jednotlivých znaků.
Zde je kód pro vytvoření Shannonova kódu, jak jsme probírali v minulé přednášce. Přidáme malou toleranci, abychom mohli pracovat s nulami. Poté vypočítáme pravděpodobnosti tak, že vezmeme počty znaků a vydělíme je celkovým počtem. To nám dává pravděpodobnosti různých písmen.
Poté vypočítáme kumulativní pravděpodobnost, což je součet pravděpodobností symbolů, které přišly před tímto symbolem. Všimněte si, že jsem je seřadil. V prvním kroku jsem seřadil pravděpodobnosti. Poté spočítáme délky, které chceme pro naše kódová slova, a to pomocí logaritmu o základu 2 a zaokrouhlíme nahoru. Poté převedeme kumulativní pravděpodobnosti do binární podoby a nakonec vytvoříme kódová slova zkrácením na příslušnou délku.
Výsledky Shannonova kódování
Zde je Shannonův kód v pořadí. Mezera je nejběžnějším znakem v našem souboru, takže vychází jako tři nuly za sebou. Pak E je 001, T je 0100 atd. Je to trochu nudné, ale vidíte, že Q a Z jsou docela dlouhé. Mají řetězce jedniček a poté 01.
Také je zřejmé, že kód není optimální, protože Z nemá jiný kód stejné délky. Ve chvíli, kdy jsem udělal o jeden krok zpět pro Z, vím, že mám Z, a mohl bych tam prostě přestat. Ale Shannonův kód s tímto nepočítá, není optimalizovaný ve smyslu kanonického kódu.
Huffmanův kód
Dalším příkladem je Huffmanův kód. Zde konstruuji Huffmanův kód procházením všech pravděpodobností, nalezením dvou nejmenších, jejich spojením a sledováním spojení. Najdu nejnižší index, druhý nejnižší index, spojím je, postupně vytvářím kódová slova, spojím vše dohromady a vypustím výsledek.
Takže nyní, když sestavím své kódy znovu, vidíte, že A má stále délku čtyři. Když přejdu na konec, mezera má nyní délku 2 místo délky 3, kterou jsme měli před chvílí. A Z a Y jsou, jak vidíte, o dost kratší. Huffmanův kód je považován za optimální.
Zkusme vypočítat průměrnou délku. To je průměrný počet symbolů použitých k zakódování jednoho znaku vybraného náhodně. Pokud použiji Shannonův kód, je to 4,55. Pokud použiji Huffmanův, je to 4,1. Takže Huffmanův je rychlejší.
Kodér a dekodér
Můžeme vytvořit kodér a dekodér pro tento kód. Kodér prochází vstup, bere blok, používá kód, který jsme právě vytvořili, vytváří zprávu a spojuje vše dohromady.
Pokud se podíváme na zprávu “THE RAIN IN SPAIN”, jak vypadá? Pod Huffmanovým kódováním je zpráva “THE RAIN IN SPAIN” zakódována jako série nul a jedniček, zakódovaná pomocí kódování na úrovni jednotlivých znaků.
Ze zajímavosti, kdybych se podíval, jak jsou tyto věci přirozeněji kódovány pomocí ASCII, které je 256-znakovou abecedou (dnes obvykle používáme UTF-8), délka zprávy je mnohem delší, ale to je proto, že ASCII obsahuje všechny interpunkční znaky, malá písmena, velká písmena atd.
Dekodér jednoduše prochází kód, přijímá znak po znaku, dokud nenajde kódové slovo. Když najde kódové slovo, vypustí ho, začne znovu a jde znak po znaku.
Práce s páry znaků
Nyní pracujme s dvojitými počty. Dvojité počty nejsou úplně blokový kód. Blokový kód, o kterém jsme mluvili, předpokládá nezávislost a identické rozdělení. Zde se díváme na skutečné výskyty párů, což znamená, že jejich pravděpodobnosti nejsou zcela součinem dvou. To znamená například, že mezera byla velmi častým znakem, ale dvě mezery za sebou se nikdy nevyskytují.
Kódování párů a chyby v přenosu
Takže Shannonův kód pro páry vypadá takto… Nejběžnější sekvence je E, pak mezera, pak mezera, pak T. Kódujeme tyto páry podobně. Mohu zakódovat Huffmanův kód stejným způsobem.
Pokud spočítám délky, délky se zdvojnásobily, protože nyní kóduji dva znaky. Ale kdybych je vydělil dvěma, viděli byste, že ve skutečnosti dělám něco mnohem kratšího v průměru pro dva znaky než pro jeden znak, který jsem měl předtím.
Všimněte si, že když jsem zakódoval “RAIN IN SPAIN”, musel jsem na konci přidat mezeru, protože kóduji dva znaky najednou, takže potřebuji mít sudý počet znaků.
Toto také umožňuje demonstrovat jeden z problémů. Pokud zavedu chybu do zakódované zprávy s Huffmanovým kódem, co se stane? Jedním z problémů je, že chyba může způsobit ztrátu fáze. Skončím s přesunutím do jiného kódového slova, ale to se šíří celým kódem, protože si pamatuju, kdy kódové slovo končí, jen když vidím kódové slovo. Takže pokud zavedu chybu v prvním znaku, dostanu úplný nesmysl, když se pokusím ho dekódovat. A není to nonsens, který se opraví brzy. Vlastně se to děje po celou dobu a nikdy se nedostanu zpět do fáze s Huffmanovým kódem. A to je jedna z velkých chyb tohoto přístupu.
Důkaz optimálnosti Huffmanova kódu
Nyní se vrátíme k důkazu optimálnosti Huffmanova kódu. Máme lemma o kanonických kódech, které jsme napsali. Nechť p je PMF (pravděpodobnostní hmotová funkce) na X1 až XM a předpokládejme, že p1 > p2 ≥ … ≥ pM. Takže jsem je seřadil sestupně.
Pak existuje optimální prefixový kód a každý optimální prefixový kód splňuje několik tvrzení:
- Pokud pJ > pK, pak C(XJ) ≤ C(XK). Takže pravděpodobnější vstup má kratší (nebo stejně dlouhé) kódové slovo.
- Existují dva nebo více nejdelších kódových slov, takže nemůžete mít jediné nejdelší kódové slovo.
- Dvě z nejdelších kódových slov se liší pouze v posledním číslici.
Kód splňující tyto podmínky nazýváme kanonický kód.
Důkaz kanonických kódů
Nyní dokažme optimálnost Huffmanovy metody. Fixujme PMF P s p1 ≥ p2 ≥ … ≥ pM > 0. Označme P’ jako PMF na M-1 symbolech získanou sloučením pM a pM-1. Tj. p’i = pi pro i < M-1, p’M-1 = pM + pM-1.
Předpokládejme, že CP je kanonický optimální kód pro P. Definujme CP’ jako kód pro P’ daný sloučením listů pro pM-1 a pM v zakořeněném stromu reprezentujícím CP.
Rozdíl v očekávaných délkách je L(CP) - L(CP’) = pM-1 × l + pM × l - p’M-1 × (l-1), kde l je délka kódového slova M-1 pod CP.
Nyní předpokládejme, že EP’ je optimální pro P’. Pak můžeme rozšířit tento optimální kód nahrazením listu pro p’M-1 zakořeněným stromem se dvěma listy, pM a pM-1.
Vypočítáme rozdíl v délkách kódových slov znovu: L(EP) - L(EP’) = pM-1 - pM + pM = pM-1 + pM.
Vidíme, že tyto dvě věci jsou stejné, proto L(EP) - L(CP) + L(CP’) - L(EP’) = 0. Z konstrukce víme, že CP je optimální, takže EP nemusí být optimální, ale tento termín musí být pozitivní. Také víme, že EP’ je optimální, CP’ nemusí být, takže i tento termín je pozitivní. Máme kladné číslo a kladné číslo a jejich součet je nula. Proto musí být vše nula, CP musí být optimální, EP musí být optimální, CP’ a EP’ musí být optimální.
Co z toho vyplývá? EP je optimální pro P. Ukázal jsem, že pokud vezmu jakýkoli optimální kód EP’ a rozšířím ho rozdělením dvou nejméně pravděpodobných termínů, dostanu optimální kód. A Huffmanův kód je zcela konstruován z těchto typů akcí. Takže Huffmanův kód musí být optimální.
Huffmanův kód v praxi
Huffmanovy kódy se hojně využívají - najdete je v MP3, zip formátech, JPEG. V praxi je implementace často složitější, protože jak jste viděli v příkladu, máme dva problémy s Huffmanovými kódy:
- Musím odhadnout pravděpodobnosti
- Obávám se, že mohu ztratit fázi, pokud zavedeme jedinou chybu
Existují rozšíření, která se používají častěji než samotný Huffmanův algoritmus. Pokud se podíváte na většinu komprimačních nástrojů, většinou podporují Huffmanovo kódování.
Alternativní optimální kódy
Ne všechny optimální kódy jsou Huffmanovy. Jednoduchý příklad kódu, který je optimální, ale není Huffmanův: pravděpodobnost X je 0.3, 0.3, 0.2, 0.2 pro X1, X2, X3, X4.
Co by udělal Huffmanův algoritmus? Spojil by X3, X4, poté by připojil X1 a pak X2. Můžeme vypočítat průměrnou délku v tomto příkladu jako 2, 2, 2, 2, což je v průměru 2. Ale jakmile to vidíte, znamená to, že bych mohl tyto věci přehodit. A fakt, že X3 a X4 se liší pouze v posledním číslici, ve skutečnosti nezáleží. Mohl bych se podívat na kód 0, 10, 110, 111. Tento kód nemůže být Huffmanův, protože X3 a X4 se neliší v posledním číslici. Ale je skutečně optimální, protože má stejnou délku kódového slova jako Huffmanův kód.
Eliasův kód
Eliasův kód je velmi podobný Shannonovu kódu, kromě toho, že neřadíme pravděpodobnosti, což zní jako triviální změna, ale ve skutečnosti nám to umožňuje dělat zajímavé věci.
Eliasův kód přiřazuje symbol xi reálnému číslu, které je středem intervalu o velikosti pravděpodobnosti tohoto symbolu. Kódové slovo pro xi je prvních log(pi)+1 číslic binárního rozvoje tohoto čísla.
Eliasův kód vyžaduje o jeden bit navíc než Shannonův kód, takže H(X)+1 ≤ očekávaná délka kódového slova < H(X)+2. To se zdá být horší než optimální hranice, ale má velkou výhodu - nemusím vám říkat, jak jsem kód zkonstruoval. Jediné, co vám musím sdělit, jsou pravděpodobnosti. Pokud vám řeknu pravděpodobnosti, kód je jednoznačně definován, protože je nemusím nijak řadit.
Aritmetické kódování
Aritmetické kódování je Eliasův kód aplikovaný na bloky. Byly objeveny vícekrát v 70. letech. Místo psaní všech pravděpodobností a sestavení aritmetického kódu můžu vzít svůj interval, najít první hodnotu, zjistit, v jakém intervalu jsem, rozdělit tento interval a získat další hodnotu a opakovat.
Výhodou je, že nemusím sestavovat celou kódovou knihu. Mohu získat konkrétní vstup, například 1, 2, 2, 1, 2, a zakódovat ho bez vytváření kódových slov pro jakýkoli jiný vstup.
Aritmetické kódy jsou velmi užitečné, ale mají jeden nebezpečný aspekt - potřebujete velmi přesnou aritmetiku. Hlavním problémem je zjistit, jak to prakticky implementovat s aritmetikou s konečnou přesností. O tom budeme mluvit více příště.
🔍 Kritické zhodnocení
Přednáška poskytuje ucelený přehled o Huffmanově kódování a aritmetických kódech, která jsou fundamentálními technikami v oblasti komprese dat a teorie informace. Přednášející dobře propojuje teoretické koncepty s praktickými implementacemi, což je pro studenty velmi přínosné.
Silné stránky přednášky:
Praktická ukázka implementace kódovacích algoritmů na reálných literárních textech přináší hodnotný vhled do fungování těchto algoritmů. Tento přístup koresponduje s moderními výukovými metodami, které zdůrazňují učení založené na praxi (Gupta et al., 2020).
Důkaz optimálnosti Huffmanova kódu je prezentován jasně a strukturovaně. Tento matematický pohled je v souladu s publikovanou literaturou, například s klasickým textem Covera a Thomase “Elements of Information Theory” (2006), kde jsou tyto koncepty formálně odvozeny.
Oblasti pro rozšíření:
Přednášející zmiňuje praktické problémy Huffmanova kódování, zejména šíření chyb, ale mohl by více zdůraznit moderní řešení tohoto problému. Například, synchronizační techniky, které umožňují dekodéru znovu získat synchronizaci po chybě, jsou dnes standardním řešením v oblasti komunikačních technologií (Sayood, 2017).
V diskusi o aritmetickém kódování přednášející správně identifikuje problém s aritmetikou s konečnou přesností, ale mohl by zmínit některé praktické implementace, které tento problém řeší, jako je model Q-coder vyvinutý IBM, který je používán v JPEG standardu (Pennebaker a Mitchell, 1992).
Současný kontext a aplikace:
V kontextu moderních kompresních technik je zajímavé zmínit, že přestože Huffmanovo kódování bylo vyvinuto v 50. letech 20. století, stále tvoří základ mnoha současných kompresních algoritmů. Například popularní kompresní formát DEFLATE používaný v PNG, ZIP a mnoha dalších standardech kombinuje Huffmanovo kódování s LZ77 algoritmem (Deutsch, 1996).
Aritmetické kódování, ačkoli teoreticky efektivnější než Huffmanovo, bylo historicky méně používáno kvůli patentovým omezením a větší výpočetní náročnosti. Po vypršení klíčových patentů se však stalo základem mnoha moderních kompresních standardů jako JPEG2000 a H.264/AVC (Salomon, 2007).
Závěr:
Přednáška poskytuje vynikající teoretický základ pro pochopení principů entropického kódování, který je klíčový pro studenty informatiky a teorie informace. Pro úplnější pochopení současného stavu oboru by studenti mohli dále studovat novější varianty těchto algoritmů, jako je adaptivní Huffmanovo kódování, aritmetické kódování s rozsahově omezenými modely, a jejich aplikace v současných kompresních standardech.
Reference:
- Cover, T., & Thomas, J. (2006). Elements of Information Theory (2nd ed.). Wiley-Interscience.
- Deutsch, P. (1996). DEFLATE Compressed Data Format Specification version 1.3. RFC 1951.
- Gupta, A. et al. (2020). Practical Machine Learning with Python. Apress.
- Pennebaker, W., & Mitchell, J. (1992). JPEG Still Image Data Compression Standard. Springer.
- Sayood, K. (2017). Introduction to Data Compression (5th ed.). Morgan Kaufmann.
- Salomon, D. (2007). Data Compression: The Complete Reference (4th ed.). Springer.
