Univerzální kód

Univerzální kód pro celá čísla v kompresi dat  je předponový kód , který převádí kladná celá čísla na binární slova, s další vlastností, že pro jakékoli skutečné rozdělení pravděpodobnosti na celých číslech, pokud je rozdělení monotónní (tj. pro libovolné ), očekávaná délky binárních slov jsou v rámci konstantního faktoru očekávaných délek, které by optimální kód přiřadil danému rozdělení pravděpodobnosti.

Univerzální kód je asymptoticky optimální, pokud koeficient mezi skutečnou a optimální očekávanou délkou souvisí s funkcí informační entropie kódu, která se blíží 1, když se entropie blíží nekonečnu.

Většina kódů celočíselných předpon přiřazuje delší klíčová slova k větším celým číslům. Takový kód lze použít k účinnému zakódování zprávy čerpané ze sady možných zpráv jednoduchým seřazením sady zpráv v sestupném pořadí pravděpodobnosti a poté předáním indexu zamýšlené zprávy. Univerzální kódy se obecně nepoužívají pro dobře známá rozdělení pravděpodobnosti.

Mezi univerzální kódy patří:

• Unární kódování
• Eliasův gama kód
• Eliášův delta kód
• Elias Omega Code
• delta kód
• Fibonacciho kódování
• Exponenciální Golombův kód

Některé neuniverzální kódy:

• jednoduché kódování , používané v kódech Elias
• Kódování rýže
• Golombovo kódování

Jejich neuniverzálnost se projevuje v tom, že pokud je některý z nich použit pro kódování Gauss-Kuzminova rozdělení nebo zeta rozdělení s parametrem s=2, pak je očekávaná délka klíčového slova nekonečná. Například při použití jednomístného kódování na distribuci zeta máme následující očekávanou délku:

Praktické použití při kompresi dat

Použití Huffmanova kódu a aritmetického kódování (pokud je lze použít společně) poskytuje lepší výsledky než jakýkoli jiný univerzální kód.

Univerzální kódy jsou však užitečné, když nelze použít Huffmanův kód – například když není možné určit přesnou pravděpodobnost každé zprávy, ale je známo pořadí jejich pravděpodobností.

Obecné kódy jsou také užitečné, když Huffmanův kód nefunguje zcela správně. Když například odesílatel zná pravděpodobnost zprávy, ale příjemce ne, Huffmanův kód vyžaduje, aby byly pravděpodobnosti předány příjemci. Použití generického kódu tyto nepříjemnosti eliminuje.

Každý univerzální kód dává své vlastní "implicitní rozdělení" pravděpodobností , kde  je délka i-tého klíčového slova a  je pravděpodobnost symbolu přenosu. Pokud skutečné pravděpodobnosti zpráv – a vzdálenost Kullback-Leibler minimalizuje kód s , bude optimální Huffmanův kód pro tuto sadu zpráv ekvivalentní tomuto kódu. Protože univerzální kódy jsou rychlejší než Huffmanův kód, je univerzální kód preferován v případech, kdy stačí dostatečně malý.

Pro jakékoli geometrické rozložení je optimální Golombovo kódování. U univerzálních kódů se implicitní rozdělení přibližně řídí mocninným zákonem , např . konkrétněji Zipfovým zákonem . Pro Fibonacciho kód se implicitní rozdělení přibližně řídí zákonem pro , kde je poměr zlatého řezu .

Odkazy

• Celočíselné kódování