Codificación aritmética

La codificación aritmética ( AC ) es una forma de codificación entrópica 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 de uso frecuente se almacenan con menos bits y los caracteres menos frecuentes con más bits, lo que resulta en un menor número total de bits utilizados. La codificación aritmética se diferencia de otras formas de codificación entrópica, como la codificación 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 . ^{[ 1 ]}

Relación con la entropía

La codificación aritmética logra la compresión subdividiendo el intervalo [0, 1) en subintervalos proporcionales a las probabilidades de los símbolos. Cuando las probabilidades de los símbolos son desiguales, los símbolos más probables reciben subintervalos más grandes, que requieren menos bits para especificar un punto dentro de ellos. El límite teórico de esta compresión viene dado por la entropía de la fuente, que el teorema de codificación de fuente de Shannon establece como el número mínimo promedio de bits por símbolo que puede lograr cualquier método sin pérdidas. ^{[ 2 ]}^{[ 3 ]} La codificación aritmética se aproxima mucho a este límite, especialmente para mensajes largos. ^{[ 1 ]}^{[ 4 ]}

Cuando todos los símbolos son igualmente probables, cada subintervalo tiene el mismo tamaño y ningún símbolo puede representarse con menos bits que otro. En este caso, la entropía alcanza su máximo de $\log _{2}n$ bits por símbolo (donde $n$ es el tamaño del alfabeto), y no es posible la compresión. Por ejemplo, una secuencia de lanzamientos de monedas justas independientes tiene una entropía de exactamente 1 bit por símbolo —el costo total de almacenamiento— por lo que la codificación aritmética no proporciona ningún beneficio. De manera similar, los símbolos ternarios independientes con probabilidades iguales tienen una entropía de aproximadamente 1,585 bits por símbolo, el máximo para un alfabeto de tres símbolos, y son igualmente incompresibles. ^{[ 3 ]}^{[ 2 ]}

La compresión es posible cuando las probabilidades son desiguales, ya que los subintervalos se vuelven desiguales en tamaño. Por ejemplo, una fuente binaria con probabilidades de 0,9 y 0,1 tiene una entropía de aproximadamente 0,469 bits por símbolo. El símbolo con probabilidad 0,9 recibe el 90 % de cada intervalo, por lo que la mayoría de los pasos de codificación apenas reducen el intervalo y se necesitan menos bits para identificar el valor final. Esto permite que la codificación aritmética alcance una relación de compresión de aproximadamente 2,1:1. ^{[ 3 ]}^{[ 1 ]}

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, consideremos 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 ineficiente: 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, quedando 11 sin usar. ^{[ 1 ]}

Una solución más eficiente consiste en 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 con la precisión suficiente para recuperarlo, como 0,0010110001² _. Esto solo requiere 10 bits; se ahorran 2 bits en comparación con la codificación de bloques simple. Esto es factible para secuencias largas porque existen algoritmos eficientes e in situ para convertir la base de números de precisión arbitraria. ^{[ 5 ]}

Para decodificar el valor, sabiendo que la cadena original tenía una longitud de 6, basta con convertirla de nuevo a base 3, redondearla a 6 dígitos y recuperar la cadena.

Definición de 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 ; véase el teorema de codificación de fuente ). ^{[ 2 ]} 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 de la óptima estará la salida. ^{[ 1 ]}

