Informační teorie, Přednáška 8: Tunstallův kód
📊 Souhrn
Přednáška se zabývá třemi typy kódování dat: Eliasovým kódem, aritmetickým kódováním a Tunstallovým kódem. V úvodu je dokončena diskuze o optimalizaci Huffmanova kódu z předchozí přednášky a představen Eliasův kód, který pracuje s reálnými čísly reprezentujícími intervaly pravděpodobností. Následuje vysvětlení aritmetického kódování, které lze chápat jako blokovou verzi Eliasova kódu. Tyto metody představují typy kódování “pevná-na-proměnnou”, kde vstup pevné délky je mapován na výstup proměnné délky.
Druhá polovina přednášky je věnována Tunstallovu kódu, který naopak představuje typ kódování “proměnná-na-pevnou”, kde vstup proměnné délky je mapován na výstup pevné délky. Tento přístup má výhodu v menší náchylnosti k chybám během přenosu, protože kód je rozdělený do bloků pevné délky. Přednáška končí matematickým důkazem optimality Tunstallova kódu a stručným představením pokročilejších metod jako je Lempel-Zivovo kódování, které dynamicky odhaduje pravděpodobnosti během kódování bez předchozí znalosti distribuce symbolů.
📝 Přepis
Rekapitulace z minulé přednášky a úvod do Eliasova kódu
Dobrá. Včera jsme dokončili důkaz optimality Huffmanova kódu a začali jsme zkoumat třídu aritmetických kódů. Konkrétně jsme viděli Eliasův kód. Nejsem si jistý, zda se vyslovuje Elias nebo Elias - nevím, jak sám své jméno vyslovoval.
V tomto kódu vezmeme naše vstupy (X) a vypočítáme reálnou hodnotu, což je součet pravděpodobností všech předchozích kódových slov, jak přicházejí, a přidáme polovinu pravděpodobnosti aktuálního kódového slova. Předpokládáme, že pořadí je dané, symboly nejsou seřazené. Tuto hodnotu nazýváme ri, což je nějaké reálné číslo. Poté vezmeme toto reálné číslo a vypočítáme strop z mínusového logaritmu PI plus jedna. Poté přeneseme tolik binárních číslic RI jako kód pro xi. To je Eliasův kód.
Vizualizace Eliasova kódu
Můžeme si vizualizovat, co se děje. Pokud mám tři různé výstupy a jejich pravděpodobnost je znázorněna intervaly nakreslenými černě, pak dostanu tři čísla R1, R2 a R3, což jsou středy těchto intervalů. Co udělám? Přenesu dostatek číslic, abych věděl, kde se kódové slovo nachází.
Například, pokud by bylo R1 rovno 1/4, pak mé kódové slovo spojené s R1 bude 00. Takže pokud dám nějaká čísla jako 0,42 a 0,61 - předpokládejme, že máme tyto pravděpodobnosti. Mám tedy něco, kde x1 nastává s pravděpodobností 0,42, x2 s pravděpodobností 0,219 a zbytek je pravděpodobnost x3. Přenesu 00, což mi řekne, že jsem v první čtvrtině prostoru.
Pokud víte, že cokoli vám pošlu začíná 00, víte, že vám dávám kódové slovo, které leží v první čtvrtině prostoru. Tam je pouze jedno kódové slovo, R1. Takže můžete identifikovat, které kódové slovo jsem poslal - poslal jsem X1.
Efektivita a praktické výhody Eliasova kódu
Tento kód není zvlášť efektivní. Vidíme, že spotřebuje o jeden bit navíc ve srovnání s optimem. Takže očekávaná délka kódového slova pro Eliasův kód bude menší než H(X) + 2, což není tak dobré, jak bychom chtěli. Ve skutečnosti můžeme také ukázat, že je větší než H(X) + 1.
Výhodou však je, že nemusím řadit pravděpodobnosti. To mi dává v praxi obrovskou výhodu, protože nemusím brát potenciálně velmi velký počet pravděpodobností, řadit je a ukládat, jak jsem je seřadil.
Aritmetické kódování
Důvod, proč je Eliasův kód zajímavý, je, že vede k aritmetickým kódům. Aritmetické kódy, jak jsem řekl včera, lze vidět několika různými způsoby. Jeden je jen jako bloková verze Eliasova kódu - vezmete Eliasův kód a aplikujete ho na bloky délky N. Pak získáte něco mnohem přesnějšího, což generuje to, čemu říkáme aritmetický kód.
Existuje však zábavnější způsob, jak na to nahlížet. Když pošlu posloupnost, identifikuji bod v prostoru. Ve skutečnosti můžete uvažovat, že identifikuji interval v prostoru.
Pojďme nakreslit obrázek podobný předchozímu. Předpokládejme, že pošlu symboly 0, 0, 1, 1. První číslice jsou nula, takže jsem ve spodní polovině. Jsem ve spodní čtvrtině, ve druhé osmině, ve čtvrté šestnáctině prostoru. Takže kdybych tento prostor rozdělil na 16 částí, byl bych někde v intervalu, který takto vypadá.
Rekurzivní vlastnost aritmetického kódování
Všimněte si, jak jsem dekódoval tuto zprávu - mohl jsem začít a nemusel jsem projít celou zprávu. Mohl jsem jen začít odečítat číslice, protože jsem věděl, kde všechno bylo. Takže touto metodou máme blokový kód, který je zcela rekurzivní.
Posláním sekvence Q známe, že máme kódové slovo nebo kódový symbol R v intervalu od Q do Q + 2^(-délka Q). Takže víme, že jsme v tomto intervalu. Když pošlu sekvenci Q, kde jsem napsal Q buď jako sekvenci, nebo jako binární expanzi reálného čísla, tak říkám, že potřebuji identifikovat, které reálné číslo by mohlo v tomto intervalu ležet.
Implementační detaily a výhody
Nebudu vám ukazovat, jak to implementovat, protože je to trochu složité. Problém je v tom, že ve skutečnosti nemůžete používat reálná čísla. Takže když to implementujete v počítači, nemůžete to dělat pomocí aritmetiky s plovoucí desetinnou čárkou, protože ztratíte přesnost.
Běžná aritmetika s plovoucí desetinnou čárkou má nanejvýš přibližně 64 bitů v čísle s plovoucí desetinnou čárkou, takže nemáte dostatečnou přesnost pro přesnou reprezentaci. Musíte vše napsat pomocí binárních sekvencí a manipulovat s nimi.
Jedna krásná věc je, že je to zcela online a můžete to implementovat způsobem, který je zcela online. Co tím myslím: pokud bych vám dal vstup 0011011011 a řekl bych, že mě zajímají pouze první dvě číslice, první dva symboly ve výstupu, můžete tím projít a říci: “Aha, to mi dává první číslici, to mi dává druhou číslici a jsem hotov.”
Takže to mohu dělat zcela dopředu a nepotřebuji konstruovat celou kódovou knihu. Nemusím vědět, co by se zakódovalo jako něco jiného, nemusím vyjmenovávat všechny tyto možnosti. Pokud dělám blokový kód pomocí něčeho jako Huffmanův kód, musím vyjmenovat všechny možné sekvence. To se stává velmi neefektivní, protože musím ukládat tento obrovský seznam možných věcí, které bych mohl kódovat, a jak je kóduji. Uchovávání těchto informací je drahé.
Optimalita aritmetického kódu
Pojďme se pokusit pochopit optimalitu, kterou můžeme získat z aritmetického kódu.
Teorém: Nechť x1 až xn jsou IID náhodné proměnné ze vstupní abecedy X s BMF p. Jako obvykle, aritmetický kód založený na blocích délky n má průměrnou délku kódového slova omezenou shora H(x1 až xn) + 2, a tedy průměrnou délku na znak H(x) + 2/n.
Pokud budu kódovat věci v dlouhých blocích, což není tak zlé kvůli rekurzivní povaze konstrukce, pak ve skutečnosti příliš nezáleží na této penaltě a dostaneme něco docela efektivního.
Variabilní na pevné kódy - Tunstallův kód
Posledním typem kódu, o kterém chci mluvit, je tzv. variabilní na pevné kódy.
Dosud jsme se dívali na pevné na variabilní kódy, kde vám dáme pevný vstup nebo pevnou délku bloku a vy mi vrátíte řetězec ve výstupní abecedě, který má libovolnou délku. To je pěkné, ale má to problém - může snadno ztratit fázi. Pokud mám chybu na začátku, zničí to odhady všeho. Dekódovaný řetězec bude zcela odlišný pro vše, co přijde po té první chybě.
Tunstallův kód považuje vstupní abecedu X na 1 až M a výstupní Y jako binární kód. Cílem je najít sadu vstupních řetězců W, které kódujeme v Y do D. Chceme mít pevnou délku řetězce na výstupu.
Základní vlastnosti Tunstallova kódu
Co potřebujeme vědět? Počet řetězců, které můžeme kódovat, je maximálně 2^D. Potřebujeme tedy, aby velikost W, kterou nazýváme K, byla menší nebo rovna 2^D.
Chceme, aby náš kód byl:
- Vlastní - žádný prvek W není prefixem jiného prvku W
- Úplný/vyčerpávající - každý řetězec v X má prefix v W
Proč to chceme? Chceme, aby byl vlastní - to je ekvivalent vlastnosti prefixu. Existuje pouze jeden způsob, jak něco kódovat. Chceme, aby byl úplný, takže bez ohledu na to, jaký řetězec vám dám v X*, existuje nějaký způsob, jak ho zakódovat.
Konstrukce Tunstallova kódu
Tunstallův kód, 1967 - tohle byla Tunstallova doktorská práce. Konstrukce je nejsnazší ukázat na příkladu.
Začínáme podobně jako u Huffmanova kódu. Najdeme kódové slovo s nejvyšší pravděpodobností. Začneme s kódovými slovy 1 až M. Najdeme kódové slovo s nejvyšší pravděpodobností a rozdělíme ho na M nových kódových slov připojením každého z 1 až M. Opakujeme, dokud nemůžeme vložit další slova.
Příklad Tunstallova kódu
Řekněme D = 3, X = {A, B}, P(X=A) = 0,7. Předpokládáme, že vše je IID.
První krok: začínám s kódovými slovy A a B s pravděpodobnostmi 0,7 a 0,3. Najdu nejpravděpodobnější kódové slovo (A) a rozdělím ho na AA a AB s pravděpodobnostmi 0,49 a 0,21. Najdu nejpravděpodobnější kódové slovo (AA) a rozdělím ho na AAA a AAB s pravděpodobnostmi 0,343 a 0,147. Najdu nejpravděpodobnější kódové slovo (AAA) a rozdělím ho na AAAA a AAAB s pravděpodobnostmi 0,2401 a 0,1029.
[proces pokračuje]
Nakonec dostanu 8 kódových slov a ty jednoduše přiřadím k 3-bitovým sekvencím. Takže pokud mi pošlete řetězec AB, podíváte se a řeknete: “První kódové slovo je AB, takže pošlu 111”. A tak dále.
Optimalita Tunstallova kódu
Teorém: Předpokládejme, že máme IID sekvenci x1 x2 vstupů v X. Mezi variabilními na pevné kódy, které jsou vlastní a úplné (s opravou, že vždy můžeme doplnit zprava, pokud potřebujeme), Tunstallův kód je optimální v tom smyslu, že maximalizuje očekávanou délku vstupního řetězce, který je kódován jako jediná sekvence v Y^D.
Důkaz je krásný. Jakýkoli vlastní a úplný kód odpovídá M-árnímu stromu, protože vždy musíte být schopni rozhodnout, jaký je další znak, který se pokusíte kódovat.
[následuje matematický důkaz optimality]
Závěr a další metody
Existují různé další výsledky, které bychom mohli ukázat. Například D děleno očekávanou délkou vstupu musí být větší nebo rovno H(X).
Existují také blokové aritmetické kódy, což jsou variace na aritmetické kódování pomocí bloků. Dávají vám variabilní na pevné kód podobný Tunstallovu, mírně méně optimální, ale lze je provádět online, jako aritmetické kódování.
Odtud se dostanete k tomu, čemu se říká Lempel-Zivovy kódy. V podstatě problémem každého kódu, který jsme dosud viděli, je, že musíte znát pravděpodobnosti před začátkem. Lempel-Ziv dynamicky odhaduje tyto pravděpodobnosti na základě toho, co jste už viděli, takže se můžete přiblížit optimu, aniž byste znali distribuci předem.
Příští týden začneme druhou polovinu kurzu, která zkoumá, co děláme, když se snažíme přenášet informace přes zašuměný kanál, takže to, co pošleme, není to, co slyšíme, a jak to dělat efektivně.
🔍 Kritické zhodnocení
Přednáška pokrývá důležité koncepty v teorii kódování, které jsou základem mnoha moderních kompresních algoritmů. Prezentované koncepty jsou matematicky správné a přesně popisují vlastnosti a optimality jednotlivých kódovacích schémat.
Eliasův kód, prezentovaný v první části, je skutečně méně efektivní než Huffmanův kód z hlediska kompresního poměru, ale jeho výhoda spočívá v jednodušší implementaci, jak bylo správně uvedeno. Dle studie Salomona (2007), Eliasův kód nachází uplatnění především v aplikacích, kde je důležitější rychlost kódování než optimální komprese.
Aritmetické kódování je v přednášce popsáno jako vylepšení Eliasova kódu. Tento popis je přesný, ale nebyly dostatečně zdůrazněny implementační výzvy. Jak uvádí Sayood (2017) ve své knize “Introduction to Data Compression”, aritmetické kódování je sice teoreticky optimální (může dosáhnout entropie zdroje), ale praktické implementace čelí problémům s přesností a efektivitou výpočtů.
Tunstallův kód je představen jako “variabilní na pevné” kódovací schéma, což je správná charakterizace. Jeho optimalita je dokázána elegantním způsobem, ale přednášející nezmínil některé praktické omezení. Jak poukázal Tjalkens a Willems (2000), Tunstallův kód má omezení při práci se zdroji s velmi nerovnoměrným rozdělením pravděpodobností a v některých případech může být méně efektivní než algoritmické alternativy.
Zmínka o Lempel-Ziv kódování na konci přednášky je vhodná, protože toto kódování představuje význačný posun v přístupu - od kódování založeného na známých pravděpodobnostech k adaptivnímu kódování, které se učí z dat. LZ77 a LZ78 (a jejich varianty jako LZW) jsou základem mnoha běžných kompresních nástrojů, jak správně poznamenává. Pro hlubší pochopení těchto algoritmů by bylo vhodné nahlédnout do práce Ziva a Lempela (1977, 1978), kde jsou tyto algoritmy původně popsány.
Pro studenty, kteří by chtěli získat praktičtější pohled na tyto algoritmy, doporučuji knihu “Modern Data Compression Algorithms” od Salomona a Minky (2010), která obsahuje pseudokódy a implementační detaily.
Celkově přednáška poskytuje solidní teoretický základ pro pochopení různých kódovacích schémat, přestože některé praktické aspekty a omezení mohly být více zdůrazněny.
Zdroje:
- Salomon, D. (2007). Data Compression: The Complete Reference. 4th Edition. Springer.
- Sayood, K. (2017). Introduction to Data Compression. 5th Edition. Morgan Kaufmann.
- Tjalkens, T., & Willems, F. (2000). “A universal variable-to-fixed length source code based on Lawrence’s algorithm.” IEEE Transactions on Information Theory.
- Ziv, J., & Lempel, A. (1977). “A universal algorithm for sequential data compression.” IEEE Transactions on Information Theory, 23(3), 337-343.
- Ziv, J., & Lempel, A. (1978). “Compression of individual sequences via variable-rate coding.” IEEE Transactions on Information Theory, 24(5), 530-536.
