Codificación aritmética

La codificación aritmética ( AC ) es una forma de codificación de entropía utilizada en la compresión de datos sin pérdidas . Normalmente, una cadena de caracteres se representa utilizando un número fijo de bits por carácter, como en el código ASCII . Cuando una cadena se convierte a codificación aritmética, los caracteres utilizados con frecuencia se almacenarán con menos bits y los caracteres que aparecen con menos frecuencia se almacenarán con más bits, lo que resultará en menos bits utilizados en total. La codificación aritmética se diferencia de otras formas de codificación entrópica, como la codificación de Huffman , en que en lugar de separar la entrada en símbolos componentes y reemplazar cada uno con un código, la codificación aritmética codifica el mensaje completo en un solo número, una fracción q de precisión arbitraria . donde 0,0 ≤ q < 1,0 . Representa la información actual como un rango, definido por dos números. ^[1] Una familia reciente de codificadores de entropía llamados sistemas numéricos asimétricos permite implementaciones más rápidas gracias a operar directamente con un único número natural que representa la información actual. ^[2]

Detalles de implementación y ejemplos.

Probabilidades iguales

En el caso más simple, la probabilidad de que aparezca cada símbolo es igual. Por ejemplo, considere un conjunto de tres símbolos, A, B y C, cada uno de los cuales tiene la misma probabilidad de ocurrir. Codificar los símbolos uno por uno requeriría 2 bits por símbolo, lo cual es un desperdicio: una de las variaciones de bits nunca se usa. Es decir, los símbolos A, B y C podrían codificarse respectivamente como 00, 01 y 10, con 11 sin usar.

Una solución más eficiente es representar una secuencia de estos tres símbolos como un número racional en base 3 donde cada dígito representa un símbolo. Por ejemplo, la secuencia "ABBCAB" podría convertirse en 0,011201 ₃ , en codificación aritmética como un valor en el intervalo [0, 1). El siguiente paso es codificar este número ternario utilizando un número binario de punto fijo de precisión suficiente para recuperarlo, como 0,0010110001 ₂ (solo tiene 10 bits); Se ahorran 2 bits en comparación con la codificación de bloques ingenua. Esto es factible para secuencias largas porque existen algoritmos eficientes implementados para convertir la base de números arbitrariamente precisos.

Para decodificar el valor, sabiendo que la cadena original tenía una longitud de 6, simplemente se puede volver a convertir a base 3, redondear a 6 dígitos y recuperar la cadena.

Definiendo un modelo

En general, los codificadores aritméticos pueden producir resultados casi óptimos para cualquier conjunto dado de símbolos y probabilidades. (El valor óptimo es −log ₂P bits para cada símbolo de probabilidad P ; consulte el teorema de codificación fuente ). Los algoritmos de compresión que utilizan codificación aritmética comienzan determinando un modelo de los datos, básicamente una predicción de qué patrones se encontrarán en los símbolos. del mensaje. Cuanto más precisa sea esta predicción, más cerca del óptimo será el resultado.

Ejemplo : un modelo estático simple para describir el resultado de un instrumento de monitoreo particular a lo largo del tiempo podría ser:

60% de probabilidad de símbolo NEUTRO
20% de probabilidad de que el símbolo sea POSITIVO
10% de probabilidad de símbolo NEGATIVO
10% de probabilidad de que aparezca el símbolo FIN DE DATOS. (La presencia de este símbolo significa que el flujo será "terminado internamente", como es bastante común en la compresión de datos; cuando este símbolo aparece en el flujo de datos, el decodificador sabrá que todo el flujo ha sido decodificado).

Los modelos también pueden manejar alfabetos distintos del simple conjunto de cuatro símbolos elegido para este ejemplo. También son posibles modelos más sofisticados: el modelado de orden superior cambia su estimación de la probabilidad actual de un símbolo en función de los símbolos que lo preceden (el contexto ), de modo que en un modelo para texto en inglés, por ejemplo, el porcentaje de probabilidad de " u" sería mucho mayor cuando sigue a una "Q" o a una "q". Los modelos pueden incluso ser adaptativos , de modo que cambien continuamente su predicción de los datos en función de lo que realmente contiene la secuencia. El decodificador debe ser del mismo modelo que el codificador.

Codificación y decodificación: descripción general

En general, cada paso del proceso de codificación, excepto el último, es el mismo; El codificador tiene básicamente sólo tres datos a considerar:

El siguiente símbolo que debe codificarse
El intervalo actual (al comienzo del proceso de codificación, el intervalo se establece en [0,1], pero eso cambiará)
Las probabilidades que el modelo asigna a cada uno de los diversos símbolos que son posibles en esta etapa (como se mencionó anteriormente, los modelos adaptativos o de orden superior significan que estas probabilidades no son necesariamente las mismas en cada paso).

El codificador divide el intervalo actual en subintervalos, cada uno de los cuales representa una fracción del intervalo actual proporcional a la probabilidad de ese símbolo en el contexto actual. Cualquier intervalo que corresponda al símbolo real que se codificará a continuación se convierte en el intervalo utilizado en el siguiente paso.

Ejemplo : para el modelo de cuatro símbolos anterior:

el intervalo para NEUTRO sería [0, 0,6)
el intervalo para POSITIVO sería [0.6, 0.8)
el intervalo para NEGATIVO sería [0.8, 0.9)
el intervalo para FIN DE DATOS sería [0,9, 1).

Cuando se han codificado todos los símbolos, el intervalo resultante identifica sin ambigüedades la secuencia de símbolos que lo produjo. Cualquiera que tenga el mismo intervalo final y modelo que se está utilizando puede reconstruir la secuencia de símbolos que debe haber ingresado al codificador para dar como resultado ese intervalo final.

Sin embargo, no es necesario transmitir el intervalo final; sólo es necesario transmitir una fracción que se encuentre dentro de ese intervalo. En particular, sólo es necesario transmitir suficientes dígitos (en cualquier base) de la fracción para que todas las fracciones que comiencen con esos dígitos caigan en el intervalo final; esto garantizará que el código resultante sea un código de prefijo .

Codificación y decodificación: ejemplo

Considere el proceso para decodificar un mensaje codificado con el modelo de cuatro símbolos dado. El mensaje está codificado en la fracción 0,538 (usando decimal para mayor claridad, en lugar de binario; también suponiendo que solo hay tantos dígitos como sean necesarios para decodificar el mensaje).

El proceso comienza con el mismo intervalo que usa el codificador: [0,1), y usando el mismo modelo, dividiéndolo en los mismos cuatro subintervalos que debe tener el codificador. La fracción 0,538 cae en el subintervalo de NEUTRAL, [0, 0,6); esto indica que el primer símbolo que leyó el codificador debe haber sido NEUTRO, por lo que este es el primer símbolo del mensaje.

Luego divida el intervalo [0, 0,6) en subintervalos:

el intervalo para NEUTRAL sería [0, 0.36), 60% de [0, 0.6) .
el intervalo para POSITIVO sería [0.36, 0.48), 20% de [0, 0.6) .
el intervalo para NEGATIVO sería [0,48, 0,54), 10% de [0, 0,6) .
el intervalo para FIN DE DATOS sería [0.54, 0.6), 10% de [0, 0.6) .

Dado que 0,538 está dentro del intervalo [0,48, 0,54), el segundo símbolo del mensaje debe haber sido NEGATIVO.

Nuevamente divida nuestro intervalo actual en subintervalos:

el intervalo para NEUTRO sería [0,48, 0,516).
el intervalo para POSITIVO sería [0,516, 0,528).
el intervalo para NEGATIVO sería [0,528, 0,534).
el intervalo para FIN DE DATOS sería [0,534, 0,540).

Ahora 0,538 se encuentra dentro del intervalo del símbolo de FIN DE DATOS; por lo tanto, este debe ser el siguiente símbolo. Dado que también es el símbolo de terminación interna, significa que la decodificación está completa. Si la transmisión no termina internamente, es necesario que haya alguna otra forma de indicar dónde se detiene la transmisión. De lo contrario, el proceso de decodificación podría continuar para siempre, leyendo por error más símbolos de la fracción de los que realmente estaban codificados en ella.

Fuentes de ineficiencia

El mensaje 0,538 del ejemplo anterior podría haberse codificado con las fracciones igualmente cortas 0,534, 0,535, 0,536, 0,537 o 0,539. Esto sugiere que el uso de decimales en lugar de binarios introdujo cierta ineficiencia. Esto es correcto; el contenido de información de un decimal de tres dígitos son bits ; el mismo mensaje podría haberse codificado en la fracción binaria 0,10001010 (equivalente a 0,5390625 decimal) a un coste de sólo 8 bits. (El cero final debe especificarse en la fracción binaria; de lo contrario, el mensaje sería ambiguo sin información externa, como el tamaño del flujo comprimido). $3\times \log _{2}(10)\aproximadamente 9,966$

Esta salida de 8 bits es mayor que el contenido de información o entropía del mensaje, que es

∑ − log 2 ⁡ ( p i ) = − log 2 ⁡ ( 0,6 ) − log 2 ⁡ ( 0,1 ) − log 2 ⁡ ( 0,1 ) = 7,381 bits . {\displaystyle \sum -\log _{2}(p_{i})=-\log _{2}(0.6)-\log _{2}(0.1)-\log _{2}(0.1)= 7.381{\text{bits}}.}

Pero se debe utilizar un número entero de bits en la codificación binaria, por lo que un codificador para este mensaje utilizaría al menos 8 bits, lo que daría como resultado un mensaje un 8,4% mayor que el contenido de entropía. Esta ineficiencia de como máximo 1 bit da como resultado una sobrecarga relativamente menor a medida que crece el tamaño del mensaje.

Además, las probabilidades de los símbolos reivindicados eran [0,6, 0,2, 0,1, 0,1), pero las frecuencias reales en este ejemplo son [0,33, 0, 0,33, 0,33). Si se reajustan los intervalos para estas frecuencias, la entropía del mensaje sería de 4.755 bits y el mismo mensaje NEUTRO NEGATIVO FIN DE DATOS podría codificarse como intervalos [0, 1/3); [1/9, 2/9); [27/5, 27/6); y un intervalo binario de [0.00101111011, 0.00111000111). Este también es un ejemplo de cómo los métodos de codificación estadística, como la codificación aritmética, pueden producir un mensaje de salida que es más grande que el mensaje de entrada, especialmente si el modelo de probabilidad está desactivado.

Codificación aritmética adaptativa

Una ventaja de la codificación aritmética sobre otros métodos similares de compresión de datos es la conveniencia de la adaptación. La adaptación es el cambio de las tablas de frecuencia (o probabilidad) mientras se procesan los datos. Los datos decodificados coinciden con los datos originales siempre que la tabla de frecuencias en la decodificación se reemplace de la misma manera y en el mismo paso que en la codificación. La sincronización se basa normalmente en una combinación de símbolos que se producen durante el proceso de codificación y decodificación.

Precisión y renormalización

Las explicaciones anteriores sobre codificación aritmética contienen cierta simplificación. En particular, están escritos como si el codificador primero calculara las fracciones que representan los puntos finales del intervalo en su totalidad, usando precisión infinita , y solo convirtiera la fracción a su forma final al final de la codificación. En lugar de intentar simular una precisión infinita, la mayoría de los codificadores aritméticos operan con un límite fijo de precisión que saben que el decodificador podrá igualar, y redondean las fracciones calculadas a sus equivalentes más cercanos con esa precisión. Un ejemplo muestra cómo funcionaría esto si el modelo requiriera que el intervalo $[0,1)$ se dividiera en tercios, y esto se aproximara con una precisión de 8 bits. Tenga en cuenta que como ahora se conoce la precisión, también lo son los rangos binarios que podremos usar.

Un proceso llamado renormalización evita que la precisión finita se convierta en un límite en el número total de símbolos que se pueden codificar. Siempre que el rango se reduce hasta el punto en que todos los valores del rango comparten ciertos dígitos iniciales, esos dígitos se envían a la salida. Por muchos dígitos de precisión que la computadora pueda manejar, ahora maneja menos, por lo que los dígitos existentes se desplazan hacia la izquierda y, a la derecha, se agregan nuevos dígitos para ampliar el rango lo más posible. Tenga en cuenta que este resultado ocurre en dos de los tres casos de nuestro ejemplo anterior.

Codificación aritmética como cambio generalizado de base.

Recuerde que en el caso de que los símbolos tuvieran iguales probabilidades, la codificación aritmética podría implementarse mediante un simple cambio de base o base. En general, la codificación aritmética (y de rango) puede interpretarse como un cambio generalizado de base . Por ejemplo, podemos observar cualquier secuencia de símbolos:

\mathrm {DABDDB}

como un número en una determinada base, suponiendo que los símbolos involucrados forman un conjunto ordenado y cada símbolo en el conjunto ordenado denota un entero secuencial A = 0, B = 1, C = 2, D = 3, y así sucesivamente. Esto da como resultado las siguientes frecuencias y frecuencias acumuladas:

La frecuencia acumulada de un artículo es la suma de todas las frecuencias que preceden al artículo. En otras palabras, la frecuencia acumulada es un total acumulado de frecuencias.

En un sistema de numeración posicional , la base, o base, es numéricamente igual a una serie de símbolos diferentes utilizados para expresar el número. Por ejemplo, en el sistema decimal el número de símbolos es 10, es decir, 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9. La base se utiliza para expresar cualquier número entero finito en un supuesto multiplicador en forma polinómica. Por ejemplo, el número 457 es en realidad 4×10 ² + 5×10 ¹ + 7×10 ⁰ , donde se presume la base 10 pero no se muestra explícitamente.

Inicialmente, convertiremos DABDDB en un número de base 6, porque 6 es la longitud de la cadena. La cadena se asigna primero a la cadena de dígitos 301331, que luego se asigna a un número entero mediante el polinomio:

6^{5}\times 3+6^{4}\times 0+6^{3}\times 1+6^{2}\times 3+6^{1}\times 3+6^ {0}\veces 1=23671

El resultado 23671 tiene una longitud de 15 bits, lo que no está muy cerca del límite teórico (la entropía del mensaje), que es de aproximadamente 9 bits.

Para codificar un mensaje con una longitud más cercana al límite teórico impuesto por la teoría de la información, necesitamos generalizar ligeramente la fórmula clásica para cambiar la base. Calcularemos los límites superior e inferior L y U y elegiremos un número entre ellos. Para calcular L multiplicamos cada término de la expresión anterior por el producto de las frecuencias de todos los símbolos ocurridos anteriormente:

{\begin{aligned}L={}&(6^{5}\times 3)+{}\\&3\times (6^{4}\times 0)+{}\\&(3 \veces 1)\veces (6^{3}\veces 1)+{}\\&(3\veces 1\veces 2)\veces (6^{2}\veces 3)+{}\\&( 3\veces 1\veces 2\veces 3)\veces (6^{1}\veces 3)+{}\\&(3\veces 1\veces 2\veces 3\veces 3)\veces (6^{ 0}\times 1){}\\={}&25002\end{aligned}}

La diferencia entre este polinomio y el polinomio anterior es que cada término se multiplica por el producto de las frecuencias de todos los símbolos que aparecieron anteriormente. De manera más general, L puede calcularse como:

L=\sum _{i=1}^{n}n^{ni}C_{i}{\prod _{k=1}^{i-1}f_{k}}

donde están las frecuencias acumuladas y son las frecuencias de ocurrencias. Los índices indican la posición del símbolo en un mensaje. En el caso especial donde todas las frecuencias son 1, esta es la fórmula de cambio de base. $\scriptstyle C_ {i}$ $\scriptstyle f_ {k}$ $\scriptstyle f_ {k}$

El límite superior U será L más el producto de todas las frecuencias; en este caso U = L + (3 × 1 × 2 × 3 × 3 × 2) = 25002 + 108 = 25110. En general, U viene dada por:

U=L+\prod _{k=1}^{n}f_{k}

Ahora podemos elegir cualquier número del intervalo [ L , U ) para representar el mensaje; Una elección conveniente es el valor con el rastro de ceros más largo posible, 25100, ya que nos permite lograr compresión al representar el resultado como 251×10 ² . Los ceros también se pueden truncar, dando 251, si la longitud del mensaje se almacena por separado. Los mensajes más largos tenderán a tener colas de ceros más largas.

Para decodificar el número entero 25100, el cálculo del polinomio se puede invertir como se muestra en la siguiente tabla. En cada etapa se identifica el símbolo actual y luego se resta el término correspondiente del resultado.

Durante la decodificación tomamos la palabra después de dividir por la potencia correspondiente de 6. Luego, el resultado se compara con los intervalos acumulativos y se selecciona el símbolo apropiado de la tabla de búsqueda. Cuando se identifica el símbolo se corrige el resultado. El proceso continúa durante la duración conocida del mensaje o mientras el resultado restante sea positivo. La única diferencia con el cambio de base clásico es que puede haber un rango de valores asociados con cada símbolo. En este ejemplo, A es siempre 0, B es 1 o 2 y D es cualquiera de 3, 4, 5. Esto está exactamente de acuerdo con nuestros intervalos que están determinados por las frecuencias. Cuando todos los intervalos son iguales a 1 tenemos un caso especial del clásico cambio de base.

Límite teórico de mensaje comprimido.

El límite inferior L nunca excede n ⁿ , donde n es el tamaño del mensaje y, por lo tanto, puede representarse en bits. Después del cálculo del límite superior U y la reducción del mensaje seleccionando un número del intervalo [ L , U ) con el rastro de ceros más largo, podemos suponer que esta longitud se puede reducir en bits. Dado que cada frecuencia en un producto ocurre exactamente el mismo número de veces que el valor de esta frecuencia, podemos usar el tamaño del alfabeto A para calcular el producto. $\log _{2}(n^{n})=n\log _{2}(n)$ $\textstyle \log _{2}\left(\prod _{k=1}^{n}f_{k}\right)$

\prod _{k=1}^{n}f_{k}=\prod _{k=1}^{A}f_{k}^{f_{k}}.

Al aplicar log ₂ para el número estimado de bits en el mensaje, el mensaje final (sin contar una sobrecarga logarítmica para las tablas de longitud y frecuencia del mensaje) coincidirá con el número de bits dado por la entropía , que para mensajes largos está muy cerca del óptimo:

-\left[\sum _{i=1}^{A}f_{i}\log _{2}(f_{i})\right]n=nH

En otras palabras, la eficiencia de la codificación aritmética se acerca al límite teórico de bits por símbolo, a medida que la longitud del mensaje se acerca al infinito. $H$

Equipartición asintótica

Podemos entender esto intuitivamente. Supongamos que la fuente es ergódica, entonces tiene la propiedad de equipartición asintótica (AEP). Según el AEP, después de una larga secuencia de símbolos, el intervalo de está casi dividido en intervalos casi del mismo tamaño. $n$ $(0,1)$

Técnicamente, para cualquier cadena pequeña y para toda lo suficientemente grande , existen cadenas tales que cada cadena tiene casi la misma probabilidad , y su probabilidad total es . $\epsilon >0$ $n$ $2^{nH(X)(1+O(\epsilon ))}$ $x_{1:n}$ $Pr(x_{1:n})=2^{-nH(X)(1+O(\epsilon ))}$ $1-O(\epsilon )$

Para cualquier cadena de este tipo, se codifica aritméticamente mediante una cadena binaria de longitud , donde es la más pequeña tal que exista una fracción de forma en el intervalo para . Dado que el intervalo for tiene tamaño , deberíamos esperar que contenga una fracción de la forma cuando . $k$ $k$ $k$ ${\frac {?}{2^{k}}}$ $x_{1:n}$ $x_{1:n}$ $2^{-nH(X)(1+O(\epsilon ))}$ ${\frac {?}{2^{k}}}$ $k=nH(X)(1+O(\epsilon ))$

Por lo tanto, con alta probabilidad, se puede codificar aritméticamente con una cadena binaria de longitud . $x_{1:n}$ $nH(X)(1+O(\epsilon ))$

Conexiones con otros métodos de compresión.

Codificación Huffman

Debido a que la codificación aritmética no comprime un dato a la vez, puede acercarse arbitrariamente a la entropía al comprimir cadenas IID . Por el contrario, el uso de la extensión de la codificación de Huffman (a cadenas) no alcanza la entropía a menos que todas las probabilidades de los símbolos alfabéticos sean potencias de dos, en cuyo caso tanto la codificación de Huffman como la aritmética alcanzan la entropía.

Cuando Huffman codifica ingenuamente cadenas binarias, no es posible la compresión, incluso si la entropía es baja (por ejemplo, ({0, 1}) tiene probabilidades {0,95, 0,05}). La codificación Huffman asigna 1 bit a cada valor, lo que da como resultado un código de la misma longitud que la entrada. Por el contrario, la codificación aritmética comprime bien los bits, acercándose a la relación de compresión óptima de

1-[-0.95\log _{2}(0.95)+-0.05\log _{2}(0.05)]\approx 71.4\%.

Una forma sencilla de abordar la suboptimidad de la codificación de Huffman es concatenar símbolos ("bloqueo") para formar un nuevo alfabeto en el que cada nuevo símbolo represente una secuencia de símbolos originales (en este caso, bits) del alfabeto original. En el ejemplo anterior, agrupar secuencias de tres símbolos antes de la codificación produciría nuevos "supersímbolos" con las siguientes frecuencias:

000: 85,7%
001,010,100: 4,5% cada uno
011,101,110: 0,24% cada uno
111: 0,0125%

Con esta agrupación, la codificación de Huffman promedia 1,3 bits por cada tres símbolos, o 0,433 bits por símbolo, en comparación con un bit por símbolo en la codificación original, es decir, compresión. Permitir secuencias arbitrariamente grandes se acerca arbitrariamente a la entropía (al igual que la codificación aritmética), pero requiere códigos enormes para hacerlo, por lo que no es tan práctico como la codificación aritmética para este propósito. $56.7\%$

Una alternativa es codificar las longitudes de ejecución mediante códigos Golomb-Rice basados en Huffman . Este enfoque permite una codificación/decodificación más sencilla y rápida que la codificación aritmética o incluso la codificación de Huffman, ya que esta última requiere búsquedas en tablas. En el ejemplo {0,95, 0,05}, un código Golomb-Rice con un resto de cuatro bits logra una relación de compresión de , mucho más cercana al óptimo que el uso de bloques de tres bits. Sin embargo , los códigos Golomb-Rice solo se aplican a entradas de Bernoulli como la de este ejemplo, por lo que no sustituyen al bloqueo en todos los casos. $71.1\%$

Historia y patentes

Los algoritmos básicos para la codificación aritmética fueron desarrollados de forma independiente por Jorma J. Rissanen , de IBM Research , y por Richard C. Pasco, Ph.D. estudiante de la Universidad de Stanford ; ambos fueron publicados en mayo de 1976. Pasco cita un borrador previo a la publicación del artículo de Rissanen y comenta sobre la relación entre sus obras: ^[3]

Rissanen [1976] desarrolló de forma independiente un algoritmo de la familia. Desplaza el elemento de código al extremo más significativo del acumulador, utilizando un puntero obtenido por suma y exponenciación. Ahora compararemos las alternativas en las tres opciones y veremos que es preferible desplazar el elemento de código en lugar del acumulador, y agregar elementos de código al extremo menos significativo del acumulador.

Menos de un año después de la publicación, IBM solicitó una patente estadounidense sobre el trabajo de Rissanen. El trabajo de Pasco no fue patentado.

Históricamente, las patentes estadounidenses han cubierto una variedad de técnicas específicas para la codificación aritmética, aunque desde entonces varios métodos bien conocidos han pasado al dominio público cuando las patentes expiraron. Las técnicas cubiertas por patentes pueden ser esenciales para implementar los algoritmos de codificación aritmética que se especifican en algunas normas internacionales formales. Cuando este es el caso, dichas patentes generalmente están disponibles para su concesión bajo lo que se denomina términos de concesión de licencia "razonables y no discriminatorios" ( RAND ) (al menos como una cuestión de política del comité de normas). En algunos casos bien conocidos (incluidos algunos relacionados con patentes de IBM que ya expiraron), dichas licencias estaban disponibles de forma gratuita y, en otros casos, se exigieron tarifas de licencia. La disponibilidad de licencias bajo términos RAND no necesariamente satisface a todos los que quieran utilizar la tecnología, ya que lo que puede parecer "razonable" para una empresa que prepara un producto de software comercial propietario puede parecer mucho menos razonable para un proyecto de software libre o de código abierto .

Al menos un importante programa de software de compresión, bzip2 , descontinuó deliberadamente el uso de codificación aritmética en favor de la codificación Huffman debido a la situación de patentes percibida en ese momento. Además, los codificadores y decodificadores del formato de archivo JPEG , que tiene opciones tanto para codificación Huffman como para codificación aritmética, normalmente solo admiten la opción de codificación Huffman, que originalmente se debió a problemas de patentes; El resultado es que casi todas las imágenes JPEG que se utilizan hoy en día utilizan la codificación Huffman ^[4], aunque las patentes de codificación aritmética de JPEG ^[5] han expirado debido a la antigüedad del estándar JPEG (cuyo diseño se completó aproximadamente en 1990). ^[6] JPEG XL , así como archivadores como PackJPG, Brunsli y Lepton, que pueden convertir sin pérdidas archivos codificados por Huffman a archivos con codificación aritmética (o sistemas numéricos asimétricos en el caso de JPEG XL), lo que muestra un ahorro de tamaño de hasta un 25 %.

El algoritmo de codificación aritmética del formato de compresión de imágenes JPEG se basa en las siguientes patentes citadas (ya caducadas). ^[7]

Patente estadounidense 4.652.856 – ( IBM ) Presentada el 4 de febrero de 1986, concedida el 24 de marzo de 1987 – Kottappuram MA Mohiuddin, Jorma Johannes Rissanen – Código aritmético de varios alfabetos sin multiplicación
Patente estadounidense 4.905.297 – (IBM) Presentada el 18 de noviembre de 1988, concedida el 27 de febrero de 1990 – Glen George Langdon, Joan L. Mitchell, William B. Pennebaker, Jorma Johannes Rissanen – Sistema codificador y decodificador de codificación aritmética
Patente estadounidense 4.935.882 – (IBM) Presentada el 20 de julio de 1988, concedida el 19 de junio de 1990 – William B. Pennebaker, Joan L. Mitchell – Adaptación de probabilidad para codificadores aritméticos
Patente JP 1021672 – ( Mitsubishi ) Presentada el 21 de enero de 1989, concedida el 10 de agosto de 1990 – Toshihiro Kimura, Shigenori Kino, Fumitaka Ono, Masayuki Yoshida – Sistema de codificación
Patente JP 2-46275 – (Mitsubishi) Presentada el 26 de febrero de 1990, concedida el 5 de noviembre de 1991 – Fumitaka Ono, Tomohiro Kimura, Masayuki Yoshida, Shigenori Kino – Aparato de codificación y método de codificación

Otras patentes (en su mayoría también vencidas) relacionadas con la codificación aritmética incluyen las siguientes.

Patente estadounidense 4.122.440 – (IBM) Presentada el 4 de marzo de 1977, concedida el 24 de octubre de 1978 – Glen George Langdon, Jorma Johannes Rissanen – Método y medios para la codificación aritmética de cadenas
Patente estadounidense 4.286.256 – (IBM) Presentada el 28 de noviembre de 1979, concedida el 25 de agosto de 1981 – Glen George Langdon, Jorma Johannes Rissanen – Método y medios para la codificación aritmética utilizando un número reducido de operaciones
Patente estadounidense 4.467.317 – (IBM) Presentada el 30 de marzo de 1981, concedida el 21 de agosto de 1984 – Glen George Langdon, Jorma Johannes Rissanen – Codificación de compresión aritmética de alta velocidad mediante actualización de valores concurrente
Patente estadounidense 4.891.643 – (IBM) Presentada el 15 de septiembre de 1986, concedida el 2 de enero de 1990 – Joan L. Mitchell, William B. Pennebaker – Compresión/descompresión de datos de codificación aritmética mediante codificadores y decodificadores de codificación aritmética diversos, empleados selectivamente
Patente JP 11782787 – ( NEC ) Presentada el 13 de mayo de 1987, concedida el 18 de noviembre de 1988 – Michio Shimada – Dispositivo de codificación aritmética de compresión de datos
Patente JP 15015487 – ( KDDI ) Presentada el 18 de junio de 1987, concedida el 22 de diciembre de 1988 – Shuichi Matsumoto, Masahiro Saito – Sistema para evitar la propagación por transporte en codificación aritmética
Patente estadounidense 4.933.883 – (IBM) Presentada el 3 de mayo de 1988, concedida el 12 de junio de 1990 – William B. Pennebaker, Joan L. Mitchell – Adaptación de probabilidad para codificadores aritméticos
Patente estadounidense 4.989.000 – (IBM) Presentada el 19 de junio de 1989, concedida el 29 de enero de 1991 – Dan S. Chevion, Ehud D. Karnin, Eugeniusz Walach – Compresión de cadenas de datos utilizando codificación aritmética con estimación de subintervalos de probabilidad simplificada
Patente estadounidense 5.099.440 – (IBM) Presentada el 5 de enero de 1990, concedida el 24 de marzo de 1992 – William B. Pennebaker, Joan L. Mitchell – Adaptación de probabilidad para codificadores aritméticos
Patente estadounidense 5.272.478 – ( Ricoh ) Presentada el 17 de agosto de 1992, concedida el 21 de diciembre de 1993 – James D. Allen – Método y aparato para codificación entrópica

Nota: Esta lista no es exhaustiva. Consulte los siguientes enlaces para obtener una lista de más patentes estadounidenses. ^[8] El códec Dirac utiliza codificación aritmética y no está pendiente de patente. ^[9]

Pueden existir patentes sobre codificación aritmética en otras jurisdicciones; consulte patentes de software para conocer un análisis sobre la patentabilidad del software en todo el mundo.

Puntos de referencia y otras características técnicas.

Cada implementación programática de codificación aritmética tiene una relación de compresión y un rendimiento diferentes. Si bien las tasas de compresión varían solo un poco (generalmente menos del 1%), ^[10] el tiempo de ejecución del código puede variar en un factor de 10. Elegir el codificador correcto de una lista de codificadores disponibles públicamente no es una tarea sencilla debido al rendimiento y la tasa de compresión. Depende también del tipo de datos, particularmente del tamaño del alfabeto (número de símbolos diferentes). Uno de dos codificadores en particular puede tener un mejor rendimiento para alfabetos pequeños, mientras que el otro puede mostrar un mejor rendimiento para alfabetos grandes. La mayoría de los codificadores tienen limitaciones en el tamaño del alfabeto y muchos de ellos están especializados en alfabetos de exactamente dos símbolos (0 y 1).

Ver también

Notas

^ Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9 de abril de 2014). Fundamentos de Multimedia. Medios de ciencia y negocios de Springer. ISBN 978-3-319-05290-8.
^ J. Duda, K. Tahboub, NJ Gadil, EJ Delp, El uso de sistemas numéricos asimétricos como reemplazo preciso de la codificación Huffman, Simposio de codificación de imágenes, 2015.
^ Pasco, Richard Clark (mayo de 1976). Algoritmos de codificación fuente para una compresión rápida de datos (Doctor). Universidad de Stanford. CiteSeerX 10.1.1.121.3377 .
^ "¿Qué es JPEG?". comp.compression Preguntas frecuentes (parte 1/3) .
^ "Recomendación T.81 (1992) Corrigendum 1 (04/01)". Recomendación T.81 (1992) . Unión Internacional de Telecomunicaciones. 9 de noviembre de 2004 . Consultado el 3 de febrero de 2011 .
^ Pennebaker, WB; Mitchell, JL (1992). Estándar de compresión de datos de imágenes fijas JPEG . Prensa académica de Kluwer. ISBN 0442012721.
^ "T.81 - COMPRESIÓN DIGITAL Y CODIFICACIÓN DE IMÁGENES FIJAS DE TONOS CONTINUOS - REQUISITOS Y DIRECTRICES" (PDF) . CCITT . Septiembre de 1992 . Consultado el 12 de julio de 2019 .
^ "Preguntas frecuentes". comp.compresión .
^ "Lanzamiento del códec de vídeo Dirac 1.0 [LWN.net]". lwn.net .
^ Por ejemplo, Howard y Vitter (1994) analizan versiones de codificación aritmética basadas en rangos de números reales, aproximaciones de números enteros a esos rangos y un tipo de aproximación aún más restringido al que llaman codificación cuasi-aritmética binaria. Afirman que la diferencia entre las versiones real y entera es insignificante, demuestran que la pérdida de compresión para su método cuasi-aritmético puede hacerse arbitrariamente pequeña y limitan la pérdida de compresión incurrida por una de sus aproximaciones a menos del 0,06%. Ver: Howard, Paul G.; Vitter, Jeffrey S. (1994), "Codificación aritmética para la compresión de datos" (PDF) , Actas del IEEE , 82 (6): 857–865, doi :10.1109/5.286189, hdl : 1808/7229 , archivado desde el original (PDF) el 18 de octubre de 2013 , consultado el 17 de octubre de 2013.

Referencias

MacKay, David JC (septiembre de 2003). "Capítulo 6: Códigos de transmisión". Teoría de la información, inferencia y algoritmos de aprendizaje . Prensa de la Universidad de Cambridge . ISBN 0-521-64298-1. Archivado desde el original (PDF/ PostScript / DjVu / LaTeX ) el 22 de diciembre de 2007 . Consultado el 30 de diciembre de 2007 .
Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 22.6. Codificación aritmética". Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8. Archivado desde el original el 11 de agosto de 2011 . Consultado el 18 de agosto de 2011 .
Rissanen, Jorma (mayo de 1976). "Desigualdad generalizada de Kraft y codificación aritmética". Revista IBM de investigación y desarrollo . 20 (3): 198–203. doi : 10.1147/rd.203.0198 . Consultado el 21 de septiembre de 2007 .
Rissanen, JJ; Langdon GG, Jr (marzo de 1979). «Codificación aritmética» (PDF) . Revista IBM de investigación y desarrollo . 23 (2): 149–162. doi :10.1147/rd.232.0149. S2CID 39909636. Archivado desde el original (PDF) el 28 de septiembre de 2007 . Consultado el 22 de septiembre de 2007 .
Witten, Ian H.; Neal, Radford M.; Cleary, John G. (junio de 1987). "Codificación aritmética para compresión de datos" (PDF) . Comunicaciones de la ACM . 30 (6): 520–540. doi :10.1145/214762.214771. S2CID 3343393. Archivado (PDF) desde el original el 28 de septiembre de 2007 . Consultado el 21 de septiembre de 2007 .

Rodionov Anatoly, Volkov Sergey (2010) "codificación aritmética p-adic" Matemáticas contemporáneas Volumen 508, 2010 Matemáticas contemporáneas
Rodionov Anatoly, Volkov Sergey (2007) "codificación aritmética p-ádica", codificación aritmética P-ádica

enlaces externos

Este artículo incorpora material de dominio público de Paul E. Black. "Codificación aritmética". Diccionario de Algoritmos y Estructuras de Datos . NIST .
Publicación en grupos de noticias con un breve ejemplo elaborado de codificación aritmética (solo números enteros).
Artículo de PlanetMath sobre codificación aritmética
Anatomía del codificador de rango El artículo explica tanto la codificación de rango como la aritmética. También tiene ejemplos de código para 3 codificadores aritméticos diferentes junto con una comparación de rendimiento.
Introducción a la codificación aritmética Archivado el 9 de noviembre de 2020 en Wayback Machine . 60 páginas.
Eric Bodden , Malte Clasen y Joachim Kneis: la codificación aritmética revelada. Informe técnico 2007-5, Sable Research Group, Universidad McGill.
Codificación aritmética + modelado estadístico = compresión de datos por Mark Nelson.
Compresión de datos con codificación aritmética de Mark Nelson (2014)
Implementación rápida de codificación de rango y rANS por James K. Bonfield