Ejemplo : un modelo estático simple para describir la salida 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 que el símbolo sea POSITIVO
10% de probabilidad de símbolo NEGATIVO
10 % de probabilidad de que aparezca el símbolo END-OF-DATA. (La presencia de este símbolo significa que el flujo de datos se "terminará internamente", algo 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 conjunto simple 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, la probabilidad porcentual de "u" sería mucho mayor cuando sigue a una "Q" o una "q". Los modelos incluso pueden ser adaptativos , de modo que cambian 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. ^{[ 1 ]}^{[ 6 ]}

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 solo tiene tres piezas de datos a considerar: ^{[ 1 ]}

El siguiente símbolo que necesita ser codificado
El intervalo actual (al inicio 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 implican 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. El intervalo que corresponda al símbolo que se va a codificar a continuación se convierte en el intervalo utilizado en el siguiente paso. ^{[ 1 ]}

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 END-OF-DATA sería [0,9, 1) .

Cuando todos los símbolos han sido codificados, el intervalo resultante identifica inequívocamente la secuencia de símbolos que lo produjo. Cualquier persona que tenga el mismo intervalo final y el mismo modelo que se está utilizando puede reconstruir la secuencia de símbolos que debió haber ingresado al codificador para producir ese intervalo final. ^{[ 1 ]}

No es necesario transmitir el intervalo final; basta con transmitir una fracción que se encuentre dentro de dicho intervalo. En concreto, solo 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 dentro del intervalo final; esto garantizará que el código resultante sea un código de prefijo . ^{[ 7 ]}

Codificación y decodificación: ejemplo

Consideremos 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 asumiendo que solo hay tantos dígitos como sean necesarios para decodificar el mensaje). ^{[ 1 ]}

El proceso comienza con el mismo intervalo utilizado por el codificador: [0,1) , y utilizando el mismo modelo, lo divide 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 END-OF-DATA 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 END-OF-DATA sería [0,534, 0,540) .

Ahora bien, 0,538 cae dentro del intervalo del símbolo END-OF-DATA; 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 ha finalizado. Si la secuencia no termina internamente, debe haber alguna otra forma de indicar dónde se detiene. De lo contrario, el proceso de decodificación podría continuar indefinidamente, leyendo erróneamente más símbolos de la fracción de los que realmente se codificaron en ella. ^{[ 1 ]}

Fuentes de ineficiencia

El mensaje 0.538 del ejemplo anterior podría haberse codificado mediante las fracciones igualmente cortas 0.534, 0.535, 0.536, 0.537 o 0.539. Esto sugiere que el uso de decimal en lugar de binario introdujo cierta ineficiencia. Esto es correcto; el contenido de información de un decimal de tres dígitos es $3\times \log _{2}(10)\approx 9.966$ bits ; el mismo mensaje podría haberse codificado en la fracción binaria 0,10001001 (equivalente a 0,53515625 decimal) con un coste de tan solo 8 bits. ^{[ 7 ]}

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

\sum -\log _{2}(p_{i})=-\log _{2}(0.6)-\log _{2}(0.1)-\log _{2}(0.1)=7.381{\text{ bits}}.

Pero en la codificación binaria se debe usar un número entero de bits, por lo que un codificador para este mensaje usaría al menos 8 bits, lo que resultaría en un mensaje un 8,4 % más grande que el contenido de entropía. Esta ineficiencia de como máximo 1 bit resulta en una sobrecarga relativamente menor a medida que aumenta el tamaño del mensaje. ^{[ 7 ]}

Además, las probabilidades de símbolo declaradas 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 los intervalos se reajustan para estas frecuencias, la entropía del mensaje sería de 4.755 bits y el mismo mensaje NEUTRAL NEGATIVE END-OF-DATA 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 más grande que el mensaje de entrada, especialmente si el modelo de probabilidad es incorrecto. ^{[ 1 ]}

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 facilidad de adaptación. La adaptación consiste en modificar las tablas de frecuencia (o probabilidad) durante el procesamiento de los datos. Los datos decodificados coinciden con los originales siempre que la tabla de frecuencia se reemplace de la misma manera y en el mismo paso que durante la codificación. La sincronización se basa, generalmente, en una combinación de símbolos que aparecen durante el proceso de codificación y decodificación. ^{[ 1 ]}^{[ 6 ]}

Precisión y renormalización

Las explicaciones anteriores sobre codificación aritmética contienen algunas simplificaciones. En particular, están escritas como si el codificador primero calculara las fracciones que representan los extremos del intervalo completo, 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 precisión infinita, la mayoría de los codificadores aritméticos operan en 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. ^{[ 7 ]} 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. Nótese 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 la cantidad total de símbolos que se pueden codificar. Cuando el rango se reduce hasta el punto en que todos los valores comparten ciertos dígitos iniciales, estos se envían a la salida. Para la cantidad de dígitos de precisión que la computadora puede manejar, ahora maneja menos, 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. Nótese que este resultado se produce en dos de los tres casos de nuestro ejemplo anterior. ^{[ 7 ]}

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

Recordemos que, en el caso de 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 radix . ^{[ 5 ]} 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, y así sucesivamente. 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 un total acumulado de frecuencias.

En un sistema de numeración posicional , la base numérica es igual a la cantidad de símbolos diferentes que se utilizan para expresar el número. Por ejemplo, en el sistema decimal, la cantidad de símbolos es 10: 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9. La base se utiliza para expresar cualquier número entero finito como un multiplicador implícito 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, ya que 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 cual no se acerca mucho al límite teórico (la entropía del mensaje), que es de aproximadamente 9 bits. ^{[ 3 ]}

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 inferior y superior L y U y elegiremos un número entre ellos. Para el cálculo de L, multiplicamos cada término de la expresión anterior por el producto de las frecuencias de todos los símbolos que aparecieron previamente: ^{[ 5 ]}

{\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 anterior radica en que cada término se multiplica por el producto de las frecuencias de todos los símbolos que aparecieron previamente. De forma más general, L se puede calcular como:

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

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

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 dado 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 la secuencia de ceros más larga posible, 25100, ya que nos permite lograr compresión al representar el resultado como 251 × 10² ^. Los ceros también se pueden truncar, dando como resultado 251, si la longitud del mensaje se almacena por separado. Los mensajes más largos tenderán a tener secuencias de ceros más largas.

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

Durante la decodificación, tomamos la parte entera después de dividir por la potencia correspondiente de 6. 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 con respecto al cambio de base clásico es que puede haber un rango de valores asociados a cada símbolo. En este ejemplo, A siempre es 0, B es 1 o 2, y D es cualquiera de 3, 4 o 5. Esto concuerda exactamente 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. ^{[ 5 ]}

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 se puede representar en $\log _{2}(n^{n})=n\log _{2}(n)$ 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 secuencia de ceros más larga podemos suponer que esta longitud se puede reducir mediante $\textstyle \log _{2}\left(\prod _{k=1}^{n}f_{k}\right)$ bits. Dado que cada frecuencia en un producto aparece 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.

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

Aplicando log ₂ al número estimado de bits en el mensaje, el mensaje final (sin contar una sobrecarga logarítmica para la longitud del mensaje y las tablas de frecuencia) coincidirá con el número de bits dado por la entropía , que para mensajes largos es muy cercano al óptimo: ^{[ 3 ]}^{[ 2 ]}

-\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 $H$ bits por símbolo, a medida que la longitud del mensaje tiende al infinito.

Equipartación asintótica

Podemos entender esto intuitivamente. Supongamos que la fuente es ergódica, entonces tiene la propiedad de equipartición asintótica (PEA). Por la PEA, después de una larga corriente de $n$ símbolos, el intervalo de $(0,1)$ está casi dividido en intervalos de tamaño casi igual. ^{[ 3 ]}

Técnicamente, para cualquier pequeño $\epsilon >0$ , para todos los suficientemente grandes $n$ , existe $2^{nH(X)(1+O(\epsilon ))}$ instrumentos de cuerda $x_{1:n}$ , de tal manera que cada cadena tenga casi igual probabilidad $Pr(x_{1:n})=2^{-nH(X)(1+O(\epsilon ))}$ y su probabilidad total es $1-O(\epsilon )$ .

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

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

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 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 Huffman como la aritmética alcanzan la entropía. ^{[ 3 ]}^{[ 8 ]}

Cuando se codifican cadenas binarias mediante el método Huffman de forma ingenua, 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 ^{[ 7 ].}

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 Huffman es concatenar símbolos ("bloquear") para formar un nuevo alfabeto en el que cada nuevo símbolo representa 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: ^{[ 6 ]}

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 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, $56.7\%$ compresión. Permitir secuencias arbitrariamente largas se acerca arbitrariamente a la entropía —al igual que la codificación aritmética—, pero requiere códigos enormes para lograrlo, por lo que no es tan práctico como la codificación aritmética para este propósito. ^{[ 6 ]}

Una alternativa es codificar las longitudes de secuencias 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 $71.1\%$ , mucho más cerca del óptimo que usando bloques de tres bits. Sin embargo, los códigos de Golomb-Rice solo se aplican a entradas de Bernoulli como la de este ejemplo, por lo que no son un sustituto del bloqueo en todos los casos. ^{[ 6 ]}

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. ^{[ 5 ]}^{[ 9 ]} Pasco cita un borrador previo a la publicación del artículo de Rissanen y comenta sobre la relación entre sus trabajos: ^{[ 9 ]}

Un algoritmo de esta familia fue desarrollado independientemente por Rissanen [1976]. Este algoritmo desplaza el elemento de código al extremo más significativo del acumulador, utilizando un puntero obtenido mediante 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 su publicación, IBM solicitó una patente estadounidense para el trabajo de Rissanen. El trabajo de Pasco no fue patentado.

Históricamente, diversas técnicas específicas para la codificación aritmética han estado protegidas por patentes estadounidenses, si bien varios métodos conocidos han pasado a ser de dominio público al expirar dichas patentes. Las técnicas patentadas pueden ser esenciales para implementar los algoritmos de codificación aritmética especificados en algunos estándares internacionales formales. En estos casos, dichas patentes suelen estar disponibles para su licenciamiento bajo términos denominados "razonables y no discriminatorios" ( RAND, por sus siglas en inglés) (al menos según la política de los comités de estandarización). En algunos casos conocidos (incluidos algunos relacionados con patentes de IBM que ya han expirado), estas licencias eran gratuitas, mientras que en otros se requerían tarifas. La disponibilidad de licencias bajo términos RAND no necesariamente satisface a todos los usuarios de la tecnología, ya que lo que puede parecer "razonable" para una empresa que desarrolla un producto de software comercial propietario puede resultar mucho menos razonable para un proyecto de software libre o de código abierto .

Al menos un programa de software de compresión importante, bzip2 , descontinuó deliberadamente el uso de la 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 para codificación Huffman y codificación aritmética, generalmente solo admiten la opción de codificación Huffman, lo que originalmente se debió a preocupaciones de patentes; el resultado es que casi todas las imágenes JPEG en uso hoy en día usan codificación Huffman ^{[ 10 ]} aunque las patentes de codificación aritmética de JPEG ^{[ 11 ]} han expirado debido a la antigüedad del estándar JPEG (cuyo diseño se completó aproximadamente en 1990). ^{[ 12 ]} JPEG XL , así como archivadores como PackJPG, Brunsli y Lepton, que pueden convertir sin pérdida archivos codificados en Huffman a aquellos con codificación aritmética (o sistemas numéricos asimétricos en el caso de JPEG XL), muestran 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). ^{[ 13 ]}

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 caducadas) 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 concurrente de valores
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 mediante codificación aritmética utilizando diversos codificadores y decodificadores de codificación aritmética empleados selectivamente.
Patente japonesa 11782787 – ( NEC ) Solicitada el 13 de mayo de 1987, concedida el 18 de noviembre de 1988 – Michio Shimada – Dispositivo de codificación aritmética para compresión de datos
Patente japonesa 15015487 – ( KDDI ) Solicitada 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 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 ) Solicitada 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. ^{[ 14 ]} El códec Dirac utiliza codificación aritmética y no está pendiente de patente. ^{[ 15 ]}

