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érdida . 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 da como resultado que se utilicen menos bits en total. La codificación aritmética difiere de otras formas de codificación de entropía, 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 todo el mensaje en un solo número, una fracción de precisión arbitraria q , 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 numerales asimétricos permiten implementaciones más rápidas gracias a la operación directa sobre 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 cada símbolo aparezca es igual. Por ejemplo, considere un conjunto de tres símbolos, A, B y C, cada uno con la misma probabilidad de aparecer. 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 utiliza. Es decir, los símbolos A, B y C podrían codificarse respectivamente como 00, 01 y 10, con 11 sin utilizar.

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 ₂ – esto son solo 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 y en el lugar para convertir la base de números arbitrariamente precisos.

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

Definir un modelo

En general, los codificadores aritméticos pueden producir una salida casi óptima 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 de la 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 estará 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 NEUTRAL
20% de probabilidad de símbolo 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 se "terminará 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 se ha decodificado todo el flujo).

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 una "q". Los modelos incluso pueden ser adaptativos , de modo que cambien continuamente su predicción de los datos en función de lo que realmente contiene el flujo. El decodificador debe tener el 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 básicamente tiene que considerar solo tres datos:

El siguiente símbolo que necesita ser codificado
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 distintos símbolos que son posibles en esta etapa (como se mencionó anteriormente, los modelos de orden superior o adaptativos 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 que ese símbolo aparezca en el contexto actual. El 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 NEUTRAL 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 de forma inequívoca la secuencia de símbolos que lo generó. Cualquiera que tenga el mismo intervalo final y el mismo modelo que se está utilizando puede reconstruir la secuencia de símbolos que debe haber ingresado al codificador para generar 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 (se utiliza el sistema decimal para mayor claridad, en lugar del binario; también se supone que solo hay tantos dígitos como sean necesarios para decodificar el mensaje).

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

A continuación, 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.

Dividamos nuevamente nuestro intervalo actual en subintervalos:

el intervalo para NEUTRAL 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 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 el flujo no termina internamente, debe haber alguna otra forma de indicar dónde se detiene el flujo. De lo contrario, el proceso de decodificación podría continuar eternamente, leyendo por error más símbolos de la fracción de los que en realidad 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 del decimal en lugar del binario introdujo cierta ineficiencia. Esto es correcto; el contenido de información de un decimal de tres dígitos es bits ; el mismo mensaje podría haberse codificado en la fracción binaria 0,10001001 (equivalente a 0,53515625 decimal) con un coste de sólo 8 bits. $3\times \log _{2}(10)\aproximadamente 9,966$

Esta salida de 8 bits es mayor que el contenido de información, o la 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 % más grande que el contenido de entropía. Esta ineficiencia de 1 bit como máximo da como resultado una sobrecarga relativamente menor a medida que aumenta el tamaño del mensaje.

Además, las probabilidades de símbolo reclamadas fueron [0.6, 0.2, 0.1, 0.1), pero las frecuencias reales en este ejemplo son [0.33, 0, 0.33, 0.33). Si los intervalos se reajustan para estas frecuencias, la entropía del mensaje sería 4.755 bits y el mismo mensaje NEUTRAL NEGATIVO FIN DE DATOS podría codificarse como intervalos [0, 1/3); [1/9, 2/9); [5/27, 6/27); y un intervalo binario de [0.00101111011, 0.00111000111). Este es también 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á fuera de lugar.

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 comodidad de la adaptación. La adaptación es el cambio de las tablas de frecuencia (o probabilidad) durante el procesamiento de 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, por lo general, en una combinación de símbolos que aparecen durante el proceso de codificación y decodificación.

Precisión y renormalización

Las explicaciones anteriores de la codificación aritmética contienen cierta simplificación. En particular, están escritas como si el codificador calculara primero las fracciones que representan los puntos finales del intervalo en su totalidad, utilizando precisión infinita , y solo convirtiera la fracción a su forma final al final de la codificación. En lugar de intentar simular precisión infinita, la mayoría de los codificadores aritméticos operan en cambio 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 exigiera que el intervalo $[0,1)$ se dividiera en tercios, y esto se aproximara con precisión de 8 bits. Tenga en cuenta que, dado que ahora se conoce la precisión, también se conocen los rangos binarios que podremos usar.

Un proceso llamado renormalización evita que la precisión finita se convierta en un límite para 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 está manejando menos que eso, por lo que los dígitos existentes se desplazan a la izquierda y, a la derecha, se agregan nuevos dígitos para expandir el rango lo más ampliamente posible. Observe que este resultado ocurre en dos de los tres casos de nuestro ejemplo anterior.

Codificación aritmética como cambio generalizado de base

Recordemos que en el caso en que los símbolos tuvieran probabilidades iguales, la codificación aritmética podría implementarse mediante un simple cambio de base o radix. 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 base determinada, suponiendo que los símbolos involucrados forman un conjunto ordenado y que cada símbolo en el conjunto ordenado denota un entero secuencial A = 0, B = 1, C = 2, D = 3, etc. Esto da como resultado las siguientes frecuencias y frecuencias acumuladas:

La frecuencia acumulada de un elemento es la suma de todas las frecuencias que lo preceden. En otras palabras, la frecuencia acumulada es el total acumulado de frecuencias.

En un sistema de numeración posicional, el radio, o base, es numéricamente igual a una serie de símbolos diferentes que se utilizan 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. El radio se utiliza para expresar cualquier número entero finito en un multiplicador presunto en forma polinómica. Por ejemplo, el número 457 es en realidad 4×10 ² + 5×10 ¹ + 7×10 ⁰ , donde se presupone 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}\times 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 el radio. Calcularemos los límites inferior y superior L y U y elegiremos un número entre ellos. Para el cálculo de L, multiplicamos cada término en la expresión anterior por el producto de las frecuencias de todos los símbolos que aparecieron anteriormente:

{\begin{aligned}L={}&(6^{5}\times 3)+{}\\&3\times (6^{4}\times 0)+{}\\&(3\times 1)\times (6^{3}\times 1)+{}\\&(3\times 1\times 2)\times (6^{2}\times 3)+{}\\&(3\times 1\times 2\times 3)\times (6^{1}\times 3)+{}\\&(3\times 1\times 2\times 3\times 3)\times (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. En términos más generales, L se puede calcular como:

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

donde son las frecuencias acumuladas y son las frecuencias de ocurrencia. Los índices indican la posición del símbolo en un mensaje. En el caso especial en el que 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 opción conveniente es el valor con el rastro de ceros más largo posible, 25100, ya que nos permite lograr la 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 rastros de ceros más largos.

Para decodificar el número entero 25100, el cálculo polinómico se puede realizar en sentido inverso, como se muestra en la tabla siguiente. 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 longitud conocida del mensaje o mientras el resultado restante sea positivo. La única diferencia en comparación con el cambio de base clásico es que puede haber un rango de valores asociados con cada símbolo. En este ejemplo, A siempre es 0, B es 1 o 2 y D es cualquiera de los siguientes: 3, 4 o 5. Esto está en exacta concordancia con nuestros intervalos que están determinados por las frecuencias. Cuando todos los intervalos son iguales a 1, tenemos un caso especial del cambio de base clásico.

Límite teórico del 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 la cola de ceros más larga, podemos suponer que esta longitud puede reducirse 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 el cálculo del 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}}.

Aplicando log ₂ para el número estimado de bits en el mensaje, el mensaje final (sin contar una sobrecarga logarítmica para las tablas de frecuencia y longitud 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 aproxima 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). Por la AEP, después de una larga secuencia de símbolos, el intervalo de se divide casi en intervalos de tamaño casi igual. $n$ $(0,1)$

Técnicamente, para cualquier pequeño , para todos los suficientemente grandes , existen cadenas , tales que cada cadena tiene una probabilidad casi igual a , 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 existe una fracción de la forma en el intervalo para . Dado que el intervalo para 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 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 de 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 del alfabeto sean potencias de dos, en cuyo caso tanto la codificación de Huffman como la aritmética alcanzan la entropía.

Cuando se codifican cadenas binarias de forma ingenua según Huffman, 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 de 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 el problema de la suboptimización de la codificación de Huffman es concatenar símbolos ("bloquear") para formar un nuevo alfabeto en el que cada símbolo nuevo 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 tiene un promedio de 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, la 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 longitudes de ejecución mediante códigos Golomb-Rice basados en Huffman . Este enfoque permite una codificación/decodificación más simple y rápida que la codificación aritmética o incluso la codificación 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 Bernoulli como la de este ejemplo, por lo que no es un sustituto del bloqueo en todos los casos. $71.1\%$

Historia y patentes

Los algoritmos básicos para la codificación aritmética fueron desarrollados independientemente por Jorma J. Rissanen , en IBM Research , y por Richard C. Pasco, un estudiante de doctorado en 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 trabajos: ^[3]

Rissanen [1976] desarrolló de forma independiente un algoritmo de esta familia: desplaza el elemento de código al extremo más significativo del acumulador, utilizando un puntero obtenido por adición 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 añadir elementos de código al extremo menos significativo del acumulador.

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

Históricamente, las patentes estadounidenses han cubierto una variedad de técnicas específicas de codificación aritmética, aunque varios métodos bien conocidos han pasado desde entonces al dominio público a medida que las patentes han expirado. 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 licencias bajo lo que se denominan términos de licencia "razonables y no discriminatorios" ( RAND , por sus siglas en inglés) (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 han expirado desde entonces), dichas licencias estaban disponibles de forma gratuita, y en otros casos se han requerido tarifas de licencia. La disponibilidad de licencias bajo los términos RAND no necesariamente satisface a todos los que podrían querer usar 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 compresión, bzip2 , abandonó deliberadamente el uso de la codificación aritmética en favor de la codificación Huffman debido a la situación de las patentes percibida en ese momento. Además, los codificadores y decodificadores del formato de archivo JPEG , que tiene opciones tanto para la codificación Huffman como para la 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 en uso 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 Huffman a otros con codificación aritmética (o sistemas numéricos asimétricos en el caso de JPEG XL), mostrando un ahorro de tamaño de hasta el 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 vencidas). ^[7]

Patente de EE. UU. 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 multialfabético 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 japonesa 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 expiradas) relacionadas con la codificación aritmética incluyen las siguientes.

Patente de EE. UU. 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 de EE. UU. 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 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 concurrentes
Patente de EE. UU. 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 y empleados de forma selectiva
Patente japonesa 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 prevenir la propagación de acarreo en la 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 mediante codificación aritmética con estimación simplificada de subintervalos de probabilidad
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 de entropía

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]

Es posible que existan patentes sobre codificación aritmética en otras jurisdicciones; consulte patentes de software para obtener un análisis de 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 relaciones 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 porque el rendimiento y la relación de compresión también dependen del tipo de datos, en particular 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 para alfabetos de exactamente dos símbolos (0 y 1).

Véase también

Notas

^ Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9 de abril de 2014). Fundamentos de multimedia. Springer Science & Business Media. ISBN 978-3-319-05290-8.
^ J. Duda, K. Tahboub, NJ Gadil, EJ Delp, El uso de sistemas numéricos asimétricos como un reemplazo preciso para la codificación de Huffman, Simposio de codificación de imágenes, 2015.
^ Pasco, Richard Clark (mayo de 1976). Algoritmos de codificación de fuentes para la compresión rápida de datos (PhD). Stanford Univ. CiteSeerX 10.1.1.121.3377 .
^ "¿Qué es JPEG?". Preguntas frecuentes sobre comp.compression (parte 1/3) .
^ "Recomendación T.81 (1992) Corrigendum 1 (01/04)". 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 . Kluwer Academic Press. ISBN 0442012721.
^ "T.81 – COMPRESIÓN DIGITAL Y CODIFICACIÓN DE IMÁGENES FIJAS DE TONO CONTINUO – REQUISITOS Y DIRECTRICES" (PDF) . CCITT . Septiembre de 1992 . Consultado el 12 de julio de 2019 .
^ "Preguntas frecuentes". comp.compression .
^ "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 enteras a esos rangos y un tipo de aproximación aún más restringido que denominan codificación cuasi-aritmética binaria. Afirman que la diferencia entre las versiones reales y enteras 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 %. Véase: Howard, Paul G.; Vitter, Jeffrey S. (1994), "Codificación aritmética para la compresión de datos" (PDF) , Proceedings of the 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 flujo". Teoría de la información, inferencia y algoritmos de aprendizaje . Cambridge University Press . ISBN 0-521-64298-1Archivado desde el original (PDF/ PostScript / DjVu / LaTeX ) el 22 de diciembre de 2007. Consultado el 30 de diciembre de 2007 .
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 22.6. Codificación aritmética". Recetas numéricas: el arte de la computación científica (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8Archivado 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". IBM Journal of Research and Development . 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). «Arithmetic coding» (PDF) . IBM Journal of Research and Development . 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) . Communications of the 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-ádica" 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 de grupo de noticias con un breve ejemplo práctico 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 aritmética como la de rango. También incluye ejemplos de código para tres codificadores aritméticos diferentes y 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 al descubierto. 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