Univerzální kód (komprese dat) - Universal code (data compression)

Fibonacci, Elias Gamma a Elias Delta vs. binární kódování

Rýže s k = 2, 3, 4, 5, 8, 16 versus binární

v komprese dat, a univerzální kód pro celá čísla je a kód předpony která mapuje kladná celá čísla na binární kódová slova s další vlastností, která je pravdivá rozdělení pravděpodobnosti na celá čísla, pokud je rozdělení monotónní (tj. p(i) ≥ p(i + 1) pro všechny pozitivníi), očekávaný délky kódových slov jsou v konstantním faktoru očekávaných délek, které optimální kód pro toto rozdělení pravděpodobnosti by bylo přiřazeno. Univerzální kód je asymptoticky optimální pokud je poměr mezi skutečným a optimálním očekávaný délky je ohraničen funkcí informační entropie kódu, který kromě toho, že je ohraničený, se blíží 1, když se entropie blíží nekonečnu.

Obecně platí, že většina předponových kódů pro celá čísla přiřazuje delší kódová slova větším celým číslům. Takový kód lze použít k efektivní komunikaci zprávy čerpané ze sady možných zpráv, jednoduchým objednáním sady zpráv snížením pravděpodobnosti a následným odesláním indexu zamýšlené zprávy. Univerzální kódy se obecně nepoužívají pro přesně známá rozdělení pravděpodobnosti a žádný univerzální kód není znám jako optimální pro jakoukoli distribuci používanou v praxi.

Univerzální kód by neměl být zaměňován s univerzální zdrojové kódování, ve kterém metodou komprese dat nemusí být kód pevné předpony a poměr mezi skutečnou a optimální očekávanou délkou se musí blížit jedné. Všimněte si však, že asymptoticky optimální univerzální kód lze použít na nezávislé identicky distribuované zdroje pomocí stále většího počtu bloky, jako metoda kódování univerzálního zdroje.

Univerzální a neuniverzální kódy

Toto je několik univerzálních kódů pro celá čísla; hvězdička (* ) označuje kód, který lze triviálně přepracovat lexikografický řád, zatímco dvojitá dýka (‡ ) označuje kód, který je asymptoticky optimální:

Eliasovo gama kódování *
Eliasovo delta kódování * ‡
Elias omega kódování *^{[je třeba další vysvětlení ]} ‡
Kódování Exp-Golomb *, který má Eliasovo gama kódování jako speciální případ. (Použito v H.264 / MPEG-4 AVC )
Fibonacciho kódování
Levenshtein kódování * ‡, originální univerzální technika kódování [1]
Bajtové kódování kde se pro označení konce kódu používá speciální bitový vzor (s nejméně dvěma bity) - například pokud je celé číslo zakódováno jako posloupnost křupky představující číslice v základna 15 místo přirozenější základna 16, pak lze k označení konce celého čísla použít nejvyšší hodnotu okusování (tj. posloupnost čtyř v binární podobě).
Množství s proměnnou délkou

Jedná se o neuniverzální:

Unární kódování, který se používá v Eliasových kódech
Rýže kódování, který se používá v FLAC zvukový kodek a který má unární kódování jako speciální případ
Golombovo kódování, který má ve zvláštních případech kódování rýže a unární kódování.

Jejich neuniverzalitu lze pozorovat, když si všimneme, že pokud se některá z nich používá k kódování Gauss – Kuzminova distribuce nebo Distribuce Zeta s parametrem s = 2 je očekávaná délka kódového slova nekonečná. Například použití unárního kódování na distribuci Zeta poskytne očekávanou délku

{ displaystyle E (l) = { frac {6} { pi ^ {2}}} sum _ {l = 1} ^ { infty} { frac {1} {l}} = infty. ,}

Na druhou stranu použití univerzálního Eliasova gama kódování pro Gauss – Kuzminovu distribuci vede k očekávané délce kódového slova (asi 3,51 bitu) poblíž entropie (asi 3,43 bitu)[2].

Vztah k praktické kompresi

Huffmanovo kódování a aritmetické kódování (pokud je lze použít) poskytují přinejmenším stejně dobrou a často lepší kompresi než jakýkoli univerzální kód.

Univerzální kódy jsou však užitečné, když nelze použít Huffmanovo kódování - například když člověk nezná přesnou pravděpodobnost každé zprávy, ale zná pouze pořadí jejich pravděpodobností.

Univerzální kódy jsou také užitečné, když jsou Huffmanovy kódy nepohodlné. Například když vysílač, ale ne příjemce, zná pravděpodobnosti zpráv, Huffmanovo kódování vyžaduje režii přenosu těchto pravděpodobností do přijímače. Použití univerzálního kódu tuto režii nemá.

Každý univerzální kód, stejně jako každý jiný binární kód s vlastním oddělením (předponou), má své vlastní „implicitní rozdělení pravděpodobnosti“ dané p(i)=2^−l(i) kde l(i) je délka ikódové slovo a p(i) je pravděpodobnost odpovídajícího symbolu. Pokud jsou skutečné pravděpodobnosti zprávy q(i) a Kullback – Leiblerova divergence D_KL(q||p) je minimalizován kódem s l(i), pak bude optimální Huffmanův kód pro tuto sadu zpráv ekvivalentní tomuto kódu. Stejně tak lze touto divergencí měřit, jak blízko je kód k optimálnímu. Protože univerzální kódy jsou jednodušší a rychlejší pro kódování a dekódování než Huffmanovy kódy (což je zase jednodušší a rychlejší než aritmetické kódování ), univerzální kód by byl vhodnější v případech, kdy D_KL(q||p) je dostatečně malý.[3]

Pro všechny geometrické rozdělení (exponenciální rozdělení na celá čísla), optimální je Golombův kód. U univerzálních kódů je implicitní distribuce přibližně a mocenský zákon jako ${ displaystyle 1 / n ^ {2}}$ (přesněji a Distribuce Zipf ).Pro Fibonacciho kód, implicitní distribuce je přibližně ${ displaystyle 1 / n ^ {q}}$ , s

{ displaystyle q = 1 / log _ {2} ( varphi) simeq 1,44,}

kde ${ displaystyle varphi}$ je Zlatý řez. Pro ternární čárkový kód (tj. kódování v základně 3, představované 2 bity na symbol), implicitní distribucí je zákon síly s ${ displaystyle q = 1 + log _ {3} (4/3) simeq 1,26}$ . Tyto distribuce tedy mají téměř optimální kódy s příslušnými zákony o moci.

externí odkazy

Komprese dat autorů: Debra A. Lelewer a Daniel S. Hirschberg (University of California, Irvine )
Informační teorie, odvození a výukové algoritmy tím, že David MacKay, má kapitolu o kódech pro celá čísla, včetně úvodu do Eliasových kódů.
Кодирование целых чисел má převážně dokumenty v anglickém jazyce o univerzálních a jiných celočíselných kódech.