miniatura|Fibonacci, Elias Gamma i Elias Delta vs. codificació binària En compressió de dades, un codi universal per a nombres enters és un codi prefix que assigna els nombres enters positius a paraules de codi binaris, amb la propietat addicional que sigui quina sigui la distribució de probabilitat real dels nombres enters, sempre que la distribució sigui monòtona (és a dir, p(i) ≥ p (i + 1) per a tot positiu i), les longituds esperades de les paraules de codi es troben dins d'un factor constant de les longituds esperades que hauria assignat el codi òptim per a aquesta distribució de probabilitat. Un codi universal és asimptòticament òptim si la relació entre les longituds esperades reals i òptimes està limitada per una funció de l'entropia d'informació del codi que, a més d'estar limitada, s'acosta a 1 a mesura que l'entropia s'acosta a infinit.

En general, la majoria de codis de prefix per a nombres enters assignen paraules de codi més llargues a nombres enters més grans. Un codi d'aquest tipus es pot utilitzar per comunicar de manera eficient un missatge extret d'un conjunt de missatges possibles, simplement ordenant el conjunt de missatges disminuint la probabilitat i després enviant l'índex del missatge previst. Els codis universals generalment no s'utilitzen per a distribucions de probabilitat conegudes amb precisió, i no es coneix cap codi universal que sigui òptim per a cap distribució utilitzada a la pràctica. miniatura|Arròs amb k = 2, 3, 4, 5, 8, 16 versus binari No s'ha de confondre un codi universal amb la codificació font universal, en què el mètode de compressió de dades no ha de ser un codi de prefix fix i la relació entre les longituds reals i les òptimes esperades ha d'aproximar-se a la unitat. Tanmateix, cal tenir en compte que un codi universal asimptòticament òptim es pot utilitzar en fonts independents distribuïdes de manera idèntica, mitjançant blocs cada cop més grans, com a mètode de codificació font universal.

Codis universals i no universals Aquests són alguns codis universals per a nombres enters; un asterisc (*) indica un codi que es pot reformular trivialment en ordre lexicogràfic, mentre que una daga doble (‡) indica un codi que és asimptòticament òptim:

Codificació gamma d'Elias * Codificació delta d'Elias * ‡ Codificació Omega d'Elias * ‡ Codificació Exp-Golomb *, que té la codificació gamma Elias com a cas especial. (Utilitzada en H.264/MPEG-4 AVC) Codificació de Fibonacci Codificació de Levenshtein * ‡, la tècnica de codificació universal original Codificació de bytes on s'utilitza un patró de bits especial (amb almenys dos bits) per marcar el final del codi; per exemple, si un enter es codifica com una seqüència de nibbles que representen dígits en base 15 en lloc de la base 16, que és més natural, aleshores es pot utilitzar el valor més alt del nibble (és a dir, una seqüència de quatre unitats en binari) per indicar el final de l'enter. Quantitat de longitud variable

Aquests són els no universals:

Codificació unitària, que s'utilitza en els codis Elias Codificació Rice, que s'utilitza en el còdec d'àudio FLAC i que té la codificació unitària com a cas especial. Codificació Golomb, que té la codificació Rice i la codificació unària com a casos especials.

La seva no universalitat es pot observar observant que, si qualsevol d'aquests s'utilitza per codificar la distribució de Gauss-Kuzmin o la distribució Zeta amb el paràmetre s=2, la longitud esperada de la paraula de codi és infinita. Per exemple, l'ús de codificació unitària a la distribució Zeta produeix una longitud esperada de

D'altra banda, l'ús de la codificació gamma universal d'Elias per a la distribució de Gauss-Kuzmin dóna com a resultat una longitud de paraula de codi esperada (uns 3,51 bits) propera a l'entropia (uns 3,43 bits) - Acadèmia Google.

Relació amb la compressió pràctica La codificació de Huffman i la codificació aritmètica (quan es poden utilitzar) donen una compressió com a mínim tan bona, i sovint millor, que qualsevol codi universal.

Tanmateix, els codis universals són útils quan no es pot utilitzar la codificació de Huffman; per exemple, quan no es coneix la probabilitat exacta de cada missatge, sinó només la classificació de les seves probabilitats.

Els codis universals també són útils quan els codis de Huffman són inconvenients. Per exemple, quan el transmissor, però no el receptor, coneix les probabilitats dels missatges, la codificació de Huffman requereix una sobrecàrrega de transmissió d'aquestes probabilitats al receptor. L'ús d'un codi universal no té aquesta sobrecàrrega.

Cada codi universal, com qualsevol altre codi binari autodelimitat (prefix), té la seva pròpia "distribució de probabilitat implícita" donada per on és la longitud de la i- èsima paraula de codi i P(i) és la probabilitat del símbol corresponent. Si les probabilitats reals del missatge són Q(i) i la divergència de Kullback-Leibler es minimitza pel codi amb , aleshores el codi de Huffman òptim per a aquest conjunt de missatges serà equivalent a aquest codi. De la mateixa manera, la proximitat d'un codi a l'òptim es pot mesurar mitjançant aquesta divergència. Com que els codis universals són més senzills i ràpids de codificar i descodificar que els codis de Huffman (que, al seu torn, són més senzills i ràpids que la codificació aritmètica), el codi universal seria preferible en els casos en què és prou petit. Programa de compressió de dades sense pèrdues: Hybrid LZ77 RLE

Per a qualsevol distribució geomètrica (una distribució exponencial sobre nombres enters), un codi Golomb és òptim. Amb codis universals, la distribució implícita és aproximadament una llei de potències com ara (més precisament, una distribució Zipf). Per al codi de Fibonacci, la distribució implícita és aproximadament , amb

on és la proporció àuria. Per al codi de coma ternària (és a dir, codificació en base 3, representada amb 2 bits per símbol), la distribució implícita és una llei de potències amb Aquestes distribucions, doncs, tenen codis gairebé òptims amb les seves respectives lleis de potència.

Referències

Categoria:Codificació Categoria:Compressió de dades