Es posible que existan patentes sobre codificación aritmética en otras jurisdicciones; consulte la sección de patentes de software para obtener información 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 relaciones de compresión varían solo un poco (generalmente menos del 1%), ^{[ 7 ]} el tiempo de ejecución del código puede variar en un factor de 10. Elegir el codificador adecuado de una lista de codificadores disponibles públicamente no es una tarea simple porque el rendimiento y la relación de compresión también dependen 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 para alfabetos de exactamente dos símbolos (0 y 1).

Notas

1 2 3 4 5 6 7 8 9 10 11 12 13 Witten , Ian H.; Neal, Radford M.; Cleary, John G. (junio de 1987). "Codificación aritmética para compresión de datos". Communications of the ACM . 30 (6): 520– 540. doi : 10.1145/214762.214771 . S2CID 3343393 .
1 2 3 4 Shannon, Claude E. (1948). "Una teoría matemática de la comunicación". Bell System Technical Journal . 27 (3): 379– 423. doi : 10.1002/j.1538-7305.1948.tb01338.x .
1 2 3 4 5 6 7 8 Cover, Thomas M.; Thomas, Joy A. (2006). Elementos de la teoría de la información (2.ª ed.). John Wiley & Sons. ISBN 978-0-471-24195-9.
↑ Rissanen, JJ; Langdon, GG, Jr (marzo de 1979). "Codificación aritmética". IBM Journal of Research and Development . 23 (2): 149– 162. doi : 10.1147/rd.232.0149 . S2CID 39909636 . {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
1 2 3 4 5 6 Rissanen, Jorma (mayo de 1976). "Desigualdad Kraft generalizada y codificación aritmética". IBM Journal of Research and Development . 20 (3): 198– 203. doi : 10.1147/rd.203.0198 .
1 2 3 4 5 Sayood, Khalid (2017). Introducción a la compresión de datos (5.ª ed.). Morgan Kaufmann. ISBN 978-0-12-809474-7.
1 2 3 4 5 6 7 Howard, Paul G.; Vitter, Jeffrey S. (1994), "Codificación aritmética para compresión de datos", Actas del IEEE , 82 (6): 857– 865, doi : 10.1109/5.286189 , hdl : 1808/7229
↑ Huffman, David (1952). "Un método para la construcción de códigos de redundancia mínima". Actas del IRE . 40 (9). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 1098–1101 . doi : 10.1109/jrproc.1952.273898 . ISSN 0096-8390 .
1 2 Pasco, Richard Clark (mayo de 1976). Algoritmos de codificación de fuente para compresión rápida de datos (PhD). Universidad de Stanford. CiteSeerX 10.1.1.121.3377 .
↑ "¿Qué es JPEG?" . comp.compression Preguntas frecuentes (parte 1/3) .
↑ "Recomendación T.81 (1992) Corrección 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 .

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 del 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» . Numerical Recipes: The Art of Scientific Computing (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8Archivado del original el 11 de agosto de 2011. Consultado el 18 de agosto de 2011 .
Rissanen, Jorma (mayo de 1976). "Desigualdad de Kraft generalizada y codificación aritmética" . IBM Journal of Research and Development . 20 (3): 198– 203. doi : 10.1147/rd.203.0198 . Recuperado el 21 de septiembre de 2007 .
Rissanen, JJ; Langdon GG, Jr (marzo de 1979). "Codificación aritmética" (PDF) . IBM Journal of Research and Development . 23 (2): 149– 162. doi : 10.1147/rd.232.0149 . S2CID 39909636. Archivado del original (PDF) el 28 de septiembre de 2007. Recuperado 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) del original el 28 de septiembre de 2007. Recuperado 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
EL MODELADO DEL LENGUAJE ES COMPRESIÓN https://arxiv.org/pdf/2309.10668

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 un 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 de rango como la aritmética. Incluye ejemplos de código para tres codificadores aritméticos diferentes, junto con una comparación de su 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: Revelando la codificación aritmética . Informe técnico 2007-5, Grupo de Investigación Sable, 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 por Mark Nelson (2014)
Implementación rápida de codificación de rango y rANS por James K. Bonfield

[Witten1987-1] 1 2 3 4 5 6 7 8 9 10 11 12 13 Witten , Ian H.; Neal, Radford M.; Cleary, John G. (junio de 1987). "Codificación aritmética para compresión de datos". Communications of the ACM . 30 (6): 520– 540. doi : 10.1145/214762.214771 . S2CID 3343393 .

[Shannon1948-2] 1 2 3 4 Shannon, Claude E. (1948). "Una teoría matemática de la comunicación". Bell System Technical Journal . 27 (3): 379– 423. doi : 10.1002/j.1538-7305.1948.tb01338.x .

[CoverThomas-3] 1 2 3 4 5 6 7 8 Cover, Thomas M.; Thomas, Joy A. (2006). Elementos de la teoría de la información (2.ª ed.). John Wiley & Sons. ISBN 978-0-471-24195-9.

[Rissanen1979-4] Rissanen, JJ; Langdon, GG, Jr (marzo de 1979). "Codificación aritmética". IBM Journal of Research and Development . 23 (2): 149– 162. doi : 10.1147/rd.232.0149 . S2CID 39909636 . {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )

[Rissanen1976-5] 1 2 3 4 5 6 Rissanen, Jorma (mayo de 1976). "Desigualdad Kraft generalizada y codificación aritmética". IBM Journal of Research and Development . 20 (3): 198– 203. doi : 10.1147/rd.203.0198 .

[Sayood2017-6] 1 2 3 4 5 Sayood, Khalid (2017). Introducción a la compresión de datos (5.ª ed.). Morgan Kaufmann. ISBN 978-0-12-809474-7.

[Howard1994-7] 1 2 3 4 5 6 7 Howard, Paul G.; Vitter, Jeffrey S. (1994), "Codificación aritmética para compresión de datos", Actas del IEEE , 82 (6): 857– 865, doi : 10.1109/5.286189 , hdl : 1808/7229

[Huffman1952-8] Huffman, David (1952). "Un método para la construcción de códigos de redundancia mínima". Actas del IRE . 40 (9). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 1098–1101 . doi : 10.1109/jrproc.1952.273898 . ISSN 0096-8390 .

[Pasco1976-9] 1 2 Pasco, Richard Clark (mayo de 1976). Algoritmos de codificación de fuente para compresión rápida de datos (PhD). Universidad de Stanford. CiteSeerX 10.1.1.121.3377 .

[10] "¿Qué es JPEG?" . comp.compression Preguntas frecuentes (parte 1/3) .

[11] "Recomendación T.81 (1992) Corrección 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 .

[12] Pennebaker, WB; Mitchell, JL (1992). Estándar de compresión de datos de imágenes fijas JPEG . Kluwer Academic Press. ISBN 0442012721.

[t81-13] "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 .

[14] "Preguntas frecuentes" . comp.compression .

[15] "Lanzamiento del códec de vídeo Dirac 1.0 [ LWN.net ] " . lwn.net .